A. Sweet Problem
题目大意：你有不同数量的红绿蓝三种颜色的糖果，每天想吃两颗颜色不同的糖果，问能吃多少天。
2019ICPC沈阳赛区flowers的弱化题qwqflowers是有n种花选m种不同种类的一朵花组成一束花问最多能组成多少束。
是否可行具有单调性，二分天数，只要选的糖果数小于等于天数，就一定存在某种方案，不会出现某一天吃两只同样的糖果。
1 #include <bits/stdc++.h>
2 #define MIN(a,b) ((((a)<(b)?(a):(b))))
3 #define MAX(a,b) ((((a)>(b)?(a):(b))))
4 #define ABS(a) ((((a)>0?(a):-(a))))
5 using namespace std;
6
7 template <typename T>
8 void read(T &x) {
9 int s = 0, c = getchar();
10 x = 0;
11 while (isspace(c)) c = getchar();
12 if (c == 45) s = 1, c = getchar();
13 while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
14 if (s) x = -x;
15 }
16
17 template <typename T>
18 void write(T x, char c = ' ') {
19 int b[40], l = 0;
20 if (x < 0) putchar(45), x = -x;
21 while (x > 0) b[l++] = x % 10, x /= 10;
22 if (!l) putchar(48);
23 while (l) putchar(b[--l] | 48);
24 putchar(c);
25 }
26
27 int r,b,g,sum;
28
29 void Input(void) {
30 read(r);
31 read(b);
32 read(g);
33 sum=r+b+g;
34 }
35
36 bool check(int x){
37 int a=MIN(x,r);
38 int u=MIN(x,b);
39 int v=MIN(x,g);
40 if (u+a+v>=2*x) return 1;
41 else return 0;
42 }
43 void Solve(void) {
44 int l=0,r=1e9;
45 int ans=0;
46 while(l<r){
47 int mid=(l+r)>>1;
48 if (check(mid)) ans=mid,l=mid+1;
49 else r=mid;
50 }
51 printf("%d\n",ans);
52 }
53
54 void Output(void) {}
55
56 main(void) {
57 int kase;
58 freopen("input.txt", "r", stdin);
59 freopen("output.txt", "w", stdout);
60 read(kase);
61 for (int i = 1; i <= kase; i++) {
62 //printf("Case #%d: ", i);
63 Input();
64 Solve();
65 Output();
66 }
67 }
神奇的代码
B. PIN Codes
题目大意：有n个PIN密码，该密码由四位数字组成（可以前导0），一次操作可以修改某个密码的某一位，问最少要进行多少次操作，使得n个密码互不相等，输出最少操作次数以及修改后的密码，如有多种情况，输出任意一种即可。
注意到n最多只有10，那么我们只要相同的数的某一位全部改成0-9即可。
1 #include <bits/stdc++.h>
2 #define MIN(a,b) ((((a)<(b)?(a):(b))))
3 #define MAX(a,b) ((((a)>(b)?(a):(b))))
4 #define ABS(a) ((((a)>0?(a):-(a))))
5 using namespace std;
6
7 template <typename T>
8 void read(T &x) {
9 int s = 0, c = getchar();
10 x = 0;
11 while (isspace(c)) c = getchar();
12 if (c == 45) s = 1, c = getchar();
13 while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
14 if (s) x = -x;
15 }
16
17 template <typename T>
18 void write(T x, char c = ' ') {
19 int b[40], l = 0;
20 if (x < 0) putchar(45), x = -x;
21 while (x > 0) b[l++] = x % 10, x /= 10;
22 if (!l) putchar(48);
23 while (l) putchar(b[--l] | 48);
24 putchar(c);
25 }
26
27 map<int,int> qwq;
28
29 int n,p,cnt;
30
31 int tmp[13],id[13],yuan[13];
32
33 bool check(int x){
34 if (qwq[x]==1) return true;
35 else return false;
36 }
37
38 void Input(void) {
39 qwq.clear();
40 cnt=0;
41 read(n);
42 for(int i=1;i<=n;++i){
43 read(p);
44 yuan[i]=p;
45 if (qwq[p]!=1) {qwq[p]=1; continue;}
46 tmp[++cnt]=p;
47 id[cnt]=i;
48 }
49 for(int i=1;i<=cnt;++i){
50 while(check(tmp[i])){
51 if (tmp[i]%10==9) tmp[i]-=9;
52 else ++tmp[i];
53 }
54 qwq[tmp[i]]=1;
55 yuan[id[i]]=tmp[i];
56 }
57 printf("%d\n",cnt);
58 for(int i=1;i<=n;++i) {
59 if (yuan[i]>=1000) printf("%d\n",yuan[i]);
60 else if (yuan[i]>=100) printf("0%d\n",yuan[i]);
61 else if (yuan[i]>=10) printf("00%d\n",yuan[i]);
62 else printf("000%d\n",yuan[i]);
63 }
64 }
65
66 void Solve(void) {}
67
68 void Output(void) {}
69
70 main(void) {
71 int kase;
72 freopen("input.txt", "r", stdin);
73 freopen("output.txt", "w", stdout);
74 read(kase);
75 for (int i = 1; i <= kase; i++) {
76 //printf("Case #%d: ", i);
77 Input();
78 Solve();
79 Output();
80 }
81 }
神奇的代码
C. Everyone is a Winner!
题目大意：MathForces举行了比赛，它可以分发n个rating，如果参赛选手数为k，则每个选手可以分到$\lfloor n/k \rfloor$个rating，但此时它并不知道k有多少，于是问你每个人分到的rating的可能的情况。（n/k的所有可能商）
当某商i=n/x，那么下一个大于该商i的除数x则是$\dfrac {n}{i}+1$，因为这里是整除，$i\times x\leq n$，因而$n\div i=k\geq x$，因为是整除其结果是$\lfloor k \rfloor$，我们取$x=\lceil k \rceil$，再进行n/x即可得到更小的商，如此即可快速找到所有的情况。
（把情况数数到oeis里发现是情况数是$\sqrt {4n+1}$的整数部分）
1 #include <bits/stdc++.h>
2 #define MIN(a,b) ((((a)<(b)?(a):(b))))
3 #define MAX(a,b) ((((a)>(b)?(a):(b))))
4 #define ABS(a) ((((a)>0?(a):-(a))))
5 using namespace std;
6
7 template <typename T>
8 void read(T &x) {
9 int s = 0, c = getchar();
10 x = 0;
11 while (isspace(c)) c = getchar();
12 if (c == 45) s = 1, c = getchar();
13 while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
14 if (s) x = -x;
15 }
16
17 template <typename T>
18 void write(T x, char c = ' ') {
19 int b[40], l = 0;
20 if (x < 0) putchar(45), x = -x;
21 while (x > 0) b[l++] = x % 10, x /= 10;
22 if (!l) putchar(48);
23 while (l) putchar(b[--l] | 48);
24 putchar(c);
25 }
26
27 int ans[700000];
28
29 void Input(void) {
30 int n,cnt=0;
31 read(n);
32 int x=1;
33 while(x<=n){
34 ans[++cnt]=n/x;
35 x=n/ans[cnt]+1;
36 }
37 ans[++cnt]=0;
38 printf("%d\n",cnt);
39 for(int i=cnt;i>0;--i) printf("%d%c",ans[i],i==1?'\n':' ');
40 }
41
42 void Solve(void) {}
43
44 void Output(void) {}
45
46 main(void) {
47 int kase;
48 freopen("input.txt", "r", stdin);
49 freopen("output.txt", "w", stdout);
50 read(kase);
51 for (int i = 1; i <= kase; i++) {
52 //printf("Case #%d: ", i);
53 Input();
54 Solve();
55 Output();
56 }
57 }
神奇的代码
D. Secret Passwords
题目大意：有n个密码，其中一个密码是系统密码。两个密码相同只要满足一个条件即可：1、两个密码中存在至少一个相同的字母 2、存在另一个密码与这两个密码分别相同。与系统密码相同的密码即可进入系统，求最小选多少个密码，保证可以进入系统。（因为密码可以输入多次）
就是找不同子串的个数，用并查集维护他们的相同关系即可。
（其实也就26个字母，可以根据一个密码里的所有字母来维护字母间的关系，最后统计出现过的字母中“不同”字母的数量即可）
1 #include <bits/stdc++.h>
2 #define MIN(a,b) ((((a)<(b)?(a):(b))))
3 #define MAX(a,b) ((((a)>(b)?(a):(b))))
4 #define ABS(a) ((((a)>0?(a):-(a))))
5 using namespace std;
6
7 template <typename T>
8 void read(T &x) {
9 int s = 0, c = getchar();
10 x = 0;
11 while (isspace(c)) c = getchar();
12 if (c == 45) s = 1, c = getchar();
13 while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
14 if (s) x = -x;
15 }
16
17 template <typename T>
18 void write(T x, char c = ' ') {
19 int b[40], l = 0;
20 if (x < 0) putchar(45), x = -x;
21 while (x > 0) b[l++] = x % 10, x /= 10;
22 if (!l) putchar(48);
23 while (l) putchar(b[--l] | 48);
24 putchar(c);
25 }
26
27 map<string,int> qwq;
28
29 const int N=2e5+10;
30
31 int f[N],pos[N];
32
33 int n;
34
35 string tmp;
36
37 int findfather(int x){
38 if (f[x]==x) return x;
39 else return f[x]=findfather(f[x]);
40 }
41 void work(int x){
42 int l=tmp.size();
43 for(int u,v,i=0;i<l;++i){
44 if (pos[tmp[i]-'a']!=0&&pos[tmp[i]-'a']!=x){
45 u=findfather(pos[tmp[i]-'a']);
46 v=findfather(x);
47 if (u!=v) f[u]=v;
48 }
49 else pos[tmp[i]-'a']=x;
50 }
51 }
52
53 void Input(void) {
54 cin>>n;
55 qwq.clear();
56 for(int i=0;i<=26;++i) pos[i]=0;
57 for(int i=1;i<=n;++i){
58 f[i]=i;
59 cin>>tmp;
60 if (qwq[tmp]==1) {f[i]=-1;continue;}
61 qwq[tmp]=1;
62 work(i);
63 }
64 int ans=0;
65 for(int i=1;i<=n;++i) if (f[i]==i) ++ans;
66 cout<<ans<<endl;
67 }
68
69 void Solve(void) {}
70
71 void Output(void) {}
72
73 main(void) {
74 ios::sync_with_stdio(0);
75 cin.tie(0); cout.tie(0);
76 freopen("input.txt", "r", stdin);
77 freopen("output.txt", "w", stdout);
78 Input();
79 Solve();
80 Output();
81 }
神奇的代码
（这里还是维护密码之间的相互关系了）