Codeforces Round #771 (Div.2) A-E 不完整题解(努力更新中)

A. Reverse

字典序最小的是1 2 3……n排列，故找到第一个a[i]!=i的地方 ，然后把这个地方换成i即可。普通地去模拟。

#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,bj=-1,bj2=-1;cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++){
            if(a[i]!=i){
                bj=i;break;
            }
        }
        if(bj!=-1){
            for(int i=1;i<=n;i++)if(a[i]==bj){bj2=i;break;}
        }
        if(bj!=-1&&bj2!=-1) {
            for (int i = 1; i < bj; i++)cout << a[i] << ' ';
            for (int i = bj2; i >= bj; i--)cout << a[i] << ' ';
            for (int i = bj2 + 1; i <= n; i++)cout << a[i] << ' ';
            cout << '\n';
        } else  for (int i = 1; i <=n; i++)cout<' ';
    }
    return 0;
}

B. Odd Swap Sort

换言之，奇数之间可以互相交换，偶数之间可以互相交换；

换言之，如果NO，说明某个奇数和偶数形成逆序对……当然这里我们只要On扫一遍数组就行了。

#include 
using namespace std;
typedef long long ll;
const int N=200010;
int a[N];
int q0,q1;
int main(){
    int t;cin>>t;
    while(t--){int flg=1;
        int n;cin>>n;
        for(int i=1,x;i<=n;i++){cin>>x;
            if(q0==0&&x%2==0)q0=x;
            if(q1==0&&x%2==1)q1=x;
            if(q0!=0&&x%2==0&&q0>x)flg=0;
            if(q0!=0&&x%2==0&&q0x;
            if(q1!=0&&x%2==1&&q1>x)flg=0;
            if(q1!=0&&x%2==1&&q1x;
        }
        if(flg)cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
        q0=q1=0;
    }
    return 0;
}

C. Inversion Graph

当时卡了许久，想了很多复杂度极其垃圾的方法没想出来，才发现这题是On的

题意：给一串1-n的排列，在所有逆序对之间连一条边，求一共有多少个连通块

劣解：我们从1到n扫这个排列，若i和a[i]之间连了一条边，则i到a[i]之间的所有数都是连通的 这是因为：在这区间之中的数，要么小于a[i]且大于i，要么大于a[i]，要么小于i，这三种情况都保证它会和前面的某个点连上一条边；考虑当连通块的最大值等于扫过数字个数时自动从排列中形成连通块“脱落”。实战中我的代码写得很劣。

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

#include 
 
using i64 = long long;
 
void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        b[i] = a[i];
        if (i > 0) {
            a[i] = std::max(a[i], a[i - 1]);
        }
    }
    
    for (int i = n - 2; i >= 0; i--) {
        b[i] = std::min(b[i], b[i + 1]);
    }
    
    int ans = 1;
    for (int i = 0; i < n - 1; i++) {
        ans += (a[i] < b[i + 1]);
    }
    
    std::cout << ans << "\n";
}
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

D. Big Brush

恶臭bfs模拟题。考虑“正难则反”，我们从结束状态反推，若有方形色块则将其保存为答案。

然后去除方形色块，并关于原来的方形色块一圈圈向外作bfs。

最后，若色块没有被去干净则输出-1，否则输出答案

