Codeforces Round #735 (Div. 2) 題解(A-D)

Codeforces Round #735 (Div. 2) 題解(A-D)

A. Cherry

題目大意：

有一個長度為 n n n的整數陣列 a a a，找出 m a x ( a l , a l + 1 , . . . , a r ) × m i n ( a l , a l + 1 , . . . a r ) , 1 ≤ l < r ≤ n max(a_l,a_{l+1},...,a_r)\times min(a_l,a_{l+1},...a_{r}),1\le l <r \le n max(al?,al+1?,...,ar?)×min(al?,al+1?,...ar?),1≤l<r≤n的最大值，

解題思路：

通過觀察樣例，我們可以大膽地猜測最優解的區間長度不會超過 2 2 2，所以我們只用遍歷一遍陣列即可，時間復雜度 O ( n ) O(n) O(n)，

現在簡單論證一下為什么這種做法是正確的：

如果存在一個區間 [ l , l + 2 ] [l,l+2] [l,l+2]是優于 [ l , l + 1 ] [l,l+1] [l,l+1]和 [ l + 1 , l + 2 ] [l+1,l+2] [l+1,l+2]的，那么區間 [ l , l + 1 ] [l,l+1] [l,l+1]的最大值和最小值一定是 a l a_l al?和 a l + 2 a_{l+2} al+2?，

如果 a l a_l al?是最大值的話，因為 a l + 1 ≥ a l + 2 a_{l+1}\ge a_{l+2} al+1?≥al+2?，那么一定存在 a l × a l + 1 ≥ a l × a l + 2 a_l\times a_{l+1}\ge a_l\times a_{l+2} al?×al+1?≥al?×al+2?，

同理，如果 a l + 2 a_{l+2} al+2?是最大值的話，那么一定存在 a l + 2 × a l + 1 ≥ a l × a l + 2 a_{l+2}\times a_{l+1}\ge a_l\times a_{l+2} al+2?×al+1?≥al?×al+2?，

所以對于區間長度大于 2 2 2的區間，我們一定能找出不弱于當前區間的區間長度為 2 2 2的區間，

代碼：

#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]);
        LL res=0;
        for(int i=1;i<n;i++){
            res=max(res,(LL)a[i]*a[i+1]);
        }
        printf("%lld\n",res);
    }
    return 0;
}

B. Cobb

題目大意：

對于一個長度為 n n n的整數陣列 a a a，找出 ? ?? 1 ≤ i < j ≤ n , i × j ? k × ( a i ∣ a j ) \forall \;1\le i<j\le n,i\times j-k\times(a_i|a_j) ?1≤i<j≤n,i×j?k×(ai?∣aj?)的最大值，其中 ∣ | ∣表示位運算中的或運算，

資料范圍： 1 ≤ n ≤ 1 0 5 , 1 ≤ k ≤ min ? ( n , 100 ) , 0 ≤ a i ≤ n 1\le n\le10^5,1\le k \le \min(n,100),0\le a_i\le n 1≤n≤105,1≤k≤min(n,100),0≤ai?≤n.

解題思路：

由于 n n n資料范圍的限制，如果本題用 O ( n 2 ) O(n^2) O(n2)的暴力做法是會 T L E TLE TLE的，

通過觀察 i × j ? k × ( a i ∣ a j ) i\times j-k\times(a_i|a_j) i×j?k×(ai?∣aj?)這個結構，我們發現對于前半部分的 i × j i\times j i×j，我們一定是會在 ( n ? 1 , n ) (n-1,n) (n?1,n)這一對取到最大值，又因為 0 ≤ a n ? 1 ∣ a n ≤ 2 × n 0\le a_{n-1}|a_n\le 2\times n 0≤an?1?∣an?≤2×n， ( n ? 1 , n ) (n-1,n) (n?1,n)這一對的最小值是 min ? ( n ? 1 , n ) = ( n ? 1 ) × n ? k × 2 × n = n 2 ? 2 × k × n ? n \min(n-1,n)=(n-1)\times n-k\times2\times n=n^2-2\times k\times n-n min(n?1,n)=(n?1)×n?k×2×n=n2?2×k×n?n，

那么我們考慮對于任何一對 ( i , j ) (i,j) (i,j)，其中 i < j i<j i<j，對于包含 i i i的某對而言，能取得的最大值就是 j = n j=n j=n并且 a i ∣ a j = 0 a_i|aj=0 ai?∣aj=0 的時候，此時能取得的最大值 max ? ( i , j ) = i × n \max(i,j)=i\times n max(i,j)=i×n，

對于上述得到的資訊，我們可以選擇將那些沒有希望大于 m i n ( n ? 1 , n ) min(n-1,n) min(n?1,n)的pair?過濾掉，

