<>A 卡片

<>问题描述

<>思路

<>代码
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 直线

<>问题描述

<>思路

<>推导

<>代码
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 货物摆放

<>题目描述

<>思路

<>代码
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 路径

<>问题描述

<>思路

<>解法一：暴力跑最短路弗洛伊德算法

<>代码一
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

<>代码二
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. #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 砝码称重

<>问题描述

<>思路

①第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。

<>代码
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 异或数列

<>题目描述

①从数列中选一个数Xi给Alice的数异或上。
②从数列中选一个数Xi给Bob的数异或上。

<>思路

①平局，最终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，0
0==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 左孩子右兄弟

<>问题描述

<>思路

<>代码
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 括号序列

<>题目描述

<>思路

①遇到左括号，直接转移状态，无需再去插入，满足添加最少
②遇到右括号，状态可以由右括号前面添加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]=f[i-1][j+1]+Σf[i-1][k]，k=0、1、2、……、j

<>代码
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. }

GitHub

Gitee