Codeforces Round #740 B,C

Codeforces Round #740 B,C"/>

Codeforces Round #740 B,C

B. Charmed by the Game

题意：
2个人打球，发球顺序是交替的，一开始如果是A发球，那么下一次就是B发球，第一个发球是谁，是不确定的

游戏中
发球者赢了，视为守住球了
接球者赢了，视为break了

现在给出A赢了a局，B赢了b局

k的值定义为break的次数，问k的所有可能值

思路：
1.分析题要求出来什么
题中要我们求出的是
在A赢了a局和B赢了b局的基础上，所有合法比赛结果中，对于每种结果的k值

2.分析题中给出的所有参数的隐藏含义
题中就给出了1个条件和2个参数
1，A赢了a场，B赢了b场
那么就可以知道总共进行了a + b 场

2.发球的交替进行的
所以，在a + b 场中发球的顺序只有2种
ABABABAB…
BABABABA…

3.根据发现的东西求解
发球顺序有2种，所以分情况讨论

A先发球
那么比赛中,可以确定
A发了 p = (a + b) / 2 场球
B发了 q = (a + b) / 2 场球
当a + b是奇数的时候 p 还要加1

那么变量就是A在B发球的时候，赢的次数，和B在A发球的时候，赢得次数
设 A 赢的次数时 x，B为 y
此时
0 <= x <= q
0 <= y <= p

这样就可知
a 接球赢了 x 次
a 发球赢了 a - x 次

b 接球赢了 y 次
b 发球赢了 b - y次

现在就要想怎样把x和y联系起来
a接球赢了 x 次
也就代表着
b发球的所有场中
a 赢了 x次
b 赢了 b - y 次
所以
x + (b - y) = q
x = q - b + y

那么就可以枚举所有的y，得到对应的x
x + y 就是 一个 k 值

B先发球
唯一变化的就是发球的场数
原本A发球的场数变成了B的，所以交换一下就好了

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>using namespace std;
const int N = 2e5 + 10;
int st[N];
vector<int> res;int f(int y,int q,int b)
{return q - b + y;
}void solve(int a,int b,int p,int q)
{for(int i = 0;i <= p;i ++){int x = f(i,q,b);if(x >= 0 && x <= q && !st[x + i]) res.push_back(x + i),st[x + i] = 1;} 
}int main()
{int t;cin >> t;while(t --){res.clear();memset(st,0,sizeof st);int a,b;cin >> a >> b;int p,q;p = (a + b) / 2;q = (a + b) / 2;if((a + b) & 1) p ++;//   vector<int> res;solve(a,b,p,q);solve(b,a,p,q);sort(res.begin(),res.end());cout << res.size() << endl;for(auto x : res) cout << x << " ";cout << endl;}return 0;
}

C. Deep Down Below

题意：
有n个洞穴，每个洞穴中有ki个怪物
一个人去杀怪物，当他的能力严格大于一个怪物的时候，就可以杀，不然就死
当进入一个洞穴后，它会从第一个一直杀到最后一个，不会出现跳过一个怪物的情况，杀死一个怪物后能量会加1
进入洞穴的顺序，他可以自己安排
问他最少需要多少能量，能杀死所有怪物

思路：
1.分析题中要求什么
进入洞穴的顺序直接影响到，初始的能量值，所以在所有顺序中找到所需的最小的能量值

2.分析题中给出的条件意义
杀一个怪物能量会加1
那么根据一个怪物的能量，和它所在位置的编号可以推出来，进入这个洞穴杀死这个怪物的最小能量值可以是多少

设位置编号为i，怪物能量为w，最小能量值为x
x + i - 1 > w
x > w - i + 1
那么对这个洞穴每一个怪物求一个x并取一个最大值，这个值就是杀死这个洞穴怪物需要的最小能量值
那么每个洞穴就对应到一个值了

现在就要找一种顺序，并且求出这个顺序下的最小能量值
因为杀完一个洞穴，能量值会增加
所以，一开始从最小的开始杀，能使能量值尽可能小

证明：
假设能量为x，一个洞穴所需最小能量值为y，另一个为z，并且y < z

如果先从z开始杀
可以找到一个x满足 x > z > y
在杀完z后
x 会增加 那么它是一定可以杀 y 的

如果从y开始杀
可以找到一个 x 满足 z > x > y
在杀完y后
x 增加完后，如果 x > z 就还可以继续杀z，如果不是，也总能找到一个x满足

那么上面的初始能量值都可以达到杀2个洞穴的结果，不过比起初始值，显然先杀y的值更小

所以进入洞穴的最好顺序就是从小到大

然后现在就需要在这个顺序上找一个最小满足条件的能量值

可以发现具有二分性质，当一个值不满足的时候，那么比他小的值都不会满足

所以进行二分即可

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;const int N = 1e9 + 10;
int n,t;
vector<pair<int,int>> a;
typedef pair<int,int> pii;int check(int x)
{for(int i = 0;i < a.size();i ++)if(x <= a[i].first)  return 0;else x += a[i].second;return 1;
}bool cmp(pii b,pii c)
{if(b.first == c.first) return b.second > c.second;return b.first < c.first;
}int main()
{cin >> t;while(t --){a.clear();cin >> n;for(int i = 1;i <= n;i ++){int x = 0;int k;cin >> k;for(int j = 1;j <= k;j ++){int y;cin >> y;y -= j - 1;x = max(x,y);}a.push_back({x,k});}sort(a.begin(),a.end(),cmp);int l = 0,r = N;while(l < r){int m = l + r >> 1;if(check(m)) r = m;else l = m + 1;}cout << r << endl;}return 0;
}