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
3 + 3 = 6
4 * 6 = 24
");
26 
27         return;
28 
29     }
30 
31     if (x==5)
32 
33     {
34 
35         printf("1 * 5 = 5
5 - 2 = 3
3 + 3 = 6
6 * 4 = 24
");
36 
37         return;
38 
39     }
40 
41     printf("%d - %d = 1
1 * 1 = 1
",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
");
58 
59         return 0;
60 
61     }
62 
63     printf("YES
");
64 
65     work(n);
66 
67     return 0;
68 
69 }

View Code

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
");
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
");
90 
91     for (int i=1;i<=n;++i) printf("%d ",ans[i]);
92 
93     return 0;
94 
95 }

View Code

C:Hack it!

题意：定义f(x)为x的各位数字之和，比如f(1234)=1+2+3+4=10，一个人用如下算法计算

sum= $\text{[math]}$

 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 }

View Code