比赛链接：传送门
Gym 101775A Chat Group（签到：待补）
Gym 101775B Scapegoat（待补）
Gym 101775C Traffic Light（贪心+思维）
思路：
需要证明两个点：
① 所有的N+1个S都是必须要走的，并且可以适当安排使得红灯只用等最长的一个。
② 上面这样的安排的答案是S+S+…+S+max(B)，而答案不可能比这个小，因为总有一种走法可以等到最长的那个红绿灯，如果其他的红绿灯也要等的话就比上面的方法大了。
#include <bits/stdc++.h> using namespace std;
const int MAX_N = 1e3 + ; double S[MAX_N];
double A[MAX_N], B[MAX_N]; int main()
{
int T;
cin >> T;
for (int kase = ; kase <= T; kase++) {
int N;
cin >> N;
for (int i = ; i <= N; i++) {
scanf("%lf", S+i);
}
double _max = -;
for (int i = ; i <= N; i++) {
scanf("%lf%lf", A+i, B+i);
_max = max(_max, B[i]);
}
for (int i = ; i <= N; i++) {
_max += S[i];
}
printf("Case #%d: %.6lf\n", kase, _max);
}
return ;
}
Gym 101775J Straight Master（差分）
好久没见过差分了，早就把这种方法忘掉了。。。比赛的时候企图用贪心+松弛标记强行搓，结果一直WA。
思路：（下面的差分都指与前一个相邻的数的差）
大于3的任意长度都可以由3、4、5的长度组成，所以长度大于3的子串都可以构成顺子。因此到第i个位置为止之前的所有正的差分都可以用于更新第i+3个位置及其之后的位置的负差分，如：
0 1 2 3 4 4 4 1
第4个位置为止正差分的和为4，第 4 + 3 = 7 个位置的差分为-3，则剩余的差分和sum为1。O(n)遍历维护差分和sum即可。
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
const int MAX_N = 2e5 + ; int N;
ll a[MAX_N];
ll k[MAX_N];
ll dis[MAX_N]; bool solve()
{
int ind = ;
if (dis[] < || dis[] < )
return false;
ll sum = ;
for (int i = ; i <= N+; i++){
sum += dis[i];
int j = i+;
if (j > N+)
break;
if (dis[j] < ) {
sum += dis[j];
dis[j] = ;
}
if (sum < )
break;
}
if (sum != )
return false;
return true;
} int main()
{
int T;
cin >> T;
for (int kase = ; kase <= T; kase++) {
cin >> N;
a[] = ;
for (int i = ; i <= N; i++) {
scanf("%lld", a+i);
k[i] = ;
dis[i] = a[i] - a[i-];
}
dis[N+] = - a[N];
bool ans = solve();
printf("Case #%d: ", kase);
if (ans)
puts("Yes");
else
puts("No");
}
return ;
}
/*
10
5
3 5 5 2 4
5
3 5 5 2 2
*/
Gym 101775K Downgrade（签到：简单模拟）
思路：
按题意模拟即可。要注意N是10，所以要判断一下状态是否会继续更新。
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
const int MAX_A = 1e5 + ; ll sum[MAX_A], L[MAX_A]; int main()
{
int T;
cin >> T;
for (int kase = ; kase <= T; kase++) {
ll A, B, N;
cin >> A >> B >> N;
sum[] = ;
for (int i = ; i <= A; i++) {
scanf("%lld", &L[i]);
sum[i] = sum[i-] + L[i];
}
ll ansa = A, ansb = B;
ll nxta, nxtb;
while (N--) {
int ind = lower_bound(sum+, sum+A+, ansa) - sum;
nxtb = ansa - sum[ind-];
nxta = ind;
if (nxta == ansa && nxtb == ansb)
break;
ansa = nxta;
ansb = nxtb;
}
printf("Case #%d: %lld-%lld\n",kase, ansa, ansb);
}
return ;
}
/*
3
3 2 2
2 2 2
3 1 2
1 1 1
3 1 1000000000
1 1 1
*/
Gym 101775L SOS（博弈+思维）
思路：
博弈有两种题，思维题、SG函数题。不管是哪种，上来先打个表。。。其他的打完了表再说。。。打表发现N为大于5的所有奇数都是Panda，N为大于14的所有偶数都是Sheep，其他的为Draw。
然后是证明：只要构造了S _ _ S的局面，然后跟对手一起把其他的空位填满，下一个填字符的人就必输了。根据N奇偶性，填满空位后面临S _ _ S的局面的人是不同的。所以有下面两种情况：
① N为奇数的时候：先手Panda要尽可能构造S _ _ S的局面，而Sheep要尽量避免被构造出S _ _ S的局面。当N = 7时，Panda第一次可以在Sheep的干扰下成功构造S _ _ S的局面：
Panda: _ _ _ S _ _ _
Sheep: _ _ _ S _ _ O
Panda: S _ _ S _ _ O
不管Sheep放在哪边，Panda都可以在另一边构造S _ _ S的局面。
② N为偶数的时候Panda要尽可能避免被Sheep构造出这样的局面，这时候就轮到Sheep来构造S _ _ S的局面了。由①可以发现，当剩下了7个空位时，可以把S放在中间，就能在Panda的干扰下构造S _ _ S的局面。但是有一点需要注意：就是N = 14时：
Panda: _ _ _ _ _ _ O _ _ _ _ _ _ _
Sheep: _ _ _ _ _ _ O _ _ _ S _ _ _
Panda: _ _ _ _ _ _ O _ _ _ S _ _ O
Sheep: _ _ _ _ _ _ O S _ _ S _ _ O
Panda: _ _ _ _ _ S O S _ _ S _ _ O
Game Over.
Sheep放第二个S的时候如果是在O的旁边，那就崩盘了。所以N=14的时候Panda还是能反制Sheep的，但是当N = 16时Panda就无还手之力了：
Panda: _ _ _ _ _ _ _ O _ _ _ _ _ _ _ _
Sheep: _ _ _ _ _ _ _ O _ _ _ _ S _ _ _
Panda: _ _ _ _ _ _ _ O _ _ _ _ S _ _ O
Sheep: _ _ _ _ _ _ _ O _ S _ _ S _ _ O
#include <bits/stdc++.h> using namespace std;
const int MAX_N = + ; int main()
{
int T;
cin >> T;
int kase = ;
while (T--) {
int N;
cin >> N;
printf("Case #%d: ", kase++);
if (N > && N % )
puts("Panda");
else if (N < )
puts("Draw");
else
puts("Sheep");
}
return ;
}
Gym 101775M World Cup（签到：待补）