Codeforces Round #772 (Div. 2) A B C D

A. Min Or Sum

思路： 一眼题，最好的情况就是二进制形式下出现过的数字最多保留$1$位。全部$|$起来即可。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int k=0;
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            k|=x;
        }
        cout<<k<<endl;
    }
    return 0;
}

B. MEX and Array

思路： 贪心，从左到右扫描，如果碰到$Local$ $Maximums$，那么改变右边的数使$a[i+1]$变成$max(a[i],a[i+2])$。为什么取$max$呢，因为如果$a[i+2]$比$a[i]$大，那么我们显然将$a[i+1]$变成a[i+2]更好，因为不但满足使得左边的$Local$ $Maximums$消失，并且确保右边的$a[i+2]$一定无法构成$Local$ $Maximums$，即是$a[i+3]$比$a[i+2]$小。反之如果$a[i+1]$变成$a[i]$那么左边确实保证了$Local$ $Maximums$消失，但是如果$a[i+3]$比$a[i+2]$小，我们又要浪费一次机会去放大$a[i+3]$，显然前者更优。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        int ans=0;
        for(int i=2;i<=n-1;i++){
            if(a[i]>a[i-1]&&a[i]>a[i+1]){
                a[i+1]=max(a[i],a[i+2]);
                ans++;
            }
        }
        cout<<ans<<endl;
        for(int i=1;i<=n;i++)cout<<a[i]<<' ';
        cout<<endl;
    }
    return 0;
}

C. Differential Sorting

思路： 比赛时候$C$翻水水了，歪掉了。以为区间维护，一开始写了$3$个$struct$维护后缀区间最值。后来$wa$掉了。 正解：从性质出发：1.如果$a[n-1]>a[n]$必错，因为$a[n-1]$无法成为一个小于等于$a[n]$的数。2:如果$a[n]$是正数，那么在满足性质$1$情况下必然可以通过$n-2$次构造使得前$n-2$个数全部变成$a[n-1]-a[n]$。3:如果$a[n]$是负数，前面出现的数必然都是负数才行，一旦出现$a[i]>a[i+1]$的情况，那么必然无法使得$a[i]<=a[i+1]$，因为小的负数-大的负数为大于等于$0$的整数，也必然$>a[i+1]$，所以一旦有$a[n]$是负数，除非原数组本身是非降序，操作次数为$0$，否则一定是$-1$。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        int x=a[n-1]-a[n];
        if(x>0){
            cout<<"-1"<<endl;
            continue;
        }
        if(a[n]<0){
            bool ok=true;
            for(int i=1;i<=n-1;i++){
                if(a[i]>a[i+1])ok=false;
            }
            if(ok){
                cout<<0<<endl;
                continue;
            }
            cout<<"-1"<<endl;
        }
        else{
            cout<<n-2<<endl;
            for(int i=1;i<=n-2;i++){
                cout<<i<<' '<<n-1<<' '<<n<<endl;
            }
        }
    }
    return 0;
}

D. Infinite Set

思路： 通过题目可知除了本身在$a$数组中出现过的数在$S$中，依次迭代的$2 * a[i]+1$和$4 * a[i]$也会依次出现在容器中。那么必定有$k<=f(x)<k+1$，$k$和$k+1$为$n$在$log2()$下的左右边界。例如$2^2<=f(5)<2^3$，那么$k为2$，$k+1$为$3$，那么显然$f(x * 2+1)$的左边界为$k+1$，$f(x * 4)$的左边界为$k+2$。那么我们很容易发现一个$dp$转移方程，左边界为$k+2$的方案数除了本身以外还可以从$k$和$k+1$处转移过来，分别通过方程$f(x * 4)$和$f(x * 2+1)$。并且在方程转移开始之前我们需要删掉无用的在$a$数组中重复出现的数，避免一个相同的数被多次重复计算。例如$a[1]=5，a[2]=10$，$a[2]$可以通过$a[1]$获得，所以$a[2]$我们没必要继续保留。那么这个操作的实现只需将数组从小到大排序，如果将一个数回溯的过程遇到了之前标记过的数说明这个数可以通过前面标记过的数获得而来，那么没必要继续保存。例如：$35$回溯过程是$35$，$17$，$8$，$2$。如果前面这个数出现任意，那么$35$即可被转移过来。那么接下去我们就可以进行$dp$转移，统计最终的总数小于$2^p$的个数。还有一点，为什么进行$dp$转移过程中不会出现同样的数呢？因为我们前面已经将所有会被任意小数转移过来的大数全部删除，那么剩余留在数组中的数必然全是互相不可转移。并且转移路线唯一，什么意思呢？比如上面提到的$35$，回溯路径是唯一的，假使后期转移过程出现相同的数，那么说明这个数不断回溯到原数组中会出现$a[j]$可以被$a[i]$转移而来的情况，那么显然与我们已经删掉所有干扰数相矛盾。所以转移方案数中的数都是独一无二的。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
const int mod=1e9+7;
signed main(){
    int n,p;
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    unordered_map<int,int>hash;
    sort(a+1,a+1+n);
    vector<int>S;
    for(int i=1;i<=n;i++){
        int j=a[i];
        bool ok=true;
        while(j){
            if(hash[j]==1)ok=false;
            if(j&1)j>>=1;
            else if(j&3)break;
            else j>>=2;
        }
        if(ok){//如果无法转移过来那么放进S中
            hash[a[i]]=1;
            S.push_back(a[i]);
        }
    }
    vector<int>sum(30),dp(p);
    for(auto x:S){
        sum[__lg(x)]++;
    }
    int ans=0;
    for(int i=0;i<p;i++){
        if(i<30){
            dp[i]=sum[i];
        }
        if(i>=1){
            dp[i]=(dp[i]+dp[i-1])%mod;
        }
        if(i>=2){
            dp[i]=(dp[i]+dp[i-2])%mod;
        }
        ans=(ans+dp[i])%mod;
    }
    cout<<ans<<endl;
    return 0;
}