Educational Codeforces Round 67 (Rated for Div. 2)

略

记录每种字母的出现次数前缀和，然后p[i][j]表示字母j出现至少i次的最靠前的位置，然后直接搜取最大即为答案，O(26(n+m)+Σ|ti|)，差点想到二分去了，复杂度会多个log

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int n,s[N][26],p[N][26],sum[26];
char str[N];
int main()
{
    scanf("%d",&n);
    scanf("%s",str+1);
    for(int i=1;i<=n;i++)
    for(int j=0;j<26;j++)
    if(j==str[i]-'a')s[i][j]=s[i-1][j]+1;else s[i][j]=s[i-1][j];
    for(int i=1;i<=n;i++)
    for(int j=0;j<26;j++)
    p[i][j]=n+1;
    for(int i=1;i<=n;i++)
    for(int j=0;j<26;j++)
    p[s[i][j]][j]=min(p[s[i][j]][j],i);
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%s",str+1);
        for(int i=0;i<26;i++)sum[i]=0;
        int len=strlen(str+1),ans=0;
        for(int i=1;i<=len;i++)sum[str[i]-'a']++;
        for(int i=0;i<26;i++)ans=max(ans,p[sum[i]][i]);
        printf("%d
",ans);
    }
}

View Code

瞎构造一波即可。对于ti=0的直接覆盖，ti=1的代入检验。

#include<bits/stdc++.h>
using namespace std;
const int N=1007;
int n,m,cnt,now,R[N],a[N],b[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)R[i]=i;
    while(m--)
    {
        int op,x,y;scanf("%d%d%d",&op,&x,&y);
        if(op==1)
        {
            for(int i=x;i<=y;i++)R[i]=max(R[i],y);
        }
        else a[++cnt]=x,b[cnt]=y;
    }
    for(int i=n;i>=1;i--)R[i]=R[R[i]];
    for(int i=1;i<=cnt;i++)if(R[a[i]]>=b[i]){puts("NO");return 0;}
    puts("YES");
    now=n+1;
    for(int i=1;i<=n;i++)
    {
        printf("%d ",now);
        if(R[i]==i)now--;else now++;
    }
}

View Code

太难了，FST了一片，显然我也FST了。正解是这样的，首先判掉每种数个数不同的情况，然后接着判不可行的。对任意区间排序，等价于交换逆序对，然后扫描b数组，然后将a数组中等于b[i]的最左的数的位置j交换一下，然后判断a[i...j]是否存在<b[i]的数，存在则无解，反之，这个数将不会再用到，改成无穷大。显然可以用线段树维护。

#include<bits/stdc++.h>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const int N=3e5+7;
int n,m,a[N],b[N],n1[N],n2[N],mn[N<<2];
queue<int>q[N];
void build(int l,int r,int rt)
{
    if(l==r){mn[rt]=a[l];return;}
    int mid=l+r>>1;
    build(lson),build(rson);
    mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
void update(int k,int v,int l,int r,int rt)
{
    if(l==r){mn[rt]=v;return;}
    int mid=l+r>>1;
    if(k<=mid)update(k,v,lson);else update(k,v,rson);
    mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)return mn[rt];
    int mid=l+r>>1,ret=1e9;
    if(L<=mid)ret=min(ret,query(L,R,lson));
    if(R>mid)ret=min(ret,query(L,R,rson));
    return ret;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]),n1[i]=n2[i]=0;
        for(int i=1;i<=n;i++)scanf("%d",&b[i]);
        for(int i=1;i<=n;i++)n1[a[i]]++,n2[b[i]]++;
        bool flag=0;for(int i=1;i<=n;i++)if(n1[i]!=n2[i]){flag=1;break;}
        if(flag){puts("NO");continue;}
        for(int i=1;i<=n;i++)while(!q[i].empty())q[i].pop();
        build(1,n,1);
        for(int i=1;i<=n;i++)q[a[i]].push(i);
        for(int i=1;i<=n;i++)
        {
            int pos=q[b[i]].front(),tmp=query(1,pos,1,n,1);
            q[b[i]].pop();
            update(pos,1e9,1,n,1);
            if(tmp<b[i])flag=1; 
        }
        if(flag)puts("NO");else puts("YES");
    }
}

View Code

直接换根DP即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
typedef long long ll;
int n;
ll ans,sz[N],f[N];
vector<int>G[N];
void dfs(int u,int fa)
{
    sz[u]=1;
    for(int i=0;i<G[u].size();i++)if(G[u][i]!=fa)dfs(G[u][i],u),sz[u]+=sz[G[u][i]];
}
void dfs2(int u,int fa)
{
    for(int i=0;i<G[u].size();i++)if(G[u][i]!=fa)
    f[G[u][i]]=f[u]+n-2*sz[G[u][i]],dfs2(G[u][i],u);
}
int main()
{
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);
    dfs(1,0);
    for(int i=1;i<=n;i++)f[1]+=sz[i];
    dfs2(1,0);
    for(int i=1;i<=n;i++)ans=max(ans,f[i]);
    printf("%I64d",ans);
}

View Code

好神仙的一道期望题。身为菜鸡的我只会求E(B(x))

而E((B(x))²)=E((1+Σ[x_i≠x_i+1])²)=E(1+Σ_{1<=i,j<=n-1,i≠j}[x_i≠x_i+1][x_j≠x_j+1]+3Σ[x_i≠x_i+1])，然后根据期望的线性性直接做即可，其中Σ_{1<=i,j<=n-1,i≠j}[x_i≠x_i+1][x_j≠x_j+1]要注意，相邻的要一起算，否则是相互独立的。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7,mod=1e9+7;
int n,ans,l[N],r[N],a[N],b[N],c[N];
int qpow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)ret=1ll*ret*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return ret;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&l[i]);
    for(int i=1;i<=n;i++)scanf("%d",&r[i]),a[i]=r[i]-l[i]+1;
    for(int i=1;i<n;i++)
    {
        int L=max(l[i],l[i+1]),R=min(r[i],r[i+1]);
        if(L<=R)b[i]=1ll*(R-L+1)*qpow(1ll*a[i]*a[i+1]%mod,mod-2)%mod;
        ans=(ans+1-b[i])%mod;
    }
    for(int i=1;i<n-1;i++)
    {
        int L=max(l[i],max(l[i+1],l[i+2])),R=min(r[i],min(r[i+1],r[i+2]));
        if(L<=R)c[i]=1ll*(R-L+1)*qpow(1ll*a[i]*a[i+1]%mod*a[i+2]%mod,mod-2)%mod;
        ans=(ans+2*(mod*2ll+1-b[i]-b[i+1]+c[i]))%mod;
    }
    int sum=mod+1-b[1];
    for(int i=3;i<n;i++)ans=(ans+2ll*sum*(mod+1-b[i]))%mod,sum=(sum+mod+1-b[i-1])%mod;
    ans=(ans+1)%mod;
    for(int i=1;i<n;i++)ans=(ans+2ll*(mod-b[i])+2)%mod;
    printf("%d",ans);
}

View Code

不会写，咕咕咕

result：新号打的。rank53，rating=1754