写篇题解证明我还在 OI 的世界里活着（
比赛地址：https://atcoder.jp/contests/abc237。
只有 ABCDEFG 的题解，H 不会。
A
模拟。
Code
void mian(){
ll n;scanf("%lld",&n);
if(-2147483648<=n&&n<=2147483647)puts("Yes");
else puts("No");
}
B
模拟。但是一个比较恶心的东西是 \(1\le H,W\le 10^5\) 然后 \(HW\le 10^5\)。其实我们只需要把所有数存到一个一维数组里，然后写一个 get(x,y) 表示 \((x,y)\) 在一维数组里的位置就行了。
Code
const int N=1e5;
int a[N+10],b[N+10];
int n,m;
int get1(int i,int j){return (i-1)*m+j;}
int get2(int i,int j){return (j-1)*n+i;}
void mian(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[get1(i,j)]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
b[get2(i,j)]=a[get1(i,j)];
for(int i=1;i<=n*m;i++){
printf("%d ",b[i]);
if(i%n==0)puts("");
}
}
C
其实所有的字符串都可以化归成这种情况：中间是一个字符串，前面是 \(cnt_1\) 个 \(\texttt a\)，后面是 \(cnt_2\) 个 \(\texttt a\)。
显然 \(cnt_1\gt cnt_2\) 时是不行的（因为不能删字符），否则看中间那个字符串是不是回文的即可。
Code
const int N=1e6;
char s[N+10];
bool check(int l,int r){
for(int i=l;i<=r;i++)
if(s[i]!=s[r-i+l])return 0;
return 1;
}
void mian(){
scanf("%s",s+1);
int n=int(strlen(s+1)),l=1,r=n;
while(s[l]=='a')l++;
while(s[r]=='a')r--;
// [1,l-1] [l,r] [r+1,n]
if(l-1>n-r)return puts("No"),void();
if(check(l,r))puts("Yes");
else puts("No");
}
D
正着做很麻烦，考虑反着做。
然后题就变成这样了：先插入一个 \(n\)，如果 \(s_i=\texttt L\)，则在最右边插入 \(i-1\)，否则在最左边插入 \(i-1\)，最后输出这个数列。
用双端队列实现即可。
Code
const int N=5e5;
char s[N+10];
void mian(){
int n;scanf("%d",&n);
scanf("%s",s+1);
std::deque<int> q;
q.push_back(n);
for(int i=n;i>=1;i--)
if(s[i]=='L')q.push_back(i-1);
else q.push_front(i-1);
for(int i=1;i<=n+1;i++){
int x=q.front();q.pop_front();
printf("%d ",x);
}
puts("");
}
E
对于每一条边 \((u,v)\)，不妨设 \(H_u\ge H_v\)，连一条权值为 \(H_u-H_v\) 的有向边 \(\langle u,v\rangle\)，再连一条权值为 \(2(H_v-H_u)\) 的有向边 \(\langle v,u\rangle\)。然后我们从 \(1\) 出发用 SPFA 跑一遍最长路即可。
（不知道为什么 SPFA 没被卡）
Code
const int N=2e5;
const int M=2e5;
struct Edge{int to,nxt,w;}e[M*2+10];int head[N+10],tote;
inline void addEdge(int u,int v,int w){e[++tote]={v,head[u],w};head[u]=tote;}
int n,m,a[N+10];
ll dis[N+10];bool vis[N+10];
void SPFA(int s){
memset(dis,~0x3f,sizeof(dis));dis[s]=0;
std::queue<int> q;q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]<dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!vis[v])q.push(v),vis[v]=1;
}
}
}
}
void mian(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
if(a[u]<a[v])std::swap(u,v);
addEdge(u,v,a[u]-a[v]);
addEdge(v,u,2*(a[v]-a[u]));
}
SPFA(1);
ll ans=0;
for(int i=1;i<=n;i++)ans=std::max(ans,dis[i]);
printf("%lld\n",ans);
}
F
看到如此小的数据范围，考虑 dp。
设 \(f_{i,j,k,l}\) 表示前 \(i\) 项，所有长度为 \(1,2,3\) 的上升子序列中结尾的最小值分别为 \(j,k,l\) 时（若不存在这样的上升子序列，则相应的值为 \(0\)）的答案。
枚举序列的第 \(i\) 项为 \(p\)，对 \(j,k,l,p\) 的大小关系分类讨论进行转移。
具体过程见代码。
Code
const int N=1000;
const int M=10;
const int P=998244353;
// f[i][j][k][l] -> 1~i, IS of length 1,2,3 end with j,k,l (as small as possible)
int n,m,f[N+10][M+5][M+5][M+5];
void mian(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)f[1][i][0][0]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k<=m;k++)
for(int l=0;l<=m;l++)
for(int p=1;p<=m;p++){
// 先把不可能出现的情况排除掉
if(j&&k&&l&&l<p)continue; // |LIS|=4
if(!k&&l)continue; // 存在 |LIS|=3 但不存在 |LIS=2|
if(k&&j>=k)continue; // 长度为 1 的 IS 的结尾比长度为 2 的大
if(l&&k>=l)continue; // 长度为 2 的 IS 的结尾比长度为 3 的大
if(!k){
if(j<p)(f[i][j][p][0]+=f[i-1][j][0][0])%=P; // j<p, p 接 j 后面，出现长度为 2 的 IS
else (f[i][p][0][0]+=f[i-1][j][0][0])%=P; // p<=j, p 作为一个新的 IS
}else if(!l){
if(k<p)(f[i][j][k][p]+=f[i-1][j][k][0])%=P; // j<k<p, p 接 k 后面，出现长度为 3 的 IS
else if(j<p)(f[i][j][p][0]+=f[i-1][j][k][0])%=P; // j<p<=k, p 接 j 后面
else (f[i][p][k][0]+=f[i-1][j][k][0])%=P; // p<=j<k, p 作为一个新的 IS
}else{
if(k<p)(f[i][j][k][p]+=f[i-1][j][k][l])%=P; // j<k<p<l, p 接 k 后面
else if(j<p)(f[i][j][p][l]+=f[i-1][j][k][l])%=P; // j<p<=k<l, p 接 j 后面
else (f[i][p][k][l]+=f[i-1][j][k][l])%=P; // p<=j<k<l, p 作为一个新的 IS
}
}
int ans=0;
for(int i=1;i<=m;i++)
for(int j=i+1;j<=m;j++)
for(int k=j+1;k<=m;k++)
(ans+=f[n][i][j][k])%=P;
printf("%d\n",ans);
}
G
待补。