【比賽記錄】2025CSP-S模擬賽17
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 20 | 20 | 10 | 150 | 5/21 |
A. zzy 的金牌
設 \(f_{i,j,k}\) 表示考慮了前 \(i\) 個盒子，總共放了 \(j\) 塊金牌，其中在第 \(i\) 個盒子放了 \(k\) 塊金牌的方案數。考慮怎樣保證可重集數量的不重不漏，限定最后每一個盒子的金牌數都小于等于前一個即可。于是我們可以首先將 \(a_i\) 倒序排序，然后求一個 \(b_i=a_i-a_{i-1}\)。于是有轉移：\(f_{i,j,k}=\sum_{x=\max(0,k-b_{i-1})}^{j-k}f_{i-1,j-k,x}\)。前綴和優化即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int mod=998244353;
int n,m,a[305],b[305],f[305][305][305];
struct node{
int p[10];
node(){}
node(int *a){
for(int i=1;i<=n;i++){
p[i]=a[i];
}
sort(p+1,p+n+1);
}
il bool operator<(const node &x)const{
for(int i=1;i<=n;i++){
if(p[i]<x.p[i]){
return 1;
}
if(p[i]>x.p[i]){
return 0;
}
}
return 0;
}
};
set<node> ans;
il void dfs(int x){
if(x>m){
ans.insert(node(a));
return ;
}
for(int i=1;i<=n;i++){
a[i]++;
dfs(x+1);
a[i]--;
}
}
int main(){
// freopen("ex_orzzy2.in","r",stdin);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(n<=7&&m<=7){
dfs(1);
cout<<ans.size();
return 0;
}
sort(a+1,a+n+1,greater<int>());
for(int i=1;i<=n;i++){
b[i]=a[i]-a[i+1];
}
if(n<=50&&m<=50){
for(int i=0;i<=m;i++){
f[1][i][i]=1;
}
for(int i=2;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=j;k++){
for(int x=max(0,k-b[i-1]);x<=j-k;x++){
(f[i][j][k]+=f[i-1][j-k][x])%=mod;
}
}
}
}
int ans=0;
for(int i=0;i<=m;i++){
(ans+=f[n][m][i])%=mod;
}
cout<<ans;
return 0;
}
for(int i=0;i<=m;i++){
f[1][i][i]=1;
}
for(int i=2;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=j;k++){
int t=max(0,k-b[i-1]);
if(t>j-k){
continue;
}
if(t){
f[i][j][k]=(f[i-1][j-k][j-k]-f[i-1][j-k][t-1]+mod)%mod;
}
else{
f[i][j][k]=f[i-1][j-k][j-k];
}
}
for(int k=1;k<=j;k++){
(f[i][j][k]+=f[i][j][k-1])%=mod;
}
}
}
cout<<f[n][m][m];
return 0;
}
}
int main(){return asbt::main();}
B. 口糧輸送
先考慮樹的做法，可以從下往上計算每一條邊需要運輸的口糧，然后在根判斷合不合法。
考慮在一棵樹中一條邊最多走一次，如果 \(\sum a-b\ge\sum w\) 那么必然合法，否則如果合法那么一定有一條邊沒有走，可以直接把它刪掉。類似地，一張圖如果合法那么它走過的邊集一定滿足 \(\sum a-b\ge\sum w\)，那么如果邊集為最小生成樹那一定也滿足。于是對于一個子圖，可以判斷它的最小生成樹是否滿足上面這個式子來判斷合不合法。當然還有一種情況就是有一些邊沒用，那就需要狀壓枚舉子集轉移了。時間復雜度 \(O(T3^n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=(1<<15)+5;
int T,n,m,a[20],b[20],fa[20];
bool vis[20],f[maxn];
struct edge{
int u,v,w;
il bool operator<(const edge &x)const{
return w<x.w;
}
}e[120];
vector<edge> hp;
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
memset(f,0,sizeof(f));
for(int S=0;S<1<<n;S++){
int cnt=0,sm1=0,sm2=0;
for(int i=1;i<=n;i++){
if(S>>(i-1)&1){
sm1+=a[i]-b[i];
vis[i]=1;
cnt++;
}
else{
vis[i]=0;
}
fa[i]=i;
}
hp.clear();
for(int i=1;i<=m;i++){
if(vis[e[i].u]&&vis[e[i].v]){
hp.pb(e[i]);
}
}
sort(hp.begin(),hp.end());
for(edge x:hp){
int u=find(x.u),v=find(x.v);
if(u!=v){
fa[u]=v,cnt--;
sm2+=x.w;
}
}
if(cnt==1&&sm1>=sm2){
f[S]=1;
}
for(int nS=S;nS;nS=(nS-1)&S){
f[S]|=f[nS]&f[S^nS];
}
}
cout<<(f[(1<<n)-1]?"Yes":"No")<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
C. 作弊
設 \(f_i\) 表示 \(1\) 到 \(i\) 的最大收益，那么有方程：\(f_i=\max_{j=0}^{i-1}f_j+cost(j,i)\)。其中 \(cost(j,i)\) 表示在 \([j,i]\) 進行一次作弊的收益。\(\max\) 這個東西像線段樹優化，于是我們想辦法維護 \(cost\) 的變化即可。
設 \(Lr_i\) 表示 \(i\) 左側最遠的 \(\le r_i\) 的位置，\(Ll_i\) 表示 \(i\) 左側最近的 \(\ge l_i\) 的位置，\(Rl\) 和 \(Rr\) 類似。這些可以用 ST 表 + 二分維護出。然后考慮右端點移動時的貢獻：
- \(r\in[i,Rl_i)\)，對 \([Ll_i,Lr_i]\) 有貢獻。
- \(r\in[Rl_i,Rr_i]\)，對 \([Ll_i,i]\) 有貢獻。
- \(r\in(Rr_i,n]\)，沒有貢獻。
于是我們將這些修改差分下來存入 vector，在 DP 的過程中進行修改即可。
Code
#include<bits/stdc++.h>
#define il inline
#define lid id<<1
#define rid id<<1|1
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,a[maxn],ll[maxn],rr[maxn];
int Ll[maxn],Lr[maxn],Rl[maxn],Rr[maxn];
struct{
int Log[maxn],st[maxn][22];
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;
struct node{
int l,r,x;
node(int l=0,int r=0,int x=0):l(l),r(r),x(x){}
};
vector<node> xg[maxn];
struct{
int mx[maxn<<2],tag[maxn<<2];
il void pushup(int id){
mx[id]=max(mx[lid],mx[rid]);
}
il void pushtag(int id,int v){
mx[id]+=v,tag[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>=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 mx[id];
}
pushdown(id);
int mid=(L+R)>>1;
if(r<=mid){
return query(lid,L,mid,l,r);
}
if(l>mid){
return query(rid,mid+1,R,l,r);
}
return max(query(lid,L,mid,l,r),query(rid,mid+1,R,l,r));
}
}S;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
ST.build();
for(int i=1,l,r;i<=n;i++){
cin>>ll[i]>>rr[i];
if(ST.query(1,i)<ll[i]){
Lr[i]=0;
}
else{
l=1,r=i;
while(l<=r){
int mid=(l+r)>>1;
if(ST.query(mid,i)>=ll[i]){
l=mid+1,Lr[i]=mid;
}
else{
r=mid-1;
}
}
}
if(a[i]>rr[i]){
Ll[i]=i+1;
}
else{
l=1,r=i;
while(l<=r){
int mid=(l+r)>>1;
if(ST.query(mid,i)>rr[i]){
l=mid+1;
}
else{
r=mid-1,Ll[i]=mid;
}
}
}
if(ST.query(i,n)<ll[i]){
Rl[i]=n+1;
}
else{
l=i,r=n;
while(l<=r){
int mid=(l+r)>>1;
if(ST.query(i,mid)>=ll[i]){
r=mid-1,Rl[i]=mid;
}
else{
l=mid+1;
}
}
}
if(a[i]>rr[i]){
Rr[i]=i-1;
}
else{
l=i,r=n;
while(l<=r){
int mid=(l+r)>>1;
if(ST.query(i,mid)>rr[i]){
r=mid-1;
}
else{
l=mid+1,Rr[i]=mid;
}
}
}
}
for(int i=1;i<=n;i++){
if(Ll[i]<=Lr[i]&&i<Rl[i]){
xg[i].pb(node(Ll[i],Lr[i],1));
xg[Rl[i]].pb(node(Ll[i],Lr[i],-1));
}
if(Ll[i]<=i&&Rl[i]<=Rr[i]){
xg[Rl[i]].pb(node(Ll[i],i,1));
xg[Rr[i]+1].pb(node(Ll[i],i,-1));
}
}
int ans=0;
for(int i=1;i<=n;i++){
S.add(1,1,n,i,i,ans);
for(node x:xg[i]){
S.add(1,1,n,x.l,x.r,x.x);
}
ans=S.query(1,1,n,1,i);
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
D. 合作的力量
改編自原神。
浙公網安備 33010602011771號