A. Prefixes
因为是对于每个偶数个的前缀“a“，”b“数量都相等，于是可以得出，只要从头开始每两个字母都是一个”a"，"b"就满足答案
所以将字符串从头遍历，每两个check一下，相等则修改，因为对修改没什么要求，我是始终修改第一个，并记录次数就行了
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 string a;
5
6 int main()
7 {
8 int n;
9 while(cin>>n)
10 {
11 cin>>a;
12 int cnt=0;
13 for(int i=0;i<n;i+=2)
14 {
15 if(a[i]+a[i+1]=='a'+'a')
16 a[i]='b',cnt++;
17 else if(a[i]+a[i+1]=='b'+'b')
18 a[i]='a',cnt++;
19 }
20 cout<<cnt<<endl;
21 cout<<a<<endl;
22 }
23 return 0;
24 }
View Code
B. Shooting
每个瓶子有个耐久值ai，已经击倒的瓶子数是x，对于每个瓶子，射击击倒需要的射击次数是（ai*x+1），现有一堆瓶子，求最少射击次数
由此可见对于一个ai，x越大，则最后射击次数越大，所以在x较小的时候先击倒耐久度大的瓶子，这样次数才较少，是个简单的贪心。
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 typedef struct
5 {
6 int id;
7 int v;
8 }can;
9
10 bool cmp(can a,can b)
11 {
12 return a.v>b.v;
13 }
14
15 can a[1005];
16
17 int main()
18 {
19 int n;
20 while(cin>>n)
21 {
22 for(int i=1;i<=n;i++)
23 {
24 cin>>a[i].v;
25 a[i].id=i;
26 }
27 sort(a+1,a+1+n,cmp);
28 int sum=0;
29 for(int i=0;i<n;i++)
30 {
31 sum+=i*a[i+1].v+1;
32 }
33 cout<<sum<<endl;
34 for(int i=1;i<=n;i++)
35 {
36 cout<<a[i].id<<" ";
37 }
38 cout<<endl;
39 }
40 return 0;
41 }
View Code
C. White Sheet
题意很好理解，求第一个矩形（白）是否被后两个矩形（黑）所覆盖。数据大小为1e6所以不能直接二维数组。
这道题可以用简单的暴力法过，由于这些矩形的顶点都是正整数点，所以我直接对白矩形边上的点，从顶点开始按+0.5的速度沿着边遍历，对每个点check他是否再黑矩形的内部，只要有一个点不在，则没有完全覆盖（按+1的话会漏点）。
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 double x1,x2,x3,x4,x5,x6;
5 double yy1,yy2,yy3,yy4,yy5,yy6;
6
7 bool check1(double x,double y)
8 {
9 if(x>=x3&&x<=x4&&y>=yy3&&y<=yy4)
10 return 1;
11 else
12 return 0;
13 }
14
15 bool check2(double x,double y)
16 {
17 if(x>=x5&&x<=x6&&y>=yy5&&y<=yy6)
18 return 1;
19 else
20 return 0;
21 }
22
23 int main()
24 {
25 while(cin>>x1>>yy1>>x2>>yy2)
26 {
27 cin>>x3>>yy3>>x4>>yy4;
28 cin>>x5>>yy5>>x6>>yy6;
29 for(double i=0.0;x1+i<=x2;i+=0.5)
30 {
31 if(check1(x1+i,yy1)||check2(x1+i,yy1))
32 continue;
33 else
34 {
35 cout<<"YES"<<endl;
36 return 0;
37 }
38 }
39 for(double i=0.0;yy1+i<=yy2;i+=0.5)
40 {
41 if(check1(x1,yy1+i)||check2(x1,yy1+i))
42 continue;
43 else
44 {
45 cout<<"YES"<<endl;
46 return 0;
47 }
48 }
49 for(double i=0.0;yy1+i<=yy2;i+=0.5)
50 {
51 if(check1(x2,yy1+i)||check2(x2,yy1+i))
52 continue;
53 else
54 {
55 cout<<"YES"<<endl;
56 return 0;
57 }
58 }
59 for(double i=0.0;x1+i<=x2;i+=0.5)
60 {
61 if(check1(x1+i,yy2)||check2(x1+i,yy2))
62 continue;
63 else
64 {
65 cout<<"YES"<<endl;
66 return 0;
67 }
68 }
69 cout<<"NO"<<endl;
70 }
71 return 0;
72 }
View Code
D. Swords
有n种剑每种x把，来了y个人，每个人会挑选有且仅有一种剑，拿z把。
现在早上得到每种剑的剩余数量，求最少的可能的人数y。
（以下均为猜想没有证明过）
找到剩余数量最多的剑，假定它没被拿过，记为x；计算分别其余的剑被拿走的数量，另存一数组，求这些数的gcd，记为z；然后拿走的剑数量/z求和，即为y。
这样找到的就是最小的y（感觉是），然后就a了。（证明挖个坑先(￣△￣；)）
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4
5 int a[200005],b[200005];
6
7 int ngcd(int n)
8 {
9 if (n == 1) return *b;
10 return __gcd(b[n-1], ngcd(n-1));
11 }
12
13 int main()
14 {
15 int n;
16 while(cin>>n)
17 {
18 int maxx=-1;
19 for(int i=0;i<n;i++)
20 {
21 cin>>a[i];
22 if(a[i]>maxx)
23 maxx=a[i];
24 }
25 int j=0;
26 for(int i=0;i<n;i++)
27 {
28 b[j]=maxx-a[i];
29 if(b[j]==0)
30 continue;
31 else
32 j++;
33 }
34 int z=ngcd(j);
35 ll y=0;
36 for(int i=0;i<j;i++)
37 y+=(b[i]/z);
38 cout<<y<<" "<<z<<endl;
39 }
40 return 0;
41 }
View Code