vp济南银牌 沈阳铜牌 感觉被其他人偷走了我的人生 哎。。。 菜就多练吧

A

玩了很多样例发现 好像是 合法括号的最小划分不超过2就可以 写出来造了很多很多数据 才敢交 1A

// ([])[]() ([]([]))
void solve(){
    string s;cin>>s;s='='+s;int n=s.size();
    for(auto &c:s)if(c=='(')c=')';else if(c=='[')c=']';
    char pre='0';
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(s[j]==s[j-1]){
                cnt++;
                int len=j-i;
                if(s[i]==pre){
                    NO return;
                }
                pre=s[i];
                string l=s.substr(i,len);
                string r=s.substr(j,len);
                reverse(all(r));
//                cout<<l<<' '<<r<<endl;
                if(l!=r){
                    NO return;
                }
                i=j+len-1;
                break;
            }
        }
    }
    if(cnt>=3){
        NO return;
    }
    YES
}

D

暴力 找到9不会很多次

void solve(){
    int la,ra,lb,rb;cin>>la>>ra>>lb>>rb;
    int ans=0;
    for(int a=la;a<=ra;a++){
        for(int b=lb;b<=rb;b++){
            int x=a+b;
            vector<int>nums;
            while(x)nums.push_back(x%10),x/=10;
            ans=max(ans,*max_element(all(nums)));
            if(ans==9){
                cout<<9<<endl;
                return;
            }
        }
    }
    cout<<ans<<endl;
}

G

很容易看出来 第i列和第m-i+1列 的1不会超过3个
这样我们考虑连边
比如考虑第i列和第m-i+1列
我们第i列（左边）第1行出现了1
第m-i+1列（右边）第2行出现了1
这样这第1行和第2行就不能属性（颜色相同）
考虑染色过程 就这样分类讨论一下连一下边就可以了
对于每一个连通块我们可以*2

int n,m,color[1000010],flag;
vector<PII>g[1000010];
void dfs(int u,int st){
    if(flag)return;
    color[u]=st;
    for(auto [v,w]:g[u]){
        if(color[v]==-1)dfs(v,(st+w)%2);
        else{
            if(color[v]!=(st+w)%2){
                cout<<0<<endl;
                flag=1;
                return;
            }
        }
        if(flag)return;
    }
}
void solve(){
    flag=0;
    cin>>n>>m;
    int a[n+1][m+1];
    for(int i=1;i<=n;i++){
        g[i].clear();
        color[i]=-1;
        for(int j=1;j<=m;j++){
            char c;cin>>c;
            a[i][j]=(c=='1');
        }
    }
    for(int i=1,j=m;i<=j;i++,j--){
        vector<int>l,r;
        for(int k=1;k<=n;k++)if(a[k][i])l.push_back(k);
        for(int k=1;k<=n;k++)if(a[k][j])r.push_back(k);
        if(l.size()+r.size()>=3){
            cout<<0<<endl;
            return;
        }
        if(l.size()==2){
            g[l[0]].push_back({l[1],1});
            g[l[1]].push_back({l[0],1});
        }
        if(r.size()==2){
            g[r[0]].push_back({r[1],1});
            g[r[1]].push_back({r[0],1});
        }
        if(l.size()==1&&r.size()==1){
            g[r[0]].push_back({l[0],0});
            g[l[0]].push_back({r[0],0});
        }
    }
    int ans=1;
    for(int i=1;i<=n;i++){
        if(color[i]==-1){
            dfs(i,0);
            if(flag)return;
            (ans*=2)%=mod;
        }
    }
    cout<<ans<<endl;
}

I

每次暴力去找后面小于他的那一个的位置
复杂度好似5e7
实际只有3ms

