经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
【题解】Educational Codeforces Round 142(CF1792)
来源:cnblogs  作者:linyihdfj  时间:2023/9/11 9:25:59  对本文有异议

没有手速,再加上被 E 卡了,废掉了。

A.GamingForces

题目描述:

Monocarp 正在玩电脑游戏。他打算杀死 \(n\) 个怪兽,第 \(i\) 个的血量为 \(h_i\)

Monocarp 的角色有两个魔法咒语如下,都可以以任意顺序用任意次(可以不用),每次使用相当于一次操作。

  1. 选择两个怪兽并扣一滴血。

  2. 选择一个怪兽并且直接杀死。

当一个怪兽血量为 \(0\) 时,他死了

求杀死所有怪兽的最少操作次数。

题目分析:

只有两个怪兽同为 \(1\) 点血,这个时候我们通过 \(1\) 操作直接把它们弄死才会比直接通过操作 \(2\) 直接弄死更优。

所以判一下这个就好了。

代码:

点击查看代码
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 10005;
  4. int a[N];
  5. int main(){
  6. int T;scanf("%d",&T);
  7. while(T--){
  8. int n;scanf("%d",&n);
  9. for(int i=1; i<=n; i++) scanf("%d",&a[i]);
  10. int cnt = 0;
  11. for(int i=1; i<=n; i++){
  12. if(a[i] == 1) ++cnt;
  13. }
  14. printf("%d\n",n - cnt / 2);
  15. }
  16. return 0;
  17. }

B.Stand-up Comedian

题目描述:

Eve 是个单口相声新手。她的第一场表演聚集了总计 \(2\) 个观众:Alice 和 Bob。

Eve 准备了 \(a_1+a_2+a_3+a_4\) 个相声表演节目。\(a_i\) 表示第 \(i\) 类相声的数目,每类的的特征如下:

  1. Alice 和 Bob 都喜欢这类相声。

  2. Alice 喜欢,Bob 不喜欢。

  3. Bob 喜欢,Alice 不喜欢。

  4. Alice 和 Bob 都不喜欢这类相声。

一开始,两位观众的心情都为 \(0\)

当一位观众听到他喜欢的相声表演时心情会\(1\),当听到的是自己不喜欢的相声时,心情减 1

当某位观众心情严格小于 \(0\) 时,这位观众会离场。只要有一位这样的观众离场,Eve 会特别伤心并且结束整个表演。若演完了所有节目,也会结束表演。

求某种安排表演顺序的方式,使得 Eve 在结束表演前能表演的节目最多。输出最多能表演的节目数。

译者注:若演完某个节目有观众退场,这个节目也算在总数之中

\(0 \le a_1,a_2,a_3,a_4 \le 10^8\)

题目分析:

好像是个大细节题,但是我一遍过就很爽[狂笑]

考虑最优的一个操作顺序肯定是:\(1 \to 2,3 \to 4\)

关键是中间 \(2,3\) 造成的贡献比较难算,可以显然发现我们先操作一次 \(2\) 后操作一次 \(3\) 它们的代价就抵消了,而且会多出两次节目,但是要注意如果 \(1\) 操作数量为 \(0\) 就不能相互抵消了。

所以就按照:操作 \(1\)\(2,3\) 抵消、操作 \(2,3\)、操作 \(4\),这样的顺序模拟一下即可。

代码:

点击查看代码
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int cnt[10];
  5. signed main(){
  6. // freopen("in.txt","r",stdin);
  7. // freopen("out.txt","w",stdout);
  8. int T;scanf("%lld",&T);
  9. while(T--){
  10. for(int i=1; i<=4; i++) scanf("%lld",&cnt[i]);
  11. int ans = 0;
  12. int a = cnt[1],b = cnt[1];ans += cnt[1];
  13. if(a == 0){
  14. if(cnt[2] + cnt[3] + cnt[4] > 0) printf("1\n");
  15. else printf("0\n");
  16. continue;
  17. }
  18. int tmp = min(cnt[2],cnt[3]);ans += 2 * tmp;
  19. cnt[2] -= tmp,cnt[3] -= tmp;
  20. if(cnt[2] > 0){
  21. tmp = min(cnt[2],b+1);ans += tmp;
  22. a += tmp,b -= tmp;
  23. }
  24. if(cnt[3] > 0){
  25. tmp = min(cnt[3],a+1);ans += tmp;
  26. a -= tmp,b += tmp;
  27. }
  28. if(a >= 0 && b >= 0){
  29. ans += min(min(a+1,b+1),cnt[4]);
  30. }
  31. printf("%lld\n",ans);
  32. }
  33. return 0;
  34. }

