Codeforces Round #737 (Div. 2)题解_codeforces round 737 (div. 2)

Problem - A - Codeforces

题目大意:给定你一个长度为n的序列,你可以将该序列划分为两个子序列,请求出两个子序列,使得两个子序列的平均值之和最大.

思路:思维题,如果一个数组内最大的数和其他较大的数分为一组,那么该组的平均值一定会小于最大的的数,我们目前只有两个序列,应该保证其中一个拥有最大平均值,那就是最大的数本身,所以该题只需要把最大的数作为一组,其他数作为一组即可.

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x = y; x<=z;++x)
#define dec(x,y,z) for(int x = y; x>=z;--x)
#define INF 0x3f3f3f3f
#define ll long long
#define LOOP ll _; cin>> _; for(ll LP_ = 1; LP_<=_; ++LP_)
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int N = 1e5+5;
int n;
ll a[N];
int main(){
    LOOP{
        cin>>n;
        ll pre = 0;
        ll maxn = -INF;
        rep(i,1,n){cin>>a[i];pre+=a[i];maxn = max(maxn, a[i]);}
        double ans = maxn + (pre-maxn) / (n-1.0);
        printf("%.9lf\n", ans);
    }

    return 0;
}
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

Problem - B - Codeforces

题目大意:给定长度为n的一个序列,序列中的各个数都不想等,你可以选择将序列分成k个子序列,并将子序列排序后重新组合在一起,请问是否可以通过这样的操作使得整个序列变成有序的.

思路:思维题,为了使排序后的序列有序,那么如果一个数它后面的数不是有序序列中恰好大于它的那个数,那么这两个数就需要拆成两个子序列,最后只需要统计拆分的子序列个数是否小于等于k即可.关于查找大于当前数的数,这里采用了二分的方法,因为n的规模为3e5.

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x = y; x<=z;++x)
#define dec(x,y,z) for(int x = y; x>=z;--x)
#define INF 0x3f3f3f3f
#define ll long long
#define LOOP ll _; cin>> _; for(ll LP_ = 1; LP_<=_; ++LP_)
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int N = 1e5+5;
int a[N], b[N];
int n, k;
int main(){
    syncfalse
    LOOP{
        cin>>n>>k;
        rep(i,1,n){cin>>a[i];b[i] = a[i];}
        a[n+1] = b[n+1] = INF;	//初始化end节点,防止误判
        sort(b+1, b+1+n);
        rep(i,1,n-1){
            int temp = upper_bound(b+1, b+1+n, a[i])-b;
            if (a[i+1] != b[temp])k--;
        }
        if (k > 0)puts("Yes");
        else puts("No");
    }

    return 0;
}
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

Problem - C - Codeforces

题目大意:给定数n,k,你可以选择n个小于2^k-1的数使得a₁&a₂&a₃&…&a_n >= a₁^ a₂^a₃…^a_n,请问有多少种选择方式,相同的数在不同的位置上也算不同的种类.

思路:组合数学+位运算.首先我们考虑一位的情况.

如果两个数相等,如果想要与操作的结果为1,那么n个数都为1,此时如果是奇数,那么异或操作的结果也为1,符合.如果不是n个1进行与操作,那么与操作得到的数一定是0,那么为了使得相等,我们必须让异或操作也为0,那么对于这种情况下只能选择偶数个1.

在考虑与操作大于异或操作的情况,这种情况下,只能是与操作为1,异或操作为0,也就是n为偶数,且有n个1的情况,这种情况下如果当前位大于了,那么剩下的低位可以随意的组合,对于这种情况我们只需要从高位开始枚举相等的那一位,该位之前的种类就是相等的组合数^{当前相等的位数,该位之后的种类就是任意组合也就是(2}n)^剩余低位的个数.

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x = y; x<=z;++x)
#define dec(x,y,z) for(int x = y; x>=z;--x)
#define INF 0x3f3f3f3f
#define ll long long
#define LOOP ll _; cin>> _; for(ll LP_ = 1; LP_<=_; ++LP_)
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int mod = 1e9+7;
const int maxn = 2e5+5;
ll fac[maxn],infac[maxn];
ll ksm(ll a,ll b,ll p)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
void init()
{
    fac[0]=infac[0]=1;
    for(int i=1;i<maxn;i++)
    {
        fac[i]=(ll)fac[i-1]*i%mod;
        infac[i]=(ll)infac[i-1]*ksm(i,mod-2,mod)%mod;
    }
}

ll quick(ll a, ll b){
    ll base = a, ans = 1;
    while(b){
        if (b&1)ans=(ans*base)%mod;
        base = (base*base)%mod;
        b >>=1;
    }
    return ans % mod;
}

int main()
{
    init();
    LOOP{
        ll n,k;
        cin>>n>>k;
        ll equalnum = 0;
        if (n&1)equalnum++;
        for (int i = 0; i < n; i+=2){
            equalnum  = (equalnum + fac[n]*infac[i]%mod*infac[n-i]%mod)%mod;
        }
        ll ans = quick(equalnum, k);
        if (n%2==0){
            ll anseven = 0;
            ll temp = quick(2, n);
            for (int i = 0; i < k; ++i){
                anseven = (anseven + quick(temp, k-1-i) * quick(equalnum, i)%mod)%mod;
            }
            ans = (ans + anseven)%mod;
        }
        cout << ans <<endl;
    }
}
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