cf#369 div2

很久没做题了,昨天这场codeforces时间比较早就做了一下。A
A.Bus to Udayland x5233
签到题

#include<stdio.h>
#include<string.h>
char mat[1000+10][5];
int main()
{
    int i,j;
    int n;
    char tmp;
    while(~scanf("%d",&n))
    {
        getchar();
        bool flag=0;
        for(i=1;i<=n;i++)
        {
            scanf("%c%c%c%c%c",&mat[i][1],&mat[i][2],&tmp,&mat[i][3],&mat[i][4]);
            getchar();
            if(flag) continue;
            if((mat[i][1]=='O') && (mat[i][2]=='O'))
            {
                mat[i][1]='+';mat[i][2]='+';
                flag=1;
                continue;
            }
            if((mat[i][3]=='O') && (mat[i][4]=='O'))
            {
                mat[i][3]='+';mat[i][4]='+';
                flag=1;
                continue;
            }
        }
        if(!flag) {printf("NO\n");continue;}
        printf("YES\n");
        for(i=1;i<=n;i++)
            printf("%c%c|%c%c\n",mat[i][1],mat[i][2],mat[i][3],mat[i][4]);
    }
    return 0;
}

B.Chris and Magic Square x3112
也很简单

#include<stdio.h>
#include<string.h>
typedef long long ll;
ll a[510][510];
int main()
{
    int i,j;
    int n;
    while(~scanf("%d",&n))
    {
        int x,y;
        int flag=1;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                scanf("%I64d",&a[i][j]);
                if(!a[i][j]) {x=i,y=j;}
            }
        if(n==1) {printf("1\n");continue;}
        ll ans=-1,tmp=0;
        for(i=1;i<=n;i++)
        {
            if(i==x) continue;
            for(j=1;j<=n;j++) tmp+=a[i][j];
            if(ans==-1) {ans=tmp;tmp=0;continue;}

            if(tmp!=ans)
            {
                flag=0;
                break;
            }
            tmp=0;
        }
        if(!flag){printf("-1\n");continue;}
        tmp=0;
        for(j=1;j<=n;j++)
        {
            if(j==y) continue;
            for(i=1;i<=n;i++) tmp+=a[i][j];
            if(tmp!=ans)
            {
                flag=0;
                break;
            }
            tmp=0;
        }
        if(!flag){printf("-1\n");continue;}
        tmp=0;
        for(i=1;i<=n;i++) tmp+=a[i][y];
        ll ret1=ans-tmp;
        tmp=0;
        for(j=1;j<=n;j++) tmp+=a[x][j];
        ll ret2=ans-tmp;
        if(ret1!=ret2 || ret1<1){printf("-1\n");continue;}
        a[x][y]=ret1;
        ll c1=0,c2=0;
        for(i=1;i<=n;i++) c1+=a[i][i],c2+=a[i][n+1-i];
        if(c1!=c2 || c1!=ans) {printf("-1\n");continue;}
        printf("%I64d\n",ret1);
    }
    return 0;
}

