B. 回文串

单点时限: 2.0 sec
内存限制: 512 MB
QQ 小方以前不会判断回文数列,现在他会了,所以他急切的想教会你。回文数列指的是一个正读和反读都一样的数列,比如 “1 2 3 2 1” 和 “1 2 2 1”。单单讲给你听肯定是不够的,为了表现自己,QQ 小方现在要考考你。
现在 QQ 小方会给你 n个数组成的数列 a1,a2,⋯,an。他每次操作允许你合并其中相邻的两个数 ai和 ai+1(i<),合并以后的两个数留在原来的位置(两个数合并以后只会留下一个数),但会变成ai+ai+1。QQ 小方想知道最少需要几次这样的操作,这个数列就会变成回文数列。
输入格式
输入包含两行,第一行一个整数 n(1≤n≤106),表示数列的长度。第二行包含 n个用空格隔开的数
a1,a2,⋯,an(0≤ai≤109),表示数列。
输出格式
输出包含一个整数,表示最少的操作次数。
样例
Input
3
1 2 3
Output
1
Input
3
1 2 4
Output
2
Input
3
3 3 3
Output
0
提示
对于样例一:只需要一步,即合并前两个。
对于样例二:只有合并成一个数的时候,才满足回文数列的要求,所以需要两步。
对于样例三:本身就是一个回文数列,不需要合并操作。

思路:

贪心 建立一个数组设立左右下标 然后左右维护直到左下标等于右下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long num[1000005];
int main()
{
int n,left,right,sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
left=1;
right=n;
while(1){
if(left>=right) break;
if(num[left]<num[right]){
num[left+1]=num[left]+num[left+1];
left++;
sum++;
}
else if(num[left]>num[right]){
num[right-1]=num[right]+num[right-1];
right--;
sum++;
}
else{
left++;
right--;
}
}
printf("%d",sum);

return 0;
}

D. 宇恒棋

单点时限: 1.0 sec
内存限制: 256 MB
QQ小方以前不会下宇恒棋,现在他会了,所以他急切的想教会你。
宇恒棋的规则是这样的:在一个 n×m的棋盘上,QQ小方和你各有一枚棋子。你们轮流行动,每一次轮到一方的回合时,他必须把自己的棋子往上,下,左或右移动一格,但不能超出棋盘的边界。如果这一方的棋子吃掉了另一方的棋子,也就是这一方在他的回合将自己的棋子移动到了另一方棋子的位置上,那这一方就赢得了这局比赛但单单讲给你听肯定是不够的,为了表现自己,QQ小方现在要考考你。
现在,该轮到QQ小方行动了。QQ小方想知道在双方采取最优策略的情况下,比赛结果究竟会是怎样的。
输入格式
第一行两个数 n,m( 1≤n,m≤100),代表棋盘有 n行 m列。
第二行四个整数
x1,y1,x2,y2( 1≤x1,x2≤n,1≤y1,y2≤m),代表QQ小方的棋子在第 x1行 y1列,而你的棋子在第 x2行 y2列,保证一开始给出的两个棋子坐标不会重合。
输出格式
一行一个字符串,如果你赢则输出 Win,如果QQ小方赢则输出 Lose,如果平局则输出 Tie。

思路:

蜜汁感觉两个人是不可能平局的 因为当一个人退步时另一个人肯定会逼近 然后就只有你死我活了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;

int main()
{
int n,m;
scanf("%d%d",&n,&m);
int x,y,a,b;
scanf("%d%d%d%d",&x,&y,&a,&b);
int p,q;
p=abs(x-a);
q=abs(y-b);
if((p+q)%2) printf("Lose");
else printf("Win");
return 0;
}

最后更新: 2019年03月25日 21:41

原始链接: http://yoursite.com/2019/03/22/EOJ-Monthly-2019-3/

× 请我吃糖~
打赏二维码