AtCoder Beginner Contest 278 vp

快来打我* 2024-03-25 23:30 78阅读 0赞

**上午第二节没课浅浅vp了一下，感觉F很有质量啊，今晚加训状压DP！**

**vp的时候被前面的题卡了一下，差点没做出来，所以基础还是很差啊**

**感觉如果被简单题卡了，按wls的话说，就开摆吧，我就这样了，破罐子破摔吧**

**然后就可以乱搞了，说不定乱搞能过呢是吧**

![1f0f71649b41843b1dd2cb908baf4d82.png][]

**不是很懂为什么vp的榜要和正式榜分开，像CF那样多好**

[Tasks - AtCoder Beginner Contest 278][]

**A - Shift**

题意：

![89d0bb6cbf7ed3f1ceefc8880d031c00.png][]

思路：

直接模拟即可

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e5+10;
    
    
    int n,k;
    int a[mxn];
    void solve(){
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        if(k>=n){
            for(int i=1;i<=n;i++) cout<<0<<" \n"[i==n];
        }else{
            for(int i=1+k;i<=n;i++) cout<<a[i]<<" ";
            for(int i=1;i<=k;i++) cout<<0<<" \n"[i==k];
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

**B - Misjudge the Time**

[(87条消息) 【时间处理】\_lamentropetion的博客-CSDN博客][87_ _lamentropetion_-CSDN]

**C - FF**

**哈希表**

这道题感觉有点奇怪，差点没做出来QwQ

本来一眼并查集，但是注意到有些结点的出边不止一条，因此肯定不是并查集

然后用G\[\]\[\]建图也不行，N的范围是1e9

但是注意到Q的范围比较小，是2e5，因此应该和Q的数据范围有关

所以考虑去存边，对于op=2的修改操作，直接把该边的属性值赋0不可用就好了

题意：

![4559ce83702b9a8fc9871a6b84dd6ba7.png][]

![32f6793a316b3931e58cc743544f76e9.png][]

Code:

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e5+10;
    const int mxe=2e5+10;
    struct ty{
        int u,v,r;
    }e[mxe<<2];
    
    map<pair<int,int>,int> mp;
    int n,q,op,u,v,tot=0;
    void solve(){
        cin>>n>>q;
        while(q--){
            cin>>op>>u>>v;
            if(op==1){
                e[++tot]={u,v,1};
                mp[{u,v}]=tot;
            }else if(op==2){
                if(mp[{u,v}]!=0) e[mp[{u,v}]].r=0,mp[{u,v}]=0;
            }else{
                if(e[mp[{u,v}]].r==1&&e[mp[{v,u}]].r==1) cout<<"Yes"<<'\n';
                else cout<<"No"<<'\n';
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

**D - All Assign Point Add**

**线段树**

不懂怎么做，糊了个线段树就过了，刚好前几天学过线段树

题意：

![c0c894bd3d42c2a10ec1beefd1c01ee0.png][]

![6523152875fb3a181d7040cae21c9357.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    struct Tree{
        int lazy,val;
    }tree[mxe<<2];
    
    int n,q,op,x,k;
    int a[mxn];
    void build(int rt,int l,int r){
        tree[rt].lazy=0;
        if(l==r){
            tree[rt].val=a[l];
            return;
        }
        int mid=l+r>>1;
        build(rt<<1,l,mid);
        build(rt<<1|1,mid+1,r);
        //pushup(rt);
    }
    void pushdown(int rt){
        tree[rt<<1].lazy=tree[rt].lazy;
        tree[rt<<1|1].lazy=tree[rt].lazy;
        tree[rt<<1].val=tree[rt].lazy;
        tree[rt<<1|1].val=tree[rt].lazy;
        tree[rt].lazy=0;
    }
    void modify1(int rt,int l,int r,int x,int k){
        if(l==r&&l==x){
            tree[rt].val+=k;
            return;
        }
        if(tree[rt].lazy!=0) pushdown(rt);
        int mid=l+r>>1;
        if(x<=mid) modify1(rt<<1,l,mid,x,k);
        else modify1(rt<<1|1,mid+1,r,x,k);
        //pushup(rt);
    }
    void modify2(int rt,int l,int r,int x,int y,int k){
        if(x<=l&&r<=y){
            tree[rt].lazy=k;
            tree[rt].val=k;
            return;
        }
        if(tree[rt].lazy!=0) pushdown(rt);
        int mid=l+r>>1;
        if(x<=mid) modify2(rt<<1,l,mid,x,y,k);
        if(y>mid) modify2(rt<<1|1,mid+1,r,x,y,k);
        //pushup(rt);
    }
    int query(int rt,int l,int r,int x){
        if(l==r&&l==x){
            return tree[rt].val;
        }
        if(tree[rt].lazy!=0) pushdown(rt);
        int mid=l+r>>1;
        if(x<=mid) return query(rt<<1,l,mid,x);
        else return query(rt<<1|1,mid+1,r,x);
    }
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        build(1,1,n);
        cin>>q;
        while(q--){
            cin>>op;
            if(op==1){
                cin>>x;
                modify2(1,1,n,1,n,x);
            }else if(op==2){
                cin>>x>>k;
                modify1(1,1,n,x,k);
            }else{
                cin>>x;
                cout<<query(1,1,n,x)<<'\n';
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

**E - Grid Filling**

**暴力+卡常技巧**

本来根本不知道怎么做，结果写了个暴力就过了，虽然被卡了几次map和define int long long

所以，在没有思路的时候，不妨写写暴力剪剪枝卡卡常，也许会有意外收获

题意：

![a84e3bd8da5db40f2f6d0c25e4f69be8.png][]

![53caf2cdb62ea0b6180511a70ae390f5.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    const int mxn=3e2+10;
    const int mxe=2e5+10;
    
    
    int H,W,N,h,w;
    int a[mxn][mxn],ans[mxn][mxn],mp[mxn];
    void solve(){
        cin>>H>>W>>N>>h>>w;
        for(int i=1;i<=H;i++){
            for(int j=1;j<=W;j++) cin>>a[i][j],mp[a[i][j]]++;
        }
        for(int i=1;i+h-1<=H;i++){
            for(int j=1;j+w-1<=W;j++){
    
                for(int k=i;k<=i+h-1;k++){
                    for(int z=j;z<=j+w-1;z++){
                        mp[a[k][z]]--;
                    }
                }
                int cnt=0;
                for(int k=1;k<=N;k++){
                    if(mp[k]>0) cnt++;
                }
                ans[i][j]=cnt;
                for(int k=i;k<=i+h-1;k++){
                    for(int z=j;z<=j+w-1;z++){
                        mp[a[k][z]]++;
                    }
                }
            }
        }
        for(int i=1;i+h-1<=H;i++){
            for(int j=1;j+w-1<=W;j++){
                cout<<ans[i][j]<<" \n"[j+w-1==W];
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

**F - Shiritori**

[(87条消息) ABC278 F - Shiritori\_lamentropetion的博客-CSDN博客][87_ ABC278 F - Shiritori_lamentropetion_-CSDN]

**G是博弈，不会！再见！**

[1f0f71649b41843b1dd2cb908baf4d82.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/71ce9956dde64110a6044081c2e9ef0b.png
[Tasks - AtCoder Beginner Contest 278]: https://atcoder.jp/contests/abc278/tasks
[89d0bb6cbf7ed3f1ceefc8880d031c00.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/808096487ca248639c389e46c1932a15.png
[87_ _lamentropetion_-CSDN]: https://blog.csdn.net/weixin_62528401/article/details/129714132?spm=1001.2014.3001.5502
[4559ce83702b9a8fc9871a6b84dd6ba7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d373a4b85a544ea6a078c652e27c44c7.png
[32f6793a316b3931e58cc743544f76e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b0a9b5320ad3475cb783a4b0a26e8b17.png
[c0c894bd3d42c2a10ec1beefd1c01ee0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/be32f866e55c42d6a30f73b7c9f3c7f4.png
[6523152875fb3a181d7040cae21c9357.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7025db79520f4be69ac70e5bcbe5066c.png
[a84e3bd8da5db40f2f6d0c25e4f69be8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/eaf4052bf0474d16b7d7f092c0b31b47.png
[53caf2cdb62ea0b6180511a70ae390f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/958bfcb4aac7432ba8f17e092f61bfb3.png
[87_ ABC278 F - Shiritori_lamentropetion_-CSDN]: https://blog.csdn.net/weixin_62528401/article/details/129714457