题目传送门
A. Maximum Square
题目意思是给你n个长条，每个长条的高度是num[i](0 < i < n)，每一条的宽度都是 1 ；然后求这些长条可以组成的最大面积的正方形的宽度是多少，将它输出来。
题目分析 ：因为要求的是正方形，而且面积是最大的，所以既要看它的宽度也要看它的高度。因为多余的面积可以删除掉，所以我们只需要知道min（长，宽）。
所以可以将所有的长度排个序，然后从大到小历经一遍就可以了。
1 #include <iostream>
2 #include <algorithm>
3 #include <string>
4 #include <cstdio>
5
6 using namespace std;
7 const int ma = 2e5 + 10;
8 int num[1005];
9 int n;
10
11 int main()
12 {
13 int k;
14 scanf("%d",&k);
15 while(k--)
16 {
17 scanf("%d",&n);
18 for(int i = 1;i <= n;i++)
19 scanf("%d",&num[i]);
20 sort(num+1,num+n+1,greater<int>());//从大到小排序
21 int maxn = 0;
22 for(int i = 1;i <= n;i++)
23 {
24 maxn = max(maxn,min(num[i],i));//i代表着宽度，maxn是最终的答案。
25 }
26 printf("%d\n",maxn);
27 }
28 return 0;
29 }
B1. Character Swap (Easy Version)
题目意思：给你两个字符串s和t，它们具有相同的长度n，给你一个操作：你可以在s中选择一个下标i [1,n],然后在t中选择一个下标j [1, n],将它们进行交换，即swap(s[i],t[j])。但是你的操作数只有一次，要使得交换后的s与t相同。并且他是要从前往后进行操作的。（当然交换次数也可以是0）
题目分析：因为操作数只有一次，（这个一定要知道，我就是因为没有看到这个条件而wa了一发，还浪费了时间去找其他错误去了，我太菜了）所以要输出YES的话，就只有一种状态可以满足，那就是只有两组不同（我将具有相同下标的s[i] 和t[i]的两个字符看成一组），而且在这四个字符中，只有两个不同的字符，最重要的是两个组的上下的字符也要相同，只有这样才可以输出YES。其它情况下都不行。
看代码：
1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 #include <string>
5 #include <cstdio>
6
7 using namespace std;
8 const int ma = 2e4 + 10;
9 const int mm = 30;
10 char s[ma],t[ma];
11 int n,num[mm];
12 int dig[mm][mm];
13
14 int main()
15 {
16 int k;
17 scanf("%d",&k);
18 while(k--)
19 {
20 scanf("%d",&n);
21 scanf(" %s",&s);
22 scanf(" %s",&t);
23 memset(num,0,sizeof(num));
24 for(int i = 0; i < n; i++)
25 num[s[i] - 'a']++,num[t[i] - 'a']++;//num数组是用来储存出现在s和t中字母的次数
26 bool f = 0;
27 for(int i = 0; i < 26; i++)
28 {
29 if(num[i] & 1)
30 {
31 f = 1;//如果出现的次数是奇数的话，那肯定是不行的，因为它都不能平均的分配
32 break;
33 }
34 }
35 if(f)
36 {
37 printf("No\n");
38 continue;
39 }
40 for(int i = 0; i < n; i++)
41 {
42 if(s[i] == t[i])
43 continue;
44 dig[s[i] - 'a'][t[i] - 'a']++;//dis数组是记录是s[i] 和 t[i] 出现的次数，如果可以输出YES的话那么只有一个有值并且它的值为2；因为
45 //它只能要小于等于不同的两组
46 }
47 int nu = 0;
48 for(int i = 0; i < 26; i++)
49 {
50 for(int j = 0; j < 26; j++)
51 {
52 nu += dig[i][j];//nu是记录次数的
53 if((dig[i][j] & 1) || nu > 3)
54 {
55 f = 1;
56 break;
57 }
58 }
59 if(f)
60 break;
61 }
62 if(f)
63 printf("No\n");
64 else
65 printf("Yes\n");
66 for(int i = 0;i < 30;i++)
67 for(int j = 0;j < 30;j++)
68 dig[i][j] = 0;//还要将dig数组清零
69 }
70 return 0;
71 }
View Code
B2. Character Swap (Hard Version)
题目意思：跟b1类似，但是它可以执行的操作数增加的变成了小于等于2 * n了，那肯定可以完成。
题目分析：因为执行的次数足够了，所以只有当在字符串s和t中的字符出现了奇数次的时候输出NO，其他情况都可以输出YES，因为我们要从前往后进行操作，所以要先将前面的字符先让它们相等
先拿出s中最前面的那个未操作的字符s[i]，在后面的s中找，看是否可以找到s[j]，可以的话就交换它们(交换s[j]和t[i]），然后将他们的下标记录下，没有的话，就从t中找，找到t[j]之后先让它跟上面的交换一下(t[j] 和 s[j]）再让t[j] 和 t[i] 交换，然后记录下他们的位置，最后将他们的位置输出来就可以了；
看代码：
1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 #include <cstdio>
5 #include <vector>
6
7 using namespace std;
8 const int ma = 30;
9 char s[55],t[55];
10 int ans[105][2];
11 int nu[ma],k;
12 struct node
13 {
14 char s1,t1;
15 int index;
16 };
17 vector<node> v;
18
19 int main()
20 {
21 scanf("%d",&k);
22 while(k--)
23 {
24 int n;
25 scanf("%d",&n);
26 scanf(" %s",&s);
27 scanf(" %s",&t);
28 memset(nu,0,sizeof(nu));
29 for(int i = 0; i < n; i++)
30 nu[s[i] - 'a']++,nu[t[i] - 'a']++;//记录在s和t字母出现的次数
31 bool f = 0;
32 for(int i = 0; i < 26; i++)
33 if(nu[i] & 1)
34 {
35 f = 1;//如果为奇数就输出NO
36 break;
37 }
38 if(f)
39 {
40 puts("No");
41 continue;
42 }
43 int in = 0;
44 bool f1 = 0;
45 for(int i = 0; i < n; i++)
46 {
47 if(s[i] == t[i])
48 continue;
49 node a;
50 a.s1 = s[i],a.t1 = t[i],a.index = i + 1;//将上下两个不同的储存在v中，
51 v.push_back(a);
52 }
53 int len = v.size(),cnt = 0;//len代表着有多少组是不同的
54 for(int i = 0; i < len; i++)
55 {
56 for(int j = i + 1; j < len; j++)
57 {
58 if(v[i].s1 == v[j].s1)
59 {
60 swap(v[i].t1,v[j].s1);
61 ans[++cnt][0] = v[j].index,ans[cnt][1] = v[i].index;//在s的后面找，看是否有跟v[i].s1相同的，有的话就记录下位置，并且要记得交换它们。
62 break;
63 }
64 if(v[i].s1 == v[j].t1)
65 {
66 swap(v[j].t1,v[j].s1);
67 swap(v[j].s1,v[i].t1);
68 ans[++cnt][0] = ans[cnt][1] = v[j].index;
69 ans[++cnt][0] = v[j].index,ans[cnt][1] = v[i].index;
70 break;
71 }
72 }
73 }
74 puts("YES");
75 printf("%d\n",cnt);
76 for(int i = 1; i <= cnt; i++)
77 {
78 printf("%d %d\n",ans[i][0],ans[i][1]);
79 ans[i][0] = ans[i][1] = 0;
80 }
81 v.clear();//记得要清零
82 }
83 return 0;
84 }
View Code