<>A card
<> Problem description
Xiao Lan has many cards , The numbers on each card are 0 reach 9. He wants to start from 1 Start spelling integers , Each spell a number , The card is saved , You can't spell other numbers . Now the card in his hand 0 reach 9 Each has 2021 Zhang , He wants to know what he can do from 1 How much do you spell ?
<> thinking
For every number that can be spelled x, Statistics x What is each of you , Give Way x from 1 Start to increase , Until the number of cards to be used is 0 until . Simulation is enough .
<> code
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. }
<> answer
3181
<>B straight line
<> Problem description
Two dimensional plane 20×21 Point , How many different lines can they form ?
<> thinking
Two points form a straight line , therefore , Enumerate all point pairs ,420 A total of points 419+418+417+……+1 yes , Namely （1+419）×419÷2=87990 yes . Remove this 87990 Duplicate lines in lines , That's the right answer .
data structure set It has the function of weight removal , So we can use set Storage structure node,node It represents the three parameters of the general formula of a straight line , Namely ax+by+c=0 Medium a,b,c. The point slope is not used because the slope is calculated k It will bring large errors .
of course ,a,b,c It must be mutually prime , Namely gcd(a,b,c)==1, To ensure that the straight line does not repeat . Divided directly by the absolute value of three numbers gcd The triples can be reduced to the simplest form .
Final output set.pair().
<> deduction
spot p1(x1,y1), spot p2(x2,y2), Slope k=(y1-y2)/(x1-x2). Point oblique equation y-y1=k(x-x1), Namely (y-y1)×(x1-x2)=(y1-y2)×(x-x1), have to yx1-x1y1-yx2+x2y1=xy1-xy2-x1y1+x1y2, so (y1-y2)x+(x2-x1)y+(x1y2-x2y1)=0.
among a=y1-y2,b=x2-x1,c=x1y2-x2y1.
If the inserted type is custom , Not a basic type , Overload required < operator , Give custom types a sorting criterion .
The above practice is to completely avoid the impact of accuracy problems , Then the point oblique expression is transformed into a general expression , Otherwise, the answer will be strange .
<> code
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. }
<> answer
40257
<>C Cargo placement
<> Title Description
have n Box cargo , Pile separately in the direction of length, width and height L,W,H Goods , satisfy n=L×W×H. given n=2021041820210418, How many stacking schemes are there in total ?
<> thinking
Ask first n All factors of . All decomposed factors are known , Let again L Take these factors separately , Calculate each L Corresponding to the obtained factor W×H, Namely n/L. therefore , Just recalculate n/L All factors of , And according to W And H From different positions W×H All value schemes , Can correspond to each L Obtained factor . Add up to get the answer .
<> code
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. }
<> answer
2430
<>D route
<> Problem description
The difference between the absolute values of two nodes is less than or equal to 21 Edge , The edge weight is the least common multiple of two numbers . node controler 1 reach 2021 Shortest path length .
<> thinking
Simulation drawing first , You can use a static adjacency table .
<> Solution I ： The shortest path Freudian algorithm of violent running
Time use 17 second . It is measured that the amount of calculation that the machine can complete in one second is 4.87×10^8.
<> Code one
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. }
<> Solution II ： linear DP
State representation d[i]： Slave node 1 reach i All paths of
Set partition ： All can from i Previous node of j Transfer to node i Path of , And j The value range of is i-21 reach i-1, And j>=1.
attribute ： minimum value
State calculation ：d[i]=min(d[i],d[j]+g[i][j])
initialization ：d[1]=0
<> Code two
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. }
<> answer
10266837
<>E Loop count
<> Title Description
Number from 1 reach 21 have 21 Nodes , If the numbers on two nodes are coprime , Then there is an undirected edge between the two nodes . At the beginning, Xiaolan is at the first node , To access each node exactly once , And finally return to the first node , How many different access schemes exist ?
<> thinking
Find the shortest Hamiltonian circuit , State compression required DP calculation .
Renumber as 0 reach 20, Transformed into standard Hamiltonian model .
State representation f[i][j]： All from start 0 Come to the end j, The state compression corresponding to all points passed is expressed as i All paths of .
attribute ： from 0 reach j Number of all paths
Set partition ： Classify according to which point is the penultimate point , That is, the last step is from step k Go to the second point j Point , And k May be divided by j Any point other than .
State calculation ：f[i][j]=Σf[i-(1<<j)][k]
Transfer conditions ： state i The first j You've come ,i-(1<<j) The second of this state k You've come , And from k reach j The path for does not exist .
initialization ：f[1][0]=1
result ： It may eventually be from the number 1 reach 20 Returned by any node of 0 node .
<> code
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. }
<> answer
881012367360
<>F Weight weighing
<> Problem description
There is a balance and n Weights , Weights can be placed on both sides of the balance . This is given separately n Weight of weights , Find out how many different weights you can weigh ?
<> thinking
The weight must be 1 reach ΣWi Within this range , And known ΣWi<=100000. Therefore, it is only necessary to judge how many kinds of weights can be obtained in this range .
State representation f[i][j]： All before i Select from two weights , The weight obtained is j Take method of .
attribute ： weight j Can it be taken , capability 1, Cannot be 0.
Set partition ： For current status f[i][j], It may be transferred from three states .
① The first i Weights not selected ,f[i][j]=f[i-1][j].
② The first i Put a weight on the left side of the balance , Put the weight on the left side of the balance and the weight is positive , be f[i][j]=f[i-1][abs(j-w[i])], Namely j-w[i] If it is negative, take the absolute value .
③ The first i Put a weight on the right side of the balance , Put the weight on the right side of the balance and the weight is negative , be f[i][j]=f[i-1][j+w[i]], be careful j+w[i]<=ΣWi.
As long as the current state can be obtained by transferring from any of the above three states , Then the current state f[i][j] Is feasible . Based on this, the state transition equation is obtained .
State calculation ：f[i][j]=f[i-1][j]|f[i-1][abs(j-w[i])]
if j+w[i]<=ΣWi,f[i][j]|=f[i-1][j+w[i]]
Bitwise operator or is used to indicate that as long as one of the above three states is true, the current state is true . Pay attention to the description of the topic 0 Not a weight .
initialization ：f[0][0]=true, That is, all States are initially unselected by all items , The total weight is 0 From this state of transition , So follow-up j Also from 0 Start cycle . Note that states represent all sets , So don't miss it 0 Situation .
<> code
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 Exclusive or sequence
<> Title Description
Initial time ,Alice and Bob Each has an integer a and b, There is a given length of n Sequence of .a and b The initial values of are 0.Alice and Bob Rotate operation ,Alice First hand , You can choose one of two options for each step ：
① Select a number from the sequence Xi to Alice On the number XOR of .
② Select a number from the sequence Xi to Bob On the number XOR of .
Each number Xi It can only be used once , When each number is used once , game over . The party with several big wins , If the numbers of both sides are the same, there will be a draw .
Both sides are smart enough , All adopt the optimal strategy , Ask who will win ?
<> thinking
① it ends in a draw , final a and b Must be equal , Namely a XOR b be equal to 0. Due to the initial a=b=0, satisfy a XOR b be equal to 0, Therefore, in the sequence X1 XOR X2 XOR …… XOR Xn be equal to 0 Time , In any case, the operation will draw .
② If all numbers are XOR and not 0, So XOR and sum At least one non 0, Both sides must strive for the highest inaction 0 The last belonging of the one . Represents all numbers in the sequence as binary , Suppose there is a x individual 0 and y individual 1,Alice Just make sure you make your own decisions y Odd number , And every time you choose one 0 Can turn the situation around .
Ⅰ if y Odd number ,x Even number , Namely n Odd number ,Alice Take first 1,Bob If you follow me 1, It's a must , If Bob take 0 Turn the situation around , that Alice You can also take it again 0 Turn the situation around , And even number 0 Just offset , So at this time Alice Be sure to win .
Ⅱ if y Odd number ,x Odd number , Namely n Even number ,Alice Take first 1, be Bob desirable 0 Turn the situation around , If Alice Then take 1, Each experience takes its own 1 After the situation , the last one 1 By all means Bob Taken , He can operate this 1 Give yourself or Alice, be Bob Be sure to win . But if y=1, Namely 1 There is only one quantity ,Alice Yes 1 after Bob You can't do it again by turning the situation around 1 Achieve the goal of winning , At this time Alice Be sure to win .
Ⅲ if y Even number , whether x how , This is an even number 1 Can be offset by XOR operations between each other , and 01==1,0
0==0, so 0 Logarithm has no effect , It can only exchange situations . At this time , You can only see the high position again , Secondary high , Until the above two situations occur , Otherwise it will be a draw . The draw has been determined through the first category , Therefore, if this situation continues, the outcome will be determined .
<> code
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 Left child right brother
<> Problem description
For a multitree , Each node can choose any child node as the left child , And connect the right brothers in any order . The parent node number of each node is smaller than itself . Calculation passed “ Left child right brother ” Binary tree transformed from representation , What is the maximum height ?
<> thinking
For each node in the tree , All its sons will become its left son in some order , Left son's right son , Left son's right son's right son ,……, and so on , Increasing depth . So for a node , Only put all its sons into a subtree , Into a binary tree, the deepest son is placed at the bottom , Will be the best . This conclusion , Through the example, we can deduce . Use tree DP Solve such problems .
State representation f[i]： with i A rooted multitree can be transformed into all binary trees .
attribute ： Maximum height of all binary trees .
State calculation ：f[i]=max(f[i],f[j]+size(i)),j yes i My son ,size(i) yes i Number of sons , That is, when it is transformed into a binary tree, all the child nodes of a node are reconnected into a chain .
initialization ： if x It's a leaf node , be f[x]=1. But the problem requires that only the root node, the tree height of which is 0, After being converted into a binary tree, the height does not include the root node , Therefore, only initialization needs to be included , Subtract when outputting the answer 1 that will do .
<> code
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 Bracket sequence
<> Title Description
Given a sequence of parentheses , It is required to add as few parentheses as possible to make the sequence legal . After adding , There are different adding effects . How many adding results are essentially different ?
<> thinking
With linear DP Solve the problem . It is divided into two sub problems , One is to insert only the left parenthesis , The other is to insert only the right parenthesis . For the latter , After flipping the image of the original string, it is still solved by inserting the left parenthesis . therefore , Only the insertion of left parentheses is discussed . The reason why the left and right parentheses can be multiplied independently , Because they are independent of each other , Can be understood as “ Back to back ”.
State representation f[i][j]： front i Parentheses after inserting several parentheses , There are more left parentheses than right parentheses j All insertion methods of . Note that only the left parenthesis can be inserted .
attribute ： Number of all insertion methods .
Set partition ： The first i Parentheses are left parentheses , Right parenthesis .
① Left parenthesis encountered , Direct transfer state , No need to insert , Meet the requirements of adding the least
② Right parenthesis encountered , The status can be added before the closing bracket k A left parenthesis is transferred , Because there are many left parentheses for each type k Status of , You can insert left parentheses into multiple j individual .
State calculation ：
①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
optimization ：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
so f[i][j]=f[i-1][j+1]+f[i][j-1]
result ：
be careful f[n][i] Not required 0 Can output , And output i As small as possible , Because the number of right parentheses is fixed , The left bracket should be added as little as possible , that i As small as possible .
initialization ：f[0][0]=1
<> code
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. }
Technology