Codeforces Round #737 (Div. 2) 題解(A-C)

Codeforces Round #737 (Div. 2) 題解(A-C)

A. Ezzat and Two Subsequences

題目大意：

給定 n n n個整數，將這 n n n個整數分成兩組，使得兩組整數的平均數之和最大，輸出這個最大的平均數之和，

解題思路：

通過觀察樣例可以發現，只要將最大的整數單獨作為一組就行了，

那么為什么這樣是對的呢，可以考慮進行這樣分組之和，從 n ? 1 n-1 n?1個整數那組拿任意一個整數過來能否取得更優的解，列個式子推一推就能明白了，因為本人比較懶就不寫詳細的證明程序了，

代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int a[N];
int n;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        double sum=0;
        for(int i=1;i<n;i++) sum+=a[i];
        sum/=(n-1);
        printf("%.8f\n",sum+a[n]);
    }
    return 0;
}

B. Moamen and k-subarrays

題目大意：

給出 n n n個不同的整數，問是否能將這 n n n個整數分成 k k k塊連續的子陣列之后，通過移位組合成一個升序的陣列，

解題思路：

因為分塊過后，子陣列內部的順序是不會發生改變的，而我們最后要得到的陣列一定是按照嚴格的順序排好的，

所以只要我們將整個陣列按照升序排序，得到每個陣列在升序陣列中的位置，

設 a i a_i ai?在最終陣列的下標是 b i b_i bi?,那么當且僅當 b i = b i ? 1 + 1 b_i=b_{i-1}+1 bi?=bi?1?+1的情況下 a i 和 a i ? 1 a_i和a_{i-1} ai?和ai?1?才能分到同一塊中，

相對的，如果 b i ≠ b i ? 1 + 1 b_i\neq b_{i-1}+1 bi??=bi?1?+1，那么 b i b_i bi?和 b i ? 1 b_{i-1} bi?1?一定要被分成兩塊，

要注意的一點是分成一塊是沒有意義的，所以我們要將答案初始化為 1 1 1，

時間復雜度 O ( n l o g n ) O(nlogn) O(nlogn)，

代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int a[N],b[N];
int n,k;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        vector<int> v;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        for(int i=0;i<n;i++) b[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin();
        int res=1;
        for(int i=1;i<n;i++){
            if(b[i]!=b[i-1]+1) res++;
        }
        puts(k>=res?"YES":"NO");
    }
    return 0;
}

C. Moamen and XOR

題目大意：

構造一個 n n n個整數的陣列 a a a，其中每個整數都要小于 2 k 2^k 2k，

問有多少種方案能夠使得以下條件成立：

a 1 & a 2 & a 3 & . . . & a n ≥ a 1 ⊕ a 2 ⊕ a 3 ⊕ . . . ⊕ a n a_1\And a_2 \And a_3\And...\And a_n\ge a_1\oplus a_2 \oplus a_3\oplus ...\oplus a_n a1?&a2?&a3?&...&an?≥a1?⊕a2?⊕a3?⊕...⊕an?

解題思路：

做法有點像數位dp，但其實也可以說是二進制的線性dp，

因為所有整數要小于 2 k 2^k 2k，所以對于每個整數在二進制的表示下最多只有 k k k位（如果 k = 0 k=0 k=0的話，那所有數都等于1，答案也就是1），

所以我們從高位向低位考慮，考慮每一位的所有情況：

