题单： 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; cin>>n>>m; for(int i=1,x;i>x; mp1[x]++; } for(int i=1,x,y;i>x>>y; if(x>y) 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(r>0){ 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(); } cout>t; 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; cin>>n>>m; for(int i=1,x;in;i++){ cin>>x; mp1[x]++; } for(int i=1,x,y;im;i++){ cin>>x>>y; if(x>y) 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(r>0){ 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; cin>>t; 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(){ cin>>n>>m; for(int i=1;i>d[i]; sort(d+1,d+1+n); for(int i=1;i>a>>b; 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(){ cin>>n>>m; for(int i=1;in;i++) cin>>d[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; cin>>a>>b; 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(){ cin>>n; for(int i=1;i>a[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(){ cin>>n; for(int i=1;in;i++) base[i]=rnd()+1; for(int i=1;in;i++){ cin>>a[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; cin>>n; for(int i=1;i>a>>b; b++; while(top>0&&a>st[top].first){ if(st[top-1].second==b){ a+=(st[top-1].first-st[top].first); top--; } top--; } st[++top]={a,b}; cout>T; 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; cin>>n; for(int i=1;in;i++){ int a,b; cin>>a>>b; b++; while(top>0&&a>st[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); cin>>T; while(T--) solve(); return 0; }`
ZR 集训 Day29 - 杂题选讲
笔记