首页 > 代码库 > Codeforces Round #287 (Div. 2) 解题报告
Codeforces Round #287 (Div. 2) 解题报告
好久没写题了，底下代码都比较糟糕，将就着看吧。。
507A Amr and Music
要学最多的乐器，所以我们贪心选择时间花费少的。注意这里可以直接用pair，就不必写struct的compare函数了
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 struct ins{ 7 int v, id; 8 } a[110]; 9 bool cmp(ins a, ins b){10 return a.v < b.v;11 }12 int n, k, cnt;13 14 int main()15 {16 scanf("%d %d", &n, &k);17 for (int i = 0; i < n; i++){18 scanf("%d", &a[i].v);19 a[i].id = i;20 }21 sort(a, a+n, cmp);22 cnt = 0;23 int j;24 for (j = 0; j < n; j++){25 cnt += a[j].v;26 if (cnt > k) break;27 }28 printf("%d\n", j);29 for (int p = 0; p < j; p++)30 printf("%d%c", a[p].id+1, p==j-1?‘\n‘:‘ ‘);31 return 0;32 }
507B Amr and Pins
每次以圆周上某位置为中心，任意旋转。通过此操作最多让圆心向任意方向前进2r的距离，也就是说一次step，可以向目标前进d(0<d<=2r)地距离，所以答案就是ceil(dist/r/2)。
因为怕精度的问题，我直接用平方做的比较，结果就WA了几次。。本来是if(dist % (r*2)) ans++，我写的 if (dist^2 % (4*r^2)) ans++，实际上两者不等价。。本来是无法整除的，平方后可能可以整除。结果后来写的二分。。因为平方太大还爆longlong了。。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<cmath> 5 using namespace std; 6 7 int r, x, y, xx, yy; 8 9 int main()10 {11 scanf("%d %d %d %d %d", &r, &x, &y, &xx, &yy);12 long long dis2 = (long long)(xx - x) * (xx - x)13 +(long long)(yy - y) * (yy - y);14 long long ll = 0, rr = 150000, ans = 0;15 while(ll <= rr){16 long long m = (ll + rr) / 2;17 long long d = (m*r*2);18 long long tmpd, tmpdis2;19 if (d > 2100000000){20 tmpd = d;21 tmpdis2 = sqrt(double(dis2));22 }23 else tmpd = d * d, tmpdis2 = dis2;24 if (tmpd >= tmpdis2){25 ans = m;26 rr = m - 1;27 }28 else ll = m + 1;29 }30 cout << ans << endl;31 return 0;32 }
瞥了眼tourist的代码，虽然不是最简单的写法，但感觉写法挺值得借鉴的（对于这题，为什么对，我也没想太清楚。。）
1 int main() { 2 long long r, x, y, xx, yy; 3 cin >> r >> x >> y >> xx >> yy; 4 long long dist = (x - xx) * (x - xx) + (y - yy) * (y - yy); 5 long long step = 4 * r * r; 6 long long res = (dist + step - 1) / step; //整数向上取整的除法 7 long long ans = sqrt(1.0 * res); //整数向上取整的开根号 8 while (ans * ans < res) ans++; 9 while (ans > 0 && (ans - 1) * (ans - 1) >= res) ans--;10 cout << ans << endl;11 return 0;12 }
507C Guess Your Way Out!
题意：给一颗高度为h的满二叉树(0..h)，第n个叶子(1<=n<=2^h)为出口，按照LRLR的序列以及一定规则来遍历树，问找到出口前访问过多少个点。
分析：按照所给定的规则，走错一步，我们将访问完整棵子树，所以答案要多加子树的点数。实际上走向出口的正确序列可以直接由n-1的二进制表示得到，比照正确序列和LRLRLR，错的时候加上多余的点就可以了。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 7 int h, flag; 8 int p[110]; 9 long long n, ans, add;10 int main()11 {12 scanf("%d %I64d", &h, &n);13 n--; ans = 0; flag = 0;14 add = 1; for (int i = 0; i < h; i++) add = add * 2;15 int len = 0; memset(p, 0, sizeof(p));16 while(n){17 p[len++] = n & 1;18 n = n / 2;19 }20 for (int i = h-1; i >= 0; i--){21 if (p[i] != flag) ans = ans + add; //flag为0向左，为1向右22 else{23 ans ++;24 flag ^= 1; //走对时才调整方向25 }26 add = add / 2;27 // cout << ans << ‘ ‘ << i << ‘ ‘ << add << endl;28 }29 cout << ans << endl;30 return 0;31 }
507D The Maths Lecture
题意：给定n，m，k，问长度为n，没有前导0的数中，有多少个满足：存在某个后缀y, y>0且无前导0, 满足y mod k = 0。输出满足条件的数的个数mod m
分析：数位dp。dp[i][j]表示长度为i，无前导0的数，且没有后缀y能满足y mod k = 0，且本身mod k = j 的数的个数。这样就可以通过不断在左侧加上新的数，进行转移，对于mod k = 0的数，即dp[i][0]，就可以累加他们到答案里。
然后需要注意，已经mod k=0的就不用转移了，否则会重复计算（也就满足dp[][]定义），从而导致全为0的后缀会被遗漏，还有p000suffix，这种中间有某些位为0的也会被遗漏，所以修改dp[i][j]的定义为长度<=i的自然数（不包括0）...然后就可以了
实际上，最后dp[i][j]表示长度不超过i的自然数(不包括0)，没有后缀满足mod k = 0，自身mod k = j 的数的个数。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 6 long long n, m, k, ans; 7 long long dp[1100][110]; 8 9 int main()10 {11 cin >> n >> k >> m;12 for (int i = 1; i < 10; i++) dp[1][i%k] ++; //初始化长度为1的，注意没有013 long long f = 1;14 for (int i = 1; i < n; i++){15 f = f * 10 % k; //10的幂次用f来代替16 for (int j = 0; j < k; j++){17 int add = j==0? 1: dp[i][j]; //之前为0的只能加上0000..18 for (int p = 1; p < 10; p++){19 dp[i+1][(j+p*f)%k] += add;20 dp[i+1][(j+p*f)%k] %= m;21 }22 }23 for (int j = 1; j < k; j++){24 dp[i+1][j] += dp[i][j];25 dp[i+1][j] %= m;26 }27 }28 ans = dp[n][0] % m; f = 9;29 for (int i = n-1; i > 0; i--){30 ans += dp[i][0] * f % m;31 ans %= m; f = f * 10 % m;32 }33 cout << ans << endl;34 return 0;35 }
507E Breaking Good
题意：给一个n点m边的连通无向图，每个边有0和1两种属性，需要你求1到n的最短路，以及：影响的道路数 num = 不在最短路上且属性为1的边的个数+在最短路上且属性为0的边的个数 尽量少。
分析：tot[i]表示属性为i的边的总数，used[i]表示最短路上属性为i的边的个数，dis[i]表示到i点的最短路，所以num = (tot[1] - used[1]) + (dis[n] - used[1])，为了num尽量小，used[1]要尽量大。所以就是两个关键字的最短路了。
代码较丑，轻拍
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<set> 5 using namespace std; 6 7 8 struct edge{ 9 int v, w, n;10 } e[200100];11 12 int esize;13 int en[100100];14 void insert(int x, int y, int z){15 e[esize].v = y;16 e[esize].w = z;17 e[esize].n = en[x];18 en[x] = esize++;19 }20 21 22 int n, m;23 int tot[2];24 int d[100100], p[100100], c[100100]; bool vis[100100];25 int q[8000000];26 int aa[100100], bb[100100], cc[100100];27 void spfa(){28 int head, tail;29 head = tail = 0;30 memset(d, 127, sizeof(int)*(n+1));31 memset(vis, 0, sizeof(bool)*(n+1));32 p[1] = d[1] = c[1] = 0; vis[1] = 1;33 q[tail++] = 1;34 while(head != tail){35 int u = q[head++];36 for (int t = en[u]; t != -1; t = e[t].n){37 int v = e[t].v;38 if (d[v] > d[u] + 1 || ((d[v] == d[u]+1) && (c[v] < c[u] + e[t].w))){39 d[v] = d[u] + 1;40 c[v] = c[u] + e[t].w;41 p[v] = u;42 if (!vis[v]){43 vis[v] = true;44 q[tail++] = v;45 }46 }47 }48 vis[u] = false;49 }50 printf("%d\n", d[n]-c[n]+tot[1]-c[n]);51 set<pair<int, int> > s;52 int cur = n, pre;53 while(cur != 1){54 pre = cur; cur = p[cur];55 s.insert(make_pair(cur, pre));56 s.insert(make_pair(pre, cur));57 }58 for (int i = 0; i < m; i++){59 if (s.find(make_pair(aa[i], bb[i])) != s.end()){60 if (cc[i] == 0) printf("%d %d 1\n", aa[i], bb[i]);61 }62 else if (cc[i] == 1) printf("%d %d 0\n", aa[i], bb[i]);63 }64 65 }66 int main()67 {68 scanf("%d %d", &n, &m);69 esize = 0; memset(en, -1, sizeof(int) * (n+1));70 tot[0] = tot[1] = 0;71 for (int i = 0, x, y, z; i < m; i++){72 scanf("%d %d %d", &x, &y, &z);73 tot[z] ++;74 insert(x, y, z);75 insert(y, x, z);76 aa[i] = x, bb[i] = y, cc[i] = z;77 }78 spfa();79 return 0;80 }
Codeforces Round #287 (Div. 2) 解题报告