C.Min Max Sort

题目描述:

对于一个排列,定义一次操作为:在排列中任选两个数字,将它们中的最大值插入至队尾,最小值插入至队首。

现在给定多个排列,问每个排列最少各需多少次操作才能变得严格递增。
\(1 \le n\le 2\times 10^5\)

题目分析:

如果我们要进行操作,那么最后 \(1\) 操作必然是 \(1,n\),然后倒推一下就会发现倒数第 \(2\) 次操作必然是 \(2,n-1\),然后就可以发现倒数第 \(i\) 次操作必然是 \(i,n-i+1\)

所以假设我们通过 \(k\) 次操作可以使排列严格递增,也就是说值在 \([k+1,n-k]\) 是不用我们管的了,已经符合条件了,将两头的 \(k\) 个进行排完序就结束了。

这个“不用管”用形式化的语言说其实就是,设 \(pos_i\) 表示数 \(i\) 出现的位置,则 \(pos_{k+1} < pos_{k+2} < \cdots < pos_{n-k}\)

所以可以直接一个个枚举 \(k\) 判断是否合法即可,也就是将 \(k\)\(\lfloor \frac{n}{2} \rfloor\) 开始依次减 \(1\),然后判断条件是否满足。

代码:

点击查看代码
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 2e5+5;
  4. int a[N],p[N];
  5. int main(){
  6. int T;scanf("%d",&T);
  7. while(T--){
  8. int n;scanf("%d",&n);
  9. for(int i=1; i<=n; i++) scanf("%d",&a[i]),p[a[i]] = i;
  10. int k = n / 2;
  11. while(k && p[k] < p[k+1] && p[n-k] < p[n-k+1]) --k;
  12. printf("%d\n",k);
  13. }
  14. return 0;
  15. }

D.Fixed Prefix Permutations

题目描述:

对于一个排列 \(p\),定义其美丽度 \(k\)

  • \(p_1=1,p_2=2,\cdots,p_k=k,p_{k+1} \neq k+1\)

\(p,q\) 均为长度为 \(n\) 的排列,定义排列的运算 \(p \cdot q\) 为:

  • \(p \cdot q = r\)\(p,q,r\) 均为长度为 \(n\) 的排列
  • \(r_j = q_{p_j}\)

现在给出 \(n\) 个长度为 \(m\) 的排列,对于每一个 \(a_i\),求 \(a_i \cdot a_j(1 \le j \le n)\) 美丽值最大为多少,允许有 \(i=j\)

多测,\(T \le 10^4\)\(\sum n \le 5 \times 10^4\)\(m \le 10\)

题目分析:

考虑如果就是给定了两个排列 \(p,q\) 怎么算它的美丽值。

要让 \(i\) 经过两个排列的置换后依旧是在 \(i\) 的位置,其实就是说设 \(pos_i\) 表示 \(i\)\(q\) 中的位置,则 \(p_i = pos_i\),可以将置换理解为走路这种东西然后就很好理解了。
所以其实就是求出 \(pos\) 之后两者的 \(lcp\)

那么这个题就很好解决了,可以直接对于每一个排列都求出 \(pos\),然后插入到 trie 树里,计算答案就是枚举每一个排列然后让它在字典树上走即可。

(我竟然一开始用了 bitset 维护这个过程,差点就过了)

代码:

