Codeforces Round #770 (Div.2) A-F 完整题解

A Min Or Sum

由于两个数的or是单调不减的，所以所有数全部or起来就行。

#include 
using namespace std;
typedef long long ll;
const int N =200010;
int a[N];
 
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;cin>>n;int ans=0;
        for(int i=1;i<=n;i++){
            int x;cin>>x;ans|=x;        }
        cout<'\n';
    }
}

B. Avoid Local Maximums

不能出现“局部极大值”，且修改数组次数最少。考虑贪心，扫一遍数组，然后对于局部极大值，把它右边的数改为相邻两数的最大值。

#include 
using namespace std;
typedef long long ll;
const int N =200010;
int a[N];
 
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;cin>>n;int ans=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        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<'\n';
        for(int i=1;i<=n;i++){
            cout<' ';
        }cout<<'\n';
        fill(a,a+5,0);
    }
}

C. Differential Sorting

题意：选择三个下标x

思路：发现a[n-1]>a[n-2]的时候显然不成立。对于成立的情况，我们可以顺其自然的想到逆推：从n开始向数组1扫，观察是否能把数组操作成单调不减的。

#include 
using namespace std;
typedef long long ll;
const int N =200010;
ll a[N];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;cin>>n;
        ll ans=0;
        for(int i=1;i<=n;i++)cin>>a[i];
        if(a[n]1]){cout<<-1<<'\n';continue;}
        int x=0,y=0,flg=1;
        for(int i=n;i>=2;i--){
            if(a[i]-a[i-1]<0){flg=0;break;}
            if(a[i]-a[i-1]>=0){
                if(a[i-1]>=a[i-1]-a[n]){
                    x=i-1,y=n;break;
                }
            }
        }
        if(flg){
            if(x==0&&y==0)cout<<0<<'\n';
            else {cout<1<<'\n';
                for(int i=1;i){
                cout<< i<<' '<' '<'\n';
            }
            }
        } else cout<<"-1\n";
    }
}

D. Infinite Set

一道比较适合你们这帮菜B算法初心者的思维题

题意：给一个n个元素的整数集合，可以把2x+1与4x加入集合中（但数字大小不能超过2^p），求最多可以放多少个数进去

由于p<=2e5,我们自然考虑对它（以及数集中的数）取对数。对于某个数（比如1），假设p=4，我们进行如下观察：

log1=0； log（2+1）=1；log（4*3）=3；

　　　　 log（4*1）=2； log（4*4）=4（不行，注意题目是取小于号）

　　　　　　　　　　     log （2*3+1）=2；log（7*2+1）=3；

　　　　　　　　　　　  log（4*2+1）=3；

容易发现这样的数是互异的，并且log要么加一，要么加二。于是题目就变成了斐波那契数列的问题。但我们统计的不是路径数，而是产生的点（换言之，走过的总步数），分别考虑走到取对数后值为n,n-1,n-2……的数有多少个，发现其个数是一个斐波那契前缀和。

最后，注意查重。比如当数集同时存在1和3的时候，由于1可以生成3，所以就不用再次计算3生成的点。

#include 
using namespace std;
typedef long long ll;
const int N =200010;
const int mod=1000000007;
ll a[N];
sets;
 
bool chk(ll i){
    while(i){
        if(s.find(i)!=s.end())return 0;
        if(i%2==1){i=i/2;}
        else if(i%4==0){
            i=i/4;
        }
        else return 1;
    }
    return 1;
}
ll fibbo[200010];
int main(){
    ll n,p;
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    fibbo[0]=1,fibbo[1]=1;
    for(int i=2;i<=200005;i++){
        fibbo[i]=(fibbo[i-1]+fibbo[i-2])%mod;
    }
    for(int i=1;i<=200005;i++){
        fibbo[i]=(fibbo[i]+fibbo[i-1])%mod;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        if(chk(a[i]))s.insert(a[i]);
    }
    ll ans=0;
    for(auto i:s){
        ll k= log2(i);
        k++;
        if(p>=k)ans=(ans+fibbo[p-k])%mod;
    }
    cout<'\n';
}

E. Cars

题意：给出一堆车之间的关系（1——必定不能相遇，2——必定可以相遇），存不存在一条道路上的车，其方向满足这样的关系。

