• 大三第一周训练

    周三

    前段时间没有写日报，而是写专题了

    概率/期望dp专题_Alex Su (*^▽^*)的博客-CSDN博客

    博弈论专题_Alex Su (*^▽^*)的博客-CSDN博客

    现在觉得写日报才每天有收获感，有动力，于是又开始写日报

    P3802 小魔女帕琪（手推概率）

    这题就是手算，算出1~7触发的概率，再算一下2~8触发的概率，发现是一样的，然后就可以推出答案了

    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.  
    6. int main()
    7. {
    8.     double a[10], N;
    9.     _for(i, 1, 7) scanf("%lf", &a[i]), N += a[i];
    10.  
    11.     double ans = (N - 6) * 5040;
    12.     _for(i, 1, 7) ans *= a[i] / max(N - i + 1, 1.0); 
    13.     printf("%.3f\n", ans);
    14.    
    15. 	return 0;
    16. }

    P1850 [NOIP2016 提高组] 换教室（期望dp+floyed）

    这题的期望比较特殊，它是比较独立的，概率不需要连乘

    也就是说期望体现在两个相邻时间段之间的贡献。这个时候就不是那种比较经典的期望dp了。

    细节上，注意初始化和边界问题。

    floyed的时候注意自己自己到自己为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.  
    6. const int N = 2e3 + 10;
    7. const int M = 300 + 10;
    8. int n, m, v, e, c[N], d[N], g[M][M];
    9. double k[N], dp[N][N][2];
    10.  
    11. int main()
    12. {
    13.     scanf("%d%d%d%d", &n, &m, &v, &e);
    14.     _for(i, 1, n) scanf("%d", &c[i]);
    15.     _for(i, 1, n) scanf("%d", &d[i]);
    16.     _for(i, 1, n) scanf("%lf", &k[i]);
    17.     memset(g, 0x3f, sizeof g);
    18.     while(e--)
    19.     {
    20.         int a, b, w;
    21.         scanf("%d%d%d", &a, &b, &w);
    22.         g[a][b] = g[b][a] = min(g[a][b], w);
    23.     }
    24.  
    25.     _for(K, 1, v)
    26.         _for(i, 1, v)
    27.             _for(j, 1, v)
    28.                 g[i][j] = min(g[i][j], g[i][K] + g[K][j]);
    29.     _for(i, 1, v) g[i][i] = 0;    //写弗洛伊德时记得要加上自己和自己为0
    30.     
    31.     _for(i, 0, n)
    32.         _for(j, 0, m) 
    33.             dp[i][j][0] = dp[i][j][1] = 1e9;
    34.     dp[1][1][1] = dp[1][0][0] = 0;
    35.     _for(i, 2, n)
    36.         _for(j, 0, m)
    37.         {
    38.             int c1 = c[i - 1], c2 = c[i], d1 = d[i - 1], d2 = d[i];
    39.             dp[i][j][0] = min(dp[i - 1][j][0] + g[c1][c2], dp[i - 1][j][1]
    40.                         + k[i - 1] * g[d1][c2] + (1 - k[i - 1]) * g[c1][c2]);
    41.             if(j > 0)
    42.                 dp[i][j][1] = min(dp[i - 1][j - 1][0] + k[i] * g[c1][d2] + (1 - k[i]) * g[c1][c2],
    43.                          dp[i - 1][j - 1][1] + k[i - 1] * k[i] * g[d1][d2] + (1 - k[i - 1]) * k[i] * g[c1][d2] + 
    44.                         k[i - 1] * (1 - k[i]) * g[d1][c2] + (1 - k[i - 1]) * (1 - k[i]) * g[c1][c2]);
    45.         }
    46.     
    47.     double ans = 1e9;
    48.     _for(i, 0, m) ans = min(ans, min(dp[n][i][0], dp[n][i][1]));
    49.     printf("%.2f\n", ans);
    50.    
    51. 	return 0;
    52. }

    E. Vasya and Magic Matrix（dp+前缀和优化）

    令N=nm，从数据范围来看，是一个O(N)的算法

    直接dp显然要O(N^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.  
    6. typedef long long ll;
    7. const int N = 1e6 + 10;
    8. const int mod = 998244353;
    9. ll dp[N], xx[N], x[N], y[N], yy[N], f[N];
    10. struct node 
    11. { 
    12.     int val, x, y; 
    13. }ve[N];
    14. int n, m, r, c, cnt;
    15.  
    16. ll binpow(ll a, ll b)
    17. {
    18.     ll res = 1;
    19.     for(; b; b >>= 1)
    20.     {
    21.         if(b & 1) res = res * a % mod;
    22.         a = a * a % mod;
    23.     }
    24.     return res;
    25. }
    26.  
    27. ll inv(ll x) { return binpow(x, mod - 2); }
    28.  
    29. bool cmp(node a, node b)
    30. {
    31.     return a.val < b.val;
    32. }
    33.  
    34. int main()
    35. {
    36.     scanf("%d%d", &n, &m);
    37.     _for(i, 1, n)
    38.         _for(j, 1, m)
    39.         {
    40.             int x; scanf("%d", &x);
    41.             ve[++cnt] = {x, i, j};
    42.         }
    43.     scanf("%d%d", &r, &c);
    44.  
    45.     sort(ve + 1, ve + cnt + 1, cmp);
    46.     _for(i, 1, cnt)
    47.     {
    48.         x[i] = (x[i - 1] + ve[i].x) % mod; xx[i] = (xx[i - 1] + ve[i].x * ve[i].x) % mod;
    49.         y[i] = (y[i - 1] + ve[i].y) % mod; yy[i] = (yy[i - 1] + ve[i].y * ve[i].y) % mod;
    50.     }
    51.  
    52.     ll tot = 0;
    53.     _for(i, 1, cnt)
    54.     {
    55.         if(i == 1 || ve[i].val != ve[i - 1].val) tot = i - 1;
    56.         dp[i] = (tot * ve[i].x * ve[i].x % mod + xx[tot] - 2 * ve[i].x * x[tot] % mod + 
    57.                 tot * ve[i].y * ve[i].y % mod + yy[tot] - 2 * ve[i].y * y[tot] % mod + f[tot]) % mod;
    58.         dp[i] = dp[i] * inv(tot) % mod;
    59.         f[i] = (f[i - 1] + dp[i]) % mod;
    60.         if(ve[i].x == r && ve[i].y == c)
    61.         {
    62.             printf("%lld\n", dp[i]);
    63.             break;
    64.         }
    65.     }
    66.  
    67. 	return 0;
    68. }

    P1365 WJMZBMR打osu! / Easy（期望dp）

    这题比较考数学

    令Fi表示以i为结尾分数的期望。发现要用到以i-1为结尾的长度的期望，注意是它的期望。

    因此还要维护Li。

    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.  
    6. const int N = 3e5 + 10;
    7. long double F[N], L[N];
    8. char s[N];
    9. int n;
    10.  
    11. int main()
    12. {
    13.     scanf("%d%s", &n, s + 1);
    14.     _for(i, 1, n)
    15.     {
    16.         if(s[i] == 'o')
    17.         {
    18.             F[i] = F[i - 1] + 2 * L[i - 1] + 1;
    19.             L[i] = L[i - 1] + 1;
    20.         }
    21.         else if(s[i] == 'x')
    22.         {
    23.             F[i] = F[i - 1];
    24.             L[i] = 0;
    25.         }
    26.         else
    27.         {
    28.             F[i] = F[i - 1] + L[i - 1] + 0.5;
    29.             L[i] = (L[i - 1] + 1) / 2;
    30.         }
    31.     }
    32.     printf("%.4Lf\n", F[n]);
    33.     
    34. 	return 0;
    35. }

    P1654 OSU!（期望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.  
    6. const int N = 1e5 + 10;
    7. double F[N], L[N], T[N], p[N];
    8. int n;
    9.  
    10. int main()
    11. {
    12.     scanf("%d", &n);
    13.     _for(i, 1, n) scanf("%lf", &p[i]);
    14.  
    15.     _for(i, 1, n)
    16.     {
    17.         F[i] = (F[i - 1] + 3 * T[i - 1] + 3 * L[i - 1] + 1) * p[i] + F[i - 1] * (1 - p[i]);
    18.         L[i] = (L[i - 1] + 1) * p[i];
    19.         T[i] = (T[i - 1] + 2 * L[i - 1] + 1) * p[i];
    20.     }
    21.     printf("%.1f\n", F[n]);
    22.     
    23. 	return 0;
    24. }

    P6046 纯粹容器（期望+组合数学）

    这题和dp没啥关系，很数学的一道题

    显然对于一个容器，答案是\sum f_i(i-1) 

    fi表示第i轮被干掉的概率 但是这个不好求，转化为前缀和

    即f_i=p_i-p_{i-1}

    pi即前i轮被干掉的概率，这个好求，用古典概型求。

    分两种情况求，一种是被左边第一个大于它的干掉，一个是右边。

    把操作看作是在一条链上选择边，这样就有n-1条边去选，如果被左边的干掉，那么l~i的边一定要全选。

    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.  
    6. typedef long long ll;
    7. const int N = 50 + 10;
    8. const int mod = 998244353;
    9. ll c[N][N], p[N];
    10. int n, a[N];
    11.  
    12. ll binpow(ll a, ll b)
    13. {
    14.     ll res = 1;
    15.     for(; b; b >>= 1)
    16.     {
    17.         if(b & 1) res = res * a % mod;
    18.         a = a * a % mod;
    19.     }
    20.     return res;
    21. }
    22.  
    23. ll inv(ll x) { return binpow(x, mod - 2); }
    24.  
    25. int main()
    26. {
    27.     _for(i, 0, 50) c[i][0] = 1;
    28.     _for(i, 1, 50)
    29.         _for(j, 1, i)
    30.             c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    31.  
    32.     scanf("%d", &n);
    33.     _for(i, 1, n) scanf("%d", &a[i]);
    34.     _for(i, 1, n)
    35.     {
    36.         int l = -1, r = -1;
    37.         for(int j = i - 1; j >= 1; j--)
    38.             if(a[j] > a[i])
    39.             {
    40.                 l = j;
    41.                 break;
    42.             }
    43.         _for(j, i + 1, n)
    44.             if(a[j] > a[i])
    45.             {
    46.                 r = j;
    47.                 break;
    48.             }
    49.         if(l == -1 && r == -1)
    50.         {
    51.             printf("%d ", n - 1);
    52.             continue;
    53.         }
    54.         
    55.         _for(j, 1, n - 1)
    56.         {
    57.             ll pa = 0, pb = 0, pab = 0;
    58.             if(l != -1 && j >= (i - l)) pa = c[n - 1 - (i - l)][j - (i - l)] * inv(c[n - 1][j]) % mod;
    59.             if(r != -1 && j >= (r - i)) pb = c[n - 1 - (r - i)][j - (r - i)] * inv(c[n - 1][j]) % mod;
    60.             if(l != -1 && r != -1 && j >= (i - l) + (r - i)) pab = c[n - 1 - (r - i) - (i - l)][j - (r - i) - (i - l)] * inv(c[n - 1][j]) % mod;
    61.             p[j] = (pa + pb - pab + mod) % mod;
    62.         }
    63.         
    64.         ll ans = 0;
    65.         _for(j, 1, n - 1)
    66.             ans = (ans + (p[j] - p[j - 1]) * (j - 1)) % mod;
    67.         printf("%lld ", (ans + mod) % mod);
    68.     }
    69.  
    70. 	return 0;
    71. }

    周四

    CF280C Game on Tree（期望）

    看作一个长度为n的操作序列

    操作看作染黑，一个点一染黑，就把它的子孙都染黑

    那么一个点被操作的前提是它的祖先都在它后面

    因此概率为 1 / dep[u]

    操作次数的期望等于每个点操作的期望之和

    每个点操作的期望就等于概率

    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.  
    6. const int N = 1e5 + 10;
    7. vector<int> g[N];
    8. int d[N], n;
    9.  
    10. void dfs(int u, int fa)
    11. {
    12.     d[u] = d[fa] + 1;
    13.     for(int v: g[u])
    14.     {
    15.         if(v == fa) continue;
    16.         dfs(v, u);
    17.     }
    18. }
    19.  
    20. int main()
    21. {
    22.     scanf("%d", &n);
    23.     _for(i, 1, n - 1)
    24.     {
    25.         int u, v;
    26.         scanf("%d%d", &u, &v);
    27.         g[u].push_back(v);
    28.         g[v].push_back(u);
    29.     }
    30.     dfs(1, 0);
    31.  
    32.     double ans = 0;
    33.     _for(i, 1, n)
    34.         ans += 1.0 / d[i];
    35.     printf("%.10f\n", ans);
    36.  
    37. 	return 0;
    38. }

    A. Little Pony and Expected Maximum（期望）

    和前面一道题的思路类似

    E=\sum f_i*i fi表示最大值为i的概率

    等于某一值的概率不好算，要转化成小于等于某一值的概率，这样就可以用古典概型

    即f_i=p_i-p_{i-1}

    p_i=\left ( i/m \right )^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.  
    6. const int N = 1e5 + 10;
    7. long double p[N];
    8. int n, m;
    9.  
    10. long double binpow(long double a, int b)
    11. {
    12.     long double res = 1;
    13.     for(; b; b >>= 1)
    14.     {
    15.         if(b & 1) res *= a;
    16.         a *= a;
    17.     }
    18.     return res;
    19. }
    20.  
    21. int main()
    22. {
    23.     scanf("%d%d", &m, &n);
    24.     _for(i, 1, m) p[i] = binpow(1.0 * i / m, n);
    25.  
    26.     long double ans = 0;
    27.     _for(i, 1, m)
    28.         ans += (p[i] - p[i - 1]) * i;
    29.     printf("%.10Lf\n", ans);
    30.  
    31. 	return 0;
    32. }

    SP1026 FAVDICE - Favorite Dice(期望)

    之前做过差不多一样的题，用dp做的。还有一种纯数学的方法

    如果现在有k个图案，拿到一个新的图案的概率为(n - k) / n

    有一个结论是，概率为p的事件发生所需要的期望次数是1/p

    因此此时要n / (n / k)期望次数才能发生

    这样枚举k，就可得到期望发生了多少次才得到全部答案

    周五

    P4550 收集邮票（期望）

    做这种期望题除了用期望dp，即设一个dp状态表示已经……还需要多少的期望。这题同样可以用这种思路。

    但还一种思路就是考虑每一次对答案的贡献，对于这道题这种思路特别简单

    如果已经有了k种，再增加一种的概率是(n - k) / n

    那么此时需要购买的期望次数为n / (n - k)

    那么枚举k从0到n-1，考虑每一次对答案的贡献

    对于次数就是当前的期望次数n / (n - k)

    对于价格，就是期望次数的前缀和，也就是当前是第几次购买

    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.  
    6. const int N = 1e5 + 10;
    7. double p[N];
    8. int n;
    9.  
    10. int main()
    11. {
    12.     scanf("%d", &n);
    13.     _for(i, 0, n - 1) p[i] = 1.0 * n / (n - i);
    14.  
    15.     double ans = 0, sum = 0;
    16.     _for(i, 0, n - 1)
    17.     {
    18.         sum += p[i];
    19.         ans += p[i] * sum;
    20.     }
    21.     printf("%.2f\n", ans);
    22.  
    23. 	return 0;
    24. }

    CodeForces 547B(单调栈)

    考虑一个数的贡献，即当前数在多长的区间中可以作为最小值。这个可以用单调栈O(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.  
    6. const int N = 2e5 + 10;
    7. int l[N], r[N], s[N], a[N], top, n;
    8. int t[N], ans[N];
    9.  
    10. int main()
    11. {
    12.     scanf("%d", &n);
    13.     _for(i, 1, n) scanf("%d", &a[i]);
    14.  
    15.     for(int i = n; i >= 1; i--)
    16.     {
    17.         while(top && a[s[top]] >= a[i]) top--;
    18.         r[i] = top ? s[top] : n + 1;
    19.         s[++top] = i;
    20.     }
    21.     top = 0;
    22.     _for(i, 1, n)
    23.     {
    24.         while(top && a[s[top]] >= a[i]) top--;
    25.         l[i] = top ? s[top] : 0;
    26.         s[++top] = i;
    27.     }
    28.  
    29.     _for(i, 1, n)
    30.     {
    31.         int len = r[i] - l[i] - 1;
    32.         t[len] = max(t[len], a[i]);
    33.     }
    34.     ans[n] = t[n];
    35.     for(int i = n - 1; i >= 1; i--)
    36.         ans[i] = max(ans[i + 1], t[i]);
    37.     _for(i, 1, n) printf("%d ", ans[i]);
    38.  
    39. 	return 0;
    40. }

    CodeForces 1540A（思维）

    关键是发现点的顺序是不影响的，所以直接排序，然后贪心即可

    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.  
    6. typedef long long ll; 
    7. const int N = 1e5 + 10;
    8. int a[N], n;
    9.  
    10. int main()
    11. {
    12.     int T; scanf("%d", &T);
    13.     while(T--)
    14.     {
    15.         scanf("%d", &n);
    16.         _for(i, 1, n) scanf("%d", &a[i]);
    17.         sort(a + 1, a + n + 1);
    18.  
    19.         ll ans = 0, sum = 0;
    20.         _for(i, 2, n) ans += a[i] - a[i - 1];
    21.  
    22.         sum = a[n];
    23.         for(int i = n - 1; i >= 1; i--)
    24.         {
    25.             ans += 1LL * (n - i) * a[i] - sum;
    26.             sum += a[i];
    27.         }
    28.         printf("%lld\n", ans);
    29.     }
    30.  
    31. 	return 0;
    32. }

    AtCoder - agc006_b （思维）

    中间放x-1 x x+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.  
    6. const int N = 2e5 + 10;
    7. int ans[N];
    8.  
    9. int main()
    10. {
    11. 	int n, x;
    12. 	scanf("%d%d", &n, &x);
    13. 	if(x == 1 || x == 2 * n - 1) 
    14. 	{
    15. 		puts("No");
    16. 		return 0;
    17. 	}
    18. 	
    19. 	ans[n - 1] = x - 1;
    20. 	ans[n] = x;
    21. 	ans[n + 1] = x + 1;
    22. 	
    23. 	int now = 0;
    24. 	_for(i, 1, 2 * n - 1)
    25. 	{
    26. 		if(ans[i]) continue;
    27. 		now++;
    28. 		if(now == x - 1) now = x + 2;
    29. 		ans[i] = now;
    30. 	}
    31. 	
    32. 	puts("Yes");
    33. 	_for(i, 1, 2 * n - 1) printf("%d\n", ans[i]);   
    34. 	
    35. 	return 0;
    36. }

    周六

    hdu 2460（tarjan+lca）

    首先tarjan可以得到一颗生成树，割边一定是生成树上的边，因为这道题只考虑割边，所以得到割边后，非生成树上的边就不用考虑了。

    每次加边显然会把路径上的割边去掉，直接暴力的话计算一下是1e8，是可以过的，因此直接暴力就行。怎么保存割边呢，用k[u]表示u到u的父亲的这条边是否是割边

    1. #include<cstdio>
    2. #include<vector>
    3. #include<map>
    4. #include<algorithm>
    5. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    6. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    7. using namespace std;
    8.  
    9. const int N = 1e5 + 10;
    10. int dfn[N], low[N], k[N], d[N], f[N], cnt, n, m, sum;
    11. vector<int> g[N];
    12.  
    13. void dfs(int u, int fa)
    14. {
    15.     d[u] = d[fa] + 1;
    16.     f[u] = fa;
    17.     dfn[u] = low[u] = ++cnt;
    18.     bool vis = false;
    19.     for(int v: g[u])
    20.     {
    21.         if(!dfn[v])
    22.         {
    23.             dfs(v, u);
    24.             low[u] = min(low[u], low[v]);
    25.             if(low[v] > dfn[u]) k[v] = 1, sum++;
    26.         }
    27.         else 
    28.         {
    29.             if(v == fa && !vis) vis = true;
    30.             else low[u] = min(low[u], dfn[v]);
    31.         }
    32.     }
    33. }
    34.  
    35. int main()
    36. {
    37.     int kase = 0;
    38.     while(scanf("%d%d", &n, &m))
    39.     {
    40.         if(n == 0 && m == 0) break;
    41.         printf("Case %d:\n", ++kase);
    42.  
    43.         _for(i, 1, n) g[i].clear(), dfn[i] = low[i] = k[i] = f[i] = 0;
    44.         cnt = sum = 0;
    45.  
    46.         while(m--)
    47.         {
    48.             int u, v;
    49.             scanf("%d%d", &u, &v);
    50.             g[u].push_back(v);
    51.             g[v].push_back(u);
    52.         }
    53.         dfs(1, 0);
    54.  
    55.       //  printf("sum: %d\n", sum);
    56.        
    57.         int q; scanf("%d", &q);
    58.         while(q--)
    59.         {
    60.             int u, v;
    61.             scanf("%d%d", &u, &v);
    62.             if(d[u] < d[v]) swap(u, v);
    63.             while(d[u] > d[v])
    64.             {
    65.                 if(k[u]) k[u] = 0, sum--;
    66.                 u = f[u];
    67.             }
    68.             while(u != v)
    69.             {
    70.                 if(k[u]) k[u] = 0, sum--;
    71.                 u = f[u];
    72.                 if(k[v]) k[v] = 0, sum--;
    73.                 v = f[v];
    74.             }
    75.             printf("%d\n", sum);
    76.         }
    77.         puts("");
    78.     }
    79.  
    80. 	return 0;
    81. }

    hdu 7158（同余）

    可以得到M是pq-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.  
    6. typedef long long ll;
    7. ll p, q, e;
    8.  
    9. bool check(ll x)
    10. {
    11.     if(x <= max(p, q)) return false;
    12.     for(int i = 2; 1LL * i * i <= x; i++)
    13.         if(x % i == 0)
    14.             return false;
    15.     return true;
    16. }
    17.  
    18. int main()
    19. {
    20.     int T; scanf("%d", &T);
    21.     while(T--)
    22.     {
    23.         scanf("%lld%lld%lld", &p, &q, &e);
    24.         ll t = p * q - 1, m = -1;
    25.         for(int i = 1; 1LL * i * i <= t; i++)
    26.             if(t % i == 0)
    27.             {
    28.                 if(check(i)) 
    29.                 {
    30.                     m = i;
    31.                     break;
    32.                 }
    33.                 if(check(t / i))
    34.                 {
    35.                     m = t / i;
    36.                     break;
    37.                 }
    38.             }
    39.         if(m == -1) puts("shuanQ");
    40.         else printf("%lld\n", e * q % m);
    41.     }
    42.    
    43. 	return 0;
    44. }

    周日

    hdu5222（拓扑排序+并查集）

    我一开始的思路不是正解的思路，是直接dfs，但是不知道为啥mle了，算一下空间是没超的，之前有一道hdu的题也是这样……

    正解是先考虑无向边，用并查集，如果没有成环的话，那么接下来就缩点，就是一个联通分量缩成一个点，然后图就是有向图了，那么由向图判断有无环就用拓扑排序即可

    1. #include<cstdio>
    2. #include<vector>
    3. #include<algorithm>
    4. #include<map>
    5. #include<queue>
    6. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    7. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    8. using namespace std;
    9. #pragma comment(linker, "/STACK:102400000,102400000") 
    10.  
    11. const int N = 1e6 + 10;
    12. int f[N], d[N], n, m1, m2, ans;
    13. vector<int> g[N];
    14.  
    15. int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
    16.  
    17. int main()
    18. {
    19.     int T; scanf("%d", &T);
    20.     while(T--)
    21.     {
    22.         scanf("%d%d%d", &n, &m1, &m2);
    23.         _for(i, 1, n) f[i] = i, d[i] = 0, g[i].clear();
    24.         ans = 0;
    25.  
    26.         while(m1--)
    27.         {
    28.             int u, v;
    29.             scanf("%d%d", &u, &v);
    30.             int fu = find(u), fv = find(v);
    31.             if(fu == fv) ans = 1;
    32.             else f[fu] = fv;
    33.         }
    34.         while(m2--)
    35.         {
    36.             int u, v;
    37.             scanf("%d%d", &u, &v);
    38.             u = find(u); v = find(v);
    39.             g[u].push_back(v);
    40.             d[v]++;
    41.         }
    42.  
    43.         queue<int> q;
    44.         vector<int> topo;
    45.         _for(i, 1, n)
    46.             if(!d[i])
    47.                 q.push(i);
    48.         while(!q.empty())
    49.         {
    50.             int u = q.front(); q.pop();
    51.             topo.push_back(u);
    52.             for(int v: g[u])
    53.                 if(--d[v] == 0)
    54.                     q.push(v);
    55.         }
    56.  
    57.         if(topo.size() != n) ans = 1;
    58.         puts(ans ? "YES" : "NO");
    59.     }
    60.  
    61. 	return 0;
    62. }

    AtCoder - arc134_c（插板法）

    首先非1的球随便放，每种是独立的，它放就是n个球放到k个盒子中，盒子不相同，可以有空，这就是典型的插板法了，即C(n + k - 1, k - 1) 

    放完之后，先在每个盒子中，有多少球就放多少1，然后即剩下的1为n，那么就是将n个球放到k个盒子中，盒子不相同，每个至少有一个，即C(n - 1, k - 1)

    无解的话，组合数那里n

    关于组合数的计算，由于C(n, m)的m很小，所以可以直接暴力计算。

    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.  
    6. typedef long long ll;
    7. const int mod = 998244353;
    8. const int N = 1e5 + 10;
    9. ll f[N], a[N];
    10. int n, k;
    11.  
    12. ll binpow(ll a, ll b)
    13. {
    14.     ll res = 1;
    15.     for(; b; b >>= 1)
    16.     {
    17.         if(b & 1) res = res * a % mod;
    18.         a = a * a % mod;
    19.     }
    20.     return res;
    21. }
    22.  
    23. ll inv(ll x) { return binpow(x, mod - 2); }
    24.  
    25. ll C(ll n, ll m) 
    26. { 
    27.     if(n < m) return 0;
    28.     ll res = 1;
    29.     _for(i, n - m + 1, n) res = res * i % mod;
    30.     return res * inv(f[m]) % mod;
    31. }
    32.  
    33. int main()
    34. {
    35.     f[0] = 1;
    36.     _for(i, 1, 200) f[i] = f[i - 1] * i % mod;
    37.  
    38.     scanf("%d%d", &n, &k);
    39.     _for(i, 1, n) scanf("%lld", &a[i]);
    40.  
    41.     ll ans = 1, sum = 0;
    42.     _for(i, 2, n)
    43.     {
    44.         ans = ans * C(a[i] + k - 1, k - 1) % mod;
    45.         sum += a[i];
    46.     }
    47.     ans = ans * C(a[1] - sum - 1, k - 1) % mod;
    48.     printf("%lld\n", ans);
    49.  
    50. 	return 0;
    51. }

    D. Round Subset（背包）

    这题的难点是想到把一个作为体积，一个作为价值跑背包

    还是做的题太少

    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.  
    6. typedef long long ll;
    7. const int N = 200 + 10;
    8. int f[N * 30][N], w[N], v[N], sum, n, K;
    9.  
    10. int main()
    11. {
    12.     scanf("%d%d", &n, &K);
    13.     _for(i, 1, n)
    14.     {
    15.         ll x; scanf("%lld", &x);
    16.         while(x % 5 == 0)
    17.         {
    18.             x /= 5;
    19.             w[i]++;
    20.         }
    21.         while(x % 2 == 0)
    22.         {
    23.             x /= 2;
    24.             v[i]++;
    25.         }
    26.         sum += w[i];
    27.     }
    28.  
    29.     //注意不合法的状态初始化为最小值
    30.     memset(f, -0x3f, sizeof f);
    31.     f[0][0] = 0;
    32.     _for(i, 1, n)
    33.         for(int j = sum; j >= w[i]; j--)
    34.             for(int k = K; k >= 1; k--)
    35.                 f[j][k] = max(f[j][k], f[j - w[i]][k - 1] + v[i]);
    36.     
    37.     int ans = 0;
    38.     _for(i, 0, sum)
    39.         ans = max(ans, min(f[i][K], i));
    40.     printf("%d\n", ans);
    41.  
    42. 	return 0;
    43. }

  • 相关阅读:
    力扣（LeetCode）算法_C++——同构字符串
    如何系统 如何进行SQL监控-执行SQL分析打印
    面试（乐观锁和悲观锁）
    常用元器件使用方法35：SPI Flash芯片W25Q128JVSIQ
    一分钟学习数据安全—自主管理身份SSI可验证凭证
    vue的v-for中循环修改变量（this.xxx）的给子组件传值覆盖重复的问题
    IMU标定
    【学习笔记】CF708E Student‘s Camp
    刷题2个月，终于挺进梦寐以求的大厂，数据结构和算法太TM重要了
    损失函数（Loss Function）与代价函数（Cost Function）、目标函数（Objective Function）区别
  • 原文地址：https://blog.csdn.net/qq_34416123/article/details/126617351