Educational Codeforces Round 115 (Rated for Div. 2) 部分简要题解

A

根据题面描述不难发现:若当前在第\(i\)列的某个空格上,只要第\(i+1\)列存在空格,就一定可以跳到这个空格上。只需要判断每行是否有空格子即可。

int n;
char s[3][N];

int main()
{
    int T=read();
    while (T--)
    {
        n=read();int ans=1;
        rep(i,1,2) scanf("%s",s[i]+1);
        rep(i,1,n) if ((s[1][i]=='1') && (s[2][i]=='1')) ans=0;
        if (ans) puts("YES");else puts("NO");
    }
    return 0;
}

B

枚举两门课分别在什么时候上,所有的人可以按照每门课是否有时间被分为四类,分别记为\(c_{00},c_{01},c_{10},c_{11}\)(其中0表示没有时间),那么只要\(c_{00}=0,c_{01}\leq n,c_{10}\leq n\)即可,\(c_{01}\)与\(c_{10}\)不足\(n\)的部分可以由\(c_{11}\)补上。

int n,a[N][6];

int main()
{
    int T=read();
    while (T--)
    {
        n=read();
        rep(i,1,n) rep(j,1,5) a[i][j]=read();
        if (n&1) {puts("NO");continue;}
        int ans=0;
        rep(i,1,5) rep(j,i+1,5)
        {
            int ok=1,c1=0,c2=0,c3=0;
            rep(k,1,n)
            {
                if ((a[k][i]) && (a[k][j])) c1++;
                else if ((!a[k][i]) && (a[k][j])) c2++;
                else if ((a[k][i]) && (!a[k][j])) c3++;
                else {ok=0;break;}
            }
            if ((ok) && (c2<=n/2) && (c3<=n/2)) {ans=1;break;}
        }
        if (ans) puts("YES");else puts("NO");
    }
    return 0;
}

C

不难发现删去的这两个数的和为定值,开个桶之后直接算答案就可以了。

int n,a[N];
map<int,int> mp;

int main()
{
    int T=read();
    while (T--)
    {
        n=read();mp.clear();
        ll sum=0;
        rep(i,1,n) {a[i]=read();sum+=a[i];mp[a[i]]++;}
        if ((sum*2)%n) {puts("0");continue;};
        ll g=sum*2/n;
        ll ans=0;
        rep(i,1,n)
        {
            ans+=mp[g-a[i]];
            if (g-a[i]==a[i]) ans--;
        }
        printf("%lld\n",ans/2);
    }
    return 0;
}

D

考虑用总数减去不合法的情况。把所有的\((a_i,b_i)\)当成二维坐标轴上的点,由于不存在相同的\((a_i,b_i)\),所以一个方案不合法当且仅当这三个点构成了"L"形。枚举中间的拐点,通过二分或其它手段算出在拐点上下左右有多少个点,然后用乘法原理乘一乘就可以了。

#define pbk push_back

int n,a[N],b[N];
vi pa[N],pb[N];

int main()
{
    int T=read();
    while (T--)
    {
        n=read();
        rep(i,1,n) 
        {
            a[i]=read();b[i]=read();
            pa[a[i]].pbk(b[i]);
            pb[b[i]].pbk(a[i]);
        }
        ll ans=1ll*n*(n-1)*(n-2)/6;
        rep(i,1,n)
        {
            int p1=lower_bound(pa[a[i]].begin(),pa[a[i]].end(),b[i])-pa[a[i]].begin(),
                p2=lower_bound(pb[b[i]].begin(),pb[b[i]].end(),a[i])-pb[b[i]].begin();
            int s1=pa[a[i]].size(),s2=pb[b[i]].size();
            ll a1=p1,b1=p2,a2=s1-p1-1,b2=s2-p2-1;
            ans-=(a1*b1+a2*b1+a1*b2+a2*b2);
        }
        printf("%lld\n",ans);
        rep(i,1,n)
        {
            pa[a[i]].clear();
            pb[b[i]].clear();
        }
    }
    return 0;
}

E

首先各凭本事算一下空白的\(n\times m\)方格里有多少合法路径。

每次将一个格子的状态翻转时,考虑影响到的路径条数:这样的路径一定会经过这个点。把影响到的路径根据这个点拆成前后两部分,前半部分和后半部分的数量分别可以通过bfs得到。之后再算出两个部分拼起来的路径数即可。

int n,m,q,ban[N][N];
ll f[N][N][2];

int query(int x,int y,int op1,int d)
{
    int ans=1;
    while (1)
    {
        if (op1) y+=d;else x+=d;
        if ((x>=1) && (x<=n) && (y>=1) && (y<=m) && (!ban[x][y]))
        {
            ans++;op1^=1;
        }
        else return ans;
    }
}

