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_JUDGE
		    freopen("IO\\in.txt","r",stdin);
		    freopen("IO\\out.txt","w",stdout);
        #endif
		int tn=1;
		cin>>tn;
		while(tn--){
			solve();
		}
	} 
	
						
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

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_JUDGE
		    freopen("IO\\in.txt","r",stdin);
		    freopen("IO\\out.txt","w",stdout);
        #endif
		int tn=1;
		cin>>tn;
		while(tn--){
			solve();
		}
	} 
	
						
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

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_JUDGE
		    freopen("IO\\in.txt","r",stdin);
		    freopen("IO\\out.txt","w",stdout);
        #endif
		int 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();
		}
	} 
	
						
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

D待补

D 题意

D 思路

D 代码

在这里插入代码片
1