void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    vector<PII>ans;
    for(int cnt=1;cnt<=n/2;cnt++){
        int i,j;
        for(i=1;i<=n;i++){
            for(j=n;j>=i+1;j--){
                if(a[i]>a[j]){
                    ans.push_back({i,j});
                    goto out;
                }
            }
        }
        out:
        sort(a.begin()+i,a.begin()+j+1);
    }
    cout<<ans.size()<<endl;
    for(auto [x,y]:ans)cout<<x<<' '<<y<<endl;
}

K

我们发现等差数列 公差恒为1
这样我们在输入的时候就可以-下标 就是来找一个数 让他们都相等 而不是等差数列就好求多了
然后发现具有单调性
二分是肯定的
check mid长度类是否有一个数让他们路径和<=k
这个数我们必然是选中位数的路径 肯定是最短的
然后就是权值线段树二分找中位数 以及 维护一些val cnt的计算路径和了

struct node{
    int l,r,v,cnt;
}tr[N<<2];
int n,m;
void pushup(int i){
    auto &u=tr[i],&l=tr[i<<1],&r=tr[i<<1|1];
    u.v=l.v+r.v;
    u.cnt=l.cnt+r.cnt;
}
void build(int i,int l,int r){
    tr[i].l=l,tr[i].r=r,tr[i].cnt=0,tr[i].v=0;
    if(l==r){
        return;
    }
    int mid=l+r>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    pushup(i);
}
void modify(int i,int x,int k,int k2){
    if(tr[i].l>=x&&tr[i].r<=x){
        auto &u=tr[i];
        u.v+=k;
        u.cnt+=k2;
        return;
    }
    if(tr[i].l>x||tr[i].r<x)return;
    if(tr[i<<1].r>=x)modify(i<<1,x,k,k2);
    if(tr[i<<1|1].l<=x)modify(i<<1|1,x,k,k2);
    pushup(i);
}
int query(int i,int f){
    if(tr[i].l==tr[i].r){
        return tr[i].l;
    }
    if(tr[i<<1].cnt>=f)return query(i<<1,f);
    else{
        return query(i<<1|1,f-tr[i<<1].cnt);
    }
}
PII query(int i,int l,int r){
    PII res={0,0};
    if(tr[i].l>=l&&tr[i].r<=r){
        auto &u=tr[i];
        return {u.v,u.cnt};
    }
    if(tr[i].l>r||tr[i].r<l)return res;
    if(tr[i<<1].r>=l){
        PII now= query(i<<1,l,r);
        res.first+=now.first;
        res.second+=now.second;
    }
    if(tr[i<<1|1].l<=r){
        PII now= query(i<<1|1,l,r);
        res.first+=now.first;
        res.second+=now.second;
    }
    return res;
}
void solve(){
    cin>>n>>m;
    vector<int>a(n+1);
    map<int,int>mp;
    vector<int>mpp(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]-=i;
        mp[a[i]]++;
    }
    int idx=0;
    for(auto [pos,w]:mp){
        ++idx;
        mp[pos]=idx;
        mpp[idx]=pos;
    }
    int ans=1;
    build(1,1,n);
    for(int i=1,j=i;i<=n&&j<=n;i++){
        while(j<=n) {
            modify(1, mp[a[j]], a[j], 1);
            int mid = j - i + 1;
            int z = mpp[query(1, up(mid, 2))];
//            cout<<i<<' '<<z<<endl;
            auto[lv, lcnt]=query(1, 1, mp[z]);
            auto[rv, rcnt]=query(1, mp[z] + 1, idx);
//            cout<<lcnt<<' '<<lv<<' '<<rcnt<<' '<<rv<<endl;
//            cout<<lcnt*z-lv+rv-rcnt*z<<' '<<m<<endl;
            if (lcnt * z - lv + rv - rcnt * z <= m){
                ans = max(ans, mid);
                j++;
            }else {
                modify(1, mp[a[i]], -a[i], -1);
                modify(1, mp[a[j]], -a[j], -1);
                break;
            }
        }
    }
    cout<<ans<<endl;
}