topcoder算法思考（630-666）

wittyResry commented 7 years ago

https://github.com/wittyResry/topcoder
在做SRM 666中树中L步可发现的顶点数，利用搜索的复杂度O(NP)明显操作复杂度，应该用动态规划的思路解决，一种解法是树形dp，先dp儿子，慢慢递归到根节点。
在做SRM 665中，咨询4和7相加问题，因为N=15，就算是5^N<=30517578125，加上减枝，不会超过复杂度，所以可以直接用搜索解决，并且添加减枝后可以接受的搜索复杂度。

wittyResry commented 7 years ago

在做SRM 663中，问是否有从initial到targe的搜索路径，告诉了两种对string的操作，应该从反向求解，实行搜索，可以大大减小搜索的解空间。

wittyResry commented 7 years ago

SRM 661,求满足M>N && LCM(1,2,...,N) = LCM(1,2,...,N,...,M)的最小M。 LCM为最小公倍数。需要知道N内的所有素因子，LCM(1,2,...,N) =p_1^k_1p_2^k_2...p_r^k_r。步骤：1. 先求助不大于N的所有素数。枚举每一个p_r可以组合成的最小的数即可。2. 于是可以知道对任意的p_x^k_x<=N我们知道max(2p_x^k_x)就是我们要的结果。3. 注意下面两个trick
```
当i = 999997
int j = i * i 会导致负数越界，需要用 long long j = 1LL * i * i 
while(i * i <= N) 也会大于整数范围(32bit)越界 需要while(1LL * i * i <= N)
```

wittyResry commented 7 years ago

SRM 717: 无向完整图，添加变方向后，给出每一个边的出度，重新构造出这个图。

构造图的过程中，无比精准，从s[i]最大的开始构造，然后分析出度，采用vis[k]来标记已经构造出的点，采用--s[]从k出发的入度（无向完全图性质，每个点都要指向其他的点）。

wittyResry commented 7 years ago

SRM 654 DIV1 250: 概率统计，给出包含'?'的字符串，并且给出每个'?'出现的概率，咨询在所有可能出现的字符串的情况下，所有substring长度的期望。=》枚举所有开始的点，算出这个开始的点出发的字符串可能性。

wittyResry commented 7 years ago

2017 TCO Round 2B: 树题目。

wittyResry commented 6 years ago

TCO17 Beijing 250: multiset底层数据结构为红黑树，排列有序，删除指定元素的复杂度为树的高度复杂度O(log). TCO17 Beijing 500: 通过DP计算出DP出N未数中有M个1，那么DP[N][M] = dp[N-1][M] + dp[N-1][M-1]

1
1 2 1
1 3 3 1
1 4 6 4 1
可以用矩阵压缩算法计算，这里只用64位即可解决，只需要设置辅助数组即可计算出来。

wittyResry commented 6 years ago

SRM 645: 特殊类DP转移方程式：dp[i+1..N][j] = min(dp[i+1..N][j], dp[i][j] + 1) when r < n && inter(r, k) , r>=i+1, k=1..n

wittyResry commented 6 years ago

SRM 644: DP[N][M] = dp[N-1][M] + dp[N-1][M-1]获取到C(N, M) 的组合数。然后枚举从每点开始的数量进行统计C(G, M-1)求和。

wittyResry commented 6 years ago

SRM 642 WaitingForBus: N辆公交从站点发车，每次发车从这N辆中选择一个进行发车，概率为prob_N，求用户在t时刻等待的车。概率与统计题目，计算出等车的数学期望。 SRM 641 TrianglesContainOrigin: 给N个点（两两不相交并且不重复），N个点选构成三角形满足将(0,0)点包含的有多少种取法。可以知道N个点可以有C(N,3)个三角形，判断是否在原点包含其中，可以用枚举每个点的弧度argue，从该点出发顺时针180度(argue+PI)内包含有X个点，则此C(X,2)为该点出发顺时针不满足的点数。可以采用两种方法加速，如二分、梯度优化降低复杂度。注意点：atan 和 atan2函数选用，建议用 atan2函数，因为atan(dy/dx)当dx=0会有异常，但atan2(dy,dx=0)可以正常计算。二分算法：

梯度（单调性）算法：

SRM 640 ChristmasTreeDecoration: 给出N个顶点（每个点有颜色），选择N-1条边构成一颗树。问使得相邻点的颜色尽可能不同的树的相似度。定义相似度为最优的树中相邻点的颜色相同的边的树木。采用的解法为并查集，先遍历一遍将相邻边颜色不同的边相连，然后在判断剩下的边，能构成一个树的选择的最小边数。

wittyResry commented 6 years ago

SRM 639 AliceGame: 每轮得分2i-1 for i=(1...oo)，每次都两人中一个得分。给出最终分数x和y。求得分为x要的最小轮。本题为数学相关，1+2+...+(2i-1)=(1+n) n / 2=ii;故必须要求求和为一个数的平方。然后i轮的下限和上限，注意所有数都为奇数，求和的奇偶性一致。（因为没有注意到奇偶性导致做错）

wittyResry commented 6 years ago

SRM 638 ShadowSculpture: 在三维坐标轴，给出到X0Y，Y0Z，Z0X平面的投影，Y和N表示是否有点。问是否存在连通体满足条件（联通表示6个方向存在一个面相接）。本题trick较多，方法为采用枚举从每个点开始进行BFS搜索，然后checkBFS出的图是否满足条件。注意有个特殊的情况，全为N是满足条件的。

wittyResry commented 6 years ago

SRM 637 GreaterGame: 游戏中有1...2N张牌，A和B互相有N张牌，A的牌是确定的，B的牌可能有一些不确定。游戏总共N轮，每轮用户互相出牌，牌大的获得1分。问A的分的数学期望。本题思想类似田忌赛马的思想，针对B的出牌，A只要出set(A剩下的牌集合).lower_bound(B牌分)的分。然后再对A剩下的每个出牌，计算数学期望。

wittyResry commented 6 years ago

SRM 636 ChocolateDividingEasy: 对一个矩阵进行分割成3*3区域，问所有的分法中，3*3区域中最小的那块是多少？要求所有分法中取最大值。本题用矩阵求和DP，然后对每个点都计算出<=(x,y)的矩阵和是多少，然后枚举每个分割点得出答案。

wittyResry commented 6 years ago

SRM 635 SimilarRatingGraph: 计算二维平面上长相似的一段距离。枚举两个起点和长度，匹配最长的距离。

wittyResry commented 6 years ago

SRM 634 ShoppingSurveyDiv1: N个人去买M种的物品（M类），每一类物品最多买1件（有可能不买），给出每种物品的购买人数。定义超过买K种物品的为大卖家。问满足条件下最少可以有几个大卖家。本题的解法为：方法一：二分法，枚举大卖家的人数，check是否满足条件。方法二：枚举临界值，要求不满足大卖家最多能买的物品总数和总物品数量进行比较。

wittyResry commented 6 years ago

SRM 633 PeriodicJumping: 从二维平面点(0,0)出发，走到(x,0)，以固定的长度循环移动a[0],...,a[n],a[0],...,a[n],...，问最少步子走到(x,0).这题思路，先走直线，在最后一步走一个三角形。所以需要满足三角形法则。需要判断一个特殊情况，如果x < sum(a[0]+..+a[n])需要满足另一个三角形法则。两边之差小于第三边。

wittyResry / myIssue

topcoder算法思考（630-666） #38