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

cf375D Tree and Queries

昨天学了莫队算法,发现真的是很神奇,特别是简化版的,按sqrt(n)分块的算法,非常好写。这道题是佳神推荐的,发现确实很好,写下题解,大牛请直接关闭本页。。
题意:题目的意思是给你一棵树,每个节点都有一个正整数值。然后给你m个询问,每次询问你一棵子树中出现次数至少为kj次的数有多少个。题目中所有数都是<=10^5
思路:这题其实是前面写的树那题和分块那题的结合。首先dfs这棵树,得到dfs序。
于是问题转化为:给出一个长为n的序列,m个询问,每次询问[l,r]上有多少个数出现次数至少为qi次
这个问题可以这样:用一个数组cn[i],表示数i出现的次数。再用一个树状数组cc[],其中第i个元素表示出现次数为i次的数有几个。然后就是前面所讲的分块算法了,这在《莫队算法相关》这篇文章里讲过了。每次单步转移(也就是类似[l,r]->[l,r+1]的转移),需要更新cn[],时间是O(1),更新cc[],时间O(lgn).求解时计算getsum(n)-getsum(qi-1),时间为O(lgn).这样复杂度是O((n^1.5)lgn),n=1e5.算了一下大概在5*10^8左右。开始用线段树出现次数为x的数的个数,结果TLE,改成树状数组就过了,不过应该是数据不卡O((n^1.5)lgn)的原因,因为正解貌似是O(n^1.5)的。。待进一步思考
ps:del和insert的时候,少写了if,导致有时候一个数删去之后出现了0次,这时候对出现0次的数的个数+1,结果就出错了。。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=1e5+5;
typedef struct Edge{
    int to,next;
}Edge;
Edge edge[maxn*2];
int head[maxn],cnt;
bool visit[maxn];
int n,m,num;
int c[maxn],d[maxn];
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
typedef struct Node{
    int begin,end;
}Node;
Node node[maxn];
void dfs(int cur)
{
    visit[cur]=1;
    node[cur].begin=(++num);
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs(v);

    }
    node[cur].end=num;
    return;
}
typedef struct Q{
    int l,r,id,count,g;
}Q;
Q q[maxn];
int cn[maxn],ans[maxn];
bool cmp(Q a,Q b)
{
    if(a.g==b.g) return a.r<b.r;
    return a.g<b.g;
}
/**
int sum[maxn<<2];
void pushup(int id)
{
    sum[id]=sum[lson]+sum[rson];
}
void update(int id,int l,int r,int pos,int v)
{
    if(l==r)
    {
        sum[id]+=v;
        return;
    }
    int m=(l+r)/2;
    if(pos<=m) update(lson,l,m,pos,v);
    else update(rson,m+1,r,pos,v);
    pushup(id);
}
int query(int id,int l,int r,int L,int R)
{
    if(L<=l && r<=R) return sum[id];
    int m=(l+r)/2;
    int ret=0;
    if(L<=m) ret+=query(lson,l,m,L,R);
    if(R>m) ret+=query(rson,m+1,r,L,R);
    return ret;
}
**/
//树状数组部分
int cc[maxn];
int lowbit(int x)
{
	return x & -x;
}
void add2(int id,int x)
{
	for(int i=id;i<=n;i+=lowbit(i))
		cc[i]+=x;
	return;
}
int getsum(int x)
{
	int sum=0;
	for(int i=x;i>=1;i-=lowbit(i))
		sum+=cc[i];
	return sum;
}
//区间询问转移
void del(int x)
{
    if(cn[d[x]]) {add2(cn[d[x]],-1);cn[d[x]]--;}

    if(cn[d[x]]) add2(cn[d[x]],1);
}
void insert(int x)
{
    if(cn[d[x]]) add2(cn[d[x]],-1);
    cn[d[x]]++;
    if(cn[d[x]]) add2(cn[d[x]],1);
}

void scan(int &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    int i,j;
    int a,b;
    while(~scanf("%d%d",&n,&m))
    {
        num=cnt=0;
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        memset(cn,0,sizeof(cn));
        //memset(sum,0,sizeof(sum));
        memset(cc,0,sizeof(cc));
        for(i=1;i<=n;i++) scan(c[i]);
        for(i=1;i<=n-1;i++) {scan(a);scan(b);add(a,b);}
        dfs(1);
        for(i=1;i<=n;i++) d[node[i].begin]=c[i];
        int x,y;
        int len=(int)sqrt(n*1.0);
        for(i=1;i<=m;i++)
        {
            scan(x);scan(y);
            q[i].l=node[x].begin;
            q[i].r=node[x].end;
            q[i].id=i;
            q[i].count=y;
            q[i].g=q[i].l/len+1;
        }
        sort(q+1,q+1+m,cmp);
        int curl=0,curr=0;
        for(i=1;i<=m;i++)
        {
            int l=q[i].l,r=q[i].r;
            while(curr<r)
            {
                curr++;
                insert(curr);
            }
            while(curr>r)
            {
                del(curr);
                curr--;
            }
            while(curl<l)
            {
                if(curl) del(curl);
                curl++;
            }
            while(curl>l)
            {
                curl--;
                insert(curl);
            }
            if(q[i].count>n) ans[q[i].id]=0;
            else ans[q[i].id]=getsum(n)-getsum(q[i].count-1);
        }
        for(i=1;i<=m;i++) printf("%d\n",ans[i]);
    }
    return 0;
}
/*
10 1
82 48 59 48 32 83 34 46 47 79
2 1
3 1
4 3
5 4
6 1
7 2
8 3
9 2
10 2
4 1
*/