C.Coloring Trees x1710
题意:有一排树。每棵树有一种颜色或者还没被涂色,如果一棵树原本就有颜色,那么不能改色,只有没被上色的树可以涂颜色。相邻且颜色相同的树属于同一组。p[i][j]表示将第i棵树涂成颜色j的代价。问:通过上色将这些树分成k组的最小代价是多少?
树的数量、颜色的数量均<=100
序列?分组?最优解?直接往dp上去想
dp[i][j][t]表示将前i个分成t组且第i个涂成颜色j的最小代价。
转移如下:
(1)如果第i个是已经有颜色,且颜色为a[i]
dp[i][a[i]][t]=min(dp[i-1][a[i]][t],min of dp[i-1][not a[i]][t-1])(注意t==1时后一项时没有的)
(2)如果第i个没有颜色
dp[i][j][t]=min(dp[i-1][j][t],min of dp[i-1][not j][t-1])+p[i][j];
初始化dp[1][j][1]时也要如上分类讨论,其余初始化为inf。
时间复杂度O(n*m*n*n), 大概10^8数量级,能过。。。
这题耗费了比较多的时间,现在熟练度下降很多~

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll inf=100000000000000000LL;
int n,m,k,t,s;
ll dp[110][110][110],p[110][110];
int a[110];
ll min(ll a,ll b){return a<b?a:b;}
int main()
{
    int i,j;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%I64d",&p[i][j]);
        if(k>n){printf("-1\n");continue;}
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                for(t=1;t<=n;t++)
                    dp[i][j][t]=inf;
        if(a[1]!=0)
        {
            dp[1][a[1]][1]=0;
        }
        else
        {
            for(i=1;i<=m;i++)
                dp[1][i][1]=p[1][i];
        }
        for(i=2;i<=n;i++)
            for(j=1;j<=m;j++)
                for(t=1;t<=k;t++)
                {
                    if(a[i]!=0)
                    {
                        if(j!=a[i]) continue;
                        ll tmp=inf;
                        dp[i][a[i]][t]=dp[i-1][a[i]][t];
                        if(t>1){
                            for(s=1;s<=m;s++)
                            {
                                if(s==a[i]) continue;
                                if(dp[i-1][s][t-1]<tmp) tmp=dp[i-1][s][t-1];
                            }
                        }
                        dp[i][a[i]][t]=min(dp[i][a[i]][t],tmp);
                        continue;
                    }
                    ll tmp=inf;
                    dp[i][j][t]=dp[i-1][j][t]+p[i][j];
                    if(t>1)
                    {
                        for(s=1;s<=m;s++)
                        {
                            if(s==j) continue;
                             if(dp[i-1][s][t-1]+p[i][j]<tmp) tmp=dp[i-1][s][t-1]+p[i][j];
                        }
                    }
                    dp[i][j][t]=min(dp[i][j][t],tmp);
                }
        ll ans=inf;
        for(i=1;i<=m;i++)
            ans=min(ans,dp[n][i][k]);
        if(ans<inf) printf("%I64d\n",ans);
        else printf("-1\n");
    }
    return 0;
}

D.Directed Roads x948
这题其实比上一题简单,个人感觉。
n个点,n条边。没有圈(自环)。每条弧可以反向,问有多少种将边反向的方案可以使得图没有环,两个方案不同当且仅当两个方案中至少存在一条不同的弧。
n<=2*10^5
容易想到对于一个环中的弧,只要不全部反向或者一条弧都不反向,其它方案都可以去掉改环。所以方案数是(2^len)-2.len 是环中弧的数量。
对于不在环中的弧,选不选无所谓,所以针对这些弧,所有方案都行, 方案数是2^k.k是这类弧的数量。最后乘法原理。
最后答案:∏((2^len)-2)*(2^k)
∏ 表示连乘
可见最后是一个简单的快速幂模mod

-_-#速度太慢了,这题没来得及submit。。。

#include<stdio.h>
#include<string.h>
typedef long long ll;
const int mod=(1e9)+7;
int n;
int a[200000+10];
int order[200000+10];
ll cal(int k)
{
    ll ans=1,p=2;
    while(k)
    {
        if(k%2)
        {
            ans=(ans*p)%mod;
            k--;
        }
        p=(p*p)%mod;
        k/=2;
    }
    return ans;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        memset(order,0,sizeof(int)*(n+5));
        int cnt=0;
        ll ans=1;
        int m=n;
        for(i=1;i<=n;i++)
        {
            if(order[i]) continue;
            j=i;
            int end=cnt+1;
            while(!order[j])
            {
                //printf("%d ",j);
                order[j]=++cnt;
                end=order[j];
                j=a[j];
            }
            if(order[j]<order[i]) continue;
            int len=end-order[j]+1;
            //printf("%d\n",len);
            m-=len;
            ans=(ans*((cal(len)-2+mod)%mod))%mod;
        }
        ans=(ans*cal(m))%mod;
        printf("%I64d\n",ans);

    }
    return 0;
}

E.ZS and The Birthday Paradox x241