Codeforces Round #737 (Div. 2) ABC

A - Ezzat and Two Subsequences

题意：给定一个数组，将其分为两个非空子序列，问如何分使得两个非空子序列的平均值最大。
思路： 猜了个结论：找到数组中最大的一个数，将其单独划为一个序列，剩下的划为另外一个序列，这样能使得平均值最大。

代码

#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
const int N = 5e5+10;
const int inf=0x3f3f3f3f;
long double a[N];
long double sum;
void solve(){
	int n;cin>>n;
    ll maxn=-inf;
    sum=0;
    rep(i,1,n){
        cin>>a[i];
        sum+=a[i];
        if(a[i]>maxn)maxn=a[i];
    }
    long double ans=(sum-maxn)/(n-1);
    ans+=maxn;
    cout<<fixed<<setprecision(9)<<ans<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

B - Moamen and k-subarrays

题意：给定一个长度为n的数组和k次划分操作，每一次操作可以在数组中划分一段连续的序列，问能否在k次操作内，将每一段序列重新进行排序使得变化后的数组满足递增。
思路
用一个map记录这个数在原数组中的排第几小，然后再回去遍历原数组，如果mp[a[i]] != mp[a[i-1]]+1,贡献加+1。
代码

#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
int  a[N];
int b[N];
map<int,int>mp;
void solve(){
    mp.clear();
	int n,k;cin>>n>>k;
    rep(i,1,n){
        cin>>a[i];b[i]=a[i];
    }
    sort(b+1,b+n+1);
    rep(i,1,n){
        mp[b[i]]=i;
    }
    int num=1;
    rep(i,2,n){
       if(mp[a[i]]==mp[a[i-1]]+1)continue;
        else num++;
    }
    if(num<=k)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

C. Moamen and XOR

题意
有n个数，且每一个数 小于 $2^k$，问有多少种组合使得这n个数的按位与的值大于等于异或的值。
思路
因为1的个数会对异或造成不同影响，所以分奇偶进行考虑
pre[i] 表示$2^i$,num1表示在当前位置，& > ⊕的总组合数 ，num2表示在当前位置，& == ⊕的总组合数。
从高位向低位遍历
1 、如果n是偶数
$num2\ast qpow(pre[i],n,mod)$表示当前位全为1，低位所有位任意取0/1的种类，
$num2\ast =pre[n-1]-1$表示在n位中取偶数个1的种类
$C_n^0$+$C_n^2$+$C_n^4$+…+$C_n^n$=$2^{n-1}$
其中$C_n^n$这一种已经在上一步算过，故要减一
2、如果n是奇数
$num2\ast =pre[n-1]+1$表示在n位中取偶数个1的种类
因为n是奇数，所以$C_n^n$还未加入到贡献中，故要加一
最后就是将num1和num2相加取模。
代码

#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
ll  a[N];
ll b[N];
ll pre[N];
ll qpow(ll x, ll y, int MOD) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans = ans*x%MOD; x = x*x%MOD; }return ans; }
void init(){
    pre[0]=1;
    rep(i,1,N)pre[i]=(pre[i-1]*2)%mod;
}
void solve(){
    int n,k;cin>>n>>k;
    ll num1=0,num2=1;
    per(i,k-1,0){
        if(n%2==0){
            num1+=num2*qpow(pre[i],n,mod)%mod;
            num1%=mod;
            num2*=pre[n-1]-1;
        }
        else {
            num2*=pre[n-1]+1;
        }
        num2%=mod;
    }
    cout<<(num1+num2)%mod<<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