Codeforces Round #369 (Div. 2) 套题

A：模拟水题不说

#include <iostream>

#include <string.h>

#include <algorithm>

#include <stdio.h>

#include <math.h>

#include <bitset>

using namespace std;

typedef long long LL;

const int N= 1e3+;

char s[N][];

int main(){

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;++i)scanf("%s",s[i]+);

      bool flag=false;

    for(int i=;i<=n;++i){

      if(s[i][]==s[i][]&&s[i][]=='O'){

         flag=true;

         s[i][]=s[i][]='+';

         break;

      }

      if(s[i][]==s[i][]&&s[i][]=='O'){

         flag=true;

         s[i][]=s[i][]='+';

         break;

      }

    }

    if(flag)printf("YES\n");

    else printf("NO\n");

    if(flag)

      for(int i=;i<=n;++i)printf("%s\n",s[i]+);

    return ;

}

B：n*n的方阵，只有一个位置是未填数的，然后问填数以后，行和列和主副对角线和相等
O(n^2)模拟即可（这题FST了，由于输出格式不太对，对了这个也许能上更多分吧）

#include <iostream>

#include <string.h>

#include <algorithm>

#include <stdio.h>

#include <math.h>

#include <bitset>

using namespace std;

typedef long long LL;

const int N= 5e2+;

LL a[N][N];

int main(){

    int n,x,y;

    scanf("%d",&n);

    for(int i=;i<=n;++i){

      for(int j=;j<=n;++j){

        scanf("%I64d",&a[i][j]);

        if(a[i][j]==){

          x=i;

          y=j;

        }

      }

    }

    if(n==){

      printf("1\n");

      return ;

    }

    LL sum=;

    if(x==)

      for(int i=;i<=n;++i)sum+=a[][i];

    else

      for(int i=;i<=n;++i)sum+=a[][i];

    LL ret=-;

    for(int i=;i<=n;++i){

      LL tmp=;

      for(int j=;j<=n;++j)

        tmp+=a[i][j];

      if(i==x){

        if(tmp<sum){

          if(ret!=-&&ret!=sum-tmp){

            printf("-1\n");

            return ;

          }

          else ret=sum-tmp;

        }

        else {

          printf("-1\n");

          return ;

        }

      }

      else{

        if(sum!=tmp){

          printf("-1\n");

          return ;

        }

      }

    }

    for(int j=;j<=n;++j){

      LL tmp=;

      for(int i=;i<=n;++i)

        tmp+=a[i][j];

      if(j==y){

        if(tmp<sum){

          if(ret!=-&&ret!=sum-tmp){

            printf("-1\n");

            return ;

          }

          else ret=sum-tmp;

        }

        else {

          printf("-1\n");

          return ;

        }

      }

      else{

        if(sum!=tmp){

          printf("-1\n");

          return ;

        }

      }

    }

    LL tmp=;

    for(int i=;i<=n;++i)tmp+=a[i][i];

    if(x==y){

      if(tmp<sum){

          if(ret!=-&&ret!=sum-tmp){

            printf("-1\n");

            return ;

          }

          else ret=sum-tmp;

        }

        else {

          printf("-1\n");

          return ;

        }

    }

     else{

        if(sum!=tmp){

          printf("-1\n");

          return ;

        }

      }

    tmp=;

    for(int i=;i<=n;++i)tmp+=a[i][n+-i];

      if(x+y==n+){

      if(tmp<sum){

          if(ret!=-&&ret!=sum-tmp){

            printf("-1\n");

            return ;

          }

          else ret=sum-tmp;

        }

        else {

          printf("-1\n");

          return ;

        }

    }

     else{

        if(sum!=tmp){

          printf("-1\n");

          return ;

        }

      }

      printf("%I64d\n",ret);

    return ;

}

C：赛场上写了个裸的O(n^4)的dp，dp[i][j][k]代表当前是第i个数，这个数是j，分成k块的最小值
由于是时限是2s，而且是CF评测机，不虚

#include <iostream>

#include <string.h>

#include <algorithm>

#include <stdio.h>

#include <math.h>

#include <bitset>

using namespace std;

typedef long long LL;

const int N= 1e2+;

LL dp[N][N][N];

LL p[N][N];

int a[N];

