codeforces round 926 div2(A-D)

2024-02-18 02:20

文章标签 codeforces round div2 926

本文主要是介绍codeforces round 926 div2(A-D)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.A

a题 $\sum_{i=2}^{n}(a_{i}-a_{i-1})$ = $a_{n}-a_{1}$ 所以我们排一下序输出 $a_{n}-a_{1}$ 即可,当然直接累加也可以

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while (t--){int n;cin>>n;vector<int>v(n+5);for(int i=1;i<=n;i++)cin>>v[i];sort(v.begin()+1,v.begin()+n+1);int ans=0;for(int i=2;i<=n;i++)ans+=v[i]-v[i-1];   cout<<ans<<"\n";}return 0;
}

b题

可以发现涂满最上面一行和最下面一行,所有的对角线都能涂满,且前2n-2个格子的贡献都为2,后两个格子的贡献为1

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while (t--){/* code */int n,k;cin>>n>>k;if(k<=4*n-4)cout<<(k-1)/2+1<<"\n";elsecout<<(k-2*n+2)<<"\n";}return 0;
}

c题

比较容易想歪的是,我每次都投1,到保底的时候再全投来赢钱,实际这样是不行的,你在保底之前就可能赢,这样你赢的钱还不一定能弥补投出去的钱,保底从0开始计数,这样得不偿失,所以计现在的投出去的总钱数为sum,现在要投的钱为tou,则应满足以下条件** tou+sum<k*tou ** 即**sum<(k-1)*tou 所以 tou=sum/(k-1)+1 **即可(向下取整再加1相当于小数点后的算1)

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while (t--){/* code */int k,x,a;cin>>k>>x>>a;int sum=0,tou;int flag=1;for(int i=1;i<=x+1;i++){tou=sum/(k-1)+1;sum+=tou;if(sum>a||tou*k<sum){flag=0;break;}}//cout<<"sum=="<<sum<<"\n";if(flag)cout<<"yes"<<"\n";elsecout<<"no"<<"\n";}return 0;
}

d题

一个树形dp,难讲清楚,大概就是设dp[i]为以i号结点为根的子树的方案数,因为任何一条简单路径不能超过两个集合中的结点,所以有两种情况
1,子树(不包括当前根节点)中的结点都无父子关系,那么根节点选了,子树都不能选,答案为1,不选根节点,则子树都是独立的,相乘就行
2.有一个节点是是所有节点的祖先(即有长度为2的路径),那么就不用再算了,因为其他地方不能再选点,直接加入到答案中就行

//树形dp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int maxn=3e5+5;
int dp[maxn],ans;void dfs(int x,int pr,vector<int>g[])
{dp[x]=1;for(auto i:g[x]){if(i==pr)continue;dfs(i,x,g);dp[x]*=dp[i];//选的点集中任意两个点不存在父子关系dp[x]%=mod;ans +=dp[i]-1;ans%=mod;}dp[x]+=1;
}//类似后序遍历,左,右,中
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while (t--){int n;cin>>n;ans=0;vector<int>g[n+5];for(int i=1;i<n;i++){int x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}dfs(1,-1,g);cout<<(ans+dp[1])%mod<<"\n";}return 0;
}