即 m a x ( i , j ) ≤ m i n ( n ? 1 , n ) ? i × n ≤ n 2 ? 2 × k × n ? n ? i < = n ? 2 × k ? 1 max(i,j)\le min(n-1,n) \Rightarrow i\times n\le n^2 - 2\times k \times n -n \Rightarrow i<=n-2\times k-1 max(i,j)≤min(n?1,n)?i×n≤n2?2×k×n?n?i<=n?2×k?1，

所以我們只用考慮 i ≥ n ? 2 ? k i\ge n-2*k i≥n?2?k這一部分pair就行，時間復雜度 O ( k 2 ) O(k^2) O(k2)，

代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int a[N];
int n,k;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        LL res=-1e9;
        for(int i=max(1,n-2*k);i<=n;i++)
            for(int j=i+1;j<=n;j++)
                res=max(res,(LL)i*j-k*(a[i]|a[j]));
        printf("%lld\n",res);
    }
    return 0;
}

C. Mikasa

題目大意：

給定整數 n n n和 m m m，找出序列 n ⊕ 0 , n ⊕ 1 , . . . , n ⊕ m n\oplus 0,n\oplus1,...,n\oplus m n⊕0,n⊕1,...,n⊕m中未出現的最小非負整數，其中 ⊕ \oplus ⊕是位運算中的異或運算，

解題思路：

轉換一下思路，可以將原問題轉換為找一個最小的整數k使得 n ⊕ k > m n\oplus k>m n⊕k>m，

設 p = m + 1 p=m+1 p=m+1，在使得k盡可能小的情況下，我們從高位向低位考慮以下四種情況，其中 n i , p i , k i n_i,p_i,k_i ni?,pi?,ki?分別代表 n , p , k n,p,k n,p,k二進制表示下的第 i i i位：

1. n i = 0 , p i = 0 , 那 么 k i = 0 n_i=0,p_i=0,那么k_i=0 ni?=0,pi?=0,那么ki?=0，
2. n i = 0 , p i = 1 , 那 么 k i = 1 n_i=0,p_i=1,那么k_i=1 ni?=0,pi?=1,那么ki?=1，
3. n i = 1 , p i = 0 , 那 么 k i = 0 n_i=1,p_i=0,那么k_i=0 ni?=1,pi?=0,那么ki?=0，
4. n i = 1 , p i = 1 , 那 么 k i = 0 n_i=1,p_i=1,那么k_i=0 ni?=1,pi?=1,那么ki?=0，

我們發現只有當 n i = 0 , p i = 1 n_i=0,p_i=1 ni?=0,pi?=1的時候，我們才需要將 k i k_i ki?變為1，并且為了使得k盡可能小，一但滿足 n ⊕ k ≥ p n\oplus k\ge p n⊕k≥p就要停止回圈，

所以只需要從高位向低位列舉 n n n和 m m m的所有二進制位，時間復雜度 O ( l o g 2 n ) O(log_2n) O(log2?n)，

代碼：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        m++;
        int res=0;
        for(int i=30;i>=0&&n<m;i--){
            if(!(n>>i&1)&&m>>i&1) n|=1<<i,res|=1<<i;
        }
        printf("%d\n",res);
    }
    return 0;
}

D. Diane

題目大意：

給定一個整數 n n n，構造出一個長度為 n n n由小寫字母組成的字串，其中對于字串中的任何一個子串在字串中出現奇數次，

解題思路：

對于連續的 k k k個 a a a，會產生 k k k個"a", k ? 1 k-1 k?1個"aa", k ? 2 k-2 k?2個"aaa"…，每種字串的數量是奇偶交替的，

那么我們可以選擇再添加連續的 k ? 1 k-1 k?1個 a a a,這一串連續的會產生 k ? 1 k-1 k?1個"a", k ? 2 k-2 k?2個"aa"…，剛好將上面連續的 k k k個 a a a產生的偶數次字串修正為奇數次，

當然這兩個字串中間需要加字母來隔開，我們發現 k + k ? 1 k+k-1 k+k?1永遠是一個奇數，那么如果 n n n是奇數的話，我們就需要在中間添上兩個字母作為擋板， n n n是偶數的話就只用添上一個字母，

所以我們對于 n n n是奇數的情況，可以構造出 a a a . . . a a a ? k b c a a a . . . a a a ? k ? 1 \underbrace{aaa...aaa}_{k} bc\underbrace{aaa...aaa}_{k-1} k aaa...aaa??bck?1 aaa...aaa??，當n=1的時候需要特判一下，

n n n是偶數的情況，可以構造出 a a a . . . a a a ? k b a a a . . . a a a ? k ? 1 \underbrace{aaa...aaa}_{k} b\underbrace{aaa...aaa}_{k-1} k aaa...aaa??bk?1 aaa...aaa??，

代碼：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        if(n==1){
            puts("a");
            continue;
        }
        for(int i=0;i<n/2-1;i++) printf("a");
        printf(n%2?"bc":"b");
        for(int i=0;i<n/2;i++) printf("a");
        puts("");
    }
    return 0;
}