ZR 集训 Day29杂题选讲

题单： CF1637E Best Pair 考虑不同的 $cnt$ 最多只有 $\sqrt{n}$ 种，所以我们直接记录每个 $cnt$ 对应的 $a_i$，对其排序，然后暴力枚举两个 $cnt$ 对应的 $a_i$，从大到小看是否满足条件，最多 $m$ 次不满足条件。 代码： C++#include using namespace std; typedef long long ll; const int N=3e5+5; int s[3000]; vector a[3000]; void solve(){ int idx=0; ll ans=-1; map mp,mp1; map,int tag; int n,m; cinnm; for(int i=1,x;ix; mp1[x]++; } for(int i=1,x,y;ixy; if(xy) swap(x,y); tag[{x,y}]=1; } for(auto[x,y]:mp1){ if(mp[y]) a[mp[y]].push_back(x); else mp[y]=++idx,s[idx]=y,a[idx].push_back(x); } for(int i=1;i=0){ int r=a[j].size()-1; int xx=min(a[i][l],a[j][r]),yy=max(a[i][l],a[j][r]); if(xx!=yy&&!tag[{xx,yy}]){ ans=max(ans,ll(s[i]+s[j])*(a[i][l]+a[j][r])); break; } else{ while(r0){ r--; int xx=min(a[i][l],a[j][r]),yy=max(a[i][l],a[j][r]); if(xx!=yy&&!tag[{xx,yy}]){ ans=max(ans,ll(s[i]+s[j])*(a[i][l]+a[j][r])); break; } } } l--; } } a[i].clear(); } coutt; while(t--) solve(); return 0; }#include using namespace std; typedef long long ll; const int N=3e5+5; int s[3000]; vectorint a[3000]; void solve(){ int idx=0; ll ans=-1; mapint,int mp,mp1; mappairint,int,int tag; int n,m; cinnm; for(int i=1,x;in;i++){ cinx; mp1[x]++; } for(int i=1,x,y;im;i++){ cinxy; if(xy) swap(x,y); tag[{x,y}]=1; } for(auto[x,y]:mp1){ if(mp[y]) a[mp[y]].push_back(x); else mp[y]=++idx,s[idx]=y,a[idx].push_back(x); } for(int i=1;iidx;i++) sort(a[i].begin(),a[i].end()); for(int i=1;iidx;i++){ for(int j=i;jidx;j++){ int l=a[i].size()-1; while(l=0){ int r=a[j].size()-1; int xx=min(a[i][l],a[j][r]),yy=max(a[i][l],a[j][r]); if(xx!=yy&&!tag[{xx,yy}]){ ans=max(ans,ll(s[i]+s[j])*(a[i][l]+a[j][r])); break; } else{ while(r0){ r--; int xx=min(a[i][l],a[j][r]),yy=max(a[i][l],a[j][r]); if(xx!=yy&&!tag[{xx,yy}]){ ans=max(ans,ll(s[i]+s[j])*(a[i][l]+a[j][r])); break; } } } l--; } } a[i].clear(); } coutans"\n"; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int t; cint; while(t--) solve(); return 0; } CF1418E Expected Damage 对于一个询问 $a,b$，分两种情况计算贡献。 假设一共有 $x$ 个 $g_i=b$。 对于 $g_i=b$，它能产生贡献的情况应该是这个 $g_i$ 排在 $x$ 个 $g_i$ 的最后 $x-a$ 个，所以概率为 $\frac{x-a}{x}$。 对于 $g_i 不难发现，对于求期望，我们对 $g$ 排序并求前缀和即可。 代码： C++#include using namespace std; typedef long long ll; const int mod=998244353; const int N=2e5+5; int n,m; int d[N],sum[N]; ll qpow(ll x,int y){ ll res=1; while(y){ if(y&1) (res*=x)%=mod; y=1,(x*=x)%=mod; } return res; } signed main(){ cinnm; for(int i=1;id[i]; sort(d+1,d+1+n); for(int i=1;iab; int k=lower_bound(d+1,d+1+n,b)-d,x=n-k+1; if(x#include using namespace std; typedef long long ll; const int mod=998244353; const int N=2e5+5; int n,m; int d[N],sum[N]; ll qpow(ll x,int y){ ll res=1; while(y){ if(y&1) (res*=x)%=mod; y=1,(x*=x)%=mod; } return res; } signed main(){ cinnm; for(int i=1;in;i++) cind[i]; sort(d+1,d+1+n); for(int i=1;in;i++) sum[i]=(sum[i-1]+d[i])%mod; while(m--){ int a,b,ans=0; cinab; int k=lower_bound(d+1,d+1+n,b)-d,x=n-k+1; if(xa){ cout"0\n"; continue; } ans=(((qpow(x,mod-2)*(x-a))%mod)*(sum[n]-sum[k-1]))%mod; ans=(ans+(((qpow(x+1,mod-2)*(x+1-a))%mod)*(sum[k-1]))%mod)%mod; cout(ans%mod+mod)%mod"\n"; } return 0; } CF1418G Three Occurrences 把每个值对应出现次数模三的这个序列进行哈希，枚举右端点，并维护一个左端点，使得区间内所有数出现次数不超过 $3$，再用一个 map 记录有多少符合要求的前缀哈希即可。 代码： C++#include using namespace std; typedef unsigned long long ull; const int N=5e5+5; const int mod=1e9+7; mt19937_64 rnd(random_device{}()); int n; ull ans; int a[N],cnt[N]; ull base[N],ha[N]; map mp; signed main(){ cinn; for(int i=1;ia[i]; (cnt[a[i]]+=1)%=3; if(cnt[a[i]]==0) ha[i]=ha[i-1]-2*base[a[i]]; else ha[i]=ha[i-1]+base[a[i]]; } memset(cnt,0,sizeof cnt); int l=0; mp[0]=1; for(int i=1;i3){ l++; cnt[a[l]]--,mp[ha[l-1]]--; } ans+=mp[ha[i]]; mp[ha[i]]++; } cout#include using namespace std; typedef unsigned long long ull; const int N=5e5+5; const int mod=1e9+7; mt19937_64 rnd(random_device{}()); int n; ull ans; int a[N],cnt[N]; ull base[N],ha[N]; mapull,int mp; signed main(){ cinn; for(int i=1;in;i++) base[i]=rnd()+1; for(int i=1;in;i++){ cina[i]; (cnt[a[i]]+=1)%=3; if(cnt[a[i]]==0) ha[i]=ha[i-1]-2*base[a[i]]; else ha[i]=ha[i-1]+base[a[i]]; } memset(cnt,0,sizeof cnt); int l=0; mp[0]=1; for(int i=1;in;i++){ cnt[a[i]]++; while(cnt[a[i]]3){ l++; cnt[a[l]]--,mp[ha[l-1]]--; } ans+=mp[ha[i]]; mp[ha[i]]++; } coutans; return 0; } CF2002E Cosmic Rays 不难发现，一般情况下，答案就是 $\max\{b_i\}$，但是对于一个连续段：$A,B,C$，若 $A,C$ 颜色相同，且 $A,C$ 的长度都大于 $B$，那此时 $A,C$ 可以合并，得到的长度为 $b_A+b_C-b_B$。 所以我们用单调栈维护这个操作即可，答案即栈底。 代码： C++#include using namespace std; #define int long long const int N=3e5+5; int T,n; pair st[N]; void solve(){ int top=0; cinn; for(int i=1;iab; b++; while(top0&&ast[top].first){ if(st[top-1].second==b){ a+=(st[top-1].first-st[top].first); top--; } top--; } st[++top]={a,b}; coutT; while(T--) solve(); return 0; }#include using namespace std; #define int long long const int N=3e5+5; int T,n; pairint,int st[N]; void solve(){ int top=0; cinn; for(int i=1;in;i++){ int a,b; cinab; b++; while(top0&&ast[top].first){ if(st[top-1].second==b){ a+=(st[top-1].first-st[top].first); top--; } top--; } st[++top]={a,b}; coutst[1].first" "; } cout"\n"; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinT; while(T--) solve(); return 0; }