2025CSP-S模拟赛67（CSP-S模拟42）
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 60(70) | 25 | 30 | 5 | 120 | 5/14(7/34) |
A. 乘筛积
对于单次查询，我们可以直接枚举 \(x\) 算出对应的 \(y\) 贡献答案，时间复杂度 \(O(\frac{C}{\max(p,q)})\)。根号分治即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e5+5,mod=998244353;
int n,m,kk,T,a[maxn],b[maxn],f[550][550];
il int solve(int p,int q,int *a,int *b,int n,int m){if(p<q){swap(p,q),swap(a,b),swap(n,m);}int ans=0;for(int i=1;i<=n&&i*p<=kk;i++){if((kk-i*p)%q==0){int j=(kk-i*p)/q;if(j>0&&j<=m){ans=(ans+a[i]*b[j])%mod;}}}return ans;
}
int main(){freopen("sedge.in","r",stdin);freopen("sedge.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m>>kk;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i];}for(int i=1;i<=547;i++){for(int j=1;j<=547;j++){f[i][j]=solve(i,j,a,b,n,m);}}cin>>T;while(T--){int p,q;cin>>p>>q;if(max(p,q)<=547){cout<<f[p][q]<<'\n';}else{cout<<solve(p,q,a,b,n,m)<<'\n';}}return 0;
}
}
signed main(){return asbt::main();}
B. 放进去
首先对于每个奢侈品单独考虑，不妨令 \(a_{i,p_1}\le a_{i,p_2}\le a_{i,p_3}\le\dots\le a_{i,p_m}\)。假设我们最终选的店铺集合是 \(S\)，那么对于 \(i\) 我们必然选择 \(S\) 中 \(a\) 最小（也就是最靠前）的 \(p_j\)。考虑差分，即对于所有 \(k<j\)，给答案加上 \(a_{i,p_{k+1}}-a_{i,p_k}\)。考虑 SOSDP，于是我们只需要给所有 \(\{p_1,p_2,\dots,p_k\}\) 的答案加上 \(a_{i,p_{k+1}}-a_{i,p_k}\)，最后再做一遍高维前缀和即可。记这个和为 \(f_S\)，\(\sum_{i\in S}b_i=g_S\)，于是 \(S\) 的答案即为 \(g_S+f_{\complement_US}\)。时间复杂度 \(O(nm\log m+m2^m)\)，轻微卡常。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=(1<<25)+5,inf=1e18;
il int pls(int x,int y){return x+y<inf?x+y:inf;
}
il void add(int &x,int y){x=pls(x,y);
}
int n,m,b[30],f[maxn],g[maxn];
struct node{int p,v;il bool operator<(const node &x)const{return v<x.v;}
}a[30];
int main(){freopen("putin.in","r",stdin);freopen("putin.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[j].v;a[j].p=j;}sort(a+1,a+m+1);a[m+1]={m+1,inf};for(int j=1,S=0;j<=m+1;j++){
// cout<<a[j].p<<' '<<a[j].v<<'\n';add(f[S],a[j].v-a[j-1].v);S|=1<<(a[j].p-1);}}for(int i=1;i<=m;i++){for(int S=0;S<1<<m;S++){if(S>>(i-1)&1){continue;}add(f[S|1<<(i-1)],f[S]);}}for(int i=1;i<=m;i++){cin>>b[i];}int ans=inf;for(int S=0;S<1<<m;S++){g[S]=pls(g[S^(S&-S)],b[__lg(S&-S)+1]);ans=min(ans,g[S]+f[((1<<m)-1)^S]);}cout<<ans;return 0;
}
}
signed main(){return asbt::main();}