题解：容易发现，无论是关系1还是关系2，两车的方向必定不同。因此可以考虑把题目转换为一个二分图染色问题。

首先考虑奇数个点的环，若存在奇数环就染不来色，寄了

然后考虑对于两车的左右关系连一张DAG，如果DAG走不到头也寄了

如果没寄，就愉快地输出结果吧~

#include 
using namespace std;
const int N=200010;
vector<int>mp[N];
int op[3][N];
int in[N],ans[N];
queue<int>q;
char c[2]={'L','R'};
char col[N];
bool dfs(int x,int mod){
    if(col[x])return (col[x]==c[mod]);
    col[x]=c[mod];mod^=1;
    for(auto i:mp[x]){
        if(!dfs(i,mod))return 0;
    }
    return 1;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>op[0][i]>>op[1][i]>>op[2][i];
        mp[op[1][i]].push_back(op[2][i]),mp[op[2][i]].push_back(op[1][i]);
    }
    for(int i=1;i<=n;i++){
        if(!col[i]){
            if(!dfs(i,0)){cout<<"NO"<<'\n';return 0;}
        }
    }
    for(int i=1;i<=n;i++)mp[i].clear();
    for(int i=1;i<=m;i++){
        if(op[0][i]==1&&col[op[1][i]]=='L')mp[op[1][i]].push_back(op[2][i]),in[op[2][i]]++;
        if(op[0][i]==1&&col[op[1][i]]=='R')mp[op[2][i]].push_back(op[1][i]),in[op[1][i]]++;
        if(op[0][i]==2&&col[op[1][i]]=='R')mp[op[1][i]].push_back(op[2][i]),in[op[2][i]]++;
        if(op[0][i]==2&&col[op[1][i]]=='L')mp[op[2][i]].push_back(op[1][i]),in[op[1][i]]++;
    }
    for(int i=1;i<=n;i++)if(!in[i])q.push(i);
    int tot=0;
    while(!q.empty()){
        int f=q.front();q.pop();ans[f]=++tot;
        for(auto i:mp[f]){in[i]--;if(!in[i])q.push(i);}
    }if(tot"NO\n";return 0;}
    cout<<"YES\n";
    for(int i=1;i<=n;i++){
        cout<' '<'\n';
    }
}

F. Closest Pair

题意 ：每个点有坐标和重量，一条线段的权值是距离乘端点质量之和。离线询问，每次询问给出l和r，找权值最小的区间。

题解：若某对点对权值最小，它们中间不能存在比质量比两点更小的数。于是可以考虑单调栈把这样的点对预处理出来，由于每个数最多进出栈一次，所以这样的点对是On的。

于是变成了一个我第一次做的二维数点问题。

#include
using namespace std;
typedef long long ll;
const int N=300010;
ll w[N],l[N],ans[N];
ll tr[N];
vectorint,ll>>pr[N],q[N];
int n;
void add(int x,ll y){
    for(;x<=n;x+=x&-x)tr[x]=min(tr[x],y);
}
ll qry(int x){
    ll res=LLONG_MAX;
    for(;x;x-=x&-x)res=min(res,tr[x]);
    return res;
}
 
int main(){cin.tie(0);ios::sync_with_stdio(0);cout.tie(0);
    int Q;cin>>n>>Q;
    stack<int>s;
    fill(tr,tr+n+3,LLONG_MAX);
    for(int i=1;i<=n;i++){
        cin>>l[i]>>w[i];
        while(!s.empty()&&w[i]<w[s.top()]){
            pr[i].push_back({s.top(),(l[i]-l[s.top()])*(w[s.top()]+w[i])});
            s.pop();
        }
        if(!s.empty()){
            pr[i].push_back({s.top(),(l[i]-l[s.top()])*(w[s.top()]+w[i])});
        }
        s.push(i);
    }
    for(int i=1;i<=Q;i++){
        int x,y;cin>>x>>y;
        q[y].push_back({x,i});
    }
    for(int i=1;i<=n;i++){
        for(auto x:pr[i]){
            add(n+1-x.first,x.second);
        }
        for(auto x:q[i]){
            ans[x.second]= qry(n+1-x.first);
        }
    }
    for(int i=1;i<=Q;i++){
        cout<'\n';
    }
}