Codeforces Round #737 (Div. 2) -16

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

又是不会数数的一天
10分钟过ab，直接下班

A 题意

n个数，分成两组，使他们的平均数加和最大

A 思路

贪心，最大的数独自一组，剩下的分组
不会证

A 代码

#include<cstdio>
#include<iostream>
#include<set>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=400505;const int inf=0x3f3f3f3f;int n,m,k;void YES(){cout<<"YES"<<endl;}void NO(){cout<<"NO"<<endl;}int a[maxn];void solve(){cin>>n;m=-inf;int c1=0,c2=0;for(int i=1;i<=n;i++){cin>>a[i];m=max(m,a[i]);c1+=a[i];}c1-=m,c2+=m;double d=(c1-0.0)/(n-1.0);cout<<fixed<<setprecision(9)<<d+c2<<endl;}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifint tn=1;cin>>tn;while(tn--){solve();}}

B 题意

n个数作如下操作一次
分成k组连续数，任意排列k组的先后，重新拼接
问是否可以排序

B 思路

显然，分到同一组的元素先后关系就确定了
因此我们离散化一下，数一下有多少个递增且公差为1的连续段，若个数小于等于k即可分组

B 代码

#include<cstdio>
#include<iostream>
#include<set>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=400505;const int inf=0x3f3f3f3f;int n,m,k;int a[maxn],b[maxn];void YES(){cout<<"YES"<<endl;}void NO(){cout<<"NO"<<endl;}void solve(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i];}sort(b+1,b+1+n);int len=unique(b+1,b+n+1)-b-1;for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+len+1,a[i])-b;} int cnt=0;int pos=1;while(pos<=n){while(a[pos]==a[pos+1]-1){pos++;}cnt++;pos++;}//cout<<cnt<<endl;if(cnt<=k)	YES();else		NO();}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifint tn=1;cin>>tn;while(tn--){solve();}}

C 题意

n个数，每个数小于2^k，问n个数按位与结果大于按位异或的方案数

C 思路

奇偶分类
dp[i]代表n个数，使用后i位构造的方案数

当n为奇数时，容易发现，对于最终两个答案的每一位，只能相等。因为若按位与为1，奇数个，按位异或也是1，若按位与为0，为了让答案更大，按位异或也需要是0。
因此答案分成两部分，一部分是n个数i全为1，这种情况只有1种，一部分是n个数有偶数个i位为1，这个可以预处理出来，我们设为x。那么转移就是dp[i]=(x+1)*dp[i-1]

当n为偶数时，如果按位与结果为1，按位异或结果一定是0，这种情况剩下i-1位随便取都可以，那么方案就是2^(i-1) ^ n，设为y。如果按位与结果为0，那么按位异或答案也一定要是0，同样也是n个数有偶数个i位为1，同样设为x。那么转移就是dp[i]=dp[i-1]*x+y

C 代码

#include<cstdio>
#include<iostream>
#include<set>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=200505;const int inf=0x3f3f3f3f;const int mod=1000000007;int n,m,k;void YES(){cout<<"YES"<<endl;}void NO(){cout<<"NO"<<endl;}ll binpow(ll a,ll b){a%=mod;ll res = 1;while(b>0){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res%mod;}int dp[maxn];int pow2[maxn];int ta[maxn];int pre[maxn];int rev[maxn];void solve(){cin>>n>>k;for(int i=1;i<=n/2;i++){pre[i]=(ta[n]*rev[2*i])%mod*rev[n-2*i]%mod;pre[i]=(pre[i-1]+pre[i])%mod;}dp[0]=1;if(n%2==0){for(int i=1;i<=k;i++)dp[i]=(binpow(pow2[i-1],n)+(dp[i-1]*pre[n/2-1])%mod)%mod;}else{for(int i=1;i<=k;i++)dp[i]=(dp[i-1]+(dp[i-1]*pre[n/2])%mod)%mod;}cout<<dp[k]<<endl;}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifint tn=1;cin>>tn;pow2[0]=1,ta[0]=1,pre[0]=1;for(int i=1;i<maxn;i++){pow2[i]=(pow2[i-1]*2)%mod;ta[i]=(i*ta[i-1])%mod;rev[i]=binpow(ta[i],mod-2);}while(tn--){solve();}}