期望得分：30+90+100=220

实际得分：30+0+10=40

 

T1智障错误：n*m是n行m列，硬是做成了m行n列

T2智障错误：读入三个数写了两个%d

T3智障错误：数值相同不代表是同一个数

既眼瘸又脑残，NOIP这样后悔去吧！

 

T1

n*m网格，有S种颜色。

按从上到下，从左到右的顺序涂色。

相邻的相同色块可得一份，问最大得分

n，S<=100000,m<=4

只有最多4列

1列：顺着涂

2列：先涂可以涂偶数个

3列：先涂%3=0的，然后一个%3=1和一个%3=2的组合，剩余的顺着涂

4列：先涂%4=0的，然后涂偶数个%4=2的，然后一个%4=1和一个%4=3的组合，如果%4=2的还剩1个，就与%4=1或%4=3的两个组合，剩余的随便涂

具体实现的时候：

假设每一种颜色都从左上角开始涂

那么这一种颜色a[i]对答案的贡献是

if(a[i]>=m) ans+=a[i]/m*(m*2-1)-m+a[i]%m+max(a[i]%m-1,0);

else ans+=a[i]-1;

a[i]/m*(m*2-1)-m 是完整的行的贡献

a[i]%m+max(a[i]%m-1,0)是不完整的1行的贡献

m=1或m=2的时候直接输出

m=3时，如果%3=2的比%3=1的多，即不能完全组合，那么就要有几个%3=2的连着图，画图可知，每三个%3=2的连着图，会损失一个相邻的相同色块（有一个%3=2的1个在上一行最后面）。所以答案还要减去（%3=2的个数 - %3=1的个数）/3

m=4时，与m=3的同理，答案还要减去（%4=3的个数 - %4=1的个数）/2

#include
      
       #include
       
        #include
        
         using namespace std;int a[100001],sum[4];int main(){    freopen("diyiti.in","r",stdin);    freopen("diyiti.out","w",stdout);    int n,m,s,T,ans;    scanf("%d",&T);    while(T--)    {        ans=0;        memset(sum,0,sizeof(sum));        scanf("%d%d%d",&n,&m,&s);        for(int i=1;i<=s;i++)         {            scanf("%d",&a[i]);            sum[a[i]%m]++;            if(a[i]>=m) ans+=a[i]/m*(m*2-1)-m+a[i]%m+max(a[i]%m-1,0);            else ans+=a[i]-1;        }        if(m==3)        {            if(sum[2]>sum[1]) ans-=(sum[2]-sum[1])/3;        }        else if(m==4)        {            if(sum[3]>sum[1]) ans-=(sum[3]-sum[1])/2;        }        printf("%d\n",ans);    }}
        
       
      

 

T2

一个数列，长为n

在里面加n-1个加号或乘号

问方案所有方案的数列和

有部分数据数列全为1

那么枚举有i个乘号，ans=Σ（C（n-1,2）*（n-i））

一、基本思路O（n^3）

dp[i]表示到第i个数的答案

枚举前一个加号在j后面

那么到j一共有2^(j-1)种方案，每种方案在j后面都是一个加号，加号后面全是乘号

令tot=a[j+1]*a[j+2]……*a[i]

dp[i]=Σ（dp[j]+2^（j-1）*tot）

#include
      
       #include
       
        #define mod 1000000007using namespace std;int n,a[100001];long long ans,b[11];long long C[1001][1001],cf[1001];long long dp[100001],pre[100001],inv[100001];bool ok;void dfs(int now,int jia,long long sum[11]){    if(now==n+1)    {        for(int i=1;i<=n;i++) ans+=sum[i],ans%=mod;        return;    }    long long tmp[11];    memcpy(tmp,sum,sizeof(tmp));    tmp[now]=a[now];    dfs(now+1,now,tmp);    tmp[now]-=a[now];    if(jia)     {        tmp[jia]*=a[now];        dfs(now+1,jia,tmp);        tmp[jia]/=a[now];    }    }long long pow(long long a,long long b){    long long res=1;    while(b)    {        if(b&1) res*=a,res%=mod;        b>>=1; a*=a; a%=mod;     }    return res;}int main(){    freopen("dierti.in","r",stdin);    freopen("dierti.out","w",stdout);    scanf("%d",&n);    for(int i=1;i<=n;i++)     {        scanf("%d",&a[i]);        if(a[i]!=1) ok=true;    }    if(ok && n<=10)    {        dfs(1,0,b);        printf("%I64d",ans);        return 0;    }    if(!ok)    {        for(int i=0;i<=1000;i++) C[i][0]=1;        for(int i=1;i<=1000;i++)            for(int j=1;j<=i;j++)                C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;        for(int i=0;i
       
      

二、预处理前缀积O（n^2）

省去上面循环计算tot的部分，预处理前缀积,

tot=pre[i]/pre[j]=pre[i]*pre[j]的逆元

预处理前缀积的逆元

