大致的题面如下：
T1
Alice 和 Bob 玩游戏。有一个长度为 \(N\) 的字符串 \(S\)，由 L 和 R 组成。Alice 先手，Bob 后手。他们可以：
- 选择一个 \(i\)。
- 如果 \(S_i\)=
L，那么只保留 \(S_{1\sim i-1}\)。 - 如果 \(S_i\)=
R，那么只保留 \(S_{i+1,|S|}\)。
第一个遇到 \(S\) 空了的输掉。问谁会赢。\(T\) 组数据。
对于 \(\sim 50\%\)，\(1\le \sum N\le 500\)。
对于 \(\sim 73\%\)，\(1\le \sum N\le 5000\)。
对于 \(100\%\)，\(1\le \sum N\le 10^6\)。
样例：
1
6
RLRLRL
Bob
T2
有一个长度为 \(N-1\) 的数组 \(f_{1\sim N-1}\)。定义 \(g_{i,j}=\min_{k=i}^{j}f_k\)。
定义 \(1\le i\le N,f'_i=\sum_{j=1}^{i-1}g_{j,i-1}+\sum_{j=i}^{n-1}g_{i,j}\)。给定 \(f'_{1\sim N}\)，还原 \(f_{1\sim N-1}\)。（如果有输出 Yes 和构造，没有输出 No）。
对于 \(11\%\)，\(N\le 5\)，A 性质。
对于另外 \(15\%\)，\(N\le 8\)。
对于另外 \(13\%\)，\(N\le 14\)。
对于另外 \(\sim 20\%\)，\(N\le 50\)，B 性质。
对于另外 \(\sim 20\%\)，\(N\le 50\)。
对于 \(100\%\)，\(N\le 80\)，\(f'_i\le 10^8\)。
A 性质：如果 Yes，存在一种满足 \(f_i\le 20\)。
B 性质：如果 Yes，存在一种满足 \(f_i\le 50\)。
样例：
3
2 3 3
Yes
1 2
T3
给定一个有 \(2^h-1\) 个节点的大根堆。用 \(a_1\dots a_{2^h-1}\neq 0\) 表示。
定义一个操作为：
- 选择一个 \(i\)，\(a_i\neq 0\)。把 \(a_i\) 替换成 \(0\)。
- 重复以下操作直到 \(2i\ge 2^h\)：
- 如果 \(a_{2i+1}>a_{2i}\)，交换 \(a_i\) 和 \(a_{2i+1}\)，\(i\leftarrow 2i+1\)。
- 否则，交换 \(a_i\) 和 \(a_{2i}\)，\(i\leftarrow 2i\)。
相当于 shiftup 操作，维护大根堆性质。
初始集合 \(S_1=S_2=\emptyset\)。有 \(q\) 个操作：
1 x y，\(S_y=S_y\cup x\)，这时 \(x\notin S_y\)。2 x y，\(S_y=S_y-\{x\}\)，这时 \(x\in S_y\)。3 x z，求有多少 \(S_1\subset S\subset S_1\cap S_2\)，满足存在操作序列- 操作完 \(a_{x\in S}\neq 0\)。(1)
- (1) 的前提下，\(\sum_{i=1}^{2^{h}-1}a_i\) 最小。(2) 保证仅有一个操作序列满足。
- (2) 的前提下，\(a_x=z\)。
对于 3 x z 输出答案。
对于 \(10\%\)，\(h\le 2,q\le 50\)。
对于 \(10\%\)，\(h\le 4,q\le 500\)。
……（有点忘了）
对于 \(100\%\)，\(h\le 18,q\le 5000(?)\)。
\(1\le a_i\le ?\)。
T1 Sol
\(N\le 5000\) 的暴力：
很容易发现如果 \(S_0\)=L 或 \(S_{N-1}\)=R 会 Alice 直接赢。如果不是这样的话，Alice 只能选连续的 L 和 R 中的（否则 Bob 就赢了）。所以不连续的就忽略。因此得到一个算法，每次删掉单个的，然后判断。
大概这样：
string chg(string x){
string res;
for (int i=1; i<x.size(); i++){
if (x[i]==x[i-1]){
res.push_back(x[i]);
}
}
return res;
}
while (s.size()){
if (s[0]=='L' || s[s.size()-1]=='R'){
cout<<"Alice"<<endl;
return;
}
string t=chg(s);
if (t==s){
break;
}
s=t;
}
cout<<"Bob"<<endl;
考虑连续的啥意思。
不就是每一次 chg，都是把连续快长度 \(-1\)。那不就是，如果有前缀 L 个数大于 R 个数最后就会缩成 L，如果有后缀 R 个数大于 L 个数最后就会缩成 R！这样 Alice 就赢了。
然后就做完了。代码很短。
大概这样：
int cur=0;
for (int i=0; i<n; i++){
cur+=s[i]=='L'?1:-1;
if (cur>0){
cout<<"Alice"<<endl;
return 0;
}
}
cur=0;
for (int i=n-1; i>=0; i--){
cur+=s[i]=='R'?1:-1;
if (cur>0){
cout<<"Alice"<<endl;
return 0;
}
}
cout<<"Bob"<<endl;