int main(){

  int n,m,k;

  scanf("%d%d%d",&n,&m,&k);

  for(int i=;i<=n;++i)scanf("%d",&a[i]);

  for(int i=;i<=n;++i){

    for(int j=;j<=m;++j)

     scanf("%I64d",&p[i][j]);

  }

  memset(dp,-,sizeof(dp));

  if(a[]!=)dp[][a[]][]=;

  else{

    for(int i=;i<=m;++i)

      dp[][i][]=p[][i];

  }

  for(int i=;i<=n;++i){

    int lim=min(k,i);

    if(a[i]!=){

      for(int j=;j<=lim;++j){

        for(int c=;c<=m;++c){

          if(dp[i-][c][j-]!=-&&a[i]!=c){

            if(dp[i][a[i]][j]==-)dp[i][a[i]][j]=dp[i-][c][j-];

            else dp[i][a[i]][j]=min(dp[i][a[i]][j],dp[i-][c][j-]);

          }

          if(dp[i-][c][j]!=-&&a[i]==c)

            if(dp[i][a[i]][j]==-)dp[i][a[i]][j]=dp[i-][c][j];

            else dp[i][a[i]][j]=min(dp[i][a[i]][j],dp[i-][c][j]);

        }

      }

      continue;

    }

    for(int x=;x<=m;++x){

      for(int j=;j<=lim;++j){

        for(int c=;c<=m;++c){

          if(dp[i-][c][j-]!=-&&x!=c){

            if(dp[i][x][j]==-)dp[i][x][j]=dp[i-][c][j-]+p[i][x];

            else dp[i][x][j]=min(dp[i][x][j],dp[i-][c][j-]+p[i][x]);

          }

          if(dp[i-][c][j]!=-&&x==c)

            if(dp[i][x][j]==-)dp[i][x][j]=dp[i-][c][j]+p[i][x];

            else dp[i][x][j]=min(dp[i][x][j],dp[i-][c][j]+p[i][x]);

        }

      }

    }

  }

  LL ret=-;

  for(int i=;i<=m;++i)

    if(dp[n][i][k]!=-){

      if(ret==-)ret=dp[n][i][k];

      else ret=min(ret,dp[n][i][k]);

    }

  printf("%I64d\n",ret);

  return ;

}

D：这种题很常见，有向环套树，看每个环的反转方案，是2^k-2（k是边数，必须翻一个，不能全翻）
剩下的树上的边翻不翻都可以是2^tot,tot代表树边，然后都乘起来即可

#include <iostream>

#include <string.h>

#include <algorithm>

#include <stdio.h>

#include <math.h>

#include <bitset>

using namespace std;

typedef long long LL;

const int N = 2e5+;

const LL mod = 1e9+;

int to[N],n;

int vis[N];

LL qpow(LL x,LL y){

  LL ret=;

  while(y){

    if(y&)ret=ret*x%mod;

    y>>=;

    x=x*x%mod;

  }

  return ret;

}

int main(){

  scanf("%d",&n);

  for(int i=;i<=n;++i)scanf("%d",&to[i]);

  LL z=n,ret=;

  for(int i=;i<=n;++i){

    if(vis[i])continue;

    int x=i;

    while(!vis[x]){

      vis[x]=i;

      x=to[x];

    }

    if(vis[x]!=i)continue;

    int t=x,cnt=;

    do{

      ++cnt;

      t=to[t];

    }while(t!=x);

    z-=cnt;

    ret=1ll*ret*((qpow(,cnt)-+mod)%mod)%mod;

  }

  ret=ret*qpow(,z)%mod;

  printf("%I64d\n",ret);

  return ;

}

E：考虑正难则反，概率等于1-A(k,2^n)/2^(nk)，然后发现最大公约数只能是2^i，约分即可

#include <iostream>

#include <string.h>

#include <algorithm>

#include <stdio.h>

#include <math.h>

#include <bitset>

using namespace std;

typedef long long LL;

const int N = 2e5+;

const LL mod = 1e6+;

LL qpow(LL x,LL y){

  LL ret=;

  while(y){

    if(y&)ret=ret*x%mod;

    x=x*x%mod;y>>=;

  }

  return ret;

}

int main(){

  LL n,k;

  scanf("%I64d%I64d",&n,&k);

  if(n<=&&k>1ll<<n){

    printf("1 1\n");

    return ;

  }

  LL num=;

  for(LL i=k-;i;i>>=){

    num+=i/;

  }

  LL b=,a=qpow(,n);

  for(LL i=;i<=k-;++i){

    LL tmp=(a-i+mod)%mod;

    b=b*tmp%mod;

    if(tmp==)break;

  }

  LL inv=qpow(qpow(,num),mod-);

  a=qpow(a,k-);

  a=a*inv%mod;

  b=b*inv%mod;

  b=(a-b+mod)%mod;

  printf("%I64d %I64d\n",b,a);

  return ;

}

巴特西

Codeforces Round #369 (Div. 2) 套题

最新文章

热门文章