点击查看代码
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 5e4+5;
  4. int n,m,a[N][11],tot = 1,pos[N][11],ch[100 * N][11];
  5. void insert(int x){
  6. int now = 1;
  7. for(int i=1; i<=m; i++){
  8. int to = pos[x][i];
  9. if(!ch[now][to]) ch[now][to] = ++tot;
  10. now = ch[now][to];
  11. }
  12. }
  13. int find(int x){
  14. int now = 1;
  15. int ans = 0;
  16. for(int i=1; i<=m; i++){
  17. if(ch[now][a[x][i]]){
  18. ++ans,now = ch[now][a[x][i]];
  19. }
  20. else break;
  21. }
  22. return ans;
  23. }
  24. int main(){
  25. // freopen("in.txt","r",stdin);
  26. // freopen("out.txt","w",stdout);
  27. int T;scanf("%d",&T);
  28. while(T--){
  29. scanf("%d%d",&n,&m);
  30. for(int i=1; i<=n; i++){
  31. for(int j=1; j<=m; j++){
  32. scanf("%d",&a[i][j]);
  33. pos[i][a[i][j]] = j;
  34. }
  35. insert(i);
  36. }
  37. for(int i=1; i<=n; i++) printf("%d ",find(i));
  38. printf("\n");
  39. for(int i=1; i<=tot; i++){
  40. for(int j=1; j<=10; j++){
  41. ch[i][j] = 0;
  42. }
  43. }
  44. tot = 1;
  45. }
  46. return 0;
  47. }

E.Divisors and Table

题目描述:

给定一张 \(n \times n\) 的表格和一个正整数 \(m = m_1 \times m_2\),表格第 \(i\) 行第 \(j\) 列的数 \(a_{i, j} = i \times j\)

现在需要你求出 \(m\) 的每个因子 \(d\) 是否在表格中出现,若出现,则求出其出现在表格中的最小行号。

\(1 \le n, m_1, m_2 \le 10^9\)

题目分析:

(一种乱搞做法)

\(10^{18}\) 以内的数,因子个数最多有大约 \(10^5\) 个,所以显然可以将 \(m\) 的的所有因子都拿出来然后挨个判断。

要求所有的因子其实就是要对 \(m\) 质因数分解,可以直接用科技对 \(m\) 分解,也可以分别为 \(m_1,m_2\) 分解后合起来,这样我们就得到了 \(m\) 的所有因子。

我们要做的其实就是分解 \(d = a \times b\),且 \(a,b \le n\),要求 \(a\) 尽可能小。

因为 \(d\)\(m\) 的因子,所以 \(a,b\) 也必然是 \(m\) 的因子,所以可以将因子排序之后二分。

具体来说就是二分最小的 \(a\) 使得 \(\lceil \frac{d}{a} \rceil \le n\),这样只需要向后枚举一些 \(a\) 使得 \(a \mid d\) 此时 \(a\) 就是最优的 \(a\) 了。

代码:

点击查看代码
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. using namespace std;
  6. #define int long long
  7. int t, n, m1, m2;
  8. vector<int> a, b, c;
  9. signed main()
  10. {
  11. scanf("%lld", &t);
  12. while (t -- )
  13. {
  14. int cnt = 0, ans = 0;
  15. a.clear();
  16. b.clear();
  17. c.clear();
  18. scanf("%lld%lld%lld", &n, &m1, &m2);
  19. for (int i = 1; i <= m1 / i; i ++ )
  20. {
  21. if(m1 % i == 0)
  22. {
  23. a.push_back(i);
  24. if(m1 / i != i) a.push_back(m1 / i);
  25. }
  26. }
  27. for (int i = 1; i <= m2 / i; i ++ )
  28. {
  29. if(m2 % i == 0)
  30. {
  31. b.push_back(i);
  32. if(m2 / i != i) b.push_back(m2 / i);
  33. }
  34. }
  35. sort(a.begin(), a.end());
  36. sort(b.begin(), b.end());
  37. for (int i = 0; i < a.size(); i ++ )
  38. for (int j = 0; j < b.size(); j ++ )
  39. c.push_back(a[i] * b[j]);
  40. sort(c.begin(), c.end());
  41. c.erase(unique(c.begin(), c.end()), c.end());
  42. for (int i = 0; i < c.size(); i ++ )
  43. {
  44. int l = 0, r = i;
  45. while (l <= r)
  46. {
  47. int mid = l + r >> 1;
  48. if ((c[i] + c[mid] - 1) / c[mid] <= n) r = mid - 1;
  49. else l = mid + 1;
  50. }
  51. for (int j = l; j < c.size(); j ++ )
  52. {
  53. if(c[j] > n) break;
  54. if(c[i] % c[j] == 0)
  55. {
  56. ans ^= c[j];
  57. cnt ++;
  58. break;
  59. }
  60. }
  61. }
  62. printf("%lld %lld\n", cnt, ans);
  63. }
  64. }