#include
      
       #include
       
        #define mod 1000000007using namespace std;int n,a[100001];long long ans,b[11];long long C[1001][1001],cf[1001];long long dp[100001],pre[100001],inv[100001];bool ok;void dfs(int now,int jia,long long sum[11]){    if(now==n+1)    {        for(int i=1;i<=n;i++) ans+=sum[i],ans%=mod;        return;    }    long long tmp[11];    memcpy(tmp,sum,sizeof(tmp));    tmp[now]=a[now];    dfs(now+1,now,tmp);    tmp[now]-=a[now];    if(jia)     {        tmp[jia]*=a[now];        dfs(now+1,jia,tmp);        tmp[jia]/=a[now];    }    }long long pow(long long a,long long b){    long long res=1;    while(b)    {        if(b&1) res*=a,res%=mod;        b>>=1; a*=a; a%=mod;     }    return res;}int main(){    freopen("dierti.in","r",stdin);    freopen("dierti.out","w",stdout);    scanf("%d",&n);    for(int i=1;i<=n;i++)     {        scanf("%d",&a[i]);        if(a[i]!=1) ok=true;    }    if(ok && n<=10)    {        dfs(1,0,b);        printf("%I64d",ans);        return 0;    }    if(!ok)    {        for(int i=0;i<=1000;i++) C[i][0]=1;        for(int i=1;i<=1000;i++)            for(int j=1;j<=i;j++)                C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;        for(int i=0;i
       
      

三、在上面的基础上前缀和优化O（n）

#include
      
       #include
       
        #define mod 1000000007using namespace std;int n,a[100001];long long cf[100001];long long dp[100001],pre[100001],inv[100001];long long pow(long long a,long long b){    long long res=1;    while(b)    {        if(b&1) res*=a,res%=mod;        b>>=1; a*=a; a%=mod;     }    return res;}int main(){    freopen("dierti.in","r",stdin);    freopen("dierti.out","w",stdout);    scanf("%d",&n);    for(int i=1;i<=n;i++)     scanf("%d",&a[i]);        cf[0]=1;         for(int i=1;i<=n;i++) cf[i]=cf[i-1]*2%mod;        long long tot;        pre[0]=1;        for(int i=1;i<=n;i++) pre[i]=pre[i-1]*a[i]%mod;        for(int i=1;i<=n;i++) inv[i]=pow(pre[i],mod-2);        long long sum1=0,sum2=1;        for(int i=1;i<=n;i++)        {            dp[i]=(sum1+sum2*pre[i]%mod)%mod;            sum1=(sum1+dp[i])%mod;            sum2=(sum2+cf[i-1]%mod*inv[i]%mod)%mod;        }         printf("%I64d",dp[n]);    }
       
      

 

T3

如果这个网格是好的，那么存在一个数，它既是所在行最小值，又是所在列最大值

所以一边枚举一边维护每一列<=这个数的个数less_l，每一行>=这个数的个数more_h

对于每个值，取最大的less_i,more_h

ans=max(n-less_i+n-more_h)

一边枚举一边维护有一种维护后缀数组的感觉

#include
      
       #include
       
        #include
        
         #include
         
          #define N 1001using namespace std;pair
          
           a[N*N];void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}int less_l[N*N],more_h[N*N],tmp[N*N];int main(){    freopen("disanti.in","r",stdin);    freopen("disanti.out","w",stdout);    int n,m;    read(n);    m=n*n;    for(int i=0;i
           
            =0;i=j) { more_h[i]=more_h[i+1]; for(j=i;j>=0 && a[i].first==a[j].first;j--) { x=a[j].second; tmp[x/n]++; more_h[i]=max(more_h[i],tmp[x/n]); } for(int k=i-1;k>j;k--) more_h[k]=more_h[i]; } int ans=m; for(int i=0;i
           
          
         
        
       
      

 

考场代码，如果网格没有重复的数，可能会AC

#include
      
       #include
       
        using namespace std;int a[1001][1001]; int key[1001],hash[1001];int h[1001][1001],l[1001][1001];int main(){    //freopen("disanti.in","r",stdin);//    freopen("disanti.out","w",stdout);    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            scanf("%d",&a[i][j]);    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++) key[j]=hash[j]=a[i][j];        sort(hash+1,hash+n+1);        for(int j=1;j<=n;j++) key[j]=lower_bound(hash+1,hash+n+1,key[j])-hash;        for(int j=1;j<=n;j++) h[i][j]=key[j]-1;    }    for(int j=1;j<=n;j++)    {        for(int i=1;i<=n;i++) key[i]=hash[i]=a[i][j];        sort(hash+1,hash+n+1);        for(int i=1;i<=n;i++) key[i]=lower_bound(hash+1,hash+n+1,key[i])-hash;        for(int i=1;i<=n;i++) l[i][j]=n-key[i];    }    int ans=n*n;    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            ans=min(ans,h[i][j]+l[i][j]);    printf("%d",ans);}