总结
T1
第一考场上很快就想出来了正解，但是由于没有看清数据范围，最后导致RE。
十年OI一场空，内存开小见祖宗
T2
这回的T2没有大问题，但是遇到一些周期性的优化的时候没有想到。
T3
第三题，考场上想的思路是有问题的，而且代码没有码出来。下来得增强代码能力。
T4
第四题，考场上想到了正解，但是在DP转移方程优化了之后，有一个边界问题没有考虑到，导致0pts。
题解
T1
我们要使一个数列的MEX，这恰好加一，那么这个时候我们原来的MEX加一就不可以有。因为如果说有Max加一的话，那么此时我将任意一个改成了MEX的话，它就会增加不止一了。
那么此时我们统计MEX+1最左边出现在哪最右边的哪，然后把最左边最右边之间的全部改成MEX之后。再去求MEX，看是否满足条件。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const long long maxn=5e5+5;
int a[maxn];
map<int,int> mp;
signed main()
{freopen("add.in","r",stdin);freopen("add.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t;cin>>t;while(t--){mp.clear();int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;int cnt=0,f=1,l=-1,r=-1;for(auto now:mp){int x=now.first;if(cnt!=x) break;cnt++;}for(int i=1;i<=n;i++){if(a[i]==cnt+1){r=i;if(l==-1) l=i;}}if(l==-1){f=0;for(auto now:mp){int x=now.first;if(x<cnt&&mp[x]>1||x>cnt) f=1;}if(f) cout<<"Yes"<<endl;else cout<<"No"<<endl;}else{for(int i=l;i<=r;i++){mp[a[i]]--,mp[cnt]++;if(mp[a[i]]==0) mp.erase(a[i]);}int ans=0;for(auto now:mp){int x=now.first;if(ans!=x) break;ans++;}if(cnt==ans-1) cout<<"Yes"<<endl;else cout<<"No"<<endl;}}return 0;
}
T2
我们会发现，如果说向左的与向右的碰撞了，我们可以不管它的碰撞，毕竟他跟编号没有任何关系，我们设它直接经过就可以了。
那么此时我为向左开一个优先队列向右的开一个优先队列。然后我去看如果说我向左队列的对头比向右队列小，那我就先去看向左的队头，让他去撞一次墙，然后去。将其踢出左边的队列，加到向右的队列去。
如果是右边的比左边的小，那我就直接反过来做就可以了。
此时你就会得到五十分。
而这时你会发现在两边的墙不坏的情况下，每经过 \(2\times 10^9+1\) 次之后，它就会回到原来的位置。所以我们在这里可以进行一定的优化。
我们看当前的左边墙壁和右边墙壁最多能够支持多少次（我们每经过 \(2\times 10^9+1\) 之后，它的墙就会被撞 \(n\) 次），把它提前减掉，最后剩余的部分我们直接算就可以了。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const long long maxn=1e6+5,len=1e9+1;
int tmp[maxn];
priority_queue<int,vector<int>,greater<int> > q0,q1;
signed main()
{freopen("ants.in","r",stdin);freopen("ants.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,a,b;cin>>n>>a>>b;for(int i=1;i<=n;i++) cin>>tmp[i];int ns=min(a,b)/n;a-=ns*n,b-=ns*n;for(int i=1;i<=n;i++){int x;cin>>x;if(x==0) q0.push(tmp[i]);else q1.push(len-tmp[i]);}int ans=0;while(!q0.empty()||!q1.empty()){while(!q0.empty()&&(!q1.empty()&&q0.top()<=q1.top()||q1.empty())){if(a<=0) ans=q0.top(),q0.pop();else q1.push(len+q0.top()),q0.pop();a--;}while(!q1.empty()&&(!q0.empty()&&q1.top()<=q0.top()||q0.empty())){if(b<=0) ans=q1.top(),q1.pop();else q0.push(len+q1.top()),q1.pop();b--;}}cout<<ans+ns*len*2;return 0;
}
T3
T3，我们在做DFS的模拟的时候我们会发现：如果说当前我要新开一条边，那么我一定是当前DFS栈里面最深且有儿子还没有便利的那个点。如果那个点有一个儿子没有连像我们需希望的那个点那么我们就需要新开一条边。
我们模拟这个过程就可以了。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const long long maxn=2e5+5,win=1145141919810ll;
int ans=0,n,m,vis[maxn];
vector<int> g[maxn];
map<int,int> a[maxn];
void go(int x)
{for(auto to:g[x]) vis[to]++;
}
signed main()
{freopen("build.in","r",stdin);freopen("build.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t;cin>>t;while(t--){ans=0;cin>>n>>m;int ans=0;for(int i=1;i<=n;i++) g[i].clear(),a[i].clear(),vis[i]=0;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);a[u][v]=a[v][u]=1;}stack<int> s;//dfs栈go(1);s.push(1);for(int i=2;i<=n;i++){while(!s.empty()&&g[s.top()].size()==vis[s.top()]) s.pop();if(s.empty()||!a[s.top()][i]) ans++;go(i),s.push(i);}cout<<ans<<endl;}return 0;
}
T4
我们很容易就可以想到一个非常暴力的DP。设 \(dp_i\) 为前 \(i\) 个我最大能赢的区间和的长度。转移方程为：
其中 \(s\) 为前缀和。
这个时候你就可以喜提六十分。
我们会发现这个式子其实是非常好优化的。我们把 \(i\) 提出来，这个优化是非常常见的，就不多说了。而条件，我们可以重新定义一下树状数组。
我们对所有前缀和做一个离散化。那么数量数组就是存的当前这一个前缀和的值，因为我们在离散化的时候，为了去重，我们会对它排序，此时前缀和和离散化之后，比他小的那些直都在原来值上面都一定比他小所以用树状数组统计前缀和即可。且在他前面。最后输出答案即可。
边界
但如果当前前面没有比它小的，那么我这个时候就要分情况了。如果前缀和大于零，那么它就可以是 \(i\)，如果前缀和小于零，那么它就只能是零了。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const long long maxn=2e5+5;
int bit[maxn],n,a[maxn],dp[maxn],s[maxn],b[maxn],m;
map<int,int> mp;
int lb(int x)
{return x&-x;
}
void update(int x,int y)
{while(x<=m) bit[x]=max(bit[x],y),x+=lb(x);
}
int query(int x)
{int ans=-inf;while(x) ans=max(ans,bit[x]),x-=lb(x);return ans;
}
signed main()
{freopen("bigwin.in","r",stdin);freopen("bigwin.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n;memset(bit,-0x3f,sizeof(bit));mp[0]=1;for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i],b[i]=s[i];b[n+1]=0;sort(b+1,b+2+n);m=unique(b+1,b+2+n)-b-1;for(int i=1;i<=m;i++) mp[b[i]]=i;int cnt=0;update(mp[0],0);for(int i=1;i<=n;i++){dp[i]=dp[i-1];int maxx=query(mp[s[i]]);if(maxx==-inf){if(s[i]>=0) dp[i]=max(dp[i],i);else dp[i]=max(0ll,dp[i]);}else dp[i]=max(dp[i],maxx+i);update(mp[s[i]],dp[i]-i);}cout<<dp[n];return 0;
}