F1.Graph Coloring

题目描述:

简单版和困难版之间的唯一区别是 \(n\) 的数据范围不同。

给出一个 \(n\) 个顶点的无向完全图。完全图是指图上任意两个顶点皆有一条边相连。你需要给图上的每条边染上红色或蓝色。

一个顶点的集合 \(S\) 被称作是红色连接的,如果对于 \(S\) 中每对顶点 \((v_1,v_2)\),都存在只通过红边和 \(S\) 中顶点的路径。相仿地,一个顶点的集合 \(S\) 被称作是蓝色连接的,如果对于 \(S\) 中每对顶点 \((v_1,v_2)\),都存在只通过蓝边和 \(S\) 中顶点的路径。

你需要以如下方式对图进行染色:

  • 至少有一条红边。
  • 至少有一条蓝边。
  • 对于每个大小不小于 \(2\) 的顶点集 \(S\)(也即 \(|S|\geqslant 2\)),\(S\) 或者是红色连接的,或者是蓝色连接的,但不能同时是红色和蓝色连接的。

计算染色方法数对 \(998244353\) 取模后的结果。

\(1\le n \le 5\times 10^3\)

题目分析:

(不写 F2 了,是一个多项式科技)

题目条件就是要求对于任意一个导出子图,要么通过红色边可以联通,要么通过蓝色边可以联通,但是不能通过两种边都可以联通。

注意到一点就是:这是一个完全图,所以蓝色边和红色边互为补图,也就是如果蓝色边不连通则红色边必然联通,反之亦然。

所以我们可以直接 \(dp_n\) 表示节点个数为 \(n\) 的图,不能通过蓝色边联通的合法的方案数。

转移就是考虑枚举点 \(n\) 所在的蓝色连通块大小 \(x\)

\[dp_n = \sum_{x=1}^{n-1} \binom{n-1}{x-1} dp_x \times (2 - [x = n-1])dp_{n-x} \]

对于 \(n\) 所在的连通块这 \(x\) 个点必然满足蓝色联通也就是红色不连通,方案数等同于 \(dp_x\)

对于其余的 \(n-x\) 个点,它们之间蓝色联通或者红色联通都可以,所以就是系数有 \(2\) 的贡献,但当 \(n-x = 1\) 时,显然只有一种方案。

因为题目要求必须同时出现红边和蓝边,所以将答案减 \(2\) 即可。

代码:

点击查看代码
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int N = 5e3+5;
  5. const int MOD = 998244353;
  6. int fac[N],inv[N],f[N];
  7. int binom(int n,int m){
  8. if(n < m || n < 0 || m < 0) return 0;
  9. return fac[n] * inv[m] % MOD * inv[n-m] % MOD;
  10. }
  11. int power(int a,int b){
  12. int res = 1;
  13. while(b){
  14. if(b & 1) res = res * a % MOD;
  15. a = a * a % MOD;
  16. b >>= 1;
  17. }
  18. return res;
  19. }
  20. signed main(){
  21. int n;scanf("%lld",&n);
  22. fac[0] = 1;
  23. for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % MOD;
  24. inv[n] = power(fac[n],MOD-2);
  25. for(int i=n-1; i>=0; i--) inv[i] = inv[i+1] * (i+1) % MOD;
  26. f[1] = 1;
  27. for(int i=2; i<=n; i++){
  28. for(int j=1; j<=i-1; j++){
  29. f[i] = (f[i] + f[j] * f[i-j] %MOD* binom(i-1,j-1) * (2 - (j == i-1))%MOD)%MOD;
  30. }
  31. }
  32. printf("%lld\n",(2 * f[n] %MOD - 2 + MOD)%MOD);
  33. return 0;
  34. }

原文链接:https://www.cnblogs.com/linyihdfj/p/17692676.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号