#include 
using namespace std;
int mp[1010][1010],mp2[1010][1010],vis[1010][1010];
queueint,int> >q;
stackint,int> >ans;
bool chk(int i,int j){
    int k=max(mp[i][j],mp[i+1][j+1]);
    k=max(k,max(mp[i][j+1],mp[i+1][j]));
 
    if(k!=0){mp2[i][j]=k;return ((mp[i][j]==k||mp[i][j]==0)&&(mp[i+1][j]==k||mp[i+1][j]==0)&&(mp[i][j+1]==k||mp[i][j+1]==0)&&(mp[i+1][j+1]==k||mp[i+1][j+1]==0));}
    return 0;
}
int fx[8]={0,1,0,-1,1,1,-1,-1},fy[8]={1,0,-1,0,1,-1,1,-1};
int main(){cin.tie(0);ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
            mp2[i][j]=mp[i][j];
            if((j!=1&&i!=1)&&chk(i-1,j-1)){q.push({i-1,j-1}),vis[i-1][j-1]=1;}
        }
    }
    while(!q.empty()){
        int sz=q.size();
        for(int i=1;i<=sz;i++){
            int f=q.front().first,s=q.front().second;
            if(f==0||s==0||f==n||s==m){q.pop();continue;}
            mp[f][s]=mp[f+1][s]=mp[f][s+1]=mp[f+1][s+1]=0;
            for(int j=0;j<8;j++){
                if(f+fx[j]==0||f+fx[j]==n||s+fy[j]==0||s+fy[j]==m)continue;
                if(chk(f+fx[j],s+fy[j])&&vis[f+fx[j]][s+fy[j]]==0){
                    vis[f+fx[j]][s+fy[j]]=1;
                    q.push({f+fx[j],s+fy[j]});
                }
            }
            ans.push(q.front());
            q.pop();
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mp[i][j]!=0){cout<<-1<<'\n';return 0;}
        }
    }
    cout<endl;
    while(!ans.empty()){
        int f=ans.top().first,s=ans.top().second;
        cout<' '<' '<'\n';
        ans.pop();
    }
    return 0;
}

E.Colorful Operations

题意：一串数组，初始状态为颜色1和值0；

有两种操作，一是对区间染色，二是相同颜色的数加上值c。

以及至多1e6次的在线询问

对于染色题，我们考虑神(暴)奇(力)的ODT，由于出题人没有卡，所以能够AC。

 显然Color就是odt中的assign，qry则访问set中的下标即可。

至于add，我们考虑使用树状数组保存区间和/单点求值，即在每一次assign时，将被推平的区间加上c。

博主数据结构很弱，有一定参考他人代码QWQ

#include 
using namespace std;
const int N=1000010;
#define int long long
int n,tr[N],col[N];
char c[6];
#define sit set::iterator
struct odt{
    int l,r;
    mutable int val;
    odt(int l,int r=0,int val=0):l(l),r(r),val(val){}
    bool operator<(const odt&a)const{return l<a.l;}
};
sets;
sit split(int pos){
    auto it=s.lower_bound(odt(pos));
    if(it!=s.end()&&it->l==pos)return it;
    --it;
    int l=it->l,r=it->r,val=it->val;
    s.erase(it);
    s.insert(odt(l,pos-1,val));
    return s.insert(odt(pos,r,val)).first;
}
int sum(int x){
    int ans=0;
    for(;x;x-=x&-x)ans+=tr[x];
    return ans;
}
void add(int a ,int x){
    for(;a<=n;a+=a&-a)tr[a]+=x;
}
void assign(int l,int r,int x){
    sit rit=split(r+1);sit lit=split(l);
    for(auto it=lit;it!=rit;++it){
        add(it->r+1,-col[it->val]);
        add(it->l,col[it->val]);
    }
    s.erase(lit,rit),s.insert(odt(l,r,x));
    add(r+1,col[x]),add(l,-col[x]);
}
int qry(int x){
    int ans=sum(x);
    auto it=s.upper_bound(x);
    --it;
    return ans+col[it->val];
}

signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int q;cin>>n>>q;
    s.insert(odt(1,n,1));
    while(q--){
        cin>>c;
        if(c[0]=='A'){int co,x;cin>>co>>x;
            col[co]+=x;
        }
        if(c[0]=='Q'){int x;cin>>x;
            cout<'\n';
        }
        if(c[0]=='C'){int l,r,x;cin>>l>>r>>x;
            assign(l,r,x);
        }
    }
}

F. Two Posters

看一眼tags：brute force,data structures,greedy,two pointers,好像很基础的样子？

再看一眼，3200

噔 噔 咚

（这题暂时放着，等我强点再来更新）