int main()
{
    n=read();m=read();q=read();
    ll ans=0;
    rep(i,1,n) rep(j,1,m)
    {
        f[i][j][0]=f[i-1][j][1]+1;
        f[i][j][1]=f[i][j-1][0]+1;
        ans+=(f[i][j][0]+f[i][j][1]-1);
    }
    while (q--)
    {
        int x=read(),y=read();
        int a1=query(x,y,0,-1),b1=query(x,y,1,-1),  
            a2=query(x,y,0,1),b2=query(x,y,1,1);
        ban[x][y]^=1;
        int now=a1*b2+a2*b1-1;
        if (ban[x][y]) ans-=now;
        else ans+=now;
        printf("%lld\n",ans);
    }
    return 0;
}

F

不知道为啥\(O(n2^n\log s_i)\)在cf上跑的飞快/wul

任意的括号序列通过不断消去匹配括号,最终可以形成))…)((…(的形式,根据括号个数可以用一个二元组\((a,b)\)表示。对于每一个括号序列,预处理出每个前缀对应的二元组(这个显然),和从当前下标开始的后缀中有多少个合法前缀(利用类似dp的思想,每次找一个最短的合法前缀跳过去),之后会用上。

看见\(n\)这么小考虑状压dp:记\(f_{S}\)为使用\(S\)中元素组成括号序列的答案。转移时枚举最终的括号序列中最后的元素\(i\),注意到如果一个序列存在未匹配的),那么无论在它的后面接上啥序列都不可能再构成合法前缀,因此对\(S\setminus \{i\}\)所构成的括号序列对应的二元组\((a,b)\)可以被唯一确定下来,之后利用这个二元组便可以找到\(s_i\)的最短前缀使得加上这个前缀后的括号序列都是合法序列(利用预处理的前缀二元组)。综上,加上\(s_i\)后给当前括号序列带来的贡献就是\(1+s_i\)的一个后缀的合法前缀数量(这个也是预处理过的)。同时,如果在加上了\(s_i\)后的串出现了未匹配的),那么这个串之后无论怎么添加括号都不会出现新的合法前缀,但是由于这么加可能产生最终答案所以还是要记下来。

具体的实现由于是赛时写的+好久没写代码可能有一些丑陋,dp数组记了两维表示当前括号序列能否继续添加后缀时的答案,同时转移为了好写用了map所以这东西是咋跑过去的

pii L=mkp(0,1),R=mkp(1,0),emp=mkp(0,0);
pii operator +(pii a,pii b)
{
    pii c;
    c.fir=a.fir;c.sec=b.sec;
    if (a.sec<b.fir) c.fir+=b.fir-a.sec;
    else c.sec+=a.sec-b.fir;
    return c;
}

int n,f[(1<<20)+10][2],len[N];
pii sum[(1<<20)+10];
vi g[N];
vector<pii> a[N];
map<pii,int> mp[N],mmp;
char s[M];

int main()
{
    n=read();
    rep(i,1,n)
    {
        scanf("%s",s+1);
        int m=strlen(s+1);len[i]=m;
        a[i].resize(m+2);
        a[i][0]=emp;
        rep(j,1,m)
        {
            pii op;
            if (s[j]=='(') op=L;else op=R;
            a[i][j]=a[i][j-1]+op;
            if (!mp[i].count(a[i][j])) mp[i][a[i][j]]=j;
        }
        g[i].resize(m+2);
        pii now=emp;mmp.clear();
        mmp[emp]=m+1;
        per(j,m,1)
        {
            pii op;
            if (s[j]=='(') op=L;else op=R;
            now=op+now;
            if ((s[j]=='(') && (mmp.count(now)))
            {
                int p=mmp[now];
                g[i][j]=g[i][p]+1;
            }
            mmp[now]=j;
        }
    }
    rep(pre,0,(1<<n)-1)
    {
        rep(i,1,n)
        {
            if ((pre>>(i-1))&1) continue;
            int now=pre^(1<<(i-1));
            sum[now]=sum[pre]+a[i][len[i]];
            int mn=min(sum[now].fir,sum[now].sec);
            sum[now].fir-=mn;sum[now].sec-=mn;
        }
    }
    memset(f,-0x3f,sizeof(f));
    f[0][0]=0;
    rep(pre,0,(1<<n)-1)
    {
        if (sum[pre].fir) continue;
        rep(i,1,n)
        {
            if ((pre>>(i-1))&1) continue;
            int sta=pre^(1<<(i-1));
            pii goal=sum[pre];swap(goal.fir,goal.sec);
            int tmp=f[pre][0];
            if (mp[i].count(goal))
            {
                tmp++;
                int pos=mp[i][goal];
                tmp+=g[i][pos+1];
            }
            pii now=sum[pre]+a[i][len[i]];
            if (now.fir) f[sta][1]=max(f[sta][1],tmp);
            else f[sta][0]=max(f[sta][0],tmp);
        }
    }
    int ans=0;
    rep(i,0,(1<<n)-1) rep(j,0,1) ans=max(ans,f[i][j]);
    printf("%d",ans);
    return 0;
}
上一篇:P4053 [JSOI2007]建筑抢修


下一篇:一些铜牌题