首页 > 代码库 > Codeforces Round #369 (Div. 2) ABCD

Codeforces Round #369 (Div. 2) ABCD

A. Bus to Udayland

题解:

水,看样例就知道题意了

代码:

#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x))  #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 #define INF 1e9typedef pair<int,int> P;const double eps=1e-9;const int maxnnode=11000;const int maxn=100100;const int mod=20071027;string line[1010];int main(){    int n;    cin>>n;    for(int i=1;i<=n;i++) cin>>line[i];    int flag=0;    for(int i=1;i<=n;i++)    {        if(line[i][0]==O&&line[i][1]==O){            flag=1;            line[i][0]=+;            line[i][1]=+;            break;        }        if(line[i][3]==O&&line[i][4]==O){            flag=1;            line[i][3]=+;            line[i][4]=+;            break;        }    }    if(!flag) cout<<"NO"<<endl;    else{        cout<<"YES"<<endl;        for(int i=1;i<=n;i++) cout<<line[i]<<endl;    }}

 

B.Chris and Magic Square

题解:

水,模拟题,注意n=1的情况,还有不能为负

代码:

#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x))  #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 #define INF 1e9typedef pair<int,int> P;const double eps=1e-9;const int maxnnode=11000;const int maxn=100100;const int mod=20071027;ll m[505][505];ll sum1[505],sum2[505],sum3[3];int main(){    int n,x0,y0;    cin>>n;    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++)        {            cin>>m[i][j];            if(m[i][j]==0)            {                x0=i;y0=j;            }         }    }    if(n==1){        cout<<1<<endl;        return 0;    }    for(int i=1;i<=n;i++)    for(int j=1;j<=n;j++) sum1[i]+=m[i][j];    for(int i=1;i<=n;i++)    for(int j=1;j<=n;j++) sum2[i]+=m[j][i];    for(int i=1;i<=n;i++)    {        sum3[1]+=m[i][i];        sum3[2]+=m[n+1-i][i];    }    int flag=0;    ll tmp;    for(int i=1;i<=n;i++)    {        if(x0!=i)         {            tmp=sum1[i];            break;        }    }    for(int i=1;i<=n;i++){        if(i==x0) continue;        if(sum1[i]!=tmp) {            flag=1;            break;        }    }    for(int i=1;i<=n;i++){        if(i==y0) continue;        if(sum2[i]!=tmp) {            flag=1;            break;        }    }    for(int i=1;i<=2;i++){        if(x0==y0&&i==1) continue;        if(x0+y0==n+1&&i==2) continue;        if(sum3[i]!=tmp)        {            flag=1;            break;        }    }    if(flag) cout<<-1<<endl;    else{        ll x;        x=tmp-sum1[x0];        if(x<=0) flag=1;        else{            if(sum2[y0]+x!=tmp) flag=1;            else{                if(x0==y0)    if(sum3[1]+x!=tmp) flag=1;                if(x0+y0==n+1) if(sum3[2]+x!=tmp) flag=1;            }        }        if(flag) cout<<-1<<endl;        else     cout<<x<<endl;    }        return 0;}

 

C. Coloring Trees

题解:

给你n个位置,每个位置可以涂m种颜色.a[i]=0表示未涂,可以涂1-m种颜色,否则表示已图

每个位置涂不同颜色的花费不同,要求将为0的位置全部涂色,连续相同的算一组,正好分成k组的最少费用

dp[i][j][k]表示前i个位置,第i个位置为颜色j,分为k组的最少费用

代码:

#include<bits/stdc++.h>using namespace std;#define ll long longconst int N=108;const ll M=1000000000008ll;ll n,m,tar,w[N][N],a[N];ll f[N][N][N];int main(void){    ll i,j,k,p;    scanf("%I64d%I64d%I64d",&n,&m,&tar);    for(i=1;i<=n;i++)scanf("%I64d",a+i);    for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%I64d",&w[i][j]);    for(i=1;i<=n;i++)    for(j=1;j<=m;j++)    for(k=0;k<=tar;k++)f[i][j][k]=M;    if(a[1])f[1][a[1]][1]=0;    else{for(j=1;j<=m;j++)f[1][j][1]=w[1][j];}    for(i=2;i<=n;i++)    if(a[i])    {        for(j=1;j<=tar;j++)        for(k=1;k<=m;k++)f[i][a[i]][j]=min(f[i][a[i]][j],f[i-1][k][j-((k==a[i])?0:1)]);    }    else    {        for(p=1;p<=m;p++)        for(j=1;j<=tar;j++)        for(k=1;k<=m;k++)f[i][p][j]=min(f[i][p][j],f[i-1][k][j-((k==p)?0:1)]+w[i][p]);    }    k=f[n][1][tar];    for(i=2;i<=m;i++)k=min(k,f[n][i][tar]);    if(k==M)cout<<-1;    else cout<<k;    return 0;}

 

D. Directed Roads

题解:

在训练指南上面抄了份有向图强连通分量的模板。。

然后水过了

代码:

#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x))  #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 #define INF 1e9typedef pair<int,int> P;const double eps=1e-9;const int maxnnode=11000;const int maxn=2*100000+10;const ll mod=1000000007;int p[maxn];int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;stack<int> S;int cnt[maxn];void dfs(int u){    pre[u]=lowlink[u]=++dfs_clock;    S.push(u);    int v=p[u];    if(!pre[v]){        dfs(v);        lowlink[u]=min(lowlink[u],lowlink[v]);    }else if(!sccno[v]){        lowlink[u]=min(lowlink[u],pre[v]);    }    if(lowlink[u]==pre[u]){        scc_cnt++;        for(;;){            int x=S.top();S.pop();            sccno[x]=scc_cnt;            if(x==u) break;        }    }}void Find_scc(int n){    dfs_clock=scc_cnt=0;    for(int i=1;i<=n;i++) if(!pre[i]) dfs(i);}ll quickmod(ll a,ll b){    ll ans=1;    while(b){        if(b&1){            ans=(ans*a)%mod;            b--;        }        b/=2;        a=a*a%mod;    }    return ans;}int main(){    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d",&p[i]);    Find_scc(n);    for(int i=1;i<=n;i++) cnt[sccno[i]]++;    ll ans=1;    for(int i=1;i<=n;i++){           if(cnt[i]==0) continue;           ll sum=0;           sum+=quickmod(2,cnt[i]);           sum%=mod;           if(cnt[i]>1)           {               sum+=mod;               sum-=2;               sum%=mod;       }       ans*=sum;       ans%=mod;    }        cout<<ans<<endl;}

 

Codeforces Round #369 (Div. 2) ABCD