首页 > 代码库 > Codeforces Round #268 (Div. 1) 题解
Codeforces Round #268 (Div. 1) 题解
A：24 Game
题意：给一个n，求从1到n通过加减乘除得到24的方法。
题解：不难想到n<4时候肯定是无解的，
n=4时候 1+2=3 3+3=6 6*4=24
n=5时候1*5=5 5-2=3 3+3=6 6*4=24
当n>5时候我们可以让n-(n-1)=1 1*1=1 这样就把1~n变成了1~n-2
所以对于任意给定的n，我们把(5~n)这段的数相邻的相减变成1最终转换成用1~4或者1~5构造答案即可。
1 #include <cstdio> 2 3 #include <cmath> 4 5 #include <iostream> 6 7 #include <algorithm> 8 9 #include <cstring>10 11 12 13 using namespace std;14 15 int n;16 17 void work(int x)18 19 {20 21 if (x==4) 22 23 {24 25 printf("1 + 2 = 3\n3 + 3 = 6\n4 * 6 = 24\n");26 27 return;28 29 }30 31 if (x==5)32 33 {34 35 printf("1 * 5 = 5\n5 - 2 = 3\n3 + 3 = 6\n6 * 4 = 24\n");36 37 return;38 39 }40 41 printf("%d - %d = 1\n1 * 1 = 1\n",x,x-1);42 43 work(x-2);44 45 }46 47 int main()48 49 {50 51 scanf("%d",&n);52 53 if (n<4)54 55 {56 57 printf("NO\n");58 59 return 0;60 61 }62 63 printf("YES\n");64 65 work(n);66 67 return 0;68 69 }
B：Two Sets
题意：给出n个数p1~pn 要求把这N个数划分成两个集合，要求若X∈A 则a-x∈A 若X∈B 则b-x属于B，a，b为给定得数。
题解：用一个map记录每个数是否出现过，若对于某个pi a-pi不在这列数中，我们就只能把pi放到B集合中，所以用一个队列记录必然出现在B集合中的数，
每次取出队头元素X，检查b-X是否在p中出现，若出现也要加入此队列，再加入b-X的同时易知a-(b-X)必然也只能出现在集合B，也要同时加入队列。
1 #include <cstdio> 2 3 #include <iostream> 4 5 #include <algorithm> 6 7 #include <cmath> 8 9 #include <cstring>10 11 #include <queue>12 13 #include <map>14 15 using namespace std;16 17 map<int,int> pos;18 19 int n,a,b,ans[500000],x[500000];20 21 int main()22 23 {24 25 queue<int> q;26 27 scanf("%d%d%d",&n,&a,&b);28 29 for (int i=1;i<=n;++i) 30 31 {32 33 scanf("%d",&x[i]);34 35 pos[x[i]]=i;36 37 }38 39 for (int i=1;i<=n;++i)40 41 {42 43 if (pos[a-x[i]]==0)44 45 {46 47 ans[i]=1;48 49 q.push(x[i]);50 51 }52 53 }54 55 while (!q.empty())56 57 {58 59 int now=q.front();60 61 q.pop();62 63 if (pos[b-now]==0) 64 65 {66 67 printf("NO\n");68 69 return 0;70 71 }72 73 if (ans[pos[b-now]]==1) continue;74 75 ans[pos[b-now]]=1;76 77 if (pos[a-b+now]!=0)78 79 {80 81 ans[pos[a-b+now]]=1;82 83 q.push(a-b+now);84 85 }86 87 }88 89 printf("YES\n");90 91 for (int i=1;i<=n;++i) printf("%d ",ans[i]);92 93 return 0;94 95 }
C:Hack it!
题意：定义f(x)为x的各位数字之和，比如f(1234)=1+2+3+4=10，一个人用如下算法计算
sum=
ans = solve(l, r) % a;
if (ans <= 0)
ans += a;
当ans=0时会出现错误，对于给定的a，我们要构造一个L,R来hack他。
gy神犇给我讲的
我们来观察l=1 r=1e18的时候的sum值
l r每当+1的时候 我们发现sum值加了1！因为r加1后后面几位即为l不加1时候的数，所以每次加1即把整个数列往前推了一位，然后r变成了1000...L！于是L,R每往后加1，sum就加1，于是先求出来l=1 r=1e18的sum值后挪(a-sum)次即可！r开到足够大目的在于这样不用考虑进位问题，否则r最前面就不是1，也不能保证后面出现L了。巧妙地构造~
关于sum的算法：令ai=(1~10^i)-1的sum值
a1=45
a2=10*a1+45*10
...
an=10*an-1+45*10^i
得到an=45*n*10^(n-1)
a18=81*1e18
所以sum=(a18+1)%a;问题得到解决。
1 #include <cstdio> 2 3 #include <cmath> 4 5 #include <iostream> 6 7 #include <cstring> 8 9 #include <algorithm>10 11 12 13 using namespace std;14 15 typedef long long LL;16 17 LL l,r,a,ans;18 19 int main()20 21 {22 23 l=1;r=1e18;24 25 scanf("%I64d",&a);26 27 ans=((3*(3*(3*(3*(5*(2*((LL)1e17%a))%a)%a)%a)%a)%a)%a+1)%a;28 29 printf("%I64d %I64d",l+a-ans,r+a-ans);30 31 return 0;32 33 }
Codeforces Round #268 (Div. 1) 题解