【1109】noip模拟赛

1．Game

【题目描述】

明明和亮亮在玩一个游戏。桌面上一行有n个格子，一些格子中放着棋子。明明和亮亮轮流选择如下方式中的一种移动棋子（图示中o表示棋子，*表示空着的格子）:

1）当一枚棋子的右边是空格子的话，可以将这枚棋子像右移动一格。

**o*** -> ***o**

2）当一枚棋子的右边连续两个都有棋子，并且这个棋子往右边数第3格没有棋子，那么可以将这个棋子可以跳过去那两个棋子

**ooo* -> ***oo*

当任何一枚棋子到达最右边的格子时，这枚棋子自动消失。当一方不能移动时，这方输。假设明明和亮亮都采取最优策略，明明先走，谁将取胜？

【输入数据】

第一行一个整数T表示数据组数， 0 < T < 10。

之后T组数据，每组两行，第一行n 表示格子个数，第二行n个字符表示每个格子的情况，o表示有棋子，*表示空着。

【输出数据】

对于每组数据一个输出，M表示明明赢，L表示亮亮赢。

【样例输入】

4

2

*o

5

*o***

6

**o**o

14

*o***ooo**oo**

【样例输出】

L

M

M

L

【数据范围】

0 <T < 10

对于50%的数据， n < 20。

对于100%的数据， n < 1000。

第一题就博弈。。跪跪跪。。

真心不会博弈。。今晚好好重学一遍。。

看题解好像很好理解？？？

Game解题报告

对于前50%的数据，由于n<20，整个棋盘的状态个数 < 2^20。 由于状态数有限，我们可以采取记忆化搜索的办法来实现。

但对于100%的数据，n的最大可能值达到999，记忆化搜索就不怎么可行了。其实本题有一个更简单的做法：

考虑每个棋子到最右边格子的距离。把所有棋子这样的距离的总和计为s。我们发现不管选择两种操作中的一种操作，每走一步，s的奇偶性都会发生一次变化。所以说，如果第一次轮到明明时，s是奇数，那么每次轮到明明时s都是奇数。而当s是奇数时，s肯定>0，这时明明总可以走最右边的棋子。也就是说当s为奇数时，总有棋子可以走。所以说，一开始若s为奇数，则明明必胜。同理，若一开始s为偶数，则当亮亮走的时候s总是奇数，所以明明必败。

