Codeforces Round 916 (Div. 3)（G未补）

2023-12-21 00:20
文章标签 codeforces round div 未补 916

本文主要是介绍Codeforces Round 916 (Div. 3)（G未补），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

A. Problemsolving Log

B. Preparing for the Contest

C. Quests

D. Three Activities

E1.E2. Game with Marbles

F. Programming Competition

A. Problemsolving Log

题意：A任务需要一分钟完成，B任务需要两分钟完成，……以此类推，给定一串任务s，由大写英文字母组成， 第i个字符表示完成了s【i】，问能完成多少个任务

思路：统计一下每个字符出现的次数，然后根据题意判断一下即可

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 1e5 + 10;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){int n;cin>>n;string s;cin>>s;// cout<<s<<endl;int cnt=0;map<char,int>mp;vector<bool>st(26,0);for(int i=0;i<n;i++){mp[s[i]]++;int c=(int)(s[i]-'A')+1;// cout<<c<<endl;if(mp[s[i]]>=c&&!st[s[i]-'A'])cnt++,st[s[i]-'A']=1;// if(s[i]<='a'+i)cnt++;}cout<<cnt<<"\n";}return 0;
}

B. Preparing for the Contest

题意：给定一串序列，如果一个第i个数字大于第i-1个数字，那么就会兴奋一次，第一个数字不会兴奋，给定一个n和k，要求构造一个长度为n的序列，满足恰好兴奋k次

思路：从小到大顺序输出k个数字，再从大到小逆序输出n-k个数即可

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 1e5 + 10;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){int n,k;cin>>n>>k;for(int i=n-k;i>=1;i--)cout<<i<<" ";for(int i=n-k+1;i<=n;i++)cout<<i<<" ";cout<<endl;}return 0;
}

C. Quests

题意：给定n个任务，只有当第i个任务前的所有任务都至少完成过一次后，才能完成第i个任务，每个任务可以完成若干次，第一次完成会获得a_{i}的经验值，后面再次完成会获得b_i的经验值，给定一个数字k，问在k次内能取得的最大经验值

思路：从第一个任务开始，对于每个任务，我们可以选择继续做下一个任务，或者选择之前做过的任务中经验值最大的任务，不断遍历，去max即可

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 1e5 + 10;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){int n,k;cin>>n>>k;vector<int>a(n),b(n);for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<n;i++)cin>>b[i];int ans=0,sum=0,maxv=0;for(int i=0;i<min(n,k);i++){sum+=a[i];maxv=max(maxv,b[i]);if(k-i-1>=0)ans=max(ans,sum+(k-i-1)*maxv);ans=max(ans,sum);}cout<<ans<<"\n";}return 0;
}

D. Three Activities

题意：给定3个序列a,b,c，要求找到a_{i}+b_{j}+c_{k}最大，且i,j,k互不相等

思路：对于每个序列进行从大到小的排序后，我们会发现，我们可以在每个序列中的前3个中各选一个找到一个满足题意的答案，暴力计算一下即可，时间复杂度为O(3^{3}).

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>#define x first
#define y secondusing namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 1e5 + 10;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){int n;cin>>n;vector<pii>a(n),b(n),c(n);for(int i=0;i<n;i++)cin>>a[i].x,a[i].y=i;for(int i=0;i<n;i++)cin>>b[i].x,b[i].y=i;for(int i=0;i<n;i++)cin>>c[i].x,c[i].y=i;sort(a.begin(),a.end(),greater<pii>());sort(b.begin(),b.end(),greater<pii>());sort(c.begin(),c.end(),greater<pii>());int ans=0;for(int i=0;i<min(n,5);i++){for(int j=0;j<min(n,5);j++){for(int k=0;k<min(n,5);k++){if(a[i].y==b[j].y||a[i].y==c[k].y||b[j].y==c[k].y)continue;ans=max(ans,a[i].x+b[j].x+c[k].x);}}}cout<<ans<<"\n";}return 0;
}

E1.E2. Game with Marbles

题意：有两个人Alice和Bob，他们有n种糖果，Alice拥有每种糖果a_{i}个，Bob拥有每种糖果b_{i}个，从Alice开始，每次可以选择一个两人都有的糖果i（即a_{i}>0,b_{i}>0)，然后对于第i个糖果，a_{i}=a_{i}-1,b_{i}=0。下一回合轮到Bob，Bob同样选择一个两人都有的糖果i（即a_{i}>0,b_{i}>0),然后对于第i个糖果a_{i}=0,b_{i}=b_{i}-1,如果两人都不能选择一个糖果i进行上述操作，则结束操作，得分就是Alice的糖果总数减去Bob的糖果总数，Alice希望得分尽可能的大，Bob希望得分尽可能的小，问如果双方都进行最优操作，最后的得分是多少/

思路：

可以考虑下为什么 Alice 会选择颜色 i，而非选择颜色 j：

  • 如果 Alice 选了颜色 i ， Bob 选了颜色 j ，这一回合的得分就是(a_{i}-1)+(1-{b_{j}})=a_{i}-b_{j}
  • 如果 Alice 选了颜色 j ， Bob 选了颜色 i ，这一回合的得分就是 (a_{j}-1)+(1-b_{i})=a_{j}-b_{i}
  • 所以需要满足 a_{i}-b_{j}>a_{j}-b{i}->a_{i}+b_{i}>a_{j}+b_{j}

