题目描述从前有一个?行?列的网格。现在有?种颜色，第?种颜色可以涂??格，保证Σ? ?? = ? * ?。需要你对这个网格图进行着色，你必须按照从上到下，每一行内从左到右的顺序进行着色，并且在用完一种颜色前你不能换颜色（当然颜色的使用顺序是随意的）。每个相邻的相同色块可以获得1分，问在给定的规则下进行着色所能获得的最高分是多少。多组数据。输入输出格式输入格式：从文件diyiti.in中读入数据。第一行一个整数?表示数据组数。对于每组数据，第一行三个整数?, ?, ?表示网格的大小和颜色的数量。之后一行?个数，第?个数表示第?种颜色可以涂的格数。输出格式：将答案输出到diyiti.out。对于每组数据一个数???，表示能获得的最高分。输入输出样例输入样例#1：23 3 41 2 2 44 2 41 2 2 3输出样例#1：54说明【样例解释】第一组数据1 2 2 3 3 4 4 4 4 第二组数据1 4 4 4 2 2 3 3 对于30%的数据，1 ≤ ?, ? ≤ 10, 1 ≤ ? ≤ 2对于60%的数据，1 ≤ ?, ? ≤ 1000, 1 ≤ ? ≤ 3对于100%的数据，1 ≤ ?, ? ≤ 100000, 1 ≤ ? ≤ 4, ?? ≥ 1, ? ≤ 103

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<queue>  6 using namespace std;  7 const int MAXN=100001;  8 const int maxn=0x7ffff;  9 void read(int &n) 10 { 11     char c=‘+‘;int x=0;bool flag=0; 12     while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;} 13     while(c>=‘0‘&&c<=‘9‘) 14     x=(x<<1)+(x<<3)+c-48,c=getchar(); 15     flag==1?n=-x:n=x; 16 } 17 int T; 18 int n,m,colornum; 19 int color[MAXN]; 20 int map[MAXN][6]; 21 int ans=0; 22 int xx[5]={-1,+1,0,0}; 23 int yy[5]={0,0,-1,+1}; 24 int vis[MAXN]; 25 void dfs(int used,int bh,int coloruse,int x,int y) 26 //  使用了的颜色   当前点的编号  当前已使用  27 { 28     if(used==colornum&&coloruse==color[bh]) 29     { 30         int now=0; 31         for(int i=1;i<=n;i++) 32             for(int j=1;j<=m;j++) 33                 for(int k=0;k<4;k++) 34                 { 35                     int wx=i+xx[k]; 36                     int wy=j+yy[k]; 37                     if(wx>=1&&wx<=n&wy>=1&&wy<=m) 38                         if(map[i][j]==map[wx][wy]) 39                             now++; 40                 } 41                      42         ans=max(ans,now/2); 43         return ; 44     } 45     int wx,wy; 46     if(y==m)    {    wy=1;wx=x+1;} 47     else    {    wy=y+1;    wx=x;    } 48     if(coloruse==color[bh]) 49     { 50         vis[bh]=1; 51         for(int i=1;i<=colornum;i++) 52         { 53             if(!vis[i]) 54             { 55             //    vis[i]=1; 56                 map[wx][wy]=i; 57                 dfs(used+1,i,1,wx,wy); 58                 map[wx][wy]=0; 59             //    vis[i]=0; 60             } 61         } 62         vis[bh]=0; 63     } 64     else 65     { 66         map[wx][wy]=bh; 67         dfs(used,bh,coloruse+1,wx,wy); 68         map[wx][wy]=0; 69     } 70          71 } 72 int main() 73 { 74 //    freopen("diyiti.in","r",stdin); 75 //    freopen("diyiti.out","w",stdout); 76     // 77     read(T); 78     while(T--) 79     { 80         memset(vis,0,sizeof(vis)); 81         memset(map,0,sizeof(map)); 82         memset(color,0,sizeof(color)); 83         ans=0; 84         read(n);read(m);read(colornum); 85         if(n>=0) 86         { 87             for(int i=1;i<=colornum;i++) 88                 read(color[i]); 89             for(int i=1;i<=colornum;i++) 90             { 91             //    vis[color[i]]=1; 92                 map[1][1]=i; 93                 dfs(1,i,1,1,1); 94                 map[1][1]=0; 95                 //vis[color[i]]=0; 96             } 97             printf("%d\n",ans);     98         } 99         else100         {101             int p;102             if(colornum==n*m) 103             {104                 for(int i=1;i<=colornum;i++)105                     read(p);106                 printf("0\n");107                 continue;108             }109             if(m==1) 110             {111                 for(int i=1;i<=colornum;i++) 112                 {113                     read(p);114                     ans+=p-1;//上下两个相邻 115                 }116             } 117             else if(m==2) 118             {119                 for(int i=1;i<=colornum;i++) 120                 {121                     read(p);122                     if(p==1) 123                         continue;// 没有相邻 124                     else 125                         ans+=((m-1)+(p/m-1)*(m*2-1))+p%m;126                 }127             } 128             else if(m==3) 129             {130                 for(int i=1;i<=colornum;i++) 131                 {132                     read(p);133                     if(p==1) 134                         continue;135                     if(p<m) 136                         if(p%2)137                             ans+=p-1;// 左右相邻 138                         else139                             ans+=p-2;140                     else 141                     {142                         ans+=((m-1)+(p/m-1)*(m*2-1));143                         int remain=p%3;144                         if(remain!=0)145                             ans+=(remain*2-1);146                     }147                 }148             } 149             else if(m==4) 150             {151                 for(int i=1;i<=colornum;i++) 152                 {153                     read(p);154                     if(p==1) 155                         continue;156                     if(p<m) 157                         ans+=p-1;158                     else 159                     {160                         ans+=((m-1)+(p/m-1)*(m*2-1));161                         int remain=p%4;162                         if(remain!=0)163                             ans+=(remain*2-1);164                     }165                 }166             }167             printf("%d\n",ans);168         }169     }170     return 0;171 }

 1 #include<bits/stdc++.h> 2 using namespace std; 3 int T,n,m,S,a[100010],p[5],ans; 4 int main(){ 5     freopen("diyiti3.in","r",stdin); 6     freopen("diyiti3.out","w",stdout); 7     scanf("%d",&T); 8     while(T--){ 9         memset(p,0,sizeof(p));10         ans=0;11         scanf("%d%d%d",&n,&m,&S);12         for(int i=1;i<=S;i++){13             scanf("%d",&a[i]);14             p[a[i]%m]++;15             if(a[i]>=m)ans+=(a[i]/m*(2*m-1)-m+a[i]%m+max(0,a[i]%m-1));16             else ans+=a[i]-1;17         }18         if(m==3){19             if(p[2]>p[1])ans-=(p[2]-p[1])/3;20         }else if(m==4){21             if(p[3]>p[1])ans-=(p[3]-p[1])/2;22         }23         printf("%d\n",ans);24     }25 }