• 如果當前位 & \And &和 ⊕ \oplus ⊕的結果分別是 1 1 1和 1 1 1，那么只有所有數這一位都為 1 1 1，并且n是奇數，一共只有 1 1 1種情況，
• 如果當前位 & \And &和 ⊕ \oplus ⊕的結果分別是 1 1 1和 0 0 0，那么只有所有數這一位都為1，并且n是偶數，一共只有 1 1 1種情況，
• 如果當前位 & \And &和 ⊕ \oplus ⊕的結果分別是 0 0 0和 1 1 1，那么只有奇數個數的這一位為1，并且不能全部的數這一位都為1，
  方案數： { 2 n ? 1 ? 1 n % 2 = 1 2 n ? 1 n % 2 = 0 \begin{cases}2^{n-1}-1&n\%2=1 \\ 2^{n-1} \ &n\%2=0\end{cases} {2n?1?12n?1 ?n%2=1n%2=0?
• 如果當前位 & \And &和 ⊕ \oplus ⊕的結果分別是 0 0 0和 0 0 0，那么只有偶數個數的這一位為1，并且不能全部的數這一位都為1，
  方案數： { 2 n ? 1 n % 2 = 1 2 n ? 1 ? 1 n % 2 = 0 \begin{cases}2^{n-1}&n\%2=1 \\ 2^{n-1}-1 \ &n\%2=0\end{cases} {2n?12n?1?1 ?n%2=1n%2=0?

可能會有人不知道 2 n ? 1 2^{n-1} 2n?1怎么來的，眾所周知組合數的和 ∑ n = 0 m C m n = 2 m \sum\limits_{n=0}^m C_m^n=2^m n=0∑m?Cmn?=2m,其中奇數項和偶數項的和都等于 2 m ? 1 2^{m-1} 2m?1，

設 f [ i ] [ 0 ] f[i][0] f[i][0]為僅考慮最高的 i i i位使得 & \And &和 ⊕ \oplus ⊕的結果相等的方案數， f [ i ] [ 1 ] f[i][1] f[i][1]為僅考慮最高的 i i i位使得 & \And &的結果大于 ⊕ \oplus ⊕的方案數，

那么可以通過上述分析得到狀態轉移方程：

• f [ i ] [ 0 ] = { f [ i ? 1 ] [ 0 ] × ( 2 n ? 1 + 1 ) n % 2 = 1 f [ i ? 1 ] [ 0 ] × ( 2 n ? 1 ? 1 ) n % 2 = 0 f[i][0]=\begin{cases}f[i-1][0]\times(2^{n-1}+1)&n\%2=1\\f[i-1][0]\times(2^{n-1}-1) &n\%2=0\end{cases} f[i][0]={f[i?1][0]×(2n?1+1)f[i?1][0]×(2n?1?1)?n%2=1n%2=0?（就是在前一位相等的基礎上分別添上00和11， & \And &和 ⊕ \oplus ⊕仍然相等）
• f [ i ] [ 1 ] = { f [ i ? 1 ] [ 1 ] × 2 n n % 2 = 1 f [ i ? 1 ] [ 0 ] + f [ i ? 1 ] [ 1 ] × 2 n n % 2 = 0 f[i][1]=\begin{cases}f[i-1][1]\times2^n&n\%2=1\\ f[i-1][0]+f[i-1][1]\times2^n&n\%2=0\end{cases} f[i][1]={f[i?1][1]×2nf[i?1][0]+f[i?1][1]×2n?n%2=1n%2=0?
  （如果在上一位已經使得 & \And &大于 ⊕ \oplus ⊕，那么在當前位對于任何一種情況都是 & \And &大于 ⊕ \oplus ⊕，如果 n n n是偶數的話，會有一種所有整數在當前二進制位都為1使得 & \And &和 ⊕ \oplus ⊕的結果是1和 0 0 0的情況，這種可以使得上一位的相等狀態轉移到當前的大于狀態）

邊界為 f [ 0 ] [ 0 ] = 1 f[0][0]=1 f[0][0]=1，

計算 2 n 2^n 2n用快速冪就行了，在容易溢位的地方別忘了取模，

時間復雜度 O ( l o g n + k ) O(logn+k) O(logn+k)，

代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10,mod=1e9+7;
int n,k;
LL f[N][2];
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=(LL)res*a%mod;
        a=(LL)a*a%mod;
        b>>=1;
    }
    return res;
}
int main()
{
    f[0][0]=1;
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        if(!k){
            puts("1");
        }
        else{
             LL p=qmi(2,n-1);
             for(int i=1;i<=k;i++){
                if(n%2){
                    f[i][0]=(f[i-1][0]*(p+1))%mod;
                    f[i][1]=(f[i-1][1]*p*2%mod)%mod;
                }
                else{
                    f[i][0]=(f[i-1][0]*(p-1))%mod;
                    f[i][1]=(f[i-1][0]+f[i-1][1]*p*2)%mod;
                }
             }
             printf("%d\n",(f[k][0]+f[k][1])%mod);
        }
    }
    return 0;
}