因此我们对 a_{i}+b_{i} 进行排序就可以了。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>#define x first
#define y secondusing namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 1e5 + 10;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){int n;cin>>n;vector<pii>a(n),b(n),c(n);for(int i=0;i<n;i++)cin>>a[i].x,a[i].y=i;for(int i=0;i<n;i++)cin>>b[i].x,b[i].y=i;for(int i=0;i<n;i++)cin>>c[i].x,c[i].y=i;sort(a.begin(),a.end(),greater<pii>());sort(b.begin(),b.end(),greater<pii>());sort(c.begin(),c.end(),greater<pii>());int ans=0;for(int i=0;i<min(n,5);i++){for(int j=0;j<min(n,5);j++){for(int k=0;k<min(n,5);k++){if(a[i].y==b[j].y||a[i].y==c[k].y||b[j].y==c[k].y)continue;ans=max(ans,a[i].x+b[j].x+c[k].x);}}}cout<<ans<<"\n";}return 0;
}

F. Programming Competition

这题地题解是看这位大佬的：https://zhuanlan.zhihu.com/p/673159169

题意：给定一棵树，每个节点除了不可以跟其祖宗节点进行匹配，其余都可以匹配。问最大匹配数。

思路：有一个很经典的题目就是，如果有n种不同类型的糖果，总数为s，两个不同的糖果可以配对成一组，问最多配对多少组。

显然，如果数量最多的糖果不超过总数的一半，那我们总是可以配对出\lfloor \frac{s}{2} \rfloor组。否则我们就无法用完数量最多的糖果，假设最大的糖果有mx个，那我们只能配对出s-mx组。

回到这题，对于每个节点，我们把不同子树内的点认为是不同的类型。所以如果出现当前最大的子树里点不超过当前节点的所有子节点总数的一半，那我们可以把剩下所有点都配对，然后退出即可。否则我们肯定是把其他子树内的点和最大的子树内的点配对完之后再递归处理最大的子树。

递归到子树的时候，某些该子树内的点已经在之前配对过了，显然应该贪心地让当前子树地根与外面地点配对，这样一定是最优地，因为根不可能和子树地任何点配对

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 2e5 + 10;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){int n;cin>>n;vector<vector<int>>g(n+1);//注意这里要用这种写法，不能写成vector<int>g[n+1]，否则dfs会报错，不知道为什么for(int i=2;i<=n;i++){int x;cin>>x;g[x].push_back(i);}vector<int>sz(n+1);//记录每个节点的子节点个数//统计每个节点的子节点个数auto dfs1 = [&](auto &&dfs1,int u)->void    {sz[u]=1;for(auto &j:g[u]){dfs1(dfs1,j);sz[u]+=sz[j];if(sz[j]>sz[g[u][0]])swap(j,g[u][0]);}};dfs1(dfs1,1);int ans=0;//找到最大匹配数，u为当前节点，c为上一轮能匹配的数量auto dfs2 = [&](auto &&dfs2,int u,int c)->void{if(g[u].empty())return;if(c>=sz[u])return;if(c>0)c-=1;//减1表示减去的是根节点，将根节点跟其他节点匹配int sum=0;//统计该节点的子节点个数for(auto j:g[u])sum+=sz[j];int mx=sz[g[u][0]];//该节点的子节点中节点个数最多的点if(mx-c<=sum-mx)//说明当前节点的最大子节点个数减去上一轮与其他节点匹配的数量之后小于总数的一半{ans+=(sum-c)/2;//那么答案就是总数的一半return;}ans+=sum-mx;//否则记录下来此时能匹配的最多的个数c+=sum-mx;//记录下来能匹配的最多的个数dfs2(dfs2,g[u][0],c);};dfs2(dfs2,1,0);cout<<ans<<"\n";}    return 0;
}

这篇关于Codeforces Round 916 (Div. 3)（G未补）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/518045。

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
Codeforces Round #261 (Div. 2)小记

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件，我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m
阅读更多...
Codeforces Beta Round #47 C凸包 （最终写法）

Codeforces Beta Round #47 C凸包 （最终写法）

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op
阅读更多...
Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A， 多边形B， 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包，如果凸包上的点是B的某个点，则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法，只需在求凸包的时候， <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int
阅读更多...
Codeforces 482B 线段树

Codeforces 482B 线段树

求是否存在这样的n个数； m次操作，每次操作就是三个数 l ，r，val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja
阅读更多...
CSS实现DIV三角形

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor
阅读更多...
创建一个大的DIV，里面的包含两个DIV是可以自由移动

创建一个大的DIV，里面的包含两个DIV是可以自由移动

创建一个大的DIV，里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;
阅读更多...
Codeforces Round 971 (Div. 4) (A~G1)

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单，不做解释 C 对于 x y 两个方向，每一个方向至少需要 x / k 向上取整的步数，取最大值。 由于 x 方向先移动，假如 x 方向需要的步数多于 y 方向的步数，那么最后 y 方向的那一步就不需要了，答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>
阅读更多...
CF#271 (Div. 2) D.（dp）

CF#271 (Div. 2) D.（dp）

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接： http://codeforces.com/contest/474/problem/D We s
阅读更多...
CF #278 (Div. 2) B.（暴力枚举+推导公式+数学构造）

CF #278 (Div. 2) B.（暴力枚举+推导公式+数学构造）

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接： http://codeforces.com/contest/488/problem/B There
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2