首页 > 代码库 > CodeForces Round #287 Div.2
CodeForces Round #287 Div.2
A. Amr and Music (贪心)
水题，没能秒切，略尴尬。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int maxn = 100 +10; 6 int a[maxn], r[maxn], ans[maxn]; 7 8 int cmp(int i, int j) { return a[i] < a[j]; } 9 10 int main()11 {12 //freopen("in.txt", "r", stdin);13 14 int n, k;15 scanf("%d%d", &n, &k);16 for(int i = 0; i < n; ++i) r[i] = i;17 for(int i = 0; i < n; ++i) scanf("%d", &a[i]);18 sort(r, r + n, cmp);19 int sum = 0, cnt = 0;20 for(int i = 0; sum + a[r[i]] <= k && cnt < n; ++i)21 {22 sum += a[r[i]];23 ans[cnt++] = r[i];24 }25 26 printf("%d\n", cnt);27 for(int i = 0; i < cnt - 1; ++i) printf("%d ", ans[i]+1);28 if(cnt) printf("%d\n", ans[cnt-1]+1);29 30 return 0;31 }
B. Amr and Pins (找规律)
题意：
给出一个圆的半径 和 圆心的始末位置。每次操作只能绕圆周上的点旋转若干角度。求该圆从初位置到末位置最少的操作次数。
分析：
不妨设圆的半径为r，圆心在原点处。
先看只旋转一次的情况，圆心所有可能位置构成的区域为 半径为2r的圆(除去圆心那点)，也可理解为半径为(0, 2r]的圆环区域
再看第二次旋转，其区域为半径在(2r, 4r]的圆环区域。 //这个不容易画图，自行脑补一下好啦
以此类推。
算法：
所以我们可以先算出圆心始末位置间的距离d，然后根据d和直径2r的关系，最终答案为
1 #include <cstdio> 2 #include <cmath> 3 4 int main() 5 { 6 //freopen("in.txt", "r", stdin); 7 8 int r, x1, y1, x2, y2, ans; 9 scanf("%d%d%d%d%d", &r, &x1, &y1, &x2, &y2);10 double d = sqrt((long long)(x1-x2)*(x1-x2) + (long long)(y1-y2)*(y1-y2));11 ans = (int)ceil(d / 2.0 / r);12 printf("%d\n", ans);13 14 return 0;15 }
C. Guess Your Way Out! (模拟 LCA)
题意：
有一个树高为h的完全二叉树 和 一个目标叶子节点， 给出一种遍历方式(LRLRLR...)
求在到达目标节点时，遍历节点的总数。(不包括目标节点)
具体参见原文Guess Your Way Out!
分析：
以官方题解中的图为例。自己最开始对这道题没什么想法，所以后面的分析相当于题解的翻译。=_=||
从树根开始走到最底端，到达节点X。
如果X刚好是目标节点E，则得到结果为树高h。
否则，找到X和E的 Least Common Ancestor (最小公共祖先)。在右子树遍历之前，一定会遍历完左子树中所有的节点 (图中用红色标出) ，从而退出，进入右子树。
所以在到达右子树之前共遍历sum[h1] + h - h1，其中sum[h1]表示树高为h1的完全二叉树的节点个数。
在进入右子树后，更新树高h、根节点编号、遍历的方向(L or R)，重复刚才的过程。
1 #include <cstdio> 2 #include <vector> 3 #include <algorithm> 4 using namespace std; 5 6 typedef long long LL; 7 8 LL h, n, sum[55], ans = 0; 9 vector<LL> anc1;10 11 int main()12 {13 //freopen("in.txt", "r", stdin);14 15 for(int i = 0; i <= 50; ++i) sum[i] = (1LL << (i+1)) - 1;16 scanf("%I64d%I64d", &h, &n);17 n += sum[h-1]; //转化成整个二叉树中的编号18 LL x = n;19 anc1.push_back(x); //目标节点的所有祖先20 while(x != 1)21 {22 x /= 2;23 anc1.push_back(x);24 }25 //for(int i = 0; i < anc1.size(); ++i) printf("%I64d ", anc1[i]);26 27 LL node = 1;28 bool choice = false; //遍历防线(L or R)29 30 while(node != n)31 {32 vector<LL> anc2; //当前叶子节点X的祖先33 for(int i = 0; i < h; ++i)34 {35 anc2.push_back(node);36 if(!choice) node = node * 2; else node = node * 2 + 1;37 choice = !choice;38 }39 if(n == node) { ans += h; break; }40 anc2.push_back(node);41 reverse(anc2.begin(), anc2.end());42 //for(int i = 0; i < anc2.size(); ++i) printf("%I64d ", anc2[i]);43 44 for(int i = 1; i <= h; ++i) if(anc1[i] == anc2[i])45 {//find LCA46 ans += sum[i-1] + h - i + 1;47 h = i - 1; //更新树高48 node = anc2[i-1];49 if((anc2[i]<<1) == node) //更新根节点的编号 及 遍历方向50 {51 node = anc2[i] * 2 + 1;52 choice = false;53 }54 else55 {56 node = (anc2[i] << 1);57 choice = true;58 }59 break;60 }61 }62 63 printf("%I64d\n", ans);64 65 return 0;66 }
CodeForces Round #287 Div.2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。