T1 玩游戏
神秘贪心。
先拆成两个序列 \(a,b\)，需要保证时刻有前缀和 \(sum_i+sum_j\le 0\)，首先两边贡献如果能为非正数，先看能否往两边跳，如果都跳不了无解，其实就是贪心地跳到前缀和比当前小的地方。跳到贡献为正数时，来到了两个序列前缀和的最低点，考虑从两边往中间跳每次也是往低跳，查看最后能否相遇即可，这题有一车假做法，之前学长的题解没有几个能过的，这是一种简介的写法 by lxyt-415x。
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10,mod=998244353,inf=1e9;
inline void Min(int &x,int y){if(x>y)x=y;}
inline void Max(int &x,int y){if(x<y)x=y;}
int n,m,a[N],pa,pd,ia,ib,b[N];
inline void work(){
pa=pd=ia=ib=0;
while((ia<n&&a[ia+1]+b[pd]<=0)||(ib<m&&a[pa]+b[ib+1]<=0)){
if(ia<n&&a[ia+1]+b[pd]<=0&&a[++ia]<=a[pa])pa=ia;
if(ib<m&&a[pa]+b[ib+1]<=0&&b[++ib]<=b[pd])pd=ib;
}
}
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
int T=read();while(T--){
m=read(),n=read();for(int i=1;i<=n;++i)a[n-i+1]=read();m-=n--;
for(int i=1;i<=m;++i)b[i]=read(),b[i]+=b[i-1];
for(int i=1;i<=n;++i)a[i]+=a[i-1];
work();int _=pa,__=pd;std::reverse(a+1,a+n+1);std::reverse(b+1,b+m+1);a[++n]=b[++m]=0;
work();puts((_+pa>=n&&__+pd>=m)?"Yes":"No");
}
}
T2 排列
简单观察发现 \(k\) 不超过 \(\log n\)，然后一个区间内的最大值会将这个区间分成不想关的两部分，根据这个性质设计 \(f_{i,j,0/1,0/1}\) 表示长度为 \(i\) 的区间，需要操作 \(j\) 次后消完，区间左边一个是否比区间最大值大，区间右边一个是否比区间最大值大的方案数，注意，\(f_{i,j,0,0}\) 表示的是操作 \(j\) 次后只剩一个数的方案数，转移就是考虑最大值的位置关系，枚举区间内最大值位置 \(k\)，容易发现这个东西需要前缀和优化，所以直接考虑意义为不超过 \(j\) 次的方案数即可。如下：
\[\begin{aligned} f_{i,j,0,0}&=f_{k-1,j,0,1}\times f_{i-k,j,1,0}\times{i\choose k-1}\\ f_{i,j,0,1}&=f_{k-1,j,0,1}\times f_{i-k,j-1,1,0}\times{i\choose k-1}\\ f_{i,j,1,0}&=f_{k-1,j-1,1,1}\times f_{i-k,j,1,0}\times{i\choose k-1}\\ f_{i,j,1,1}&=(f_{k-1,j,1,1}\times f_{i-k,j,1,1}-(f_{k-1,j,1,1}-f_{k-1,j-1,1,1})\times(f_{i-k,j,1,1}-f_{i-k,j-1,1,1}))\times{i\choose k-1}\\ \end{aligned} \]第一种情况比较简单，第二，三种情况就是有最大值的一遍保证操作次数不超过 \(j-1\) 次，从而在 \(j\) 次内将区间内最大值消掉。第四种情况限制同第二，三种情况，但是只需要保证被一遍消掉即可，所以再减去两边都是 \(j\) 次的情况即可，答案就是 \(f_{n,k,0,0}-f_{n,k-1,0,0}\)，时间复杂度 \(\mathcal{O}(n^2\log n)\)。
T3 最短路
不会，贺也没贺懂。
T4 矩形
我去，怎么没改这个，反正就是直接上扫描线并查集维护连通块即可，明天补。
总结
有事一点不会场，暴力还挂了，T1 又是一个一车假做法的神秘贪心，没会过这种题，T2 就是 DP 魅力时刻，简直什么都能刻画，T3 理解不了几点，还没找到一个说的详细的题解，又打出了退役水平。
标签：ch,NOIP,int,最大值,long,times,模拟,define From： https://www.cnblogs.com/Ishar-zdl/p/18533159