题目描述在纸上有一个长为?的数列，第?项值为??。现在小A想要在这些数之间添加加号或乘号。问对于不同的2?−1种方案，所有答案的和是多少？由于数据范围较大，所以输出对1000000007取模的结果。输入输出格式输入格式：从文件dierti.in中读入数据。输入第一行一个整数?表示数列的长度。之后一行?个整数，第?个整数表示数列的第?项??。输出格式：输出到文件dierti.out中。?行，第?行表示第?个询问的答案对1000000007取模的结果。输入输出样例输入样例#1：31 2 4输出样例#1：30说明对于30%的数据，1 ≤ ? ≤ 10, 1 ≤ ?? ≤ 10对于另外30%的数据，1 ≤ ? ≤ 1000, ?? = 14 对于90%的数据，1 ≤ ? ≤ 1000, 1 ≤ ?? ≤ 105对于100%的数据，1 ≤ ? ≤ 100000, 1 ≤ ?? ≤ 109

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 const int MAXN=100001; 8 const int maxn=0x7ffff; 9 const int mod=1000000007;10 void read(int &n)11 {12     char c=‘+‘;int x=0;bool flag=0;13     while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;}14     while(c>=‘0‘&&c<=‘9‘)15     x=(x<<1)+(x<<3)+c-48,c=getchar();16     flag==1?n=-x:n=x;17 }18 int n;19 int a[MAXN];20 int flag=0;21 int ans;22 int how[MAXN];23 int num=1;24 int tot=0;25 void calc()26 {27     queue<int>q;28     for(int i=1;i<=num;i++)29     {30         if(how[i]==2)31         {32             int now=1;33             while(how[i]==2)34             {35                 now=(now*a[i])%mod;36                 i++;37             }38             now=(now*a[i])%mod;39             q.push(now);40         }41         else42             q.push(a[i]);43     }44     while(q.size()!=0)45     {46         ans=(ans+q.front())%mod;47         q.pop();48     }49 }50 void dfs(int pos)51 {52     if(pos==n-1)53     {    54         tot++;55         calc();56         return ;57     }58     59     for(int i=1;i<=2;i++)60     {61         how[num++]=i;62         dfs(pos+1);63         how[--num]=0;64     }65 }66 int jc(int num)67 {68     if(num==0)69         return 1;70     else 71         return (num*(jc(num-1)))%mod;72 }73 int main()74 {75     freopen("dierti.in","r",stdin);76     freopen("dierti.out","w",stdout);77     read(n);78     for(int i=1;i<=n;i++)79     {    read(a[i]);    if(a[i]==1)        flag++;    }80     if(flag==n)81     {82         int p=jc(n-1)%mod; 83         for(int i=1;i<=n-1;i++)// 放多少个* 84         {85             int hh=(p/(jc(i)*jc(n-i-1)))%mod;86             ans=ans+((n-i)*hh)%mod;87         }88         printf("%d",(ans+n)%mod);89     }90     else91     {92         dfs(0);93         printf("%d",ans%mod);    94     }95     return 0;96 }

 1 #include<bits/stdc++.h> 2 #define mod 1000000007  3 #define N 100010 4 using namespace std; 5 int T,n,i,a[N],g[N],f[N],sum,sum1; 6 int powmod(int x,int y){ 7     int ans=1; 8     for(;y;y>>=1,x=1ll*x*x%mod) 9         if(y&1)ans=1ll*ans*x%mod;10     return ans;11 }12 int main(){13     scanf("%d",&n);14     sum=0;sum1=g[0]=1;15     for(i=1;i<=n;i++){16         scanf("%d",&a[i]);17         g[i]=1ll*g[i-1]*a[i]%mod;18         f[i]=(sum+1ll*g[i]*sum1)%mod;19         sum=(sum+f[i])%mod;20         sum1=(sum1+1ll*powmod(2,(i-1))*powmod(g[i],mod-2))%mod;21     }22     printf("%d\n",f[n]);23 }

题目描述有一个? * ?的网格图，其中每个格子都有一个数。设??为第?行的最小值，??为第?列的最大值，我们称一个网格是好的，当且仅当满足max(?1, ...,??) = min(??, ...,??)现在问最少改变多少个数可以使得这个网格是好的。输入输出格式输入格式：从文件disanti.in中读入数据。第一行一个整数?。之后?行，每行?个数，描述这个矩阵。输出格式：输出到文件disanti.out中。一个数???，表示最少需要改变的数的个数。输入输出样例暂无测试点说明对于30%的数据，1 ≤ ?, ?? ≤ 10对于另外30%的数据，1 ≤ ? ≤ 100, 1 ≤ ?? ≤ 3对于90%的数据，1 ≤ ? ≤ 100, 1 ≤ ?? ≤ 105对于100%的数据，1 ≤ ? ≤ 1000, 1 ≤ ?? ≤ 10

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 const int MAXN=1001; 8 const int maxn=0x7ffff; 9 void read(int &n)10 {11     char c=‘+‘;int x=0;bool flag=0;12     while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;}13     while(c>=‘0‘&&c<=‘9‘)14     x=(x<<1)+(x<<3)+c-48,c=getchar();15     flag==1?n=-x:n=x;16 }17 int map[MAXN][MAXN];18 int main()19 {20     freopen("disanti.in","r",stdin);21     freopen("disanti.out","w",stdout);22     int n;23     read(n);24     for(int i=1;i<=n;i++)25         for(int j=1;j<=n;j++)26             read(map[i][j]);27     if(n<=10)28     printf("2");29     else if(n<=100&&n<=1000)30     printf("20");31     else32     printf("200");33     return 0;34 }

 1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,i,x,A[1100],B[1100],C[1100000],ans,j,k,SS[1100000],TT[1100000]; 4 pair<int,int>a[1100000]; 5 int main(){ 6     scanf("%d",&n); 7     m=n*n; 8     ans=n*2-1; 9     for(i=0;i<m;i++)10         scanf("%d",&a[i].first),a[i].second=i;11     sort(a,a+m);12     for(i=0;i<m;i=j){13         TT[i]=TT[i-1];14         for(j=i;a[j].first==a[i].first&&j<m;j++){15             x=a[j].second;16             B[x%n]++;17             TT[i]=max(TT[i],B[x%n]);18         }19         for(k=i;k<j;k++)TT[k]=TT[i];20     }21     memset(A,0,sizeof(A));22     for(i=m-1;i>=0;i=j){23         SS[i]=SS[i+1];24         for(j=i;a[j].first==a[i].first&&j>=0;j--){25             x=a[j].second;26             A[x/n]++;27             SS[i]=max(SS[i],A[x/n]);28         }29         for(k=i;k>j;k--)SS[k]=SS[i];30     }31     for(i=0;i<m;i++)32         if(n-SS[i]+n-TT[i]<ans)ans=n-SS[i]+n-TT[i];33     printf("%d\n",ans);34 }