贴个代码：

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 const int N=25,M=1<<21; 8 int n,f[2][M],a[N],b[N]; 9 char c[N],cc[N];10 11 int dfs(int x,int s)12 {13if((s&1)!=0) s--;14if(f[x][s]!=-1) return f[x][s];15int ss,ans=0;16for(int i=0;i<n;i++)17{18 if((s&(1<<i))!=0 && (i-1>=0 && (s&(1<<(i-1)))==0)) 19 {20 ss=s-(1<<i)+(1<<(i-1));21 if(dfs(1-x,ss)==0) ans=1;22 }23 if((s&(1<<i))!=0 && (i-1>=0 && (s&(1<<(i-1)))!=0) && (i-2>=0 && (s&(1<<(i-2)))!=0) && (i-3>=0 && (s&(1<<(i-3)))==0)) 24 {25 ss=s-(1<<i)+(1<<(i-3));26 if(dfs(1-x,ss)==0) ans=1;27 }28}29f[x][s]=ans;30// printf("f %d %d = %d\n",x,s,ans);31return ans;32 }33 34 void solve1()35 {36scanf("%s",c);37memset(f,-1,sizeof(f));38f[0][0]=f[1][0]=0;39int x=0;40for(int i=0;i<n;i++)41{42 if(c[i]=='o') x|=(1<<(n-1-i));43}44// printf("x = %d\n",x);45if(dfs(0,x)==1) printf("M\n");46else printf("L\n");47 }48 49 void solve2()50 {51scanf("%s",c+1);52int sum=0;53for(int i=1;i<=n;i++)54{55 if(c[i]=='o') sum+=n-i;56}57if(sum%2==0) printf("L\n");58else printf("M\n");59 }60 61 int main()62 {63// freopen("a.in","r",stdin);64freopen("game.in","r",stdin);65freopen("game.out","w",stdout);66int T,x;67scanf("%d",&T);68while(T--)69{70 scanf("%d",&n);71 if(n<=20) solve1();72 else solve2();73}74return 0;75 }

View Code

2．Walk

【题目描述】

有一块n *n 的土地上，明明和亮亮站在(1,1)处。每块地上写有一个数字a(i, j)。现在他们决定玩一个游戏，每一秒钟，他们俩走向相邻且坐标变大的格子（从(x,y)到(x+1,y)或者从(x,y)到(x,y+1)），他们俩可以按照不同方式来走，最后经过2n-1步到达(n,n)处。明明和亮亮每一秒钟计算他们站的两个位置上数字的差的绝对值，他们希望这些差值的和最大，请问这个最大的和是多少？

【输入数据】

第一行一个正整数n。

后面n行，每行n个整数，分别表示每块地上的数字。

【输出数据】

一个整数，表示最大的差值的和。

【样例输入】

4

1 2 3 4

1 5 3 2

8 1 3 4

3 2 1 5

【样例输出】

13

【数据范围】

n <= 100, 每块地上的数字的绝对值不超过300。

没什么好说的。就直接dp,f[i][j][k]表示走了i步，第一个人的横坐标是j，第二个人的横坐标是k。

通过走了i步可以算出纵坐标。

第一维只开了100又跪了。。

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 const int N=210; 8 int n,a[N][N],f[N][N][N]; 9 int dx[2]={0,1};10 int dy[2]={1,0};11 12 int myabs(int x){return x>0 ? x:-x;}13 int minn(int x,int y){return x<y ? x:y;}14 int maxx(int x,int y){return x>y ? x:y;}15 16 int main()17 {18// freopen("a.in","r",stdin);19freopen("walk.in","r",stdin);20freopen("walk.out","w",stdout);21scanf("%d",&n);22for(int i=0;i<n;i++)23 for(int j=0;j<n;j++)24 scanf("%d",&a[i][j]);25memset(f,-1,sizeof(f));26f[0][0][0]=0;27int x1,y1,x2,y2,xx1,yy1,xx2,yy2;28for(int i=0;i<=2*n-2;i++)29 for(int j=0;j<n;j++)30 for(int k=0;k<n;k++)31 {32 if(f[i][j][k]==-1) continue;33 // printf("f %d %d %d = %d\n",i,j,k,f[i][j][k]);34 x1=j;y1=i-j;35 x2=k;y2=i-k;36 for(int ii=0;ii<=1;ii++)37 for(int jj=0;jj<=1;jj++)38 {39xx1=x1+dx[ii];yy1=y1+dy[ii];40xx2=x2+dx[jj];yy2=y2+dy[jj];41if(xx1>=n || yy1>=n || xx2>=n || yy2>=n) continue;42f[i+1][xx1][xx2]=maxx(f[i+1][xx1][xx2],f[i][x1][x2]+myabs(a[xx1][yy1]-a[xx2][yy2]));43 }44 }45printf("%d\n",f[2*n-2][n-1][n-1]);46return 0;47 }

View Code

3.Trip

【题目描述】

小朋友们出去郊游，明明和亮亮负责在草地上开一个篝火晚会。这个草地你可以认为是又 N * M 块单位长度为1的小正方形的草组成。

显然有的地方草长的好，有的地方长的不好，坐在上面显然舒服度是不一样的，于是每一块草都有一个舒服度 F。

现在明明和亮亮要选定一个 a*b 的草场作为晚会的地点，小朋友们就坐在上面，显然他希望小朋友们坐的最舒服！

不过别急，篝火晚会怎么能少了篝火呢，篝火需要占用 c*d 的草地，当然，篝火必须严格放置在选定的草地的内部，也就是说，篝火的边界不能和选定操场的边界有公共部分，不然学生们怎么围着篝火开晚会呢？

给定 N*M 大草地每一块的舒服度，寻找一个 a*b 的草地，除去一个严格内部的 c*d 的子草地，使得总的舒服度最大。

【输入数据】

第1行：6个整数，M , N, b, a, d, c

第2~N+1行：每行 M 个整数，第 i行j列的整数 Fi,j 表示，第 i行j列的单位草地的舒服度。

【输出数据】

一个整数，表示最大的舒服值。

【样例输入】

8 5 5 3 2 1

1 5 10 3 7 1 2 5

6 12 4 4 3 3 1 5

2 4 3 1 6 6 19 8

1 1 1 3 4 2 4 5

6 6 3 3 3 2 2 2

【样例输出】

70

【数据说明】

下面的图片就是对样例的解释，阴影区域就是最佳的选择方案。

比如方案 4 1 4 1 就是显然非法的，因为篝火出现出现在了选定草地的边界，学生们无法严格围住篝火。

【数据范围】

1 ≤ Fi,j ≤ 100

3 ≤ a ≤ N

3 ≤ b ≤ M

1 ≤ c ≤ a-2

1 ≤ d ≤ b-2

对于 40% 的数据 N,M ≤ 10

对于 60% 的数据 N,M ≤ 150

对于 100% 的数据 N,M ≤ 1000

这题其实就是求一个矩阵里的最小值。

然后就可以行做一遍，列做一遍。

我们可以一行一行的求出每个连续b-d-1个c*d矩形的最小值。再基于这个最小值，一列一列的求出每个a*b大矩形中和最小的c*d矩形。这样我们就可以找到最优的舒服值了。本算法的时间复杂度是O(MN)。

原本用优先队列。。然后超时了4个点哭。。

然后用单调队列就巨快了。。orz。。

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<vector> 6 #include<queue> 7 using namespace std; 8 9 const int N=1100;10 int n,m,A,B,C,D;11 int a[N][N],c[N][N],s[N][N],t[N][N],p[N][N],rr[N][N],R[N][N];12 struct node{int x,d;}q[N*N];13 14 int maxx(int x,int y){return x>y ? x:y;}15 16 17 void solve()18 {19node k;20int ind,l,r;21for(int i=1;i<=n;i++)22{23 l=1;r=0;24 for(int j=1;j+D-1<=B-2;j++)25 {26 k.x=j;k.d=p[i][j];27 while(q[r].d>k.d && l<=r) r--;28 q[++r]=k;29 ind=j;30 }31 for(int j=1;j+B-2<=m;j++)32 {33 while(q[l].x<j) l++;34 rr[i][j]=q[l].d;35 ind++;k.x=ind;k.d=p[i][ind];36 while(q[r].d>k.d && l<=r) r--;37 q[++r]=k;38 }39}40for(int i=1;i<=m;i++)41{42 l=1;r=0;43 for(int j=1;j+C-1<=A-2;j++)44 {45 k.x=j;k.d=rr[j][i];46 while(q[r].d>k.d && l<=r) r--;47 q[++r]=k;48 ind=j;49 }50 for(int j=1;j+A-2<=n;j++)51 {52 while(q[l].x<j) l++; 53 R[j][i]=q[l].d;54 ind++;k.x=ind;k.d=rr[ind][i];55 while(q[r].d>k.d && l<=r) r--;56 q[++r]=k;57 }58}59int ans=0;60for(int i=1;i+A-1<=n;i++)61 for(int j=1;j+B-1<=m;j++)62 ans=maxx(ans,t[i][j]-R[i+1][j+1]);63printf("%d\n",ans);64 }65 66 int main()67 {68// freopen("a.in","r",stdin);69freopen("trip.in","r",stdin);70freopen("trip.out","w",stdout);71scanf("%d%d%d%d%d%d",&m,&n,&B,&A,&D,&C);72for(int i=1;i<=n;i++)73 for(int j=1;j<=m;j++)74 scanf("%d",&a[i][j]);75memset(s,0,sizeof(s));76for(int i=1;i<=n;i++)77 for(int j=1;j<=m;j++)78 {79 s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];80 }81for(int i=1;i+A-1<=n;i++)82 for(int j=1;j+B-1<=m;j++)83 t[i][j]=s[i+A-1][j+B-1]-s[i+A-1][j-1]-s[i-1][j+B-1]+s[i-1][j-1];84for(int i=1;i+C-1<=n;i++)85 for(int j=1;j+D-1<=m;j++)86 p[i][j]=s[i+C-1][j+D-1]-s[i+C-1][j-1]-s[i-1][j+D-1]+s[i-1][j-1];87solve();88return 0;89 }

点分治裸题。。

先找出树的重心，对于每个点维护一个到树的重心的乘积d[x]。

然后找经过树的重心的树链是否有乘积为k的。

然后分治算各个子树。

ps：学了奥爷爷的线性求逆元。。强啊。。

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<vector> 6 #include<queue> 7 using namespace std; 8 9 typedef long long LL; 10 const int N=1000100,M=1000010,mod=1000003,INF=(int)1e9; 11 int n,len,sl,tl,a1,a2; 12 LL K,d[N],val[N],t[N],s[N],v[M],ny[M]; 13 int first[N],size[N],mark[N],id[M]; 14 struct node{ 15int x,y,next; 16 }a[2*N]; 17 18 int minn(int x,int y){return x<y ? x:y;} 19 20 LL quickpow(LL x,LL y) 21 { 22LL ans=1; 23while(y) 24{ 25 if(y&1) ans=ans*x%mod; 26 x=x*x%mod; 27 y/=2; 28} 29return ans; 30 } 31 32 int ins(int x,int y) 33 { 34a[++len].x=x;a[len].y=y; 35a[len].next=first[x];first[x]=len; 36 } 37 38 void find_root(int x,int fa,int tot,int &root) 39 { 40size[x]=1; 41bool bk=1; 42for(int i=first[x];i;i=a[i].next) 43{ 44 int y=a[i].y; 45 if(mark[y] || y==fa) continue; 46 find_root(y,x,tot,root); 47 size[x]+=size[y]; 48 if(2*size[y]>tot) bk=0; 49} 50if(bk && 2*(tot-size[x])<=tot) root=x; 51 } 52 53 void DFS(int x,int fa,int root) 54 { 55d[x]=d[fa]*val[x]%mod; 56t[++tl]=d[x];id[tl]=x; 57LL now=(ny[d[x]]*K%mod)*val[root]%mod; 58if(v[now]) 59{ 60 int X=x,Y=v[now]; 61 if(X>Y) swap(X,Y); 62 if(X<a1) a1=X,a2=Y; 63 else if(X==a1 && Y<a2) a2=Y; 64} 65size[x]=1; 66for(int i=first[x];i;i=a[i].next) 67{ 68 int y=a[i].y; 69 if(mark[y] || y==fa) continue; 70 DFS(y,x,root); 71 size[x]+=size[y]; 72} 73 } 74 75 int dfs(int x,int tot) 76 { 77find_root(x,0,tot,x); 78// printf("tot = %d root = %d\n",tot,x); 79mark[x]=1; 80sl=0;s[++sl]=val[x]; 81d[x]=val[x]; 82for(int i=first[x];i;i=a[i].next) 83{ 84 int y=a[i].y; 85 if(mark[y]==1) continue; 86 tl=0; 87 DFS(y,x,x); 88 for(int j=1;j<=tl;j++) 89 { 90 s[++sl]=t[j]; 91 if(v[t[j]]==0) v[t[j]]=id[j]; 92 else v[t[j]]=minn(v[t[j]],id[j]); 93 } 94} 95if(v[K]) 96{ 97 int X=x,Y=v[K]; 98 if(X>Y) swap(X,Y); 99 if(X<a1) a1=X,a2=Y;100 else if(X==a1 && Y<a2) a2=Y;101}102for(int i=1;i<=sl;i++) v[s[i]]=0;103for(int i=first[x];i;i=a[i].next)104{105 int y=a[i].y;106 if(mark[y]==1) continue;107 dfs(y,size[y]);108}109 }110 111 int main()112 {113// freopen("a.in","r",stdin);114freopen("multik.in","r",stdin);115freopen("multik.out","w",stdout);116scanf("%d%d",&n,&K);117len=0;a1=INF;a2=INF;118memset(v,0,sizeof(v));119memset(mark,0,sizeof(mark));120memset(first,0,sizeof(first));121ny[1]=1;122for(int i=2;i<=mod;i++) 123 ny[i]=(mod-(mod/i))*ny[mod%i]%mod;124 // ny[i]=quickpow(i,mod-2);125for(int i=1;i<=n;i++) 126 scanf("%d",&val[i]);127for(int i=1;i<n;i++)128{129 int x,y;130 scanf("%d%d",&x,&y);131 ins(x,y);132 ins(y,x);133}134dfs(1,n);135if(a1<INF) printf("%d %d\n",a1,a2);136else printf("No solution\n");137return 0;138 }

如果觉得《【1109】noip模拟赛》对你有帮助，请点赞、收藏，并留下你的观点哦！