【20161108】总结
分类:
IT文章
•
2022-03-20 10:13:52
啊啊啊，今天的题目比较简单。
然后我我我。。因为吸取以前教训，花时间拍了2题，然后就A了那两题，
其他两题，一个没搞边界爆了数组，一个打完点分治没调过样例，直接交暴力了。。ORZ
1、
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。
刚看题，似曾相识。。
仔细一看，有点不一样。。。
再看，，像是阶梯nim，开心地打了起来。
然后。。。错了。。。。看了一看。。好像又不怎么一样。。
怎么破好心慌= =
打完2、3题后回来做。。。先打个暴力。。。敲敲敲....
感觉可以先弄到最右边，因为根据奇偶可以确定谁先遇到后面一排棋子的状态。
然后谁赢呢，这样可以找规律了耶，然后找规律：MMLLMMLLMMLL....找到了ORZ
试试对不对，一排，哇！！！成功了！！！【我自己其实是蒙B的。。。
然后就A了。。。
放题解：
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7 #define Maxn 1010
8
9 char s[Maxn];
10
11 int main()
12 {
13 int T;
14 scanf("%d",&T);
15 while(T--)
16 {
17 int n;
18 scanf("%d",&n);
19 scanf("%s",s);
20 int sum=0,p=0,q=0,ans=0;
21 for(int i=n-2;i>=0;i--)
22 {
23 if(s[i]=='o') p+=sum,q++;
24 else sum++;
25 }
26 if(p%2==0)
27 {
28 if(q%4==1||q%4==2) printf("M
");
29 else printf("L
");
30 }
31 else
32 {
33 if(q%4==1||q%4==2) printf("L
");
34 else printf("M
");
35
36 }
37 // else printf("M
");
38 }
39 return 0;
40 }
View Code
2、
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。
这题R了ORZ。。。
有小伙伴数组没有开够。。。
打的时候十分有信心，我这样打数组不用开两倍的，不会爆！！
然后就。。没有判边界ORZ。。。
bac代码：
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7 #define Maxn 110
8
9 int a[Maxn][Maxn],f[Maxn][Maxn][Maxn];
10
11 int mymax(int x,int y) {return x>y?x:y;}
12 int myabs(int x) {return x>0?x:-x;}
13
14 int main()
15 {
16 int n;
17 scanf("%d",&n);
18 for(int i=1;i<=n;i++)
19 for(int j=1;j<=n;j++)
20 scanf("%d",&a[i][j]);
21 memset(f,0,sizeof(f));
22 for(int i=2;i<=2*n-1;i++)
23 for(int j=1;j<i;j++) if(i-j<=n)
24 for(int k=1;k<i;k++) if(i-k<=n)
25 {
26 if(j>n||k>n) continue;
27 int y1=i-j,y2=i-k;
28 if(j<=n&&k<=n) f[j+1][y1][k+1]=mymax(f[j+1][y1][k+1],f[j][y1][k]+myabs(a[j+1][y1]-a[k+1][y2]));
29 if(j<=n&&y2<=n) f[j+1][y1][k]=mymax(f[j+1][y1][k],f[j][y1][k]+myabs(a[j+1][y1]-a[k][y2+1]));
30 if(y1<=n&&k<=n) f[j][y1+1][k+1]=mymax(f[j][y1+1][k+1],f[j][y1][k]+myabs(a[j][y1+1]-a[k+1][y2]));
31 if(y1<=n&&y2<=n) f[j][y1+1][k]=mymax(f[j][y1+1][k],f[j][y1][k]+myabs(a[j][y1+1]-a[k][y2+1]));
32 }
33 printf("%d
",f[n][n][n]);
34 return 0;
35 }
View Code
3、
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
各种乱搞的题目，我用倍增各种乱搞，还有前缀和。。。
其实一开始对倍增是拒绝的，上了个厕所之后。。。
还是倍增吧，区间最值，想不到其他更好的【线段树是什么？
然后正解是，单调队列。。。。ORZ。。这是个滑动窗口啊傻！！！
倍增垃圾版：
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7 #define Maxn 1010
8
9 int w[Maxn][Maxn],sm[Maxn][Maxn],v[Maxn][Maxn];
10 int mn[Maxn][Maxn];
11 int f[Maxn][12];
12 int n,m,b,a,d,c;
13
14 int mymin(int x,int y) {return x<y?x:y;}
15 int mymax(int x,int y) {return x>y?x:y;};
16
17 void ffind()
18 {
19 for(int i=c;i<=n;i++)
20 for(int j=d;j<=m;j++)
21 v[i][j]=sm[i][j]-sm[i-c][j]-sm[i][j-d]+sm[i-c][j-d];
22 /*for(int i=1;i<=n;i++)
23 {
24 for(int j=1;j<=m;j++)
25 printf("%d ",v[i][j]);
26 printf("
");
27 }*/
28
29
30 int id=0;
31 while((1<<id)<=b-d-1) id++;id--;
32 // printf("id=%d
",id);
33 // printf("xx=%d
",b-d-1);
34
35 for(int i=c;i<=n;i++)
36 {
37 memset(f,63,sizeof(63));
38 for(int j=d;j<=m;j++)
39 {
40 f[j][0]=v[i][j];
41 for(int k=1;j-(1<<k)+1>=d;k++)
42 f[j][k]=mymin(f[j-(1<<k-1)][k-1],f[j][k-1]);
43 if(j>=b-2) mn[i][j]=mymin(f[j][id],f[j-b+d+1+(1<<id)][id]);
44 }
45 }
46 for(int i=1;i<=n;i++)
47 for(int j=1;j<=m;j++) v[i][j]=mn[i][j];
48
49 /*for(int i=1;i<=n;i++)
50 {
51 for(int j=1;j<=m;j++)
52 printf("%d ",v[i][j]);
53 printf("
");
54 }
55 printf("
");*/
56 id=0;
57 while((1<<id)<=a-c-1) id++;id--;
58 // printf("id=%d
",id);
59 // printf("xx=%d
",a-c-1);
60 memset(mn,63,sizeof(63));
61 for(int j=b-2;j<=m;j++)
62 {
63 memset(f,63,sizeof(63));
64 for(int i=c;i<=n;i++)
65 {
66 f[i][0]=v[i][j];
67 for(int k=1;i-(1<<k)+1>=c;k++)
68 f[i][k]=mymin(f[i-(1<<k-1)][k-1],f[i][k-1]);
69 if(i>=a-2) mn[i][j]=mymin(f[i][id],f[i-a+c+1+(1<<id)][id]);
70 }
71 }
72 /*for(int i=1;i<=n;i++)
73 {
74 for(int j=1;j<=m;j++)
75 printf("%d ",mn[i][j]);
76 printf("
");
77 }*/
78 }
79
80 void init()
81 {
82 scanf("%d%d%d%d%d%d",&m,&n,&b,&a,&d,&c);
83 for(int i=1;i<=n;i++)
84 for(int j=1;j<=m;j++)
85 scanf("%d",&w[i][j]);
86 memset(sm,0,sizeof(sm));
87 for(int i=1;i<=n;i++)
88 for(int j=1;j<=m;j++)
89 sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+w[i][j];
90 /*for(int i=1;i<=n;i++)
91 {
92 for(int j=1;j<=m;j++)
93 printf("%d ",sm[i][j]);
94 printf("
");
95 }*/
96 ffind();
97 }
98
99 int main()
100 {
101 init();
102 int ans=0;
103 for(int i=a;i<=n;i++)
104 for(int j=b;j<=m;j++)
105 {
106 ans=mymax(ans,sm[i][j]-sm[i-a][j]-sm[i][j-b]+sm[i-a][j-b]-mn[i-1][j-1]);
107 }
108 printf("%d
",ans);
109 return 0;
110 }
View Code
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7 #define Maxn 100010
8 #define Mod 1000003
9 #define INF 0xfffffff
10 #define LL long long
11
12 LL v[Maxn],ny[Mod+11100],k;
13 int n;
14
15 struct node
16 {
17 int x,y,next;
18 }t[Maxn*2];int len;
19 int first[Maxn];
20
21 void ins(int x,int y)
22 {
23 t[++len].x=x;t[len].y=y;
24 t[len].next=first[x];first[x]=len;
25 }
26
27 int mymax(int x,int y) {return x>y?x:y;}
28 int mymin(int x,int y) {return x<y?x:y;}
29
30 LL qpow(LL x,LL b)
31 {
32 LL ans=1;
33 while(b)
34 {
35 if(b&1) ans=(ans*x)%Mod;
36 x=(x*x)%Mod;
37 b>>=1;
38 }
39 return ans;
40 }
41
42 bool vis[Maxn];
43 int sm[Maxn],mx[Maxn];
44 int ffind(int x,int tot,int f)
45 {
46 sm[x]=1;mx[x]=0;
47 int rt=-1;
48 for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&vis[t[i].y])
49 {
50 int y=t[i].y;
51 int rrt=ffind(y,tot,x);
52 if(mx[rrt]<mx[rt]||rt==-1) rt=rrt;
53 mx[x]=mymax(mx[x],sm[y]);
54 sm[x]+=sm[y];
55 }
56 mx[x]=mymax(mx[x],tot-sm[x]);
57 if(rt==-1||mx[x]<mx[rt]) return x;
58 return rt;
59 }
60
61 LL dis[Maxn];
62 int q[Maxn],ql,wr[Mod+1100];
63 int a1,a2;
64 void dfs(int x,int f,int rt)
65 {
66 dis[x]=(v[x]*dis[f])%Mod;
67 q[++ql]=x;
68 LL A=(((ny[dis[x]]*dis[rt])%Mod)*k)%Mod;
69 if(wr[A]<=n)
70 {
71 int n1=mymin(wr[A],x),n2=mymax(wr[A],x);
72 if(n1<a1||(n1==a1&&n2<a2)) a1=n1,a2=n2;
73 }
74
75 for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&vis[t[i].y])
76 {
77 int y=t[i].y;
78 dfs(y,x,rt);
79 }
80 }
81
82
83 void get_ans(int x)
84 {
85 ql=0;dis[x]=v[x];wr[v[x]]=x;
86 int now;
87 vis[x]=0;
88 for(int i=first[x];i;i=t[i].next) if(vis[t[i].y])
89 {
90 now=ql;
91 dfs(t[i].y,x,x);
92 for(int j=now+1;j<=ql;j++) wr[dis[q[j]]]=mymin(wr[dis[q[j]]],q[j]);
93 }
94
95 for(int i=1;i<=ql;i++) wr[dis[q[i]]]=INF;
96 wr[v[x]]=INF;
97 for(int i=first[x];i;i=t[i].next) if(vis[t[i].y])
98 {
99 int rt=ffind(t[i].y,sm[t[i].y],0);
100 // printf(".
");
101 // printf("%d
",t[i].y);
102 get_ans(rt);
103 }
104 }
105
106 int main()
107 {
108 // for(int i=1;i<Mod;i++) ny[i]=qpow(i,Mod-2);
109 ny[1]=1;
110 for(int i=2;i<Mod;i++) ny[i]=(Mod-Mod/i)*ny[Mod%i]%Mod;
111 // printf(".
");
112 scanf("%d%lld",&n,&k);
113 for(int i=1;i<=n;i++) scanf("%d",&v[i]);
114 len=0;
115 memset(first,0,sizeof(first));
116 for(int i=1;i<n;i++)
117 {
118 int x,y;
119 scanf("%d%d",&x,&y);
120 ins(x,y);ins(y,x);
121 }
122 memset(vis,1,sizeof(vis));
123 int rt=ffind(1,n,0);
124 memset(wr,63,sizeof(wr));
125 a1=a2=INF;
126 get_ans(rt);
127 if(a1==INF) printf("No solution
");
128 else printf("%d %d
",a1,a2);
129 return 0;
130 }
