【比賽記錄】2025暑假集訓模擬賽合集Ⅲ
2025CSP-S模擬賽41
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 27 | 40 | 8 | 175 | 10/19 |
A. 限速（speed）
如果最小生成樹中最大的邊權 \(\ge k\)，那么只需在最小生成樹上做修改即可，其它生成樹不可能更優；否則用與 \(k\) 的差值最小的邊替換掉一條即可。用二分實現 kruskal 的又是什么人類呢
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e5+5,inf=0x3f3f3f3f;
int n,m,kk,fa[maxn],sz[maxn];
struct edge{
int u,v,w;
edge(int u=0,int v=0,int w=0):u(u),v(v),w(w){}
il bool operator<(const edge &x)const{
return w<x.w;
}
}e[maxn];
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il bool check(int x){
for(int i=1;i<=n;i++){
fa[i]=i,sz[i]=1;
}
for(int i=1;i<=m;i++){
if(e[i].w>x){
break;
}
int u=find(e[i].u),v=find(e[i].v);
if(u!=v){
fa[v]=u,sz[u]+=sz[v];
}
}
return sz[find(1)]==n;
}
int main(){
freopen("speed.out","w",stdout);
freopen("speed.in","r",stdin);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>kk;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
e[i]=edge(u,v,w);
}
sort(e+1,e+m+1);
if(check(kk)){
int ans=inf;
for(int i=1;i<=m;i++){
ans=min(ans,abs(e[i].w-kk));
}
cout<<ans;
return 0;
}
int l=1,r=1e9;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)){
r=mid;
}
else{
l=mid+1;
}
}
ll ans=0;
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<=m;i++){
if(e[i].w>l){
break;
}
int u=find(e[i].u),v=find(e[i].v),w=e[i].w;
if(u!=v){
fa[v]=u;
ans+=max(w-kk,0);
}
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
B. 酒鬼 （drunkard）
對于 \(p_i>1\)，如果 \(p_i+q_i\not\equiv p_j+q_j\pmod{2}\) 那么產生矛盾。而對于 \(p_i=1\)，如果與后面產生矛盾那么可以將最小出發時間變大為 \(q_i+1\) 來滿足要求。同時對于相鄰時間，\(|p_i-p_j|>q_j-q_i\) 那么不合法。用 map 維護，模擬即可。
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
#define lwrb lower_bound
using namespace std;
namespace asbt{
const int inf=0x3f3f3f3f;
int n,m,mn,mx=inf;
bool flag;
map<int,pii> S;
il bool check(pii a,pii b){
if(abs(a.fir-b.fir)>b.sec-a.sec){
return 0;
}
if(a.fir>1&&a.sec<=mn){
return 0;
}
if(b.fir>1){
mx=min(mx,b.sec-b.fir+1);
}
#define chk ((a.fir+a.sec)%2==(b.fir+b.sec)%2)
if(a.fir==1&&a.sec<=mx){
if(!chk){
mn=max(mn,a.sec+1);
}
return 1;
}
return chk;
#undef chk
}
int main(){
freopen("drunkard.in","r",stdin);
freopen("drunkard.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
S[0]=mp(1,0);
while(m--){
string opt;
cin>>opt;
switch(opt[1]){
case 'l':{
int p,q;
cin>>p>>q;
if(flag){
continue;
}
if(S.count(q)&&S[q].fir!=p){
flag=1;
continue;
}
auto t=S.lwrb(q);
if(t!=S.end()&&!check(mp(p,q),t->sec)){
flag=1;
continue;
}
if(!check(prev(t)->sec,mp(p,q))){
flag=1;
continue;
}
S[q]=mp(p,q);
break;
}
case 'i':{
if(flag){
cout<<"bad\n";
}
else{
cout<<mn<<'\n';
}
break;
}
default:{
if(flag){
cout<<"bad\n";
}
else if(mx==inf){
cout<<"inf\n";
}
else{
cout<<mx<<'\n';
}
break;
}
}
}
return 0;
}
}
int main(){return asbt::main();}
C. 距離（distance）
\(\min(|a_x-a_y|,|b_x-b_y|)=|a_x-a_y|+|b_x-b_y|-\max(|a_x-a_y|,|b_x-b_y|)\)。前面是曼哈頓距離，后面是切比雪夫距離，切比雪夫轉曼哈頓后就轉化為了形如 \(\sum\limits_{x\in\operatorname{subtree}(u)}\sum\limits_{y\in\operatorname{subtree}(u)}|a_x-a_y|\) 的子問題。考慮權值線段樹，在每個節點維護答案、數量和總和即可線性對數求解。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define ls(id) tr[id].ls
#define rs(id) tr[id].rs
#define cnt(id) tr[id].cnt
#define sum(id) tr[id].sum
#define ans(id) tr[id].ans
using namespace std;
namespace asbt{
const int maxn=5e5+5,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 void add(int &x,int y){
x=pls(x,y);
}
il void mns(int &x,int y){
x=sub(x,y);
}
int n,tot,rt[maxn],ans[maxn];
ll a[maxn],b[maxn],c[maxn],d[maxn];
vector<int> e[maxn];
struct{
int ls,rs,cnt,sum,ans;
}tr[maxn*39];
il void pushup(int id){
cnt(id)=cnt(ls(id))+cnt(rs(id));
sum(id)=pls(sum(ls(id)),sum(rs(id)));
// cout<<cnt(ls(id))<<' '<<sum(ls(id))<<' '<<cnt(rs(id))<<' '<<sum(rs(id))<<'\n';
ans(id)=((ans(ls(id))+ans(rs(id))+cnt(ls(id))*1ll*sum(rs(id))-cnt(rs(id))*1ll*sum(ls(id)))%mod+mod)%mod;
}
il void insert(int &id,ll l,ll r,ll p){
if(!id){
id=++tot;
ls(id)=rs(id)=cnt(id)=sum(id)=ans(id)=0;
}
if(l==r){
// cout<<sum(id)<<' '<<p<<'\n';
cnt(id)++,sum(id)=((sum(id)+p)%mod+mod)%mod;
// cout<<ans(id)<<' ';
return ;
}
ll mid=(l+r)>>1;
if(p<=mid){
insert(ls(id),l,mid,p);
}
else{
insert(rs(id),mid+1,r,p);
}
pushup(id);
}
il int merge(int p,int q,ll l,ll r){
if(!p||!q){
return p+q;
}
if(l==r){
cnt(p)+=cnt(q),add(sum(p),sum(q));
// cout<<ans(p)<<' '<<ans(q)<<' ';
return p;
}
ll mid=(l+r)>>1;
ls(p)=merge(ls(p),ls(q),l,mid);
rs(p)=merge(rs(p),rs(q),mid+1,r);
pushup(p);
return p;
}
il void dfs(int u,int fa,ll *a,bool flag){
insert(rt[u],-2e9,2e9,a[u]);
for(int v:e[u]){
if(v==fa){
continue;
}
dfs(v,u,a,flag);
rt[u]=merge(rt[u],rt[v],-2e9,2e9);
}
(flag?add:mns)(ans[u],ans(rt[u]));
}
il void init(){
tot=0;
for(int i=1;i<=n;i++){
rt[i]=0;
}
}
int main(){
// freopen("C.in","r",stdin);
freopen("distance.in","r",stdin);
freopen("distance.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
e[u].pb(v),e[v].pb(u);
}
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
a[i]<<=1,b[i]<<=1;
c[i]=(a[i]+b[i])>>1,d[i]=(a[i]-b[i])>>1;
// cout<<a[i]<<' '<<b[i]<<' '<<c[i]<<' '<<d[i]<<'\n';
}
init(),dfs(1,0,a,1);
init(),dfs(1,0,b,1);
init(),dfs(1,0,c,0);
init(),dfs(1,0,d,0);
for(int i=1;i<=n;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
}
int main(){return asbt::main();}
D. 團隊選拔（selection）
2025CSP-S模擬賽42
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 40 | - | 0 | 140 | 13/20 |
A. 追逐游戲 (chase)
考慮小 Y 的策略，一定要先走到 \((S,T)\) 的路徑上，然后再和小 Z 相向/同向走。于是我們只需要先找到 \(S'\) 到 \((S,T)\) 上最近的點，然后再判斷二者的位置即可。時間復雜度線性對數。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int n,m,dep[maxn],dfn[maxn],cnt;
int oula[maxn<<1],idx[maxn<<1];
int anc[maxn][20];
vector<int> e[maxn];
il void dfs(int u,int fa){
dep[u]=dep[fa]+1;
dfn[u]=++cnt,oula[cnt]=cnt,idx[cnt]=u;
anc[u][0]=fa;
for(int i=1;i<=18;i++){
anc[u][i]=anc[anc[u][i-1]][i-1];
}
for(int v:e[u]){
if(v==fa){
continue;
}
dfs(v,u);
oula[++cnt]=dfn[u];
}
}
struct{
int Log[maxn<<1],st[maxn<<1][20];
il void build(){
for(int i=2;i<=cnt;i++){
Log[i]=Log[i>>1]+1;
}
for(int i=1;i<=cnt;i++){
st[i][0]=oula[i];
}
for(int j=1;j<=Log[cnt];j++){
for(int i=1;i+(1<<j)-1<=cnt;i++){
st[i][j]=min(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 min(st[l][p],st[r-(1<<p)+1][p]);
}
}ST;
il int lca(int u,int v){
if(dfn[u]>dfn[v]){
swap(u,v);
}
return idx[ST.query(dfn[u],dfn[v])];
}
il int dis(int u,int v){
return dep[u]+dep[v]-dep[lca(u,v)]*2;
}
il int kth(int u,int k){
int t=0;
while(k){
if(k&1){
u=anc[u][t];
}
k>>=1,t++;
}
return u;
}
il int kth(int u,int v,int k){
int x=lca(u,v);
if(k<=dis(u,x)){
return kth(u,k);
}
return kth(v,dis(u,v)-k);
}
int main(){
// system("fc ex_chase2.out my.out");
freopen("chase.in","r",stdin);
freopen("chase.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
e[u].pb(v),e[v].pb(u);
}
dfs(1,0),ST.build();
while(m--){
int x,y,z;
cin>>x>>y>>z;
int t=lca(x,z),_t=lca(y,z);
if(dep[t]<dep[_t]){
t=_t;
}
_t=lca(x,y);
if(dep[t]<dep[_t]){
t=_t;
}
int dx1=dis(x,t),dz1=dis(z,t);
if(dx1<dz1){
cout<<dz1+dis(t,y)<<' '<<y<<'\n';
continue;
}
x=kth(x,y,dz1);
int dt1=dis(x,t);
if(dt1&1){
cout<<dz1+dt1/2+1<<' '<<kth(t,x,dt1>>1)<<'\n';
}
else{
cout<<dz1+dt1/2<<' '<<kth(x,t,dt1>>1)<<'\n';
}
}
return 0;
}
}
int main(){return asbt::main();}
B. 統計
考慮維護 \(V_{i,j}\) 表示 \([1,i]\) 中 \(j\) 出現了多少次，于是 \([l,r]\) 合法等價于 \(\forall j\in[1,m-1],V_{r,j}-V_{l-1,j}=V_{r,j+1}-V_{l-1,j+1}\Leftrightarrow\forall j\in[1,m-1],V_{r,j}-V_{r,j+1}=V_{l-1,j}-V_{l-1,j+1}\)。于是我們維護 \(V\) 的差分數組的哈希值，再用哈希表存一下即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ull unsigned ll
using namespace std;
namespace asbt{
const int maxn=1e6+49,N=1e6,M=1e6+39;
ull bas=2e6+39;
int T,n,m,hd[maxn],enm;
ll ans;
ull pw[maxn];
struct{
ull val;
int sz,nxt;
}e[maxn];
il void insert(ull x){
int y=x%M;
for(int i=hd[y];i;i=e[i].nxt){
if(e[i].val==x){
ans+=e[i].sz++;
return ;
}
}
e[++enm]={x,1,hd[y]},hd[y]=enm;
}
int main(){
freopen("st.in","r",stdin);
freopen("st.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
pw[0]=1;
for(int i=1;i<=N;i++){
pw[i]=pw[i-1]*bas;
}
cin>>T;
while(T--){
cin>>n>>m,enm=ans=0;
for(int i=0;i<M;i++){
hd[i]=0;
}
ull ha=0;
for(int i=1;i<m;i++){
ha+=N*pw[i];
}
insert(ha);
for(int i=1,x;i<=n;i++){
cin>>x;
if(x>1){
ha-=pw[x-1];
}
if(x<m){
ha+=pw[x];
}
insert(ha);
}
cout<<ans<<'\n';
}
return 0;
}
}
signed main(){return asbt::main();}
C. 軟件工程
按是否有某個集合的交集為空分類討論。如果有，那么除了這個集合外的集合中一定都只有一條線段，直接取最長的 \(k-1\) 條線段即可。如果沒有，首先如果 \(i\) 完全覆蓋了 \(j\)，那么 \(i\) 要么單獨成一個集合要么和 \(j\) 放在一個集合，不會有其他可能。于是先將所有 \(i\) 去掉，剩下的線段 \(l\) 和 \(r\) 一定都是單增的，可以 DP 求出最大貢獻，最后再在去掉的線段中取剩下的集合即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e3+5;
int n,m,c1,c2;
ll f[maxn][maxn],g[maxn][maxn];
struct node{
int l,r;
}a[maxn],b[maxn],c[maxn];
il bool cmp1(node x,node y){
return x.r-x.l>y.r-y.l;
}
il bool cmp2(node x,node y){
return x.l<y.l||x.l==y.l&&x.r>y.r;
}
il ll solve1(){
sort(a+1,a+n+1,cmp1);
ll ans=0;
for(int i=1;i<m;i++){
ans+=a[i].r-a[i].l;
}
return ans;
}
il ll solve2(){
sort(a+1,a+n+1,cmp2);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i].l<=a[j].l&&a[i].r>=a[j].r){
c[++c2]=a[i];
goto togo;
}
}
b[++c1]=a[i];
togo:;
}
// cout<<c1<<'\n';
// for(int i=1;i<=c1;i++){
// cout<<b[i].l<<' '<<b[i].r<<'\n';
// }
for(int i=0;i<=c1;i++){
g[0][i]=b[1].r;
}
for(int i=1;i<=m;i++){
for(int j=i;j<=c1;j++){
f[i][j]=g[i-1][j-1]-b[j].l;
g[i][j]=max(g[i][j-1],f[i][j]+b[j+1].r);
}
}
// for(int i=0;i<=m;i++){
// for(int j=1;j<=c1;j++){
// cout<<f[i][j]<<' ';
// }
// cout<<'\n';
// }
sort(c+1,c+c2+1,cmp1);
// cout<<c2<<'\n';
// for(int i=1;i<=c2;i++){
// cout<<c[i].l<<' '<<c[i].r<<'\n';
// }
ll ans=0;
for(int i=1;i<=min(m,c1);i++){
ll res=f[i][c1];
// cout<<res<<'\n';
for(int j=1;j<=min(c2,m-i);j++){
res+=c[j].r-c[j].l;
}
ans=max(ans,res);
}
return ans;
}
int main(){
freopen("se.in","r",stdin);
freopen("se.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].l>>a[i].r;
}
// cout<<solve1()<<' '<<solve2()<<'\n';
cout<<max(solve1(),solve2());
return 0;
}
}
int main(){return asbt::main();}
D. 命運的X
答案為 \(\sum\limits_{i\in[1,n]\land B[1,i]=B[n-i+1,n]}m^i\)。洛谷題解區有一個巧妙而有趣的證明，就不抄了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e5+5,mod=998244353;
int T,m,n,a[maxn],nxt[maxn];
il int qpow(int x,int y){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
x=x*1ll*x%mod,y>>=1;
}
return res;
}
int main(){
freopen("x.in","r",stdin);
freopen("x.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>m>>n;
for(int i=1,j=0;i<=n;i++){
cin>>a[i];
if(i==1){
continue;
}
while(j&&a[i]!=a[j+1]){
j=nxt[j];
}
if(a[i]==a[j+1]){
j++;
}
nxt[i]=j;
}
int ans=0;
for(int i=n;i;i=nxt[i]){
(ans+=qpow(m,i))%=mod;
}
cout<<ans<<'\n';
}
return 0;
}
}
int main(){return asbt::main();}
2025CSP-S模擬賽43
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 10 | - | 20 | 130 | 8/19 |
A. 四舍五入
題目要求 \(i\bmod j<\frac{j}{2}\)，我們考慮 \(j\) 與 \(i\) 的大小關系。如果 \(i<j\) 那么 \(i\bmod j=i\)，\(j>2i\)。否則 \(j\le i\)，此時從 \(i\) 的角度計算 \(j\) 的數量是困難的，考慮計算每個 \(j\) 的貢獻。對于 \(k\in\mathbb{N}^*\)，\(i\in[kj,kj+\lfloor\frac{j}{2}\rfloor]\) 都會被 \(j\) 貢獻，差分即可。時間復雜度調和級數。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e6+5;
int n,f[maxn];
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j+=i){
f[j]++,f[min(j+(i+1)/2,n+1)]--;
}
}
for(int i=1;i<=n;i++){
f[i]+=f[i-1];
cout<<f[i]+n-min(i<<1,n)<<' ';
}
return 0;
}
}
int main(){return asbt::main();}
B. 填算符
首先不可以發現，將 \(k\) 個 & 都放在前面得到的答案一定是最優的，因為先或后與有可能會浪費，而如果先與后或都無法得到 \(1\)，先或后與更不可能得到 \(1\)。然后考慮將每個 & 往后移，對于第 \(i\) 個位置，如果將目前最后一個 & 移到這里不影響答案，那么就移過來。用 ST 表預處理區間與和區間或即可。時間復雜度線性對數。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e6+5;
int n,m,Log[maxn],stk[maxn],top;
ll a[maxn];
struct btand{
il ll operator()(ll x,ll y){
return x&y;
}
};
struct btor{
il ll operator()(ll x,ll y){
return x|y;
}
};
template<typename Tp>struct STable{
Tp opt;
ll st[maxn][22];
il void build(){
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]=opt(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
}
il ll query(int l,int r){
int p=Log[r-l+1];
return opt(st[l][p],st[r-(1<<p)+1][p]);
}
};
STable<btand> STand;
STable<btor> STor;
int main(){
freopen("bitop.in","r",stdin);
freopen("bitop.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=2;i<=n;i++){
Log[i]=Log[i>>1]+1;
}
STand.build(),STor.build();
ll ans=a[1];
for(int i=2;i<=m+1;i++){
ans&=a[i];
}
for(int i=m+2;i<=n;i++){
ans|=a[i];
}
int j=m;
for(int i=n-1;i;i--){
if(!j||i<=j){
break;
}
if(((STand.query(1,j)|STor.query(j+1,i))&a[i+1]&ans)==ans){
stk[++top]=i,j--;
}
else{
ans^=a[i+1]&ans;
}
}
while(j){
stk[++top]=j--;
}
while(top){
cout<<stk[top--]<<' ';
}
return 0;
}
}
int main(){return asbt::main();}
C. 道路修建
D. 逆序圖
首先有一個性質：連通塊是值域連續的一段區間。原因是由于單調性，兩個連通塊不可能相互嵌套。
考慮 DP。設：
-
\(f_{i,0}\) 表示 \(1\) 到 \(i\) 的排列形成了很多個連通塊的總權值和。
-
\(f_{i,1}\) 表示 \(1\) 到 \(i\) 的排列形成了一個連通塊的總權值和。
-
\(g_i\) 表示 \(1\) 到 \(i\) 的排列形成了一個連通塊的總方案數。
題目求 \(f(P_i-P_j)\)，只和差值有關，于是可以進行轉移。
枚舉每對數的貢獻，有：
\[f_{i,0}=\sum_{j=1}^{i-1}f(j)(i-j){i\choose 2}(i-2)!
\]
容斥可得：
\[g_i=i!-\sum_{j=1}^{i-1}j!g_{i-j}\\
f_{i,1}=f_{i,0}-\sum_{j=1}^{i-1}j!f_{i-j,1}+f_{j,0}g_{i,j}
\]
于是對于 \(ans_i\) 表示 \(1\) 到 \(i\) 的排列的答案，考慮將這一塊加入末尾，或跳過這一塊，或以這一塊為開頭，有：
\[ans_i=\sum_{j=0}^{i-1}ans_j\times f_{i-j,1}+ans_j\times g_{i-j}+j!\times f_{i-j,1}
\]
時間復雜度 \(O(n^2)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e3+5,mod=998244353;
il int pls(int x,int y){
return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){
x=pls(x,y);
}
il int sub(int x,int y){
return x<y?x-y+mod:x-y;
}
il void mns(int &x,int y){
x=sub(x,y);
}
int n,a[maxn],fac[maxn],f[maxn][2],g[maxn],ans[maxn];
int main(){
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
fac[0]=1;
for(int i=1;i<=n;i++){
fac[i]=fac[i-1]*1ll*i%mod;
}
for(int i=1;i<n;i++){
cin>>a[i];
}
g[1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
g[i]=(fac[j]*1ll*g[i-j]+g[i])%mod;
f[i][0]=(a[j]*1ll*(i-j)+f[i][0])%mod;
}
g[i]=sub(fac[i],g[i]);
f[i][0]=i*1ll*(i-1)/2%mod*fac[i-2]%mod*f[i][0]%mod;
for(int j=1;j<i;j++){
f[i][1]=(fac[j]*1ll*f[i-j][1]+f[j][0]*1ll*g[i-j]+f[i][1])%mod;
}
f[i][1]=sub(f[i][0],f[i][1]);
for(int j=0;j<i;j++){
ans[i]=(ans[j]*1ll*(f[i-j][1]+g[i-j])+fac[j]*1ll*f[i-j][1]+ans[i])%mod;
}
}
cout<<ans[n];
return 0;
}
}
int main(){return asbt::main();}
2025CSP-S模擬賽44
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | - | 94 | 10 | 204 | 9/16 |
T2 大水題沒看出來就會個 T1 還假了，我真服了
A. 選彩筆（rgb）
考慮二分，對于每個 \(i\)，給 \((R_i,G_i,B_i)\) 的權值加一，于是我們要選的相當于是一個邊長為 \(mid\) 的立方體，枚舉頂點，三維前綴和即可。注意 \((R_i,G_i,B_i)\) 不一定是立方體的頂點，否則就會被這組數據卡掉：
12 12
0 1 0
1 0 0
2 1 0
1 2 0
0 1 2
1 0 2
2 1 2
1 2 2
0 0 1
0 2 1
2 0 1
2 2 1
別問我怎么知道的
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,a[maxn],b[maxn],c[maxn],cnt[305][305][305];
il bool check(int kk){
for(int x1=1,x2=kk+1;x2<=300;x1++,x2++){
for(int y1=1,y2=kk+1;y2<=300;y1++,y2++){
for(int z1=1,z2=kk+1;z2<=300;z1++,z2++){
if(cnt[x2][y2][z2]-cnt[x1-1][y2][z2]-cnt[x2][y1-1][z2]-cnt[x2][y2][z1-1]+cnt[x1-1][y1-1][z2]+cnt[x1-1][y2][z1-1]+cnt[x2][y1-1][z1-1]-cnt[x1-1][y1-1][z1-1]>=m){
return 1;
}
}
}
}
return 0;
}
int main(){
freopen("rgb.in","r",stdin);
freopen("rgb.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i];
cnt[++a[i]][++b[i]][++c[i]]++;
}
for(int i=1;i<=300;i++){
for(int j=1;j<=300;j++){
for(int k=1;k<=300;k++){
cnt[i][j][k]+=cnt[i-1][j][k]+cnt[i][j-1][k]+cnt[i][j][k-1]-cnt[i-1][j-1][k]-cnt[i-1][j][k-1]-cnt[i][j-1][k-1]+cnt[i-1][j-1][k-1];
}
}
}
// for(int i=1;i<=10;i++){
// for(int j=1;j<=10;j++){
// for(int k=1;k<=10;k++){
// cout<<i<<' '<<j<<' '<<k<<' '<<cnt[i][j][k]<<'\n';
// }
// }
// }
int l=0,r=300;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)){
r=mid;
}
else{
l=mid+1;
}
}
cout<<l;
return 0;
}
}
int main(){return asbt::main();}
B. 兵蟻排序（sort）
首先發現每個位置最多能往前移動的距離等于它前面比它大的數的數量。依次考慮 \(b\) 的每一位 \(i\)，在 \(a\) 中找到第一個等于 \(b_i\) 的位置 \(j\)，然后將 \(j\) 一格一格地往前移即可，如果移不了就無解。顯然操作次數小于 \(n^2\)。
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
using namespace std;
namespace asbt{
const int maxn=1e3+5;
int T,n,a[maxn],b[maxn];
vector<pii> ans;
int main(){
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
ans.clear();
for(int i=1;i<=n;i++){
if(a[i]==b[i]){
continue;
}
int j=i+1;
for(;j<=n;j++){
if(a[j]==b[i]){
break;
}
}
while(j>i){
if(a[j]>a[j-1]){
cout<<-1<<'\n';
goto togo;
}
ans.pb(mp(j-1,j));
swap(a[j-1],a[j]),j--;
}
}
cout<<0<<'\n'<<ans.size()<<'\n';
for(pii i:ans){
cout<<i.fir<<' '<<i.sec<<'\n';
}
togo:;
}
return 0;
}
}
int main(){return asbt::main();}
C. 人口局 DBA（dba）
考慮枚舉這個比 \(n\) 小的數前面有多少位與 \(n\) 相同，設后面還剩 \(a\) 位且和為 \(s\)，于是我們需要求 \(\sum_{j=1}^{a}x_j=s,x_j\in[0,m-1],x_1<p\) 的解有多少組。
首先不考慮 \(x_1<p\) 這個限制。考慮二項式反演，令 \(h_i\) 表示恰好有 \(i\) 個數 \(\ge m\) 的方案數，\(g_k\) 表示欽定 \(i\) 個數 \(\ge m\) 的方案數，于是有：
\[g_k=\sum_{i=k}^{a}{i\choose k}h_i\Leftrightarrow h_i=\sum_{k=i}^{a}(-1)^{k-i}{k\choose i}g_k
\]
而根據插板法，我們又可以算出 \(g_k={a\choose k}{s-km+a-1\choose a-1}\)，于是有：
\[f_{a,s}=h_0=\sum_{k=0}^{a}(-1)^k{a\choose k}{s-km+a-1\choose a-1}
\]
再考慮到 \(x_1<p\)，答案即為：
\[\begin{aligned}
&\sum_{i=0}^{p-1}f_{a-1,s-i}\\
=&\sum_{i=0}^{p-1}\sum_{k=0}^{a-1}(-1)^k{a-1\choose k}{s-i-km+a-2\choose a-2}\\
=&\sum_{k=0}^{a-1}(-1)^k{a-1\choose k}\sum_{i=0}^{p-1}{s-i-km+a-2\choose a-2}\\
=&\sum_{k=0}^{a-1}(-1)^k{a-1\choose k}({s-km+a-1\choose a-1}-{s-p-km+a-1\choose a-1})
\end{aligned}
\]
時間復雜度 \(O(L^2)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e3+5,maxm=4e6+2e3+5,mod=1e9+7;
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;
}
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 void add(int &x,int y){x=pls(x,y);}
il void mns(int &x,int y){x=sub(x,y);}
int m,L,aa[maxn],fac[maxm],inv[maxm];
il void init(int n=4e6+2e3){
fac[0]=1;
for(int i=1;i<=n;i++){
fac[i]=fac[i-1]*1ll*i%mod;
}
inv[n]=qpow(fac[n]);
for(int i=n;i;i--){
inv[i-1]=inv[i]*1ll*i%mod;
}
}
il int C(int x,int y){
if(x<y||y<0){
return 0;
}
return fac[x]*1ll*inv[y]%mod*inv[x-y]%mod;
}
int main(){
freopen("dba.in","r",stdin);
freopen("dba.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>m>>L;
for(int i=1;i<=L;i++){
cin>>aa[i];
}
init();
int s=aa[L],ans=0;
for(int i=L-1,a=2,p;i;i--,a++){
s+=aa[i],p=aa[i];
for(int k=0;k<a;k++){
(k&1?mns:add)(ans,C(a-1,k)*1ll*(C(s-k*m+a-1,a-1)-C(s-p-k*m+a-1,a-1)+mod)%mod);
}
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號