A---Birthday
http://codeforces.com/contest/1068/problem/A
题意：
有n种硬币，m个人。m个人要给Ivan送硬币，每个人送的硬币都要互不相同但数量一样。Ivan现在已经有k种了，具体哪k种不知道。现在要求朋友们送的硬币至少有l种是IVan没有的。
思路：
刚开始想的是l/m取上整。后来发现题意是不知道Ivan有的是哪几种，为了保证一定至少l种的话，就需要（l+k）/m取上整。
不可能的情况是人数乘每个人送的硬币数超过n。
用longlong
1 #include <bits/stdc++.h> 2 #define inf 0x3f3f3f3f 3 using namespace std; 4 5 long long n, m, l, k; 6 int main() 7 { 8 while(scanf("%I64d%I64d%I64d%I64d", &n, &m, &k, &l) != EOF){ 9 long long cnt; 10 if((l + k) % m == 0){ 11 cnt = (l + k) / m; 12 } 13 else { 14 cnt = (l + k) / m + 1; 15 } 16 if(cnt * m > n){ 17 printf("-1 "); 18 } 19 else{ 20 printf("%I64d ", cnt); 21 22 } 23 24 } 25 return 0; 26 }
B---LCM
http://codeforces.com/contest/1068/problem/B
题意：
给定一个数b，问对于1~1e18的所有数a，(frac{lcm(a,b)}{a})有多少种可能。
思路：
(frac{lcm(a,b)}{a} = frac{a*b}{a*gcd(a,b)} = frac{b}{gcd(a,b)})
所以只需要统计b的因子数就行了，a是1~1e18，因子肯定是多于b的。
1 #include <bits/stdc++.h> 2 #define inf 0x3f3f3f3f 3 using namespace std; 4 typedef long long LL; 5 6 LL b; 7 8 int main() 9 { 10 while(scanf("%I64d", &b) != EOF){ 11 int cnt = 0; 12 for(int i = 1; i <= sqrt(b); i++){ 13 if(b % i == 0){ 14 if(i != sqrt(b)){ 15 cnt += 2; 16 } 17 else{ 18 cnt++; 19 } 20 } 21 } 22 printf("%d ", cnt); 23 } 24 return 0; 25 }
C---Colored Rooks【思维好题】
http://codeforces.com/contest/1068/problem/C
题意：
有n种颜色，给定m对关系。每对关系有一个颜色a和颜色b，表示a和b时候harmonize。现在要把n种颜色放进一个1e9*1e9的棋盘中，同一个颜色的子集要相连通，不同的不能相连，harmonize的颜色也要相连通。问如何摆放。
思路：
看上去就应该是以某一种策略进行摆放就可以了。但是我居然刚开始愚蠢的在想dfs。后来想想这也 太复杂了吧。
首先我们应该能想到同一个颜色的子集肯定都是能相连的。
那就只用考虑让不同的别相连就行了。这也的话，每个颜色i都放在（i，i）中，就好了。
最后要考虑怎样让harmonize的颜色相连。因为棋盘很大啊，而且也没有说放的数量要尽量少，所以在新的空行 j 里（j,a）放a (j,b）放 b 就可以了。这也不会影响前面。
1 #include <bits/stdc++.h> 2 #define inf 0x3f3f3f3f 3 using namespace std; 4 typedef long long LL; 5 6 int n, m; 7 struct node{ 8 int x, y; 9 node(){} 10 node(int i, int j){ 11 x = i; 12 y = j; 13 } 14 }; 15 vector<node>grid[105]; 16 17 int main() 18 { 19 while(scanf("%d%d", &n, &m) != EOF){ 20 for(int i = 1; i <= n; i++){ 21 grid[i].clear(); 22 grid[i].push_back(node(i, i)); 23 } 24 int j = n + 1; 25 for(int i = 0; i < m; i++){ 26 int a, b; 27 scanf("%d%d", &a, &b); 28 grid[a].push_back(node(a, j)); 29 grid[b].push_back(node(b, j)); 30 j++; 31 } 32 33 for(int i = 1; i <= n; i++){ 34 printf("%d ", grid[i].size()); 35 for(int j = 0; j < grid[i].size(); j++){ 36 printf("%d %d ", grid[i][j].x, grid[i][j].y); 37 } 38 } 39 } 40 return 0; 41 }
D---Array Without Local Maximum
http://codeforces.com/contest/1068/problem/D
题意：
给定一个序列，序列中数的范围在1~200， -1的地方表示不知道这个位置的数是多少。现在要求最后的序列中没有局部最大值，问有多少种填数的方案。
思路：
最开始就想到应该是dp，用(dp[i][j])表示第(i)个位置填的是(j)时的方案数。
刚开始天真的觉得最后的序列要么非递减要么非递增。实际上并不是的。由于存在相等的情况，序列不一定是单调的。
但是可以知道仍然存在着两种情况：1.(i-1)的数比(i)的要小 2.(i-1)的数要大于等于(i)的
因此dp数组要再多开一维，(dp[i][j][0])表示第(i)个位置填(j)且前一个数比他小，(dp[i][j][1])表示第(i)个位置填(j)且前一个数大于等于他
于是我们可以得到状态转移方程：
(dp[i][j][0] = sum_{k = 1} ^ {j}(dp[i-1][k][0] + dp[i-1][k][1]))
(dp[i][j][1] = sum_{k = j} ^ {200}dp[i-1][k][1] + dp[i - 1][j][0]) 当(num[i-1])大于等于(num[i])时，(num[i-2])只能大于等于(num[i-1])
对于(num[i] != -1)，我们只转移(dp[i][num[i]][0])和(dp[i][num[i]][1])
而且我们发现转移方程中有一部分求和，j增大，他们对应也变多。所以用前缀和维护一下。
要使用longlong。而且对于( - )，要先( +mod ) 再 ( %mod ) ，(sum)数组因为对于(i )只会用到 (i-1)的求和，所以不需要开三维，否则会MLE
最后的输出应该是(dp[n][num[n][1])或(sum[200][1])
1 #include <bits/stdc++.h> 2 #define inf 0x3f3f3f3f 3 using namespace std; 4 typedef long long LL; 5 6 int n; 7 const int maxn = 1e5 + 5; 8 const int mod = 998244353; 9 int num[maxn]; 10 LL dp[maxn][205][2], sum[205][2]; 11 12 int main() 13 { 14 while(scanf("%d", &n) != EOF){ 15 for(int i = 1; i <= n; i++){ 16 scanf("%d", &num[i]); 17 memset(dp[i], 0, sizeof(dp[i])); 18 //memset(sum[i], 0, sizeof(sum[i])); 19 } 20 memset(sum, 0, sizeof(sum)); 21 22 if(num[1] != -1){ 23 dp[1][num[1]][0] = 1ll; 24 for(int j = num[1]; j <= 200; j++){ 25 sum[j][0] = 1ll; 26 } 27 } 28 else{ 29 for(int j = 1; j <= 200; j++){ 30 dp[1][j][0] = 1ll; 31 sum[j][0] = (sum[j - 1][0] + 1ll) % mod; 32 } 33 } 34 35 for(int i = 2; i <= n; i++){ 36 if(num[i] != -1){ 37 dp[i][num[i]][0] = (sum[num[i] - 1][0] + sum[num[i] - 1][1]) % mod; 38 dp[i][num[i]][1] = (dp[i - 1][num[i]][0] + sum[200][1]) % mod; 39 dp[i][num[i]][1] = (dp[i][num[i]][1] - sum[num[i] - 1][1] + mod) % mod; 40 memset(sum, 0, sizeof(sum)); 41 for(int j = num[i]; j <= 200; j++){ 42 sum[j][0] = dp[i][num[i]][0] % mod; 43 sum[j][1] = dp[i][num[i]][1] % mod; 44 } 45 } 46 else{ 47 for(int j = 1; j <= 200; j++){ 48 dp[i][j][0] = (sum[j - 1][0] + sum[j - 1][1]) % mod; 49 dp[i][j][1] = (dp[i - 1][j][0] + sum[200][1]) % mod; 50 dp[i][j][1] = (dp[i][j][1] - sum[j - 1][1] + mod) % mod; 51 } 52 memset(sum, 0, sizeof(sum)); 53 for(int j = 1; j <= 200; j++){ 54 sum[j][0] = (sum[j - 1][0] + dp[i][j][0]) % mod; 55 sum[j][1] = (sum[j - 1][1] + dp[i][j][1]) % mod; 56 } 57 58 } 59 } 60 61 if(num[n] != -1){ 62 printf("%lld ", dp[n][num[n]][1] % mod); 63 } 64 else{ 65 printf("%lld ", sum[200][1] % mod); 66 } 67 } 68 69 return 0; 70 }
E---Multihedgehog
http://codeforces.com/contest/1068/problem/E
题意：
1-hedgehog是有一个节点的度至少是3，其他的节点度都是1
k-hedgehog是有一个节点的度至少是3，和他连接的节点都是k-1-hedgehog的中心点
现在给定一棵有n个点的树，问他是不是k-hedgehog
思路：
每次删掉叶子节点，用一个二维数组来存每次删除之后每个节点的度。
删除完之后判断被删除节点的父节点满不满足是p-hedgehog的条件，p是操作的次数。
最后看一下是不是只剩一个节点了。
1 #include <bits/stdc++.h> 2 #define inf 0x3f3f3f3f 3 using namespace std; 4 typedef long long LL; 5 6 int n, k; 7 const int maxn = 1e5 + 5; 8 struct edge{ 9 int v; 10 int nxt; 11 }e[maxn * 2]; 12 int head[maxn], tot; 13 int degree[maxn][16], son[maxn]; 14 bool vis[maxn], yes[maxn]; 15 16 void addedge(int u, int v) 17 { 18 e[tot].v = v; 19 e[tot].nxt = head[u]; 20 head[u] = tot++; 21 e[tot].v = u; 22 e[tot].nxt = head[v]; 23 head[v] = tot++; 24 degree[u][0]++; 25 degree[v][0]++; 26 } 27 28 29 30 int main() 31 { 32 while(scanf("%d%d", &n, &k) != EOF){ 33 34 35 36 for(int i = 1; i <= n; i++){ 37 head[i] = -1; 38 memset(degree[i], 0, sizeof(degree[i])); 39 vis[i] = false; 40 son[i] = 0; 41 yes[i] = true; 42 } 43 tot = 0; 44 45 for(int i = 1; i < n; i++){ 46 int u, v; 47 scanf("%d%d", &u, &v); 48 addedge(u, v); 49 } 50 if(n <= 3 || k >= 15){ 51 printf("No "); 52 continue; 53 } 54 bool flag = true; 55 int sum = n; 56 for(int p = 1; p <= k; p++){ 57 for(int i = 1; i <= n; i++){ 58 if(degree[i][p - 1] == 1){ 59 for(int j = head[i]; j != -1; j = e[j].nxt){ 60 if(vis[e[j].v])continue; 61 if(!vis[e[j].v] && degree[e[j].v][p - 1] == 1){ 62 flag = false; 63 break; 64 } 65 degree[e[j].v][p]++; 66 //if(yes[i])son[e[j].v]++; 67 } 68 vis[i] = true; 69 sum--; 70 } 71 if(!flag)break; 72 } 73 if(!flag)break; 74 for(int i = 1; i <= n; i++){ 75 if(degree[i][p] == 0 || vis[i])continue; 76 if(degree[i][p] <= 2){ 77 flag = false; 78 break; 79 } 80 degree[i][p] = 1; 81 } 82 if(!flag)break; 83 84 if(sum == 1){ 85 if(p == k){ 86 flag = true; 87 break; 88 } 89 else{ 90 flag = false; 91 break; 92 } 93 } 94 } 95 96 //cout<<cnt<<" "<<flag<<endl; 97 98 if(flag && sum == 1){ 99 printf("Yes "); 100 } 101 else{ 102 printf("No "); 103 } 104 } 105 return 0; 106 }