放假之后的第一天，打着玩，状态有点差，写了两个题，第三个WA了一发就摸鱼去了

 

A.

题意：给两个长度均为n(1e5)的01串ab，ab的和为c，c的长度也是n。当ab的某一位均为1，c的这一位可以为2（总之就是不进位）。当c的连续的某几位相等时，就把连续的合并成一个，这样得到d。这个题目中，n和b已经给定，让你找到一个a使最后得到的d最大

 

分析：这个题要求d最大，那么最好的情况就是c的相邻的两位值都不相同，并且高位尽可能大。这样贪心的策略就很明显了，a从高到低，能取1的时候就取1，当取1的时候得到的c与高一位的相同时，a就只能取0。从高到低跑一遍就好了

 

代码：

 1 char str[100010];
 2 
 3 int main()
 4 {
 5     int T = 1;
 6     T = read();
 7     while (T --)
 8     {
 9         int n;
10         n = read();
11         scanf ("%s", str);
12         int pre = 0;
13         for (int i = 0; i < n; i ++)
14         {
15             int now = str[i] - '0';
16             if(pre == now + 1)
17             {
18                 printf ("0");
19                 pre = now;
20             }    
21             else
22             {
23                 printf ("1");
24                 pre = now + 1;
25             }
26         }
27         printf ("\n");
28     }
29     return 0;
30 }

A

 

 

B.

题意：给定一个数d(1e4)，要求找到一个最小的数，满足它的因子数>=4并且它们之间的相差>=d

 

分析：这个题容易造成误解（就是这个原因WA了一发，后面过了之后才发的公告），开始以为直接是1,1+d,1+2d,(1+d)(1+2d)，后面发现如果1+d或者1+2d不为质数的时候，这个数会有其它的因子，导致不符合要求。所以应找到一个质数a满足a>=1+d，然后再找到质数b满足b>=a+d，最后的答案就是a*b

 

代码：

 1 bool prime(int x)
 2 {
 3     for (int i = 2; i * i <= x; i ++)
 4         if (x % i == 0) return false;
 5     return true;
 6 }
 7 
 8 int main()
 9 {
10     int T = 1;
11     T = read();
12     while (T --)
13     {
14         int a = read();
15         int ans1, ans2;
16         ans1 = 1 + a;
17         while (!prime(ans1)) ans1 ++;
18         ans2 = ans1 + a;
19         while (!prime(ans2)) ans2 ++;
20         printf ("%d\n", ans1 * ans2); 
21     }
22     return 0;
23 }

B

 

刚回家，去做一个核酸，剩下的慢慢补。。