cf1187解题报告

cf

A

去掉都有的,剩下的取最大值+1

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    int T;
    cin>>T;
    while(T--) {
        int n,s,t;
        cin>>n>>s>>t;
        int k=s+t-n;
        s-=k,t-=k;
        int ans=max(s,t)+1;
        cout<<ans<<"\n";
    }   
    return 0;
}

B

有点笨的办法，每个字母分别二分，得到的最大值是答案。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=4e5+7;
int n,m,sum[N][26],tong[26];
char s[N];
int main() {
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;++i) {
        for(int j=0;j<26;++j) sum[i][j]=sum[i-1][j];
        sum[i][s[i]-'a']++;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;++i) {
        scanf("%s",s+1);
        int len=strlen(s+1),ans=0;
        for(int j=0;j<26;++j) tong[j]=0;
        for(int j=1;j<=len;++j) tong[s[j]-'a']++;
        for(int j=0;j<26;++j) {
            int l=1,r=n,tmp=0;
            while(l<=r) {
                int mid=(l+r)>>1;
                if(sum[mid][j]>=tong[j]) tmp=mid,r=mid-1;
                else l=mid+1;
            }
            ans=max(ans,tmp);
        }
        printf("%d\n",ans);
    }
    return 0;
}

C

1的区间是相同的个数，能降就降，最后check。
wrong了几发：先n^2判断包含判断NO,然后直接YES,显然是错的。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int read() {int x;cin>>x;return x;}
int n,m;
vector<pair<int,int> > a[2];
int vis[N],ans[N];
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i) {
        int opt=read(),l=read(),r=read();
        a[opt].push_back(make_pair(l,r));
    }
    sort(a[0].begin(),a[0].end());
    sort(a[1].begin(),a[1].end());
    for(int i=1;i<=n;++i) ans[i]=1;
    int js=n<<1,l=0;
    for(auto i:a[1]) {
        if(i.second<=l) continue;
        if(i.first>l) {js--;for(int j=l+1;j<i.first;++j) ans[j]=js--;}
        for(int j=i.first;j<=i.second;++j) ans[j]=js;
        l=max(i.second,l);
    }
    while(l+1<=n) ans[++l]=--js;
    for(auto i:a[0]) {
        int flag=0;
        for(int j=i.first+1;j<=i.second;++j)
            if(ans[j]!=ans[j-1]) flag=1;
        if(!flag) return puts("NO"),0;
    }
    printf("YES\n");
    for(int i=1;i<=n;++i) cout<<ans[i]<<" ";
    return 0;
}

D

我感觉D和E反了。
一开始：前后的数字的前面的大于他的相对位置不变。
正确：和一开始差不多？类似冒泡，依次把\(b_i\)的对应的\(a_j\)挪过来，挪的过程中当然是只能和最大的挪。
是区间的最小值。用线段树维护。

#include <bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int N=3e5+7;
int T,n,a[N],b[N];
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
namespace seg {
    int mi[N<<2];
    void build(int l,int r,int rt) {
        if(l==r) return mi[rt]=a[l],void();
        int mid=(l+r)>>1;
        build(l,mid,ls);
        build(mid+1,r,rs);
        mi[rt]=min(mi[ls],mi[rs]);
    }
    int query(int l,int r,int L,int R,int rt) {
        if(L<=l&&r<=R) return mi[rt];
        int mid=(l+r)>>1;
        if(L<=mid&&R>mid) return min(query(l,mid,L,R,ls),query(mid+1,r,L,R,rs));
        else if(L<=mid) return query(l,mid,L,R,ls);
        else return query(mid+1,r,L,R,rs);
    }
    void modify(int L,int l,int r,int rt) {
        if(l==r) return mi[rt]=0x3f3f3f3f,void();
        int mid=(l+r)>>1;
        if(L<=mid) modify(L,l,mid,ls);
        else modify(L,mid+1,r,rs);
        mi[rt]=min(mi[ls],mi[rs]);
    }
}
vector<int> T_T[N],OwO[N];
int pos[N];
void solve() {
    n=read();
    for(int i=1;i<=n;++i) T_T[i].clear(),OwO[i].clear();
    for(int i=1;i<=n;++i) a[i]=read(),T_T[a[i]].push_back(i);
    for(int i=1;i<=n;++i) b[i]=read(),OwO[b[i]].push_back(i);
    for(int i=1;i<=n;++i) if(T_T[i].size()!=OwO[i].size()) return puts("NO"),void();
    for(int i=1;i<=n;++i) pos[i]=0;
    seg::build(1,n,1);
    for(int i=1;i<=n;++i) {
        int r=T_T[b[i]][pos[b[i]]++];
        if(seg::query(1,n,1,r,1)<b[i]) return puts("NO"),void();
        seg::modify(r,1,n,1);
    }
    return puts("YES"),void();
}
int main() {
    T=read();
    while(T--) solve();
    return 0;
}

E

题目大意：给你一棵白色树，每次选个和黑点的白点，加上他所在白色联通块的贡献，然后染黑。初始点任选。
先求出任意一个点的贡献。然后考虑换根就行了。
\(f[u]=f[v]+n-siz[v]*2\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+7;
vector<int> G[N];
int n,siz[N],f[N];
void dfs1(int u,int fa) {
    siz[u]=1;
    for(auto v:G[u]) {
        if(v==fa) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
    }
    f[1]+=siz[u];
}
void dfs2(int u,int fa) {
    for(auto v:G[u]) {
        if(v==fa) continue;
        f[v]=f[u]+n-siz[v]-siz[v];
        dfs2(v,u);
    }
}
signed main() {
    scanf("%lld",&n);
    for(int i=1,u,v;i<n;++i) {
        scanf("%lld%lld",&u,&v);
        G[u].push_back(v),G[v].push_back(u);
    }
    dfs1(1,0),dfs2(1,0);
    int ans=0;
    for(int i=1;i<=n;++i) ans=max(ans,f[i]);
    printf("%lld\n",ans);
    return 0;
}