A 卡片
问题描述
小蓝有许多张卡片，每张卡片上的数字都是0到9。他想从1开始拼正整数，每拼一个数，卡片就保存起来，不能再拼其他数。现在他手里的卡片0到9各有2021张，他想知道自己能从1拼到多少？
思路
对于每一个能拼的数x，统计x的每一位分别是什么，让x从1开始增加，直到需要用的某一卡片数量为0为止。模拟即可。
代码
1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
4. int card[10];
5. int main()
6. {
7. for (int i = 0; i <= 9; i++)card[i] = 2021;
8. bool flag = true;
9. int num = 1;
10. for (num = 1; flag; num++) {
11. int x = num;
12. while (x) {
13. int cur = x % 10;
14. if (card[cur])card[cur]--;
15. else { flag = false; break; }
16. x /= 10;
17. }
18. }
19. cout << num - 2 << endl;
20. return 0;
21. }
答案
3181
B 直线
问题描述
二维平面给出20×21个点，它们能构成多少条不同的直线？
思路
两点构成一直线，因此，枚举所有的点对，420个点共构成419+418+417+……+1对，即（1+419）×419÷2=87990对。除去这87990条直线中重复的直线，就是正确答案。
数据结构set具有去重的功能，因此我们可以用set存储结构体node，node表示的是直线一般式的三个参数，即ax+by+c=0中的a，b，c。不用点斜式是因为计算斜率k会带来较大误差。
当然，a，b，c一定是互素的，即gcd(a,b,c)==1，才能保证直线不重复。直接除以三个数绝对值的gcd把三元组化为最简形式即可。
最后输出set.pair()。
推导
点p1(x1,y1)，点p2(x2,y2)，斜率k=(y1-y2)/(x1-x2)。点斜式方程y-y1=k(x-x1)，即(y-y1)×(x1-x2)=(y1-y2)×(x-x1)，得yx1-x1y1-yx2+x2y1=xy1-xy2-x1y1+x1y2，故(y1-y2)x+(x2-x1)y+(x1y2-x2y1)=0。
其中a=y1-y2，b=x2-x1，c=x1y2-x2y1。
如果插入的类型是自定义的，不是基本类型，需要重载<运算符，给自定义类型一个排序准则。
以上的做法是为了完全避免精度问题造成的影响，才将点斜式转化为一般式表示，否则答案将会千奇百怪。
代码
1. #include<iostream>
2. #include<algorithm>
3. #include<set>
4. using namespace std;
5. struct node1 {
6. int a, b, c;
7. friend bool operator < (const node1 &A, const node1 &B) {
8. if (A.a == B.a)return A.b == B.b ? A.c < B.c : A.b < B.b;
9. return A.a < B.a;
10. }
11. }line[87991];
12. struct node2 {
13. int x, y;
14. }point[421];
15. set<node1> s;
16. int gcd(int a, int b) {
17. return b == 0 ? a : gcd(b, a%b);
18. }
19. int main()
20. {
21. int cnt = 0;
22. for (int i = 0; i < 20; i++) {
23. for (int j = 0; j < 21; j++) {
24. point[cnt++] = { i,j };
25. }
26. }
27. for (int i = 0; i < cnt; i++) {
28. for (int j = i + 1; j < cnt; j++) {
29. int a = point[i].y - point[j].y;
30. int b = point[j].x - point[i].x;
31. int c = point[i].x*point[j].y - point[j].x*point[i].y;
32. int GCD = gcd(abs(a), gcd(abs(b), abs(c)));
33. a /= GCD, b /= GCD, c /= GCD;
34. s.insert({ a,b,c });
35. }
36. }
37. cout << s.size() << endl;
38. return 0;
39. }
答案
40257
C 货物摆放
题目描述
有n箱货物，长宽高的方向上分别堆L、W、H的货物，满足n=L×W×H。给定n=2021041820210418，总共有多少种堆放货物的方案？
思路
先求n的所有因数。已知所有分解出的因数，再让L分别取这些因数，计算每一个L取得的因数所对应的W×H，即n/L。因此，只需要再计算n/L的所有因数，并按照W与H的不同位置来求得W×H的所有取值方案，就可以对应到每一个L取得的因数。累加即得答案。
代码
1. #include<iostream>
2. #include<algorithm>
3. #define int long long
4. using namespace std;
5. int n = 2021041820210418;
6. int ans[100000];
7. int cal(int x) {
8. int t = 0;
9. for (int i = 1; i*i <= x; i++) {
10. if (x%i == 0) {
11. if (i*i == x)t++;
12. else t += 2;
13. }
14. }
15. return t;
16. }
17. signed main()
18. {
19. int cnt = 0;
20. for (int i = 1; i*i <= n; i++) {
21. if (n%i == 0) {
22. if (i*i == n)ans[++cnt] = i;
23. else ans[++cnt] = i, ans[++cnt] = n / i;
24. }
25. }
26. int res = 0;
27. for (int i = 1; i <= cnt; i++) {
28. res += cal(ans[i]);
29. }
30. cout << res << endl;
31. return 0;
32. }
答案
2430
D 路径
问题描述
两结点数字绝对值之差小于等于21有边，边权为两数的最小公倍数。计算结点1到2021的最短路径长度。
思路
先模拟建图，可以用静态邻接表。
解法一：暴力跑最短路弗洛伊德算法
用时17秒。测得本机在一秒内可以完成的计算量为4.87×10^8。
代码一
1. #include<iostream>
2. #include<algorithm>
3. #define inf 0x3f3f3f3f
4. using namespace std;
5. int g[2022][2022];
6. int gcd(int a, int b) {
7. return b == 0 ? a : gcd(b, a%b);
8. }
9. int lcm(int a, int b) {
10. return a*b / gcd(a, b);
11. }
12. int main()
13. {
14. for (int i = 1; i <= 2021; i++) {
15. for (int j = i + 1; j <= 2021; j++) {
16. if (abs(i - j) <= 21)g[i][j] = g[j][i] = lcm(i, j);
17. else g[i][j] = g[j][i] = inf;
18. }
19. }
20. for (int k = 1; k <= 2021; k++) {
21. for (int i = 1; i <= 2021; i++) {
22. for (int j = 1; j <= 2021; j++) {
23. if (g[i][k] + g[k][j] < g[i][j]) {
24. g[i][j] = g[i][k] + g[k][j];
25. }
26. }
27. }
28. }
29. cout << g[1][2021] << endl;
30. return 0;
31. }
解法二：线性DP
状态表示d[i]：从结点1到i的所有路径
集合划分：所有能从i的上一个结点j转移到结点i的路径，且j的取值范围是i-21到i-1，且j>=1。
属性：最小值
状态计算：d[i]=min(d[i],d[j]+g[i][j])
初始化：d[1]=0
代码二
1. #include<iostream>
2. #include<algorithm>
3. #include<cstring>
4. using namespace std;
5. int g[2022][2022];
6. int gcd(int a, int b) {
7. return b == 0 ? a : gcd(b, a%b);
8. }
9. int lcm(int a, int b) {
10. return a*b / gcd(a, b);
11. }
12. int d[2022];
13. int main()
14. {
15. for (int i = 1; i <= 2021; i++) {
16. for (int j = i - 1; j >= i - 21 && j >= 1; j--) {
17. g[j][i] = lcm(i, j);
18. }
19. }
20. memset(d, 0x3f, sizeof(d));
21. d[1] = 0;
22. for (int i = 1; i <= 2021; i++) {
23. for (int j = i - 1; j >= i - 21 && j >= 1; j--) {
24. d[i] = min(d[i], d[j] + g[j][i]);
25. }
26. }
27. cout << d[2021] << endl;
28. return 0;
29. }
答案
10266837
E 回路计数
题目描述
编号从1到21有21个结点，若两结点上的数互质，则两结点间存在一条无向边。初始时小蓝在第一个结点，若要恰好访问每个结点一次，并最终返回第一个结点，问存在多少种不同的访问方案？
思路
求最短哈密顿回路，需要用状态压缩DP计算。
分别重新编号为0到20，转化为标准哈密顿模型。
状态表示f[i][j]：所有从起点0走到终点j，走过的所有点对应的状态压缩表示为i的所有路径。
属性：从0到j的所有路径的数量
集合划分：根据倒数第二个点是哪个点来分类，即最后一步是从第k个点走到第j个点，且k可能为除j之外的任意一个点。
状态计算：f[i][j]=Σf[i-(1<<j)][k]
转移条件：状态i的第j位已经走到，i-(1<<j)这一状态的第k位已经走到，且从k到j的路径存在。
初始化：f[1][0]=1
结果：可能最终是从编号1到20的任意一个结点返回的0结点。
代码
1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
4. const long long maxn = 1 << 21;
5. bool g[22][22];
6. long long f[maxn][22];
7. int gcd(int a, int b) {
8. return b == 0 ? a : gcd(b, a%b);
9. }
10. int main()
11. {
12. for (int i = 1; i <= 21; i++) {
13. for (int j = i + 1; j <= 21; j++) {
14. if (gcd(i, j) == 1)g[i - 1][j - 1] = g[j - 1][i - 1] = true;
15. }
16. }
17. f[1][0] = 1;
18. for (int i = 1; i <= maxn - 1; i++) {
19. for (int j = 0; j < 21; j++) {
20. if (i >> j & 1) {
21. for (int k = 0; k < 21; k++) {
22. if ((i - (1 << j)) >> k & 1 && g[k][j]) {
23. f[i][j] += f[i - (1 << j)][k];
24. }
25. }
26. }
27. }
28. }
29. long long ans = 0;
30. for (int i = 1; i < 21; i++) {
31. ans += f[maxn - 1][i];
32. }
33. cout << ans << endl;
34. return 0;
35. }
答案
881012367360
F 砝码称重
问题描述
有一架天平和n个砝码，砝码可以放在天平两边。分别给出这n个砝码的重量，求一共可以称出多少种不同的重量？
思路
称出的重量一定在1到ΣWi这一区间内，且已知ΣWi<=100000。因此只需要判断这一区间内可以取得的重量一共有多少种即可。
状态表示f[i][j]：所有从前i个砝码中选择，取得的重量为j的取法。
属性：重量j能否被取到，能为1，不能为0。
集合划分：对于当前的状态f[i][j]，可能是由三种状态转移而来。
①第i个砝码不选，f[i][j]=f[i-1][j]。
②第i个砝码放在天平左边，记砝码放在天平左边重量为正，则f[i][j]=f[i-1][abs(j-w[i])]，即j-w[i]若为负取绝对值即可。
③第i个砝码放在天平右边，记砝码放在天平右边重量为负，则f[i][j]=f[i-1][j+w[i]]，注意j+w[i]<=ΣWi。
只要能从上述三种状态中的任意一种可行的状态转移得到当前的状态，那么当前的状态f[i][j]就是可行的。据此得状态转移方程。
状态计算：f[i][j]=f[i-1][j]|f[i-1][abs(j-w[i])]
若j+w[i]<=ΣWi，f[i][j]|=f[i-1][j+w[i]]
位运算符或就是用来表示只要上述三种状态有一个为真则当前状态就为真。注意题目说明0不算一种重量。
初始化：f[0][0]=true，即所有状态最初都是由所有物品都不选，总重量为0这种状态转移而来的，故后续的j也要从0开始循环。注意状态表示的是所有集合，因此不要漏掉0的情况。
代码
1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
4. const int maxn = 100005;
5. int w[102], sum = 0;
6. bool f[102][maxn];
7. int main()
8. {
9. int N;
10. cin >> N;
11. for (int i = 1; i <= N; i++)cin >> w[i], sum += w[i];
12. f[0][0] = true;
13. for (int i = 1; i <= N; i++) {
14. for (int j = 0; j <= sum; j++) {
15. f[i][j] = f[i - 1][j] | f[i - 1][abs(j - w[i])];
16. if (j + w[i] <= sum)f[i][j] |= f[i - 1][j + w[i]];
17. }
18. }
19. int ans = 0;
20. for (int i = 1; i <= sum; i++) {
21. if (f[N][i])ans++;
22. }
23. cout << ans << endl;
24. return 0;
25. }
G 异或数列
题目描述
初始时，Alice和Bob分别有一个整数a和b，有一个给定的长度为n的数列。a和b的初始值均为0。Alice和Bob轮流操作，Alice先手，每步可以从两个选项中选一种：
①从数列中选一个数Xi给Alice的数异或上。
②从数列中选一个数Xi给Bob的数异或上。
每个数Xi只能用一次，当每个数都被用过一遍后，游戏结束。拥有数大的一方获胜，双方数字相同即平局。
双方都足够聪明，都采用最优策略，问谁能获胜？
思路
①平局，最终a和b一定相等，即a异或b等于0。由于初始时a=b=0，满足a异或b等于0，故数列中X1异或X2异或……异或Xn等于0时，无论如何操作必平局。
②如果所有数字异或和不为0，那么异或和sum至少存在一位不为0，双方必定是要争最高不为0的那一位的最后的归属。将数列中所有数字表示为二进制，假设在最高位有x个0和y个1，Alice只需要保证自己决策的时候y为奇数，并且每选择一个0都可以扭转局势。
Ⅰ若y为奇数，x为偶数，即n为奇数，Alice先取1，Bob如果也跟着取1，是必输的，如果Bob取0扭转局势，那么Alice也可以再取0扭转局势，并且偶数个0恰好抵消，故此时Alice必胜。
Ⅱ若y为奇数，x为奇数，即n为偶数，Alice先取1，则Bob可取0扭转局势，如果Alice接着取1，经历各自取1的情况后，最后一个1一定是Bob取的，他可以操作这个1给自己或Alice，则Bob必胜。但如果y=1，即1的数量只有一个，Alice取了1之后Bob就无法通过扭转局势再取1达到制胜的目的，这时Alice必胜。
Ⅲ若y为偶数，无论x如何，这偶数个1都可以通过互相之间的异或操作来抵消，而01==1，00==0，故0对数没有影响，只能起到交换局势的作用。这时，就只能再去看次高位、次次高位，直到出现上述两种情况为止，否则就是平局。而平局已经通过第一大类确定了，故此种情况继续下去一定可以分出胜负。
代码
1. #include<iostream>
2. #include<algorithm>
3. #include<cstring>
4. using namespace std;
5. const int maxn = 2e5 + 5;
6. int x[maxn], n, one[22];
7. int solve(int x[], int n) {
8. memset(one, 0, sizeof(one));
9. int sum = 0;
10. for (int i = 1; i <= n; i++)sum ^= x[i];
11. if (sum == 0)return 0;
12. int h = 1;
13. for (int i = 1; i <= n; i++) {
14. int cur = x[i], cnt = 0;
15. while (cur) {
16. cnt++;
17. if (cur & 1)one[cnt]++;
18. cur = cur >> 1;
19. }
20. h = max(h, cnt);
21. }
22. for (int i = h; i >= 1; i--) {
23. if (one[i] & 1) {
24. if (n & 1)return 1;
25. else {
26. if (one[i] == 1)return 1;
27. else return -1;
28. }
29. }
30. }
31. }
32. int main()
33. {
34. int T;
35. cin >> T;
36. while (T--) {
37. cin >> n;
38. for (int i = 1; i <= n; i++)cin >> x[i];
39. int ans = solve(x, n);
40. cout << ans << endl;
41. }
42. return 0;
43. }
H 左孩子右兄弟
问题描述
对于一颗多叉树，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。每个结点的父结点编号比自己小。计算通过“左孩子右兄弟”表示法转化成的二叉树，高度最高是多少？
思路
对于树上的每一个结点，它的所有儿子都会按照某种顺序依次成为它的左儿子、左儿子的右儿子、左儿子的右儿子的右儿子、……，以此类推，深度不断增加。因此对于一个结点，只有把它的所有儿子形成的子树中，转化为二叉树深度最深的儿子放到最下面，才会最优。这一结论，通过样例可以推得。用树形DP求解此类问题。
状态表示f[i]：以i为根的多叉树能够转化成的所有二叉树。
属性：所有二叉树的最大高度。
状态计算：f[i]=max(f[i],f[j]+size(i))，j是i的儿子，size(i)是i的儿子个数，即转化为二叉树时将一个结点的所有子结点重连接成链。
初始化：若x是叶子结点，则f[x]=1。但题目要求只有根结点这一个结点的树高度为0，且转化成二叉树后高度不将根结点计算在内，因此只有初始化时需要计入，输出答案时再减去1即可。
代码
1. #include<iostream>
2. #include<algorithm>
3. #include<vector>
4. using namespace std;
5. const int maxn = 1e5 + 5;
6. int N;
7. vector<int> son[maxn];
8. int dfs(int cur) {
9. int ans = 1;
10. for (int i = 0; i < son[cur].size(); i++) {
11. ans = max(ans, dfs(son[cur][i]) + int(son[cur].size()));
12. }
13. return ans;
14. }
15. int main()
16. {
17. cin >> N;
18. int x;
19. for (int i = 2; i <= N; i++) {
20. cin >> x;
21. son[x].push_back(i);
22. }
23. int ans = dfs(1) - 1;
24. cout << ans << endl;
25. return 0;
26. }
I 括号序列
题目描述
给定一个括号序列，要求尽可能少地添加若干括号使得序列变得合法。添加完成后，有不同的添加效果。请问有多少种本质不同的添加结果？
思路
用线性DP求解本题。分为两个子问题，一个是只插入左括号，另一个是只插入右括号。对于后者，将原字符串镜像翻转后仍然按照插入左括号的方法求解。因此，只讨论插入左括号的情况。左右括号之所以可以独立相乘，是因为它们相互独立，可以理解为“背靠背”。
状态表示f[i][j]：前i个括号插入若干个括号后，左括号比右括号多j个的所有插入方法。注意只能插入左括号。
属性：所有插入方法的数量。
集合划分：第i个括号是左括号、右括号的情况。
①遇到左括号，直接转移状态，无需再去插入，满足添加最少
②遇到右括号，状态可以由右括号前面添加k个左括号转移而来，因为对于每种左括号多k个的状态，都可以通过插入左括号到多j个。
状态计算：
①a[i]=’(‘，f[i][j]=f[i-1][j-1]
②a[i]=’)’，f[i][j]=Σf[i-1][k]，k=0、1、2、……、j+1
优化：f[i][j-1]=Σf[i-1][k]，k=0、1、2、……、j
f[i][j]=f[i-1][j+1]+Σf[i-1][k]，k=0、1、2、……、j
故f[i][j]=f[i-1][j+1]+f[i][j-1]
结果：
注意f[n][i]需要不为0才能输出，并且要输出i尽可能小的，因为右括号数目固定，左括号应尽量少添加，那么i也就尽量小。
初始化：f[0][0]=1
代码
1. #include<iostream>
2. #include<algorithm>
3. #include<string>
4. #include<cstring>
5. using namespace std;
6. typedef long long ll;
7. const ll mod = 1e9 + 7;
8. const ll maxn = 5005;
9. ll f[maxn][maxn];
10. ll cal(string s) {
11. memset(f, 0, sizeof(f));
12. f[0][0] = 1;
13. for (int i = 1; i <= s.size(); i++) {
14. if (s[i - 1] == '(') {
15. for (int j = 1; j <= s.size(); j++)f[i][j] = f[i - 1][j - 1];
16. }
17. else {
18. f[i][0] = (f[i - 1][1] + f[i - 1][0]) % mod;
19. for (int j = 1; j <= s.size(); j++) {
20. f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod;
21. }
22. }
23. }
24. for (int i = 0; i <= s.size(); i++) {
25. if (f[s.size()][i])return f[s.size()][i];
26. }
27. }
28. int main()
29. {
30. string s;
31. cin >> s;
32. ll x = cal(s);
33. reverse(s.begin(), s.end());
34. for (int i = 0; i < s.size(); i++) {
35. if (s[i] == '(')s[i] = ')';
36. else s[i] = '(';
37. }
38. ll y = cal(s);
39. ll ans = x*y%mod;
40. cout << ans << endl;
41. return 0;
42. }
|