【比賽記錄】2025 暑假集訓模擬賽合集Ｉ
2025CSP-S模擬賽29
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 50 | 50 | 30 | 0 | 130 | 10/17 |
A. 二分圖匹配
首先考慮一個樸素的 DP：設 \(f_{i,j}\) 表示 \(S_1[1\dots i]\) 和 \(S_2[1\dots j]\) 的最大匹配數量。發現空間開不下。注意到 \(f\) 數組的值最大為 \(\min(n,m)\)，考慮交換下標與值域，設 \(f_{i,j}\) 表示 \(S_1[1\dots i]\) 匹配了 \(j\) 位在 \(S_2\) 上的最短前綴。記 \(g_{i,j}\) 表示 \(S_2\) 中第 \(i\) 位之后第一次出現字符 \(j\) 的位置，于是有轉移：\(f_{i,j}=\min(f_{i-1,j},g_{f_{i-1,j-1},{S_1}_i})\)。時間復雜度 \(O(26m+n^2)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e3+5,maxm=1e6+5,inf=1e9;
int n,m,f[maxn][maxn],g[maxm][30],pos[30];
string s1,s2;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>s1>>s2;
s1=" "+s1,s2="A"+s2;
memset(pos,0x3f,sizeof(pos));
for(int i=m;~i;i--){
for(int j=0;j<=25;j++){
g[i][j]=pos[j];
}
pos[s2[i]-'A']=i;
}
memset(f,0x3f,sizeof(f));
for(int i=0;i<=n;i++){
f[i][0]=0;
for(int j=1;j<=i;j++){
f[i][j]=min(f[i-1][j],f[i-1][j-1]>=inf?inf:g[f[i-1][j-1]][s1[i]-'A']);
}
}
for(int i=n;~i;i--){
if(f[n][i]<=m){
cout<<i;
break;
}
}
return 0;
}
}
int main(){return asbt::main();}
B. 虛圖
考慮直接對這些關鍵點二進制分組，當前位為 \(1\) 的連一條 \(S\xrightarrow{0} a_i\)，否則連一條 \(a_i\xrightarrow{0} T\)，從 \(S\) 跑最短路，用 \(dis_T\) 更新答案即可。因為兩個不同的點至少有一位不同，所以這樣的分組方式遍歷了所有組合。時間復雜度 \(O((n+m)\log^2n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pii pair<int,int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=2e5+5;
const ll inf=1e18;
int n,m,kk,a[maxn];
ll dis[maxn];
bool vis[maxn];
vector<pii> e[maxn];
struct edge{
int u,v,w;
}E[maxn];
priority_queue<pii> q;
il void dijkstra(int u){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[u]=0,q.push(mp(0,u));
while(q.size()){
int x=q.top().sec;
q.pop();
if(vis[x]){
continue;
}
vis[x]=1;
for(pii i:e[x]){
int v=i.fir,w=i.sec;
if(!vis[v]&&dis[v]>dis[x]+w){
dis[v]=dis[x]+w;
q.push(mp(-dis[v],v));
}
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>kk;
for(int i=1;i<=m;i++){
cin>>E[i].u>>E[i].v>>E[i].w;
}
for(int i=1;i<=kk;i++){
cin>>a[i];
}
int S=n+1,T=n=S+1;
ll ans=inf;
for(int i=0;i<=17;i++){
for(int j=1;j<=m;j++){
e[E[j].u].pb(mp(E[j].v,E[j].w));
e[E[j].v].pb(mp(E[j].u,E[j].w));
}
for(int j=1;j<=kk;j++){
if(j>>i&1){
e[S].pb(mp(a[j],0));
}
else{
e[a[j]].pb(mp(T,0));
}
}
dijkstra(S),ans=min(ans,dis[T]);
for(int j=1;j<=n;j++){
e[j].clear();
}
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
C. 冒泡
考慮將答案差分，分為 \([1,r]\) 和 \([1,l]\) 兩部分。
對于 \([1,x]\)，考慮枚舉當前考慮的數有前端有多少與 \(x\) 相同。假設 \(x\) 為 \(\overline{a_1a_2a_3\dots}\)，如果當前枚舉的為 \(\overline{a_1k}\;(k<a_2)\)，那么后面的位數都可以隨意亂選。將此時的答案拆成已確定的部分、未確定的部分和二者之間。設未確定的還有 \(len\) 位，對于已確定的部分，求出其逆序對數 \(tot\)，這一部分答案為 \(tot\times10^{len}\)；對于未確定的部分，任選兩個位置組成逆序對，其他位置亂選，答案為 \(\frac{len\times(len-1)}{2}\times45\times10^{len-2}\)；二者之間的部分，假設前面有一個 \(c\)，若希望構成逆序對則后面一個位置的取值有 \(0\dots c-1\) 共 \(c\) 種，貢獻為 \(c\times len\times10^{len-1}\)。
注意這樣無法算入 \(x\) 的貢獻，需要另外求出來。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e5+5,mod=1e9+7;
int T,pw[maxn];
string l,r;
il int calc(string s){
int x=s.size(),tot=0,sum=0,res=0,cnt[15]={0};
for(char ch:s){
int c=ch^48;
x--;
for(int i=0;i<c;i++){
if(x>=2){
(res+=x*(x-1)/2%mod*45%mod*pw[x-2])%=mod;
}
if(x>=1){
(res+=(sum+i)*x%mod*pw[x-1])%=mod;
}
(res+=(tot+cnt[i+1])*pw[x])%=mod;
}
(tot+=cnt[c+1])%=mod,(sum+=c)%=mod;
for(int i=0;i<=c;i++){
cnt[i]++;
}
}
return res;
}
il int nxd(string s){
int cnt[15]={0},res=0;
for(char ch:s){
int c=ch^48;
for(int i=c+1;i<=9;i++){
(res+=cnt[i])%=mod;
}
cnt[c]++;
}
return res;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
pw[0]=1;
for(int i=1;i<=5e5;i++){
pw[i]=pw[i-1]*10%mod;
}
cin>>T;
while(T--){
cin>>l>>r;
cout<<(calc(r)-calc(l)+nxd(r)+mod)%mod<<"\n";
}
return 0;
}
}
signed main(){return asbt::main();}
D. 親戚
記 \(a_i\) 表示包含了 \(x\) 的限制組成的集合，大小為 \(1\) 的限制不算。考慮組成了樹之后，對于葉子節點 \(u\)，一定有 \(a_u\subseteq a_{fa_u}\)。于是想到一個構造樹的方式：每次選擇一對點使得 \(a_u\subseteq a_v\) 且 \(u\) 還未被加入至樹中，將 \(u\) 加入至樹中。此時將所有包含 \(u\) 的限制的大小減一，如果減成 \(1\) 了那么就刪去這個限制。這樣的復雜度為 \(O(n^3m)\)。顯然 \(a\) 可以用 bitset 維護，優化至 \(O(\frac{n^3m}{w})\)。考慮將 \(u\) 加入樹中，此時大小減成 \(1\) 的限制中剩下的那個點一定是 \(v\)，于是可以用棧維護每個點被包含于哪些點，刪去 \(u\) 時將 \(v\) 暴力重構。時間復雜度 \(O(\frac{n^2m}{w})\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e3+5;
int T,n,m,cnt[maxn];
int top[maxn],stk[maxn][maxn];
bool vis[maxn];
bitset<maxn> a[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++){
a[i].reset(),vis[i]=0;
}
for(int i=1,x;i<=m;i++){
cin>>cnt[i];
if(cnt[i]==1){
cin>>x;
continue;
}
for(int j=1;j<=cnt[i];j++){
cin>>x;
a[x].set(i);
}
}
for(int i=1;i<=n;i++){
top[i]=0;
for(int j=1;j<=n;j++){
if(i==j){
continue;
}
if((a[i]|a[j])==a[j]){
stk[i][++top[i]]=j;
}
}
}
for(int i=1;i<n;i++){
for(int j=1;j<=n;j++){
if(!vis[j]&&top[j]){
int k=stk[j][top[j]--];
while(top[j]&&vis[k]){
k=stk[j][top[j]--];
}
if(vis[k]){
continue;
}
for(int x=1;x<=m;x++){
if(a[j][x]&&--cnt[x]==1){
a[k].reset(x);
}
}
top[k]=0;
for(int x=1;x<=n;x++){
if(x==k){
continue;
}
if((a[k]|a[x])==a[x]){
stk[k][++top[k]]=x;
}
}
vis[j]=1;
goto togo1;
}
}
cout<<"NO\n";
goto togo2;
togo1:;
}
cout<<"YES\n";
togo2:;
}
return 0;
}
}
int main(){return asbt::main();}
/*
8 8
4 1 5 4 6
1 4
3 2 1 6
3 2 7 3
4 2 5 7 1
7 5 7 8 2 6 1 3
7 3 8 5 6 4 7 1
5 3 8 1 6 4
*/
2025CSP-S模擬賽30
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 10 | 50 | - | - | 60 | 7/15 |
A. 天才俱樂部
\[\sum_{i=1}^{n}(a_i\bmod k)=s\\
\Leftrightarrow\sum_{i=1}^{n}(a_i-\lfloor\frac{a_i}{k}\rfloor\times k)=s\\
\Leftrightarrow k\times\sum_{i=1}^{n}\lfloor\frac{a_i}{k}\rfloor=\sum_{i=1}^{n}a_i-s\\
\Rightarrow k\mid \sum_{i=1}^{n}a_i-s
\]
注意最后一步得出的只是必要條件，因此枚舉 \(\sum_{i=1}^{n}a_i-s\) 的因子再一一驗證即可。時間復雜度 \(O(tn\sqrt{\sum_{i=1}^{n}a_i-s})\)。注意特判 \(\sum_{i=1}^{n}a_i=s\) 的情況。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int T,n,m,a[105];
il bool chk(int x){
int t=0;
for(int i=1;i<=n;i++){
t+=a[i]%x;
}
return t==m;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
int sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
if(sum==m){
cout<<"YES\n";
continue;
}
sum-=m;
for(int i=1;i<=sum/i;i++){
if(sum%i==0&&(chk(i)||chk(sum/i))){
cout<<"YES\n";
goto togo;
}
}
cout<<"NO\n";
togo:;
}
return 0;
}
}
int main(){return asbt::main();}
B. 實戰教學
考慮二分答案 \(mid\)，首先如果 \(\exist i,a_i+b_i>mid\) 那么一定不合法。于是對于每個配對 \((x,y)\)，一定有 \(b_y\le mid-a_x\)。發現隨著 \(a_x\) 的增大滿足條件的 \(y\) 的數量不增，于是考慮從大到小枚舉 \(a_x\)，貪心地在所有滿足條件的 \(y\) 中選擇 \(a_y\) 最大的那一個。可以用線段樹維護，時間復雜度線性對數方。
似乎可以用棧做到線性對數，但是 ds 代替思考還是太棒了??
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,a[maxn],b[maxn],p[maxn],q[maxn],fp[maxn];
bool vis[maxn];
struct seg{
int mxp,mxa,mxb;
seg(int mxp=0,int mxa=0,int mxb=0):mxp(mxp),mxa(mxa),mxb(mxb){}
il seg operator+(const seg &x)const{
seg res;
if(mxa>x.mxa){
res=*this;
}
else{
res=x;
}
res.mxb=max(mxb,x.mxb);
return res;
}
}tr[maxn<<2];
il void pushup(int id){
tr[id]=tr[lid]+tr[rid];
}
il void build(int id,int l,int r){
if(l==r){
tr[id]=seg(p[l],a[p[l]],b[p[l]]);
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
}
il seg query(int id,int l,int r,int lim){
if(l==r){
return tr[id].mxb<=lim?tr[id]:seg();
}
int mid=(l+r)>>1;
if(tr[lid].mxb<=lim){
return tr[lid]+query(rid,mid+1,r,lim);
}
return query(lid,l,mid,lim);
}
il void upd(int id,int l,int r,int x){
if(l==r){
tr[id].mxa=0;
return ;
}
int mid=(l+r)>>1;
if(x<=mid){
upd(lid,l,mid,x);
}
else{
upd(rid,mid+1,r,x);
}
pushup(id);
}
il bool chk(int x){
for(int i=1;i<=n;i++){
if(a[i]+b[i]>x){
return 0;
}
vis[i]=0;
}
// cout<<x<<"\n";
build(1,1,n);
for(int i=1;i<=n;i++){
if(vis[q[i]]){
continue;
}
vis[q[i]]=1;
upd(1,1,n,fp[q[i]]);
seg t=query(1,1,n,x-a[q[i]]);
if(!t.mxa){
return 0;
}
// cout<<q[i]<<" "<<t.mxp<<"\n";
vis[t.mxp]=1;
upd(1,1,n,fp[t.mxp]);
}
return 1;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
n<<=1;
for(int i=1;i<=n;i++){
cin>>a[i];
p[i]=q[i]=i;
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
sort(p+1,p+n+1,[](int x,int y){return b[x]<b[y];});
// for(int i=1;i<=n;i++){
// cout<<p[i]<<" ";
// }
// cout<<"\n";
for(int i=1;i<=n;i++){
fp[p[i]]=i;
}
sort(q+1,q+n+1,[](int x,int y){return a[x]>a[y];});
ll l=1,r=2e9;
while(l<r){
int mid=(l+r)>>1;
if(chk(mid)){
r=mid;
}
else{
l=mid+1;
}
}
cout<<l;
return 0;
}
}
int main(){return asbt::main();}
C. 穿越銀匙之門
無根樹非常難辦，考慮先枚舉根，將它變成有根樹。那么根就不能動了。當然也有可能根也需要先操作一下，那就暴力枚舉根的操作。
然后此時，我們發現一個點需要操作的充要條件為它在兩棵樹上的父親不同。考慮判斷是否有解，發現在 \(A\) 樹中，兒子一定在父親前面修改；在 \(B\) 樹中，兒子一定在父親后面修改。那么可以就此跑一個拓撲排序，來判斷可行性。同時這也引出了一個判不合法的方式：在 \(A\) 樹中，如果兒子不需要修改而父親需要修改，那么無解。時間復雜度 \(O(tn^3)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int inf=1e9;
int T,n,af[55],bf[55],ad[55],q[55],gd[55];
bool f[55];
vector<int> A[55],B[55],G[55];
il void dfs(int u,int fa,vector<int>* e,int *p){
p[u]=fa;
for(int v:e[u]){
if(v==fa){
continue;
}
dfs(v,u,e,p);
}
}
il int calc(){
int cnt=0;
for(int i=1;i<=n;i++){
f[i]=af[i]!=bf[i];
cnt+=f[i];
G[i].clear(),gd[i]=0;
}
for(int i=1;i<=n;i++){
if(!f[i]&&f[af[i]]){
return inf;
}
if(f[i]){
if(f[af[i]]){
G[i].pb(af[i]),gd[af[i]]++;
}
if(f[bf[i]]){
G[bf[i]].pb(i),gd[i]++;
}
}
}
int hd=1,tl=0;
for(int i=1;i<=n;i++){
if(f[i]&&!gd[i]){
q[++tl]=i;
}
}
while(hd<=tl){
int u=q[hd++];
for(int v:G[u]){
if(--gd[v]==0){
q[++tl]=v;
}
}
}
return tl==cnt?cnt:inf;
}
il void solve(){
cin>>n;
for(int i=1;i<=n;i++){
ad[i]=0;
A[i].clear(),B[i].clear();
}
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
A[u].pb(v),A[v].pb(u);
ad[u]++,ad[v]++;
}
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
B[u].pb(v),B[v].pb(u);
}
dfs(1,0,A,af),dfs(1,0,B,bf);
for(int i=1;i<=n;i++){
if(af[i]!=bf[i]){
goto togo;
}
}
cout<<0<<"\n";
return ;
togo:;
int ans=inf;
for(int i=1;i<=n;i++){
if(ad[i]>1){
continue;
}
dfs(i,0,B,bf);
for(int j=1;j<=n;j++){
if(i==j){
continue;
}
dfs(j,0,A,af);
af[j]=i,af[i]=0;
ans=min(ans,calc()+1);
}
}
cout<<(ans==inf?-1:ans)<<"\n";
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
}
int main(){return asbt::main();}
D. 繩網委托
考慮將為 \(0\) 的位置賦值為 \(1\)，\(1\) 的位置賦值為 \(-1\)，記前綴和為 \(pre\)，\(1\) 的個數為 \(cnt\)，LIS 中最后一個 \(0\) 在原序列中的位置為 \(x\)，那么長度為 \(cnt+pre_x\)。而本題還有翻轉操作，可以注意到翻轉之后的前綴和就是原序列的一段前綴再加上 \(k\) 段不交的子串。
經過這個轉化后，和這道題就非常類似了。考慮一個反悔貪心：每次選出最大的子串并加入答案，同時將這個子串中的數取相反數。這樣如果后面選到的子串和這次的子串有重合，就相當于是將這次的子串反悔掉了一部分。線段樹維護即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lid id<<1
#define rid id<<1|1
#define fir first
#define sec second
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int n,a[maxn],b[maxn],ans[maxn];
bool tag[maxn<<2];
struct node{
int l,r,sum;
node(int l=0,int r=0,int sum=0):l(l),r(r),sum(sum){}
il node operator+(const node &x)const{
return sum>x.sum?*this:x;
}
};
struct seg{
int sum,lm,rm,mm,pl,pr,ml,mr;
seg(int sum=0,int lm=0,int rm=0,int mm=0,int pl=0,int pr=0,int ml=0,int mr=0)
:sum(sum),lm(lm),rm(rm),mm(mm),pl(pl),pr(pr),ml(ml),mr(mr){}
il seg operator+(const seg &x)const{
seg res;
res.sum=sum+x.sum;
node t1=node(0,pl,lm)+node(0,x.pl,sum+x.lm);
node t2=node(x.pr,0,x.rm)+node(pr,0,rm+x.sum);
node t3=node(ml,mr,mm)+node(x.ml,x.mr,x.mm)+node(pr,x.pl,rm+x.lm);
res.lm=t1.sum,res.pl=t1.r;
res.rm=t2.sum,res.pr=t2.l;
res.mm=t3.sum,res.ml=t3.l,res.mr=t3.r;
return res;
}
};
pair<seg,seg> tr[maxn<<2];
il void pushup(int id){
tr[id].fir=tr[lid].fir+tr[rid].fir;
tr[id].sec=tr[lid].sec+tr[rid].sec;
}
il void pushtag(int id){
tag[id]^=1;
swap(tr[id].fir,tr[id].sec);
}
il void pushdown(int id){
if(tag[id]){
pushtag(lid),pushtag(rid);
tag[id]=0;
}
}
il void build(int id,int l,int r){
if(l==r){
tr[id].fir=seg(b[l],b[l],b[l],b[l],l,l,l,l);
tr[id].sec=seg(-b[l],-b[l],-b[l],-b[l],l,l,l,l);
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
}
il void upd(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
pushtag(id);
return ;
}
pushdown(id);
int mid=(L+R)>>1;
if(l<=mid){
upd(lid,L,mid,l,r);
}
if(r>mid){
upd(rid,mid+1,R,l,r);
}
pushup(id);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
int cnt=0;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
if(a[i]){
cnt+=b[i],b[i]=-b[i];
}
}
build(1,1,n);
if(tr[1].fir.lm>0){
cnt+=tr[1].fir.lm;
upd(1,1,n,1,tr[1].fir.pl);
}
for(int i=1;i<=n;i++){
ans[i]=ans[i-1]+tr[1].fir.mm;
upd(1,1,n,tr[1].fir.ml,tr[1].fir.mr);
}
for(int i=1;i<=n;i++){
ans[i]=max(ans[i-1],ans[i]);
}
for(int i=0;i<=n;i++){
cout<<cnt+ans[i]<<"\n";
}
return 0;
}
}
signed main(){return asbt::main();}
2025CSP-S模擬賽31
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 50 | 100 | 30 | 49 | 229 | 5/18 |
A. 花海
一個暴力的做法是枚舉 \(x_1\)，\(x_2\)，\(y_1\)，\(y_2\)，此時的權值即為 \(sum_{x_2,y_2}-sum_{x_1-1,y_2}-sum_{x_2,y_1-1}+sum_{x_1-1,y_1-1}-sum_{x_2-1,y_2-1}+sum_{x_1,y_2-1}+sum_{x_2-1,y_1}-sum_{x_1,y_1}\)。考慮令 \(n\le m\)，于是 \(n\le\sqrt{2\times10^5}\)。枚舉 \(x_1\)，\(x_2\)，\(y_1\)，動態維護 \(y_2\) 的最大貢獻。具體地，倒過來枚舉 \(y_1\)，用當前的 \(y_1\) 更新答案后再更新 \(sum_{x_2,y_2}-sum_{x_1-1,y_2}-sum_{x_2-1,y_2-1}+sum_{x_1,y_2-1}\) 的最大值。時間復雜度 \(O(n^2m)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=455,inf=1e9;
int n,m;
vector<int> a[maxn];
int main(){
freopen("flower.in","r",stdin);
freopen("flower.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
if(n<m){
for(int i=0;i<=n;i++){
a[i].resize(m+5);
}
// for(int i=0;i<=n;i++){
// for(int j=0;j<=m;j++){
// cout<<a[i][j]<<" ";
// }
// cout<<"\n";
// }
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
}
else{
swap(n,m);
for(int i=0;i<=n;i++){
a[i].resize(m+5);
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
cin>>a[i][j];
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
// cout<<a[i][j]<<" ";
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
// cout<<"\n";
}
int ans=-inf;
for(int x1=1;x1<=n;x1++){
for(int x2=x1+1;x2<=n;x2++){
int tmp=-inf;
for(int y1=m;y1;y1--){
ans=max(ans,tmp-a[x2][y1-1]+a[x1-1][y1-1]+a[x2-1][y1]-a[x1][y1]);
tmp=max(tmp,a[x2][y1]-a[x1-1][y1]-a[x2-1][y1-1]+a[x1][y1-1]);
}
}
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
B. 劃分
考慮 DP，設 \(dp_i\) 表示考慮了前 \(i\) 個位置的最小規模和，于是有轉移：
\[dp_i=\min_{\operatorname{sum}[j+1,i]\le m}\{dp_j+\max[j+1,i]\}
\]
滿足條件的 \(j\) 顯然是一段連續區間，可以二分出來。用單調棧維護區間 \(\max\) 的變化，線段樹優化即可。時間復雜度線性對數。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lwrb lower_bound
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=1e5+5,inf=1e18;
int n,m,a[maxn],sa[maxn],stk[maxn],top;
int mn[maxn<<2],tag[maxn<<2],dp[maxn];
il void pushup(int id){
mn[id]=min(mn[lid],mn[rid]);
}
il void pushtag(int id,int v){
tag[id]+=v,mn[id]+=v;
}
il void pushdown(int id){
if(tag[id]){
pushtag(lid,tag[id]);
pushtag(rid,tag[id]);
tag[id]=0;
}
}
il void add(int id,int L,int R,int l,int r,int v){
if(l>r){
return ;
}
if(L>=l&&R<=r){
pushtag(id,v);
return ;
}
pushdown(id);
int mid=(L+R)>>1;
if(l<=mid){
add(lid,L,mid,l,r,v);
}
if(r>mid){
add(rid,mid+1,R,l,r,v);
}
pushup(id);
}
il int query(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return mn[id];
}
pushdown(id);
int mid=(L+R)>>1,res=inf;
if(l<=mid){
res=min(res,query(lid,L,mid,l,r));
}
if(r>mid){
res=min(res,query(rid,mid+1,R,l,r));
}
return res;
}
struct{
int st[maxn][18],Log[maxn];
il void build(){
for(int i=2;i<=n;i++){
Log[i]=Log[i>>1]+1;
}
for(int i=1;i<=n;i++){
st[i][0]=a[i];
}
for(int j=1;j<=Log[n];j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
}
il int query(int l,int r){
int p=Log[r-l+1];
return max(st[l][p],st[r-(1<<p)+1][p]);
}
}ST;
int main(){
freopen("split.in","r",stdin);
freopen("split.out","w",stdout);
// freopen("split3.in","r",stdin);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
sa[i]=sa[i-1]+a[i];
}
if(n<=1e3){
ST.build();
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=i-1;~j;j--){
if(sa[i]-sa[j]>m){
break;
}
dp[i]=min(dp[i],dp[j]+ST.query(j+1,i));
}
}
}
else{
stk[++top]=0;
for(int i=1;i<=n;i++){
add(1,0,n,i-1,i-1,dp[i-1]+a[i]);
while(top&&a[stk[top]]<a[i]){
add(1,0,n,stk[top-1],stk[top]-1,a[i]-a[stk[top]]);
top--;
}
stk[++top]=i;
dp[i]=query(1,0,n,lwrb(sa,sa+i,sa[i]-m)-sa,i-1);
}
}
cout<<dp[n];
return 0;
}
}
signed main(){return asbt::main();}
C. 落子無悔
對于兩個序列 \(a\) 和 \(b\)，我們設 \(s0\) 和 \(s1\) 分別為 \(0\) 和 \(1\) 的數量，由鄰項交換可知 \(a\) 排在 \(b\) 前面更優等價于 \(\frac{s0_a}{s1_a}\ge\frac{s0_b}{s1_b}\)。于是我們的做法就比較顯然了：每次選出 \(\frac{s0}{s1}\) 最大的點，將其與父親節點合并，用 set 維護即可。注意把根特判掉。時間復雜度線性對數。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int n,fa[maxn],p[maxn],a[maxn];
int _0[maxn],_1[maxn],nxt[maxn],lst[maxn];
il int find(int x){
return x!=p[x]?p[x]=find(p[x]):x;
}
struct node{
int u,_0,_1;
node(int u=0,int _0=0,int _1=0):u(u),_0(_0),_1(_1){}
il bool operator<(const node &x)const{
if(_0*1ll*x._1==x._0*1ll*_1){
return u<x.u;
}
return _0*1ll*x._1>x._0*1ll*_1;
}
};
set<node> S;
int main(){
freopen("board.in","r",stdin);
freopen("board.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=2;i<=n;i++){
cin>>fa[i];
}
for(int i=1;i<=n;i++){
cin>>a[i];
_0[i]=a[i]^1,_1[i]=a[i];
p[i]=i,nxt[i]=lst[i]=i;
}
for(int i=2;i<=n;i++){
S.insert(node(i,_0[i],_1[i]));
}
// for(node x:S){
// cout<<x.u<<" "<<x._0<<" "<<x._1<<"\n";
// }
for(int i=1;i<n;i++){
// cout<<i<<"\n";
int u=S.begin()->u,v=find(fa[u]);
S.erase(node(u,_0[u],_1[u]));
if(v!=1){
S.erase(node(v,_0[v],_1[v]));
}
_0[v]+=_0[u],_1[v]+=_1[u];
nxt[lst[v]]=u,lst[v]=lst[u];
p[u]=v;
if(v!=1){
S.insert(node(v,_0[v],_1[v]));
}
}
ll cnt=0,ans=0;
for(int i=1;;i=nxt[i]){
// cout<<i<<"\n";
if(!a[i]){
ans+=cnt;
}
else{
cnt++;
}
if(i==nxt[i]){
break;
}
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
D. 體測
2025CSP-S模擬賽33
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 100 | 30 | - | 230 | 3/20 |
A. 機器人
dfs，暴力枚舉每一步有沒有遇到障礙物，用 set 維護答案即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
int n;
bool vis[50][50],ban[50][50];
string s;
set<pii> S;
il void dfs(int x,int y,int d){
if(d>n){
S.insert(mp(x,y));
return ;
}
int nx,ny;
switch(s[d]){
case 'L':{
nx=x-1,ny=y;
break;
}
case 'R':{
nx=x+1,ny=y;
break;
}
case 'D':{
nx=x,ny=y-1;
break;
}
default:{
nx=x,ny=y+1;
break;
}
}
if(!vis[nx+20][ny+20]){
vis[nx+20][ny+20]=1;
dfs(nx,ny,d+1);
ban[nx+20][ny+20]=1;
dfs(x,y,d+1);
ban[nx+20][ny+20]=0;
vis[nx+20][ny+20]=0;
}
else if(ban[nx+20][ny+20]){
dfs(x,y,d+1);
}
else{
dfs(nx,ny,d+1);
}
}
int main(){
// system("fc robot3.ans my.out");
// freopen("robot3.in","r",stdin);
// freopen("my.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>s;
s=" "+s;
vis[20][20]=1;
dfs(0,0,1);
cout<<S.size()<<"\n";
for(pii x:S){
cout<<x.fir<<" "<<x.sec<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
B. 旅行
首先考慮一個暴力的思路：將每個點拆成若干個點，代表可能的顏色，對邊設點，將邊與端點對應的顏色用并查集合并即可。發現每次合并在一段時間后就會撤銷，使用可撤銷并查集，線段樹分治即可。時間復雜度線性對數方，需要卡常。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace IO{
const int bufsz=1<<20;
char ibuf[bufsz],*p1=ibuf,*p2=ibuf;
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)
il int read(){
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
int x=0u;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
#undef getchar
char obuf[bufsz],*p3=obuf,s[50];
#define flush() (fwrite(obuf,1,p3-obuf,stdout),p3=obuf)
#define putchar(ch) (p3==obuf+bufsz&&flush(),*p3++=(ch))
il void write(int x){
int top=0u;
do{
s[++top]=x%10|48;
x/=10;
}while(x);
while(top){
putchar(s[top--]);
}
putchar('\n');
}
#undef putchar
struct FL{
~FL(){
flush();
}
}fl;
#undef flush
}
using IO::read;
using IO::write;
const int maxn=1e5+5;
int T,n,m,cnt,tot,top,col[maxn],pos[maxn],ban[maxn];
int fa[maxn*5],sz[maxn*5],tz[maxn*5],ans[maxn];
pii stk[maxn<<1];
map<pii,int> bid;
map<int,int> did[maxn];
vector<pii> g[maxn<<2];
struct{
int u,v,w;
}e[maxn];
il int find(int x){
return x!=fa[x]?find(fa[x]):x;
}
il void merge(int u,int v){
u=find(u),v=find(v);
if(u==v){
return ;
}
if(sz[u]>sz[v]){
swap(u,v);
}
stk[++top]=mp(u,v);
sz[v]+=sz[u],fa[u]=v;
if(tz[u]&&tz[v]){
--tot;
}
tz[v]+=tz[u];
}
il void che(){
int u=stk[top].fir,v=stk[top].sec;
--top,fa[u]=u,sz[v]-=sz[u],tz[v]-=tz[u];
if(tz[u]&&tz[v]){
++tot;
}
}
int l,r;
pii x;
il void add(int id,int L,int R){
if(L>=l&&R<=r){
g[id].pb(x);
return ;
}
int mid=(L+R)>>1;
if(l<=mid){
add(lid,L,mid);
}
if(r>mid){
add(rid,mid+1,R);
}
}
il void solve(int id,int l,int r){
int ttp=top;
for(pii i:g[id]){
merge(i.fir,i.sec);
}
if(l==r){
ans[l]=tot;
}
else{
int mid=(l+r)>>1;
solve(lid,l,mid);
solve(rid,mid+1,r);
}
while(top>ttp){
che();
}
g[id].clear();
}
int main(){
// system("fc tour3.ans my.out");
// freopen("tour3.in","r",stdin);
// freopen("my.out","w",stdout);
T=read();
while(T--){
cnt=n=read(),m=read();
bid.clear();
for(int i=1u;i<=n;++i){
did[i].clear();
ban[i]=0u;
}
for(int i=1u,u,v,w;i<=n;++i){
u=read(),v=read(),w=read();
// cout<<u<<" "<<v<<" "<<w<<"\n";
if(u>v){
swap(u,v);
}
did[u][w]=++cnt;
did[v][w]=++cnt;
if(bid.count(mp(u,v))){
ban[bid[mp(u,v)]]=i;
}
else{
bid[mp(u,v)]=i;
}
col[i]=w,pos[i]=0u;
}
for(int i=1u,u,v,w;i<=m;++i){
u=read(),v=read(),w=read();
if(u>v){
swap(u,v);
}
did[u][w]=++cnt;
did[v][w]=++cnt;
e[i]={u,v,w};
}
for(int i=1u;i<=m;++i){
int u=e[i].u,v=e[i].v,w=e[i].w;
int k=bid[mp(u,v)];
if(col[k]==w){
continue;
}
l=pos[k],r=i-1;
x=mp(k,did[u][col[k]]),add(1u,0u,m);
x=mp(k,did[v][col[k]]),add(1u,0u,m);
col[k]=w,pos[k]=i;
if(ban[k]){
k=ban[k];
l=pos[k],r=i-1;
x=mp(k,did[u][col[k]]),add(1u,0u,m);
x=mp(k,did[v][col[k]]),add(1u,0u,m);
col[k]=w,pos[k]=i;
}
}
for(pair<pii,int> i:bid){
int u=i.fir.fir,v=i.fir.sec,k=i.sec;
l=pos[k],r=m;
x=mp(k,did[u][col[k]]),add(1u,0u,m);
x=mp(k,did[v][col[k]]),add(1u,0u,m);
if(ban[k]){
k=ban[k];
l=pos[k],r=m;
x=mp(k,did[u][col[k]]),add(1u,0u,m);
x=mp(k,did[v][col[k]]),add(1u,0u,m);
}
}
for(int i=1u;i<=cnt;++i){
fa[i]=i,sz[i]=1u,tz[i]=i<=n;
}
tot=n,solve(1u,0u,m);
// cerr<<ans[0]<<"\n";
for(int i=1u;i<=m;++i){
write(ans[i]);
}
}
// cerr<<mx<<"\n";
return 0;
}
}
int main(){return asbt::main();}
C. 點餐
考慮第 \(i\) 個客人怎么做，將 \(b\) 升序排序，枚舉 \(j\ge i\)，強制選擇 \(j\)，那么 \(b\) 的最大值即為 \(b_j\)，再在前 \(j-1\) 個位置中選擇前 \(i-1\) 小的 \(a\) 即可，需要主席樹。進一步可以發現的是，最優決策點是有單調性的。于是分治即可。時間復雜度線性對數方。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lwrb lower_bound
using namespace std;
namespace asbt{
const int maxn=2e5+5,maxm=maxn*20,inf=1e18;
int n,tot,lsh[maxn],tong[maxn],rt[maxn],ans[maxn];
int cnt,ls[maxm],rs[maxm],sz[maxm],sum[maxm];
struct node{
int a,b;
}p[maxn];
il void pushup(int id){
sz[id]=sz[ls[id]]+sz[rs[id]];
sum[id]=sum[ls[id]]+sum[rs[id]];
}
il void insert(int &p,int q,int l,int r,int x){
p=++cnt;
if(l==r){
sum[p]=lsh[x],sz[p]=1;
return ;
}
int mid=(l+r)>>1;
if(x<=mid){
rs[p]=rs[q];
insert(ls[p],ls[q],l,mid,x);
}
else{
ls[p]=ls[q];
insert(rs[p],rs[q],mid+1,r,x);
}
pushup(p);
}
il int query(int id,int l,int r,int x){
if(!id||!x){
return 0;
}
if(sz[id]==x){
return sum[id];
}
int mid=(l+r)>>1;
if(x<=sz[ls[id]]){
return query(ls[id],l,mid,x);
}
return sum[ls[id]]+query(rs[id],mid+1,r,x-sz[ls[id]]);
}
il int calc(int x,int y){
// cout<<x<<" "<<y<<" "<<query(rt[y-1],1,n,x-1)<<"\n";
return query(rt[y-1],1,n,x-1)+lsh[p[y].a]+p[y].b;
}
il void solve(int L,int R,int l,int r){
if(L>R){
return ;
}
int mid=(L+R)>>1;
int &res=ans[mid]=inf,p=-1;
for(int i=max(l,mid);i<=r;i++){
int t=calc(mid,i);
if(t<res){
res=t,p=i;
}
}
// cout<<mid<<" "<<p<<" "<<calc(mid,p)<<"\n";
solve(L,mid-1,l,p);
solve(mid+1,R,p,r);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i].a>>p[i].b;
lsh[++tot]=p[i].a;
}
sort(lsh+1,lsh+tot+1);
for(int i=1;i<=n;i++){
int t=lwrb(lsh+1,lsh+tot+1,p[i].a)-lsh;
p[i].a=t+tong[t],tong[t]++;
}
sort(p+1,p+n+1,[](node x,node y){return x.b<y.b||x.b==y.b&&x.a<y.a;});
for(int i=1;i<=n;i++){
insert(rt[i],rt[i-1],1,n,p[i].a);
}
solve(1,n,1,n);
for(int i=1;i<=n;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
signed main(){return asbt::main();}
D. 無窮括號序列
設 \(f_{k,i}\) 表示 \(B^k\) 中第 \(i\) 個左括號的下標，于是答案可以通過差分+二分求出，問題變為求 \(f\)。
考慮轉移，分兩種情況：
-
\(f_{k-1,i}\) 下一個位置為右括號，
()會變成)(，于是 \(f_{k,i}=f_{k-1,i}+1\) -
\(f_{k+1,i}\) 下一個位置為左括號，
((會變成(*，于是 \(f_{k,i}=f_{k-1,i+1}-1\)。
于是 \(f_{k,i}=\min(f_{k-1,i}+1,f_{k-1,i+1}-1)\)。
我們假設 \(f_{k,i}\) 是從 \(f_{0,j}\) 轉移過來的，于是轉移過程中 \(\min\) 中的第二項選了 \(j-i\) 次，第一項選了 \(k-j+i\) 次。于是有：
\[f_{k,i}=\min_{j=i}^{i+k}\{f_{0,j}+k-2j+2i\}
\]
考慮用 ST 表維護 \(F_j=f_{0,j}-2j\) 的最小值，但是序列太長了。記序列 \(A\) 中有 \(m\) 個左括號，于是 \(f_{0,j+m}=f_{0,j}+n\)。于是：
\[F_j=F_{j\bmod m}+(n-2m)\times\lfloor\frac{j}{m}\rfloor
\]
于是只需要預處理出 \(F_0\) 到 \(F_{2m-1}\) 即可。但是如果 \(k>m\)，我們依然求不了，考慮 \(n\) 和 \(2m\) 的關系。
-
\(n\ge2m\)，則 \(F_{j+m}\ge F_j\)，最小值在 \([i,i+m)\) 中。
-
\(n<2m\)，類似地，最小值在 \((i+k-m,i+k]\) 中。
這樣就又可以求了。輕微卡常，減少取模即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e5+5,inf=1e9;
int T,n,m,q,f[maxn],Log[maxn],st[maxn][19];
string s;
il int query(int l,int r){
int p=Log[r-l+1];
return min(st[l][p],st[r-(1<<p)+1][p]);
}
il int F(int k,int i){
#define qum(x) (x=x>=0?x:x+m)
if(k<=m){
int p=i%m;qum(p);
int t=(i-p)/m;
return query(p,p+k)+k+2*i+(n-2*m)*t;
}
if(n>=m<<1){
int p=i%m;qum(p);
int t=(i-p)/m;
return query(p,p+m-1)+k+2*i+(n-2*m)*t;
}
int p=(i+k)%m;qum(p);
int t=(i+k-m-p)/m;
return query(p+1,p+m)+k+2*i+(n-2*m)*t;
#undef qum
}
il int g(int k,int p){
int l=-inf,r=inf;
while(l<r){
int mid=(l+r+1)>>1;
if(F(k,mid)<=p){
l=mid;
}
else{
r=mid-1;
}
}
return l;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(int i=2;i<=2e5;i++){
Log[i]=Log[i>>1]+1;
}
cin>>T;
while(T--){
cin>>s>>q;
n=s.size(),m=0;
for(int i=0;i<n;i++){
if(s[i]=='('){
f[m++]=i;
}
}
if(!m){
while(q--){
int k,l,r;
cin>>k>>l>>r;
cout<<0<<'\n';
}
continue;
}
for(int i=0;i<m;i++){
f[i+m]=f[i]+n;
}
for(int i=0;i<m<<1;i++){
st[i][0]=f[i]-i*2;
}
for(int j=1;j<=17;j++){
for(int i=0;i+(1<<j)-1<m<<1;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
while(q--){
int k,l,r;
cin>>k>>l>>r;
cout<<g(k,r)-g(k,l-1)<<'\n';
}
}
return 0;
}
}
int main(){return asbt::main();}
2025CSP-S模擬賽34(牛宏昊)
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 50 | 60 | 0 | 35 | 145 | 3/17 |
A. 酒吧
假設我們最終選的是 \(b_1,b_2,\dots,b_k\)，那么答案為 \(\sum_{i=1}^{k-1}(b_{i+1}-b_i)\times(p_{b_i}+p_{b_{i+1}})\)。發現這實際上是梯形面積的兩倍。那么我們相當于是要在所有的點 \((i,p_i)\) 中選一些點使線下面積最大，用單調棧維護上凸包即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e5+5;
int n,a[maxn],q[maxn],tl;
int main(){
freopen("bar.in","r",stdin);
freopen("bar.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
#define K(i,j) (a[j]-a[i])*1.0l/(j-i)
for(int i=1;i<=n;i++){
while(tl>1&&K(q[tl-1],q[tl])<K(q[tl],i)){
tl--;
}
q[++tl]=i;
}
#undef K
int ans=0;
for(int i=1;i<tl;i++){
ans+=(q[i+1]-q[i])*(a[q[i]]+a[q[i+1]]);
}
cout<<ans;
return 0;
}
}
signed main(){return asbt::main();}
B. 逆轉
考慮二分答案 \(mid\)，求出 \(f_i\) 表示從 \(1\) 到 \(i\) 和不超過 \(mid\) 最多能選多少個，\(g_i\) 類似地表示后綴。考慮在 \(1\) 到 \(i\) 中盡可能多選，顯然從小到大選最優。于是用大根堆維護，若能加入則直接加，否則若比堆頂小則替換堆頂即可。時間復雜度線性對數方。CF上卡常
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace IO{
const int bufsz=1<<20;
char ibuf[bufsz],*p1=ibuf,*p2=ibuf;
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)
il int read(){
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
int x=0;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
#undef getchar
char obuf[bufsz],*p3=obuf,s[50];
#define flush() (fwrite(obuf,1,p3-obuf,stdout),p3=obuf)
#define putchar(ch) (p3==obuf+bufsz&&flush(),*p3++=(ch))
il void write(ll x){
int top=0;
do{
s[++top]=x%10|48;
x/=10;
}while(x);
while(top){
putchar(s[top--]);
}
}
struct FL{
~FL(){
flush();
}
}fl;
#undef flush
#undef putchar
}
using IO::read;
using IO::write;
const int maxn=3e5+5;
int T,n,m,a[maxn],f[maxn],g[maxn];
il bool check(ll x){
ll sum=0;
priority_queue<int> q;
for(int i=1;i<=n;i++){
if(sum+a[i]<=x){
q.push(a[i]),sum+=a[i];
}
else if(q.size()&&a[i]<q.top()){
sum-=q.top(),q.pop();
q.push(a[i]),sum+=a[i];
}
f[i]=q.size();
}
sum=0;
while(q.size()){
q.pop();
}
for(int i=n;i;i--){
if(sum+a[i]<=x){
q.push(a[i]),sum+=a[i];
}
else if(q.size()&&a[i]<q.top()){
sum-=q.top(),q.pop();
q.push(a[i]),sum+=a[i];
}
g[i]=q.size();
}
f[0]=g[n+1]=0;
for(int i=0;i<=n;i++){
if(f[i]+g[i+1]>=m){
return 1;
}
}
return 0;
}
int main(){
freopen("ace.in","r",stdin);
freopen("ace.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
ll l=1,r=3e14;
while(l<r){
ll mid=(l+r)>>1;
if(check(mid)){
r=mid;
}
else{
l=mid+1;
}
}
write(l);
return 0;
}
}
int main(){return asbt::main();}
C. 世界
設 \(f_{i,j}\) 表示 \(n-i,k=j\) 的答案，于是有方程：
\[f_{i,j}=\frac{(m-i)(i-j+1)}{(i+1)m}f_{i+1,j}+\frac{(m-i)j}{m(i+1)}f_{i+1,j+1}+\frac{i}{m(i-1)}(\sum_{k=j}^{i-1}f_{k,j}+\sum_{k=1}^{j-1}f_{i-k,j-k})
\]
將 \(f_{i+1,j+1}\) 移項到一邊，發現另一邊的第二維都 \(\le j\)。但是此時我們不能遞推，因為上面那個式子中 \(j\ne1\)。也就是說，我們需要求出 \(j=2\) 的所有 \(f_{i,j}\)。
考慮主元法，將 \(\forall i\in[3,m],f_{i,2}\) 設為主元，做前綴和即可用這 \(m-2\) 個主元表示其它值。注意到我們在表示過程中 \(i\ne m\)，而這正好有 \(j\in[2,m-1]\) 共 \(m-2\) 個，于是再用它們的式子高斯消元即可。答案即為 \(f_{n,k}\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=255,mod=1e9+7;
il int pls(int x,int y){
return x+y<mod?x+y:x+y-mod;
}
il int sub(int x,int y){
return x<y?x-y+mod:x-y;
}
il int qpow(int x,int y=mod-2){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
x=x*1ll*x%mod,y>>=1;
}
return res;
}
int n,kk,m,inv[maxn];
struct node{
int a[maxn];
node(){
for(int i=1;i<m;i++){
a[i]=0;
}
}
il int&operator[](int x){
return a[x];
}
il node operator+(node x)const{
node res;
for(int i=1;i<m;i++){
res[i]=pls(a[i],x[i]);
}
return res;
}
il node operator-(node x)const{
node res;
for(int i=1;i<m;i++){
res[i]=sub(a[i],x[i]);
}
return res;
}
il node operator*(int x)const{
node res;
for(int i=1;i<m;i++){
res[i]=a[i]*1ll*x%mod;
}
return res;
}
}a[maxn][maxn],f[maxn][maxn],g[maxn][maxn],h[maxn];
il void gsjd(int n){
for(int i=1;i<=n;i++){
for(int j=1;j<=n+1;j++){
cout<<h[i][j]<<" ";
}
cout<<"\n";
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if(h[j][i]){
swap(h[i],h[j]);
break;
}
}
int t=qpow(h[i][i]);
for(int j=1;j<=n;j++){
if(i==j){
continue;
}
for(int k=i+1;k<=n+1;k++){
h[j][k]=sub(h[j][k],h[j][i]*1ll*t%mod*h[i][k]%mod);
}
}
}
for(int i=1;i<=n;i++){
h[i][n+1]=h[i][n+1]*1ll*qpow(h[i][i])%mod;
}
}
int main(){
freopen("world.in","r",stdin);
freopen("world.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>kk>>m;
if(kk==1||kk==n){
cout<<n;
return 0;
}
inv[1]=1;
for(int i=2;i<=m;i++){
inv[i]=inv[mod%i]*1ll*(mod-mod/i)%mod;
}
for(int i=1;i<=m;i++){
a[i][1][m-1]=a[i][i][m-1]=i;
}
for(int i=3;i<=m;i++){
a[i][2][i-2]=1;
}
for(int j=1;j<=m;j++){
for(int i=j;i<=m;i++){
f[i][j]=f[i-1][j]+a[i][j];
g[i][j]=g[i-1][j-1]+a[i][j];
}
if(j>1){
for(int i=j+1;i<m;i++){
a[i+1][j+1]=a[i][j]*(m*1ll*(i+1)%mod*inv[m-i]%mod*inv[j]%mod)-a[i+1][j]*((i-j+1)*1ll*inv[j]%mod)-(f[i-1][j]+g[i-1][j-1])*(i*1ll*(i+1)%mod*inv[i-1]%mod*inv[m-i]%mod*inv[j]%mod);
}
}
}
for(int i=2;i<m;i++){
h[i-1]=(f[m-1][i]+g[m-1][i-1])*inv[m-1]-a[m][i];
h[i-1][m-1]=(mod-h[i-1][m-1])%mod;
}
gsjd(m-2);
int ans=0;
for(int i=1;i<=m-2;i++){
// cout<<a[n][kk][i]<<" ";
ans=pls(ans,a[n][kk][i]*1ll*h[i][m-1]%mod);
}
// cout<<"\n";
cout<<pls(ans,a[n][kk][m-1]);
return 0;
}
}
int main(){return asbt::main();}
D. 染色
沒動。（一語雙關
浙公網安備 33010602011771號