codeforces global round 23
constest :codeforces global round 23
contest time:2022.10.16
contest grade: 2800
contest rating changes: +447
Problem - A - Codeforces
题目大致意思是说给定一个01数组，操作1是选择其中两个连续的数，用较小值替代，操作二是说选择一个区间用最大值替代。只能选择一个操作且只能操作一次，问能否使得数组最后只剩下一个1。其实，不难想到，如果说数组当中存在至少一个1，那么区间就可以被1所替代，那就行了；如果说区间里面没有1，取最小值也还是0，照样不行，所以说最终只是要判断数组当中是否存在1。
#include
using namespace std;
int main()
{int t;cin>>t;while(t--){int n,k;cin>>n>>k;int a[55];int flag=0;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]) flag=1;} if(flag) cout<<"YES\n";else cout<<"NO\n"; }return 0;
} 总结：还是不难想到，简单题。
Problem - B - Codeforces
大致意思就是说给定一个01数组，每一次操作可以任意选择下标i，j，使得a[j]+=a[i]并删掉a[i]，问最少多少次操作之后可以使得数组是非严格单调递增的。其实，对于01数列，非严格单调递增就是使得后面的数是1就行了，没必要说还要加到2去，模拟一下就会知道，其实就是看有多少数字是错位的，也就是不满足单调递增顺序的。
//最少的操作数使得数组变成非严格单调递增
#include
using namespace std;
int a[100010],b[100010];
int main()
{int t;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];sort(a+1,a+n+1);int cnt=0;for(int i=1;i<=n;i++)if(a[i]!=b[i])cnt++;cout< 总结：思维题。就是相当于前面的1掉到后面去，看要交换几次可以使得前面是0，后面都是1.
Problem - C - Codeforces
大致意思是说给定一个长度为n的全排列，可以进行n次操作，在第i次操作时，可以选择一个后缀，使得每一个数都加上i。问怎么样操作可以使得最终的逆序对最小。也就是说要使得最终序列是非严格单调递增的。因为是对后缀的每一个数都加上同样的数，其实在后缀里面的相对大小是不变的，主要的就是看在哪个位置出现了逆序对，对其进行修改就行。因为是全排列，而且可以加的数也是全排列，且操作数量有限，可以试着想一下一次就完成他就好了，那可以每一次加上前一个数，反正是全排列，后面也不会再用到了。
//每一次操作，可以找一个非空后缀使得每一个数+i
#include
using namespace std;
int a[100010];
int ans[100010];
void solve()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i],ans[i]=0;//如果说后面是单调递增地就一直都是，如果说不是再变int cnt=0;for(int i=2;i<=n;i++){if(a[i]>t;while(t--) solve();return 0;
} 总结：思维题。一步到位。
Problem - D - Codeforces
题意：让你选k个路径 路径上的每个数c[i]+1，限制条件是同一个根下的两个儿子abs(c[u]-c[v])<=1
求c[i]*s[i]的总和
分析：一开始想着贪心排序 将每一层的点按照s的大小排序然后去选择每一层节点 思路直接寄 不能将各个层割裂开来考虑
正解：每一层每一个节点的基础点数是cnt（上一层传下来的点数）/size(这一层节点的数量）可以多选的节点数为p p=cnt%size; 除此外 这一层层是关联的 如果你这一个节点多选了其下面最大的一条链也要多选一次 所以我们要选择是 最大的一条链 而不是一层里面最大的点 用树形dp记录一下最大点的val。
#include
using namespace std;
enum{N=200009};
basic_stringe[N];
int s[N],o;
long long ans;
int dfs(int x,int y){ans+=s[x]*1ll*y;if(e[x].empty())return s[x];basic_stringw;for(int o:e[x]){w+=dfs(o,y/e[x].size());}sort(begin(w),end(w),greater());int p=y%e[x].size();for(int i=0;i>T;T--;){cin>>n>>o;ans=0;for(i=1;i<=n;++i)e[i]={};for(i=2;i<=n;++i)cin>>j,e[j]+=i;for(i=1;i<=n;++i)cin>>s[i];dfs(1,o);cout< 总结：树上问题，可以考虑一下树上dp和dfs。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！