T1「NOIP模拟」开挂
简单题，容易发现最后的 \(a\) 数组是可以确定的。然后我们举一个简单的例子，假设初始序列 \(a\) 为 2 2 3，最后的 \(a\) 数组就为 2 3 4。然后我们发现就会有两种方案操作，第一种为一个 \(3\) 加一和一个 \(2\) 加一，另一种为一个 \(2\) 加二，于是我们发现无论 \(b\) 是什么，我们总可以让第二种的代价小于等于第一种的代价。所以我们得出结论，让一个数挪得越多，并把最小的 \(b\) 给他越优，就是一个贪心。然后就没了，详细看代码。然后因为要对 \(2^{64}\) 取模，开 unsigned long long 就好了。
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N=1e6+5;
int n;
int a[N],b[N],c[N],fx[N];
map<int,int> mp;
bool cmp(int l,int r){return l>r;
}
int find(int x){return fx[x]==x?x:fx[x]=find(fx[x]);
}
void hb(int x,int y){if(a[x]+c[x]>=a[y]+c[y]){fx[y]=x;}else{fx[x]=y;}return ;
}
signed main(){freopen("openhook.in","r",stdin);freopen("openhook.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++){fx[i]=i;}for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){cin>>b[i];}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){if(mp[a[i]]==0){mp[a[i]]=i;c[i]=0;if(mp[a[i]-1]!=0){int kl=find(mp[a[i]-1]);hb(kl,find(i));}if(mp[a[i]+1]!=0){int kl=find(mp[a[i]+1]);hb(kl,find(i));}}else{int kl=find(mp[a[i]]);mp[a[kl]+c[kl]+1]=i;c[i]=a[kl]+c[kl]+1-a[i];hb(kl,find(i));if(mp[a[kl]+c[kl]+2]!=0){kl=find(mp[a[kl]+c[kl]+2]);hb(kl,find(i));}}}sort(c+1,c+1+n,cmp);sort(b+1,b+1+n);int ans=0;for(int i=1;i<=n;i++){ans=ans+c[i]*b[i];}cout<<ans<<'\n';return 0;
}
T2「NOIP模拟」叁仟柒佰万
好题。首先有一个结论，不管你怎么分，每一段的 \(mex\) 等于整个序列的 \(mex\)。
证明如下：如果有一种划分，令其每一段的 \(mex\) 为 \(x\)。
当 \(x<mex\) 时，因为 \(0\) 到 \(mex-1\) 的数全部都在序列中出现过了，所以不管你怎么划分，肯定有一段会被分到一个 \(x\)，此时这一段的 \(mex\) 就无法取到 \(x\)，矛盾。
当 \(x>mex\) 时，显然不可能，矛盾。
所以我们知道这个结论后，就很好做了。因为我们要求的是区间数量，对于区间数量有一个很经典的方法，定一求一。我们枚举区间的右端点 \(r\)，定义 \(l\) 为最大的满足 \(l\) 到 \(r\) 这个区间的 \(mex\) 等于整个序列的 \(mex\) 的位置，容易发现 \(1\) 到 \(l\) 都满足这个条件，所以有 \(dp_i\) 表示前 \(i\) 个位置的方案数，转移为 \(dp_r=1+\sum_{i=1}^{l-1}dp[i]\) 然后弄个前缀和就好了。详细看代码。
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=3e7+7e6+5;
int n,a[N],vis[N];
int sum[N];
int ksm(int x,int y){int res=1;while(y){if(y&1)res=(long long)res*x%mod;x=(long long)x*x%mod;y>>=1;}return res;
}
void sl(){int n;cin>>n;if(n==37000000){long long x,y;cin>>x>>y; a[1]=0;for(int i=2;i<=n;i++){a[i]=(x*a[i-1]+y+i)&(262143);}}else{for(int i=1;i<=n;i++){cin>>a[i];}}int mex=0;for(int i=1;i<=n;i++){vis[a[i]]++;while(vis[mex]){mex++;}}for(int i=1;i<=n;i++){vis[a[i]]--;}if(mex==0){cout<<ksm(2,n-1)<<'\n';return ;}int l=1,cnt=0;sum[0]=1;for(int i=1;i<=n;i++){if(a[i]<mex&&vis[a[i]]==0) cnt++;sum[i]=0;vis[a[i]]++;if(cnt==mex){while(1){if(vis[a[l]]==1 && a[l]<mex)break;else{vis[a[l++]]--;}}sum[i]+=sum[l-1];sum[i]%=mod;}sum[i]=(sum[i]+sum[i-1])%mod;}cout<<(sum[n]-sum[n-1]+mod)%mod<<'\n';while(l<=n){vis[a[l++]]--;}
}
signed main(){freopen("clods.in","r",stdin);freopen("clods.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){sl();}return 0;
}
T3「NOIP模拟」超级加倍
神秘好题。嗯，我们的老师在讲这道题的时候有一句话：“对于这种树上最值问题就要考虑 \(Kruskal\) 重构树啊。”嗯，所以这道题就是 \(Kruskal\) 重构树，我们建两棵重构树，其中一颗树 \(a\) 的边权为边两端点编号的最小值，相反另一颗树 \(b\) 就是最大值，如果在 \(a\) 中，\(x\) 和 \(y\) 的 \(lca\) 的权值为 \(x\)，在 \(b\) 中，\(x\) 和 \(y\) 的 \(lca\) 的权值为 \(y\)。就是一条合法路径，也就是说一条路径 \(x\) 到 \(y\)（\(x\le y\)）,如果 \(adfn_x>adfn_y\) 且 \(bdfn_x<bdfn_y\)。则路径合法，然后就没有了。
没有代码。