您的位置:澳门402永利com > 澳门402永利com网络 > 四子连棋,21夏令营清北学堂解题报告

四子连棋,21夏令营清北学堂解题报告

发布时间:2019-11-12 09:39编辑:澳门402永利com网络浏览(161)

    1004 四子连棋,1004四子

    2017.7.21夏令营清北学堂解题报告,2017.7.21夏令营

    预计分数:

    60+30+0=90=划水

    实际分数:

    90+30+20=140=rank5=雷蛇鼠标

    一句话总结:今天该买彩票!

     

    T1:

    图片 1题目描述 从前有一个?行?列的网格。 现在有?种颜色,第?种颜色可以涂??格,保证 Σ︀ ?? = ? * ?。 需要你对这个网格图进行着色,你必须按照从上到下,每一行内从左到右 的顺序进行着色,并且在用完一种颜色前你不能换颜色(当然颜色的使用顺序 是随意的)。 每个相邻的相同色块可以获得1分,问在给定的规则下进行着色所能获得的 最高分是多少。 多组数据。 输入输出格式 输入格式: 从文件diyiti.in中读入数据。 第一行一个整数?表示数据组数。 对于每组数据,第一行三个整数?, ?, ?表示网格的大小和颜色的数量。 之后一行?个数,第?个数表示第?种颜色可以涂的格数。 输出格式: 将答案输出到diyiti.out。 对于每组数据一个数???,表示能获得的最高分。 输入输出样例 输入样例#1: 2 3 3 4 1 2 2 4 4 2 4 1 2 2 3 输出样例#1: 5 4 说明 【样例解释】 第一组数据 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, ? ≤ 10 3 T1

    感觉这题好鬼畜,从来没有见过这种类型的题,一开始噼里啪啦的敲了90+行的暴力,

    不出所料只能过30%的数据,没办法,只能留着对拍了。。。。

    后来发现了一个公式:

    当p%m==0的时候的方案数是:((m-1)+(p/m-1)*(m*2-1));

    然后特判一下每种情况搞一搞就好了,

    预计能过60%的数据,

    但是最后居然得了90分,,

    而且另外的十分不知道怎么丢的,,,,=.=

    暴力:

     

    图片 2 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("%dn",ans); 98 } 99 else 100 { 101 int p; 102 if(colornum==n*m) 103 { 104 for(int i=1;i<=colornum;i++) 105 read(p); 106 printf("0n"); 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 else 139 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("%dn",ans); 168 } 169 } 170 return 0; 171 } T1暴力

     

    图片 3 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("%dn",ans); 24 } 25 } T1正解

     

    T2:

     

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

     

    第一眼:DP,十分不可做。。

    第二眼:30%的暴力好像可以搞一搞

    第三眼:其余30%的数据好像可以用组合数搞一搞

    第三眼:最后40%不要了,开始搞吧,

     

    于是噼里啪啦敲完第一题的鬼畜代码(就是实现个加减法我连队列都用上了,,,,)

    然后开始搞其余30%,其实这时候剩下的时间已经不多了,于是想也没想就直接暴力就组合数。

    暴力敲的应该是对的,但是因为求组合数牵扯到除法而且这道题还要取mod,当时想到需要求逆元了然而这时候也就还剩十几分钟所以果断放弃

    后来有大佬说全是一的情况只要把所有数的平方全加起来再加个什么东西就可以,,,,,

     

    正解:动规,用f[i]表示第i轮的所有情况的和,然后就不会了,,,,

    暴力:

     

    图片 5 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 else 42 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 else 91 { 92 dfs(0); 93 printf("%d",ans%mod); 94 } 95 return 0; 96 } T2暴力

     

    图片 6 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("%dn",f[n]); 23 } T2正解

     

     

     

    T3

     

    图片 7题目描述 有一个? * ?的网格图,其中每个格子都有一个数。 设??为第?行的最小值,??为第?列的最大值,我们称一个网格是好的,当 且仅当满足 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 T3

     

    这题,,是我有史以来骗的最完美的、

    说一下我的思路:

    当n>100时,cout<<rand();

    else cout<<2;

    然后,就得了20分。

    为什么是2不是3呢?

    我们想,对于一个n<=10的矩阵,

    改一次会不会太少了?

    所以

    改两次!

     

    正解:我们假设一个i是要找的答案。

    那么这个i就要满足&……¥*……(&(*#@!&#(*@……¥(*&#%2

     

     

    图片 8 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 else 32 printf("200"); 33 return 0; 34 } 骗分

     

    图片 9 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("%dn",ans); 34 } T3

     

     

     

     

    总结:

    还算考的不错,但这次考试能得rank5,运气成分真的是非常的大。

    T1有七八个人A掉,

    T2有一个人A掉 ,五六个90分,

    说明自己的提升空间还很大。

    加油!

    2017 noip 创造奇迹!

     

     

    预计分数: 60+30+0=90=划水 实际分数: 90+30+20=140=rank5=雷蛇鼠标 一句话总结:今天该买彩票...

    1004 四子连棋

     

     时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果     题目描述 Description

    在一个4*4的棋盘上摆放了14颗棋子,其中有7颗白色棋子,7颗黑色棋子,有两个空白地带,任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格,这叫行棋一步,黑白双方交替走棋,任意一方可以先走,如果某个时刻使得任意一种颜色的棋子形成四个一线(包括斜线),这样的状态为目标棋局。

     
     

     

    输入描述 Input Description

    从文件中读入一个4*4的初始棋局,黑棋子用B表示,白棋子用W表示,空格地带用O表示。
    

    输出描述 Output Description

    用最少的步数移动到目标棋局的步数。

    样例输入 Sample Input

    BWBO
    WBWB
    BWBW
    WBWO

    样例输出 Sample Output

    5

    数据范围及提示 Data Size & Hint

    hi

    分类标签 Tags 点此展开 

     

    图片 10 1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int MAXN=10; 5 int map[MAXN][MAXN]; 6 int vis[MAXN][MAXN][MAXN][MAXN]; 7 int kong1x,kong1y; 8 int kong2x,kong2y; 9 int hang[MAXN];// 储存每一行有多少个黑棋子 10 int lie[MAXN]; 11 int leftdjx;//左对角线 12 int rightdjx;// 右对角线 13 int ans=0x7fffffff; 14 int xx[5]={-1,+1,0,0}; 15 int yy[5]={0,0,-1,+1}; 16 int how;// 1表示应该走黑棋 2表示白棋 17 void dfs(int k1x,int k1y,int k2x,int k2y,int step) 18 { 19 for(int i=1;i<=4;i++) 20 { 21 if(leftdjx==4||rightdjx==4||hang[i]==4||(hang[i]==0&&k1x!=i&&k2x!=i)||lie[i]==4||(lie[i]==0&&k1y!=i&&k2y!=i)) 22 { 23 if(step<ans) 24 ans=step; 25 return ; 26 } 27 } 28 if(step>ans) 29 return; 30 for(int i=0;i<4;i++) 31 { 32 int flag=0; 33 int wx=k1x+xx[i]; 34 int wy=k1y+yy[i]; 35 if(((map[wx][wy]==how)||how==2)&&wx<=4&&wx>=1&&wy<=4&&wy>=1&&map[wx][wy]!=2&&vis[k1x][k1y][wx][wy]==0) 36 { 37 if(map[wx][wy]==1) 38 how=0; 39 else if(map[wx][wy]==0) 40 how=1; 41 if(map[wx][wy]==1) 42 { 43 hang[k1x]++; 44 hang[wx]--; 45 lie[k1y]++; 46 lie[wy]--; 47 if(k1x==k1y) 48 leftdjx++; 49 if(k1x+k1y==5) 50 rightdjx++; 51 flag=1; 52 if(wx==wy) 53 leftdjx--; 54 if(wx+wy==5) 55 rightdjx--; 56 } 57 vis[k1x][k1y][wx][wy]=1; 58 map[k1x][k1y]=map[wx][wy]; 59 map[wx][wy]=2; 60 dfs(wx,wy,k2x,k2y,step+1); 61 /*if(map[wx][wy]==1) 62 how=0; 63 else if(map[wx][wy]==0) 64 how=1;*/ 65 vis[k1x][k1y][wx][wy]=0; 66 map[wx][wy]=map[k1x][k1y]; 67 map[k1x][k1y]=2; 68 if(flag==1) 69 { 70 hang[k1x]--; 71 hang[wx]++; 72 lie[k1y]--; 73 lie[wy]++; 74 if(k1x==k1y) 75 leftdjx--; 76 if(k1x+k1y==5) 77 rightdjx--; 78 if(wx==wy) 79 leftdjx++; 80 if(wx+wy==5) 81 rightdjx++; 82 } 83 } 84 } 85 for(int i=0;i<4;i++) 86 { 87 int flag=0; 88 int wx=k2x+xx[i]; 89 int wy=k2y+yy[i]; 90 if(((map[wx][wy]==how)||how==2)&&wx<=4&&wx>=1&&wy<=4&&wy>=1&&map[wx][wy]!=2&&vis[k2x][k2y][wx][wy]==0) 91 { 92 if(map[wx][wy]==1) 93 how=0; 94 else if(map[wx][wy]==0) 95 how=1; 96 if(map[wx][wy]==1) 97 { 98 hang[k2x]++; 99 hang[wx]--; 100 lie[k2y]++; 101 lie[wy]--; 102 if(k2x==k2y) 103 leftdjx++; 104 if(k2x+k2y==5) 105 rightdjx++; 106 flag=1; 107 if(wx==wy) 108 leftdjx--; 109 if(wx+wy==5) 110 rightdjx--; 111 } 112 vis[k2x][k2y][wx][wy]=1; 113 map[k2x][k2y]=map[wx][wy]; 114 map[wx][wy]=2; 115 dfs(k1x,k1y,wx,wy,step+1); 116 /*if(map[wx][wy]==1) 117 how=0; 118 else if(map[wx][wy]==0) 119 how=1;*/ 120 vis[k2x][k2y][wx][wy]=0; 121 map[wx][wy]=map[k2x][k2y]; 122 map[k2x][k2y]=2; 123 if(flag==1) 124 { 125 hang[k2x]--; 126 hang[wx]++; 127 lie[k2y]--; 128 lie[wy]++; 129 if(k2x==k2y) 130 leftdjx--; 131 if(k2x+k2y==5) 132 rightdjx--; 133 if(wx==wy) 134 leftdjx++; 135 if(wx+wy==5) 136 rightdjx++; 137 } 138 } 139 } 140 } 141 int main() 142 { 143 for(int i=1;i<=4;i++) 144 { 145 for(int j=1;j<=4;j++) 146 { 147 char c; 148 cin>>c; 149 if(c=='B') 150 { 151 map[i][j]=1;// 黑色棋子 152 hang[i]++; 153 lie[j]++; 154 if(i==j)leftdjx++; 155 if(i+j==5)rightdjx++; 156 } 157 else if(c=='W') 158 { 159 map[i][j]=0;//白色棋子 160 } 161 else 162 { 163 map[i][j]=2; 164 if(kong1x==0&&kong1y==0) 165 { 166 kong1x=i; 167 kong1y=j; 168 } 169 else 170 { 171 kong2x=i; 172 kong2y=j; 173 } 174 } 175 } 176 } 177 how=2; 178 dfs(kong1x,kong1y,kong2x,kong2y,0); 179 printf("%d",ans); 180 return 0; 181 } View Code

     

    四子连棋,1004四子 1004 四子连棋 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题解 查看运行结果 题目描述 Description 在一个4*...

    本文由澳门402永利com发布于澳门402永利com网络,转载请注明出处:四子连棋,21夏令营清北学堂解题报告

    关键词:

上一篇:getline使用例题注意点2

下一篇:没有了