• 大三第十二周学习笔记


    周三

    M. Rock-Paper-Scissors Pyramid(思维)

    斜着看,每次复制一遍加一个

    用一个栈维护,如果当前可以打败栈顶的,就出栈,如果相同,入不入栈都可以,如果打不过也要入栈,因为它可以阻挡后面的。

    最后栈底就是留下来的。

    1. #include<bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5. const int N = 1e6 + 10;
    6. char s[N];
    7. int top;
    8. int main()
    9. {
    10. map<char, int> mp;
    11. mp['S'] = 0; mp['P'] = 1; mp['R'] = 2;
    12. int T; scanf("%d", &T);
    13. while(T--)
    14. {
    15. string str; cin >> str;
    16. int len = str.size();
    17. top = 0;
    18. rep(i, 0, len)
    19. {
    20. while(top && (mp[str[i]] + 1) % 3 == mp[s[top]]) top--;
    21. s[++top] = str[i];
    22. }
    23. printf("%c\n", s[1]);
    24. }
    25. return 0;
    26. }

    P3396 哈希冲突(根号分治)

    用根号为分界线,一部分暴力,一部分预处理

    对于这道题,模数小于等于根号n时,直接预处理

    模数大于等于根号n时,直接暴力

    1. #include<bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5. const int N = 1.5e5 + 10;
    6. const int M = 400;
    7. int s[M][M], a[N], n, m;
    8. int main()
    9. {
    10. scanf("%d%d", &n, &m);
    11. _for(i, 1, n) scanf("%d", &a[i]);
    12. int block = sqrt(n);
    13. _for(i, 1, n)
    14. _for(j, 1, block)
    15. s[j][i % j] += a[i];
    16. while(m--)
    17. {
    18. char op[10]; int x, y;
    19. scanf("%s%d%d", op, &x, &y);
    20. if(op[0] == 'A')
    21. {
    22. if(x <= block) printf("%d\n", s[x][y]);
    23. else
    24. {
    25. int res = 0;
    26. for(int i = y; i <= n; i += x) res += a[i];
    27. printf("%d\n", res);
    28. }
    29. }
    30. else
    31. {
    32. _for(j, 1, block) s[j][x % j] += y - a[x];
    33. a[x] = y;
    34. }
    35. }
    36. return 0;
    37. }

    Array Queries(根号分治)

    1e5左右的数据范围要很敏感,很可能是n根号n的算法

    这题而言,每次p最少会增加k

    那么当k大于根号n时,最多跳根号n次

    当k小于根号n时,可以用dp直接求出,倒着求一遍

    1. #include<bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5. const int N = 1e5 + 10;
    6. const int M = 350;
    7. int dp[N][M], a[N], n, m;
    8. int main()
    9. {
    10. scanf("%d", &n);
    11. _for(i, 1, n) scanf("%d", &a[i]);
    12. int block = sqrt(n);
    13. for(int i = n; i >= 1; i--)
    14. _for(k, 1, block)
    15. {
    16. int j = i + a[i] + k;
    17. if(j > n) dp[i][k] = 1;
    18. else dp[i][k] = dp[j][k] + 1;
    19. }
    20. scanf("%d", &m);
    21. while(m--)
    22. {
    23. int p, k;
    24. scanf("%d%d", &p, &k);
    25. if(k <= block) printf("%d\n", dp[p][k]);
    26. else
    27. {
    28. int res = 0;
    29. while(p <= n)
    30. {
    31. p = p + a[p] + k;
    32. res++;
    33. }
    34. printf("%d\n", res);
    35. }
    36. }
    37. return 0;
    38. }

    周四

    A. Ban or Pick, What's the Trick(记忆化搜索)

    注意要逆推,当前的选择肯定根据选择之后的结果是什么

    逆推的话,记忆化搜索比写循环要方便

    注意空间要开两倍

    1. #include<bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5. typedef long long ll;
    6. const int N = 1e5 + 10;
    7. int a[N], b[N], n, k;
    8. ll dp[N << 1][15][15]; //交之前一定要检查一下空间开够了没有
    9. ll dfs(int round, int numa, int numb)
    10. {
    11. if(round == 2 * n + 1) return 0;
    12. if(dp[round][numa][numb] != -1) return dp[round][numa][numb];
    13. int ta = round / 2 - numb + numa;
    14. int tb = (round + 1) / 2 - numa + numb;
    15. if(round % 2 == 1)
    16. {
    17. ll res = dfs(round + 1, numa, numb);
    18. if(ta + 1 <= n && numa + 1 <= k) res = max(res, dfs(round + 1, numa + 1, numb) + a[ta + 1]);
    19. return dp[round][numa][numb] = res;
    20. }
    21. else
    22. {
    23. ll res = dfs(round + 1, numa, numb);
    24. if(tb + 1 <= n && numb + 1 <= k) res = min(res, dfs(round + 1, numa, numb + 1) - b[tb + 1]);
    25. return dp[round][numa][numb] = res;
    26. }
    27. }
    28. int main()
    29. {
    30. scanf("%d%d", &n, &k);
    31. _for(i, 1, n) scanf("%d", &a[i]);
    32. _for(i, 1, n) scanf("%d", &b[i]);
    33. sort(a + 1, a + n + 1, greater<int>());
    34. sort(b + 1, b + n + 1, greater<int>());
    35. memset(dp, -1, sizeof dp);
    36. printf("%lld\n", dfs(1, 0, 0));
    37. return 0;
    38. }

    周五

    G. Matryoshka Doll(dp+组合数学)

    很容易想到dp[i][j]表示前i个物品分成j组的方案数

    当前物品要不独立成一组,要不和之前的一组

    设p为最大的下标使得ai - ap >= r

    那么显然ai只能和1到p分为一组

    那么关键是1到p有多少组可以让ai加进去呢

    注意到p+1到i-1这一部分,两两是不可能为一组的,且ai不能和它们一组

    那么只剩下j - (i - p - 1)这么多组了,ai可以加入其中一个

    1. #include<bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5. typedef long long ll;
    6. const int N = 5000 + 10;
    7. const int mod = 998244353;
    8. int L[N], a[N], n, k, R;
    9. ll dp[N][N];
    10. int main()
    11. {
    12. int T; scanf("%d", &T);
    13. while(T--)
    14. {
    15. scanf("%d%d%d", &n, &k, &R);
    16. _for(i, 1, n) scanf("%d", &a[i]);
    17. int l = n;
    18. for(int r = n; r >= 1; r--)
    19. {
    20. while(l - 1 >= 0 && a[r] - a[l] < R) l--;
    21. L[r] = l;
    22. }
    23. dp[0][0] = 1;
    24. _for(i, 1, n)
    25. _for(j, 1, k)
    26. {
    27. dp[i][j] = dp[i - 1][j - 1];
    28. int t = i - L[i] - 1;
    29. if(j - t > 0) dp[i][j] = (dp[i][j] + dp[i - 1][j] * (j - t) % mod) % mod;
    30. }
    31. printf("%lld\n", dp[n][k]);
    32. }
    33. return 0;
    34. }

    J. Sum Plus Product(找规律)

    那a,b,c三个数试一下,是abc+ac+bc+ab+a+b+c

    每一项就是abc这三个取字母或者取1

    可以写成(a + 1)(b + 1)(c + 1) - 1

    那么答案就是加1乘起来然后减1

    1. #include<bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5. typedef long long ll;
    6. const int mod = 998244353;
    7. int main()
    8. {
    9. int T; scanf("%d", &T);
    10. while(T--)
    11. {
    12. int n; scanf("%d", &n);
    13. ll ans = 1;
    14. _for(i, 1, n)
    15. {
    16. int x; scanf("%d", &x);
    17. ans = ans * (x + 1) % mod;
    18. }
    19. ans--;
    20. if(ans < 0) ans += mod;
    21. printf("%lld\n", ans);
    22. }
    23. return 0;
    24. }

    Shortest Path in GCD Graph(容斥)

    找和u和v互质的数有多少个,那么将两个数质因数分解,然后容斥一下即可

    主要要特判gcd=2的情况

    1. #include<bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5. typedef long long ll;
    6. const int N = 1e7 + 10;
    7. int vis[N], a[N], n, q, ans;
    8. vector<int> p, ve;
    9. void init()
    10. {
    11. vis[0] = vis[1] = 1;
    12. _for(i, 2, 1e7)
    13. {
    14. if(!vis[i]) a[i] = i, p.push_back(i); //取最小质因子的时候不要忘了质数为质数本身
    15. for(int x: p)
    16. {
    17. if(x * i > 1e7) break;
    18. vis[x * i] = 1;
    19. a[x * i] = x;
    20. if(i % x == 0) break;
    21. }
    22. }
    23. }
    24. vector<int> deal(int x)
    25. {
    26. vector<int> res;
    27. while(x > 1)
    28. {
    29. int t = a[x];
    30. res.push_back(t);
    31. while(x % t == 0) x /= t;
    32. }
    33. return res;
    34. }
    35. void dfs(int i, int cnt, ll cur)
    36. {
    37. if(i == ve.size())
    38. {
    39. if(cur > 1)
    40. {
    41. if(cnt % 2 == 1) ans += n / cur;
    42. else ans -= n / cur;
    43. }
    44. return;
    45. }
    46. dfs(i + 1, cnt + 1, cur * ve[i]);
    47. dfs(i + 1, cnt, cur);
    48. }
    49. int gcd(int a, int b) { return !b ? a: gcd(b, a % b); }
    50. int main()
    51. {
    52. init();
    53. scanf("%d%d", &n, &q);
    54. while(q--)
    55. {
    56. int u, v;
    57. scanf("%d%d", &u, &v);
    58. vector<int> pu = deal(u), pv = deal(v);
    59. ve = pu;
    60. for(int x: pv) ve.push_back(x);
    61. sort(ve.begin(), ve.end());
    62. ve.erase(unique(ve.begin(), ve.end()), ve.end());
    63. if(ve.size() == pu.size() + pv.size())
    64. {
    65. puts("1 1");
    66. continue;
    67. }
    68. ans = 0;
    69. dfs(1, 1, ve[0]);
    70. dfs(1, 0, 1);
    71. printf("%d %d\n", 2, n - ans + (gcd(u, v) == 2));
    72. }
    73. return 0;
    74. }

    Arithmetic Subsequence(奇偶分治)

    这题妙啊,奇数偶数是突破口

    奇数全部放左边,偶数全部放右边

    那么三元组一定全在左边或权在右边

    然后考虑递归处理,比如现在全是奇数,那么相减后最低位都为0,那么就没用了,所有数直接右移一位,这时又产生了奇数和偶数。

    考虑二进制位,从最低位开始,为1的放左边为0放右边,然后再看倒数第二位……

    那么就按照这个策略排序一遍,就一定不会有等差数列

    特判一下一个数出现三次以上

    1. #include<bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5. const int N = 5e3 + 10;
    6. unordered_map<int, int> mp;
    7. int a[N], n;
    8. bool cmp(int x, int y)
    9. {
    10. _for(j, 0, 30)
    11. {
    12. int tx = (x >> j) & 1, ty = (y >> j) & 1;
    13. if(tx != ty) return tx > ty;
    14. }
    15. return true; //注意可能有相等的情况 要return true
    16. }
    17. int main()
    18. {
    19. int T; scanf("%d", &T);
    20. while(T--)
    21. {
    22. mp.clear();
    23. scanf("%d", &n);
    24. int flag = 1;
    25. _for(i, 1, n)
    26. {
    27. scanf("%d", &a[i]);
    28. if(++mp[a[i]] >= 3) flag = 0;
    29. }
    30. if(!flag)
    31. {
    32. puts("NO");
    33. continue;
    34. }
    35. puts("YES");
    36. sort(a + 1, a + n + 1, cmp);
    37. _for(i, 1, n) printf("%d ", a[i]);
    38. puts("");
    39. }
    40. return 0;
    41. }

  • 相关阅读:
    UE4_常见动画节点学习_Two Bone IK双骨骼IK
    服务器产生丢包的原因有哪些
    SpringBoot-快速搭建并快速验证是否可用
    Echarts5.* 关系图谱(relation graph)添加节点拖拽、点击节点高亮效果
    一次带你掌握MVC和MVVM的区别
    JWT 使用入门(三)请求流程
    LLMs 应用开发框架 Semantic Kernel 和 LangChain 比较
    【云原生 | Docker 基础篇】07、本地镜像发布到私有库
    循环神经网络(Recurrent Neural Network)
    关卡一: jQuery编程
  • 原文地址:https://blog.csdn.net/qq_34416123/article/details/128007504