【比賽記錄】2025CSP-S模擬賽5
A. 十年之約
發現 \(f(n)\) 很小，考慮計算每個值 \(x\) 是多少個數的 \(f\) 值。顯然要求 \(f(i)=x\)，必定滿足 \(\operatorname{lcm}[1,x-1]\mid i\land\operatorname{lcm}[1,x]\nmid i\)。因此貢獻就是 \(\lfloor\frac{n}{\operatorname{lcm}[1,x-1]}\rfloor-\lfloor\frac{n}{\operatorname{lcm}[1,x]}\rfloor\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define gcd __gcd
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int mod=1e9+7;
int T,n;
il int lcm(int x,int y){
return x/gcd(x,y)*y;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n;
int ans=0,cur=1,cnt=0;
for(int i=2;;i++){
int tmp=lcm(cur,i);
int num=n/cur-n/tmp;
cur=tmp,cnt+=num,ans+=num*i;
if(cnt==n){
break;
}
}
cout<<ans%mod<<"\n";
}
return 0;
}
}
signed main(){return asbt::main();}
B. 可愛三小只
考慮操作是不用考慮順序的，行列交叉產生的貢獻是好計算的，因此把行和列分開計算。那么就是一個簡單的貪心了，可以用堆來做。
然后將行和列合并，考慮枚舉有多少次行操作。假設有 \(i\) 次，那么行列交叉就會使答案變小 \(i\times(k-i)\)。時間復雜度 \(O((nm+k)\log nm)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e3+5,maxm=1e6+5;
int n,m,k,p,a[maxn][maxn];
int f[maxm],g[maxm];
priority_queue<int> q;
il void calc(int p,int *f){
for(int i=1;i<=k;i++){
int tmp=q.top();
q.pop();
f[i]=f[i-1]+tmp;
q.push(tmp-p);
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>k>>p;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
int tmp=0;
for(int j=1;j<=m;j++){
tmp+=a[i][j];
}
q.push(tmp);
}
calc(p*m,f);
while(q.size()){
q.pop();
}
for(int j=1;j<=m;j++){
int tmp=0;
for(int i=1;i<=n;i++){
tmp+=a[i][j];
}
q.push(tmp);
}
calc(p*n,g);
int ans=-1e18;
for(int i=0;i<=k;i++){
ans=max(ans,f[i]+g[k-i]-p*i*(k-i));
}
cout<<ans;
return 0;
}
}
signed main(){return asbt::main();}
C. 蛋糕塌了
序列排序后對答案沒有影響。
考慮排序后的序列 \(a\)，對于兩個數 \(a_i\) 和 \(a_j\)（\(i<j\)），它們產生的貢獻為 \(\frac{a_i\times a_j}{2^{j-i+1}}\)。考慮一個分治位置 \(mid\in[i,j)\)，可以將這個式子拆成 \(\frac{a_i}{2^{mid-i+1}}\times\frac{a_j}{2^{j-mid}}\)。那么我們將這個東西放在線段樹上維護，對于每個區間維護答案和兩個類似前后綴的東西（分別是 \(\frac{a_l}{2}+\frac{a_{l+1}}{2^2}+\dots+\frac{a_r}{2^{r-l+1}}\) 和 \(\frac{a_r}{2}+\frac{a_{r-1}}{2^2}+\dots+\frac{a_l}{2^{r-l+1}}\)）。這個區間的答案就是兩個分治區間的答案加上兩個區間合并造成的貢獻。需要離散化，而且相同的數得離散到不同的位置。
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{
namespace cplx{bool begin;}
const int maxn=3e5+5,mod=1e9+7;
int n,m,a[maxn],inv[maxn];
int lsh[maxn<<1],cnt[maxn<<1];
il int qpow(int x,int y){
int res=1;
while(y){
if(y&1){
(res*=x)%=mod;
}
(x*=x)%=mod,y>>=1;
}
return res;
}
struct{
int p,x;
}b[maxn];
struct node{
int len,sum,pre,suf;
node(){
len=sum=pre=suf=0;
}
node(int x){
len=1,sum=0;
pre=suf=x*inv[1]%mod;
}
il node operator+(const node &x)const{
node res;
res.len=len+x.len;
res.sum=(sum+x.sum+suf*x.pre)%mod;
res.pre=(pre+x.pre*inv[len])%mod;
res.suf=(suf*inv[x.len]+x.suf)%mod;
return res;
}
}tr[maxn<<3];
il void pushup(int id){
tr[id]=tr[lid]+tr[rid];
}
il void insert(int id,int l,int r,int x){
if(l==r){
tr[id]=node(lsh[x]);
return ;
}
int mid=(l+r)>>1;
if(x<=mid){
insert(lid,l,mid,x);
}
else{
insert(rid,mid+1,r,x);
}
pushup(id);
}
il void erase(int id,int l,int r,int x){
if(l==r){
tr[id]=node();
return ;
}
int mid=(l+r)>>1;
if(x<=mid){
erase(lid,l,mid,x);
}
else{
erase(rid,mid+1,r,x);
}
pushup(id);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
int tot=0;
for(int i=1;i<=n;i++){
cin>>a[i];
lsh[++tot]=a[i];
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>b[i].p>>b[i].x;
lsh[++tot]=b[i].x;
}
sort(lsh+1,lsh+tot+1);
for(int i=1;i<=n;i++){
a[i]=lwrb(lsh+1,lsh+tot+1,a[i])-lsh;
cnt[a[i]]++;
a[i]+=cnt[a[i]]-1;
}
for(int i=1;i<=m;i++){
int &tmp=b[i].x;
tmp=lwrb(lsh+1,lsh+tot+1,tmp)-lsh;
cnt[tmp]++;
tmp+=cnt[tmp]-1;
}
inv[n]=qpow(qpow(2,n),mod-2);
for(int i=n;i;i--){
inv[i-1]=(inv[i]+inv[i])%mod;
}
for(int i=1;i<=n;i++){
insert(1,1,tot,a[i]);
}
cout<<tr[1].sum<<"\n";
for(int i=1;i<=m;i++){
int p=b[i].p,x=b[i].x;
erase(1,1,tot,a[p]);
a[p]=x;
insert(1,1,tot,a[p]);
cout<<tr[1].sum<<"\n";
}
return 0;
}
}
signed main(){return asbt::main();}
D. 西安行
首先將題意轉化成一個計數問題：
有 \(n\) 個格子，除了 \(a_i,i\in[1,m]\) 這 \(m\) 個格子之外，在每個格子后都可以放置一個隔板。規定第 \(1\) 個格子前和第 \(n\) 個格子后一定有隔板。每兩個相鄰的格子之間要放一黑一白兩個小球，位置可以重合。求放置的方案數。
那么我們就可以設計 DP：設 \(dp_{i,0/1/2}\) 表示前 \(i\) 個格子，最后一段放了 \(0/1/2\) 個球的方案數。那么對于可放置或不可放置的格子 \(i\)，可以設計出刷表的轉移式：
-
可放置
-
\(dp_{i+1,0}=dp_{i,0}+dp_{i,2}\)
-
\(dp_{i+1,1}=2dp_{i,0}+dp_{i,1}+2dp_{i,2}\)
-
\(dp_{i+1,2}=dp_{i,0}+dp_{i,1}+2dp_{i,2}\)
-
-
不可放置
-
\(dp_{i+1,0}=dp_{i,0}\)
-
\(dp_{i+1,1}=2dp_{i,0}+dp_{i,1}\)
-
\(dp_{i+1,2}=dp_{i,0}+dp_{i,1}+dp_{i,2}\)
-
于是可以設計出轉移矩陣，進行矩陣快速冪。時間復雜度 \(O(27m\log n)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5,mod=1e9+7;
int n,m,a[maxn];
struct juz{
int mat[3][3];
juz(){
memset(mat,0,sizeof mat);
}
il int*operator[](int x){
return mat[x];
}
il juz operator*(juz x)const{
juz res;
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++){
for(int k=0;k<=2;k++){
(res[i][j]+=mat[i][k]*x[k][j])%=mod;
}
}
}
return res;
}
}bas0,bas1,ans;
il juz qpow(juz x,int y){
juz res;
res[0][0]=res[1][1]=res[2][2]=1;
while(y){
if(y&1){
res=res*x;
}
x=x*x,y>>=1;
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i];
}
ans[0][0]=1;
bas0[0][0]=bas0[0][2]=bas0[1][1]=bas0[1][2]=bas0[2][0]=1;
bas0[0][1]=bas0[2][1]=bas0[2][2]=2;
bas1[0][0]=bas1[0][2]=bas1[1][1]=bas1[1][2]=bas1[2][2]=1;
bas1[0][1]=2;
a[0]=-1;
for(int i=1;i<=m;i++){
ans=ans*qpow(bas0,a[i]-a[i-1]-1)*bas1;
}
cout<<(ans*qpow(bas0,n-a[m]-1))[0][2];
return 0;
}
}
signed main(){return asbt::main();}
浙公網安備 33010602011771號