（T1）lnsyoj2208 逆流而上/P10737 [SEERC2020] Reverse Game
考虑到失败时字符串应为前面都是0，后面都是1(例如"0000001111111")
所以可以将原串的逆序对数求出，记为m，对于每个可翻转的串进行分类讨论:
1."10"->"01"可以将原串的逆序对减1。
2."100"->"001" "110"->"011" "1010"->"0101"可以将原串的逆序对减2。
综上所述，该问题变成了取石子问题。
所以当m%3==0时后手(B)胜，否则先手(A)胜。
代码如下:
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
int cnt1;
int T;
int n;
char s[1000005];
signed main(){
scanf("%lld",&T);
while(T--){
scanf("%s",s+1);
n=strlen(s+1);
cnt1=0;
int res=0;
for(int i=1;i<=n;i++){
if(s[i]=='1'){
cnt1++;
}
else if(s[i]=='0'){
res+=cnt1;
}
}
if(res%3==0){
printf("B\n");
}
else{
printf("A\n");
}
}
return 0;
}
（T2）lnsyoj2209 帝国飘摇/P10455 Genius Acm
未订正
（T3）lnsyoj2210 致命冲击/P5069 [Ynoi2015] 纵使日薄西山
未订正
（T4）lnsyoj2211 通天之塔/P10652 「ROI 2017 Day 1」前往大都会
此题一共有两个问，可以分别求一下：
1.对于第一问，直接跑最短路即可。
2.对于第二问，可以使用dp解决，方法如下:
设\(f_i\)为到i点时e的和的最大值
可得\(f_i=f_j+(dis_i-dis_j)^2\)
利用斜率优化dp，经过化简得\(f_{i}-dis_{i}^{2}=f_{j}+dis_{j}^{2}-2dis_{i}dis_{j}\)
由此得\(\begin{cases}x=dis_{j}\\y=f_{j}+dis_{j}^{2}\\k=2dis_{i}\\b=f_{i}-dis_{i}^{2}\end{cases}\)
因为要使\(f_i\)最大，所以应该使\(b\)最大，所以维护上凸包。
考虑\(x\)和\(k\)均单调递增，所以维护单调栈。
对于本题需要先建一个最短路图（\(dis_{u}+w_{u,v}=dis_{v}\)的边所连成的图），然后对于每个火车线分别维护一个单调栈（坑点：对于在同一条火车线但被分成两段的边需要分别开栈）。
对于所有点需要按\(dis\)进行排序，保证\(x\)和\(k\)单调，然后对于每个点，先通过经过这个点的所有铁路线算出这个点的dp，再把这个点放到经过这个点的每个铁路所维护的凸包中。
最后得出答案。
代码如下：
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
struct Edge{
int next;
int to;
int w;
//int vi;
int u;
}es[2000005];
int head[1000005],cnt;
vector<int> vi[1000005];
vector<int> nr[1000005];
inline void add(int u,int v,int w,int vi1){
es[cnt].next=head[u];
es[cnt].to=v;
es[cnt].w=w;
es[cnt].u=u;
vi[vi1].push_back(cnt);
head[u]=cnt;
cnt++;
}
int n,m;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
struct ys{
int dis;
int id;
}yss[1000005];
bool cmp1(ys a,ys b){
return a.dis<b.dis;
}
bool cmp2(ys a,ys b){
return a.id<b.id;
}
bool vis[1000005];
int dp[1000005];
vector<int> stas[1000005];
vector<int> cov[1000005];
inline int calc(int i,int j){//yss编号
return dp[yss[j].id]+(yss[i].dis-yss[j].dis)*(yss[i].dis-yss[j].dis);
}
inline long double slope(int a,int b){//yss编号
return 1.0*(dp[yss[a].id]+yss[a].dis*yss[a].dis-dp[yss[b].id]-yss[b].dis*yss[b].dis)/\
(long double)(yss[a].dis-yss[b].dis);
}
int cntv;
signed main(){
cnt=1;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
int l,u,v,w;
scanf("%lld",&l);
scanf("%lld",&u);
for(int j=1;j<=l;j++){
scanf("%lld",&w);
scanf("%lld",&v);
add(u,v,w,i);
u=v;
}
}
for(int i=1;i<=n;i++){
yss[i].dis=0x3f3f3f3f3f3f3f3f;
yss[i].id=i;
}
yss[1].dis=0;
pq.push({0,1});
while(!pq.empty()){
int u=pq.top().second;
pq.pop();
if(vis[u]){
continue;
}
vis[u]=true;
for(int i=head[u];i;i=es[i].next){
int v=es[i].to;
if(yss[u].dis+es[i].w<yss[v].dis){
yss[v].dis=yss[u].dis+es[i].w;
pq.push({yss[v].dis,v});
}
}
}
for(int i=1;i<=m;i++){
for(int j=0;j<vi[i].size();j++){
if(yss[es[vi[i][j]].u].dis+es[vi[i][j]].w==yss[es[vi[i][j]].to].dis){
nr[i].push_back(vi[i][j]);
}
}
}
for(int i=1;i<=m;i++){
if(!nr[i].empty()){
cntv++;
cov[es[nr[i][0]].u].push_back(cntv);
cov[es[nr[i][0]].to].push_back(cntv);
}
for(int j=1;j<nr[i].size();j++){
if(es[nr[i][j]].u!=es[nr[i][j-1]].to){
cntv++;
cov[es[nr[i][j]].u].push_back(cntv);
}
cov[es[nr[i][j]].to].push_back(cntv);
}
}
sort(yss+1,yss+n+1,cmp1);
for(int i=1;i<=n;i++){
for(int j=0;j<cov[yss[i].id].size();j++){
if(stas[cov[yss[i].id][j]].empty()){
continue;
}
while(stas[cov[yss[i].id][j]].size()>1 && \
calc(i,stas[cov[yss[i].id][j]][stas[cov[yss[i].id][j]].size()-1])<\
calc(i,stas[cov[yss[i].id][j]][stas[cov[yss[i].id][j]].size()-2])){
stas[cov[yss[i].id][j]].pop_back();
}
dp[yss[i].id]=max(dp[yss[i].id],calc(i,stas[cov[yss[i].id][j]].back()));
}
for(int j=0;j<cov[yss[i].id].size();j++){
while(stas[cov[yss[i].id][j]].size()>1 && \
slope(i,stas[cov[yss[i].id][j]][stas[cov[yss[i].id][j]].size()-1])>\
slope(stas[cov[yss[i].id][j]][stas[cov[yss[i].id][j]].size()-1],stas[cov[yss[i].id][j]][stas[cov[yss[i].id][j]].size()-2])){
stas[cov[yss[i].id][j]].pop_back();
}
stas[cov[yss[i].id][j]].push_back(i);
}
}
sort(yss+1,yss+n+1,cmp2);
printf("%lld %lld\n",yss[n].dis,dp[n]);
return 0;
}