Dyd's Blog

He who has a strong enough why can bear almost any how.

CF1455C Ping-pong

结论题?

Ping-pong

$1100$ ,不是很简单了,先考虑贪心吧

但是一个细节是体力少的一方可以不打,等对方体力耗完,可以这样理解:反正体力少这把必输,且打不打体力差都变小 $1$ ,不如不打保留实力

由上也可以得到一个策略:设双方体力为 $x, y$ ,若 $x > y(y > x)$ ,则体力大的一方赢 $x - y$ 次,双方体力都变成 $y$

而当体力相同时,先开球的人必输,但他们是优先保证自己赢的多,所以先/后手都不会让体力被一把打尽,就会故意输(对于先手,这把输了双方体力相同,而对方变成下一把的先手;对于后手,这把输了自己体力更大,下把必胜),所以体力相同的时候两人一定是每个人都把自己的体力赢完

但第一局Alice必须开球,所以她的胜场会少 $1$

另外,其实看样例找规律也能做吧?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
#define LL long long
#define STC static
using namespace std;
const int N = 1;

int main()
{
int T, x, y;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &x, &y);
printf("%d %d\n", x - 1, y);
}
return 0;
}