【比賽記錄】2025CSP-S模擬賽3
A. 光
首先有一個貪心，每次選擇需要電量最大的位置加上 \(4\)，給相鄰的兩個位置加上 \(2\)，再給對角位置加上 \(1\)。
這樣不正確的原因是最后一些位置可能剩不下 \(4\) 個電量了，而我們四個四個放，就會產生浪費。那么我們之間暴力枚舉最后每個位置都剩下多少（\(0\) 到 \(3\)），然后再貪心即可。時間復雜度 \(O(256(a+b+c+d))\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int inf=0x3f3f3f3f;
int A,B,C,D;
il int solve(int a,int b,int c,int d){
int res=0;
while(a>0||b>0||c>0||d>0){
res++;
int tmp=max({a,b,c,d});
if(a==tmp){
a-=4,b-=2,c-=2,d--;
}
else if(b==tmp){
b-=4,a-=2,d-=2,c--;
}
else if(c==tmp){
c-=4,a-=2,d-=2,b--;
}
else{
d-=4,b-=2,c-=2,a--;
}
}
return res<<2;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>A>>B>>C>>D;
int ans=inf;
for(int a=0;a<=3;a++){
for(int b=0;b<=3;b++){
for(int c=0;c<=3;c++){
for(int d=0;d<=3;d++){
ans=min(ans,a+b+c+d+solve(A-a-b/2-c/2-d/4,B-b-a/2-d/2-c/4,C-c-a/2-d/2-b/4,D-d-b/2-c/2-a/4));
}
}
}
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
B. 爬
對于每個點，我們考慮按位拆貢獻。對于當前位，枚舉有多少個為 \(1\) 的兒子節點爬上來，簡單組合數計算方案數即可。注意當這個點上只有一個螞蟻時不算貢獻，還有要特判根。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5,mod=1e9+7;
int n,a[maxn],fa[maxn];
int _2[maxn],fac[maxn],inv[maxn];
vector<int> e[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;
}
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;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=2;i<=n;i++){
cin>>fa[i];
e[fa[i]].pb(i);
}
_2[0]=1;
for(int i=1;i<=1e5;i++){
_2[i]=_2[i-1]*2ll%mod;
}
fac[0]=1;
for(int i=1;i<=n;i++){
fac[i]=fac[i-1]*1ll*i%mod;
}
inv[n]=qpow(fac[n],mod-2);
for(int i=n;i;i--){
inv[i-1]=inv[i]*1ll*i%mod;
}
int ans=0;
for(int i=1,tot;i<=n;i++){
tot=e[i].size();
for(int j=0,cnt;j<=30;j++){
cnt=0;
for(int u:e[i]){
if(a[u]>>j&1){
cnt++;
}
}
for(int k=0;k<=cnt;k++){
if(k==0){
if(a[i]>>j&1){
(ans+=(_2[tot-cnt]-1+mod)*1ll*_2[n-tot-(i==1?1:2)]%mod*_2[j]%mod)%=mod;
}
}
else if(k==1){
if(a[i]>>j&1){
if(i!=1){
(ans+=cnt*1ll*(_2[tot-cnt]-1+mod)%mod*_2[n-tot-2]%mod*_2[j]%mod)%=mod;
}
}
else{
(ans+=cnt*1ll*_2[tot-cnt]%mod*_2[n-tot-(i==1?1:2)]%mod*_2[j]%mod)%=mod;
if(i!=1){
(ans+=cnt*1ll*(_2[tot-cnt]-1+mod)%mod*_2[n-tot-2]%mod*_2[j]%mod)%=mod;
}
}
}
else if(k&1){
if(a[i]>>j&1){
if(i!=1){
(ans+=C(cnt,k)*1ll*_2[tot-cnt]%mod*_2[n-tot-2]%mod*_2[j]%mod)%=mod;
}
}
else{
(ans+=C(cnt,k)*1ll*_2[tot-cnt]%mod*_2[n-tot-1]%mod*_2[j]%mod)%=mod;
}
}
else{
if(a[i]>>j&1){
(ans+=C(cnt,k)*1ll*_2[tot-cnt]%mod*_2[n-tot-(i==1?1:2)]%mod*_2[j]%mod)%=mod;
}
}
}
}
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
/*
5
64 19 1 46 1
1 1 1 1
*/
C. 字符串
考慮 \(c\) 的限制非常的討厭，數據范圍是允許我們去 \(O(n)\) 枚舉的，所以我們首先就枚舉 \(\underbrace{BBB\dots B}_{c}A\underbrace{BBB\dots B}_{c}\) 這樣的有幾段。然后我們把剩下的 \(A\) 和 \(B\) 填充進去。
首先填 \(A\)，顯然可以在最開頭填一個，產生 \(1\) 的貢獻。然后本質上就是每填進去長為 \(a\) 的 \(A\) 序列，就產生 \(1\) 的貢獻。
然后填 \(B\)，如果當前最后一個字母是 \(A\)，那顯然可以在最后面添加一個 \(B\) 來產生 \(1\) 的貢獻。然后我們把所有長為 \(c\) 的 \(B\) 串都填成 \(k\cdot b+1,k\in\mathbb{Z}\) 的長度。此時再多一段長為 \(b\) 的 \(B\) 串就會再產生 \(1\) 的貢獻。不要忘了如果 \(c>b\) 那么一開始就會有貢獻。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
int T,n,m,a,b,c;
il void solve(){
cin>>n>>m>>a>>b>>c;
int ans=0;
for(int i=0;;i++){ // BBB/A 有幾段
int cnta=i/2,cntb=(i+1)/2;
int A=n-cnta,B=m-cntb*c;
if(A<0||B<0){
break;
}
int res=i;
res+=(c-(c-1)%b-1)/b*cntb;
if(A>0){
A--,res++;
}
res+=A/a;
if(i%2==0&&B>0){
B--,res++;
}
int tmp=((1-c)%b+b)%b;
if(tmp){
int num=min(B/tmp,cntb);
res+=num,B-=num*tmp;
}
res+=B/b;
ans=max(ans,res);
}
cout<<ans<<"\n";
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
}
int main(){return asbt::main();}
D. 奇怪的函數
首先，這個函數其實顯然是一個分三段的連續的函數，形如：
\[F(x)=\begin{cases}
L&\ x\le l\\
x+D&\ l<x<r\\
R&\ x\ge r
\end{cases}
\]
于是我們維護函數的 \(L\)，\(R\) 和 \(D\)，即可通過沒有修改的那個包。維護這三個值是可以線性完成的。
考慮一次修改后我們就要再整個掃一遍，無法接受。考慮分塊，那么每次修改重構一個塊，查詢就去掃所有塊，單次時間都是 \(O(\sqrt{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,maxb=320,inf=1e18;
int n,m,blen,bnum,bel[maxn],st[maxb],ed[maxb];
struct{
int opt,val;
}a[maxn];
struct{
int L,R,D;
}b[maxb];
il void upd(int x){
b[x].L=-inf,b[x].R=inf,b[x].D=0;
for(int i=st[x];i<=ed[x];i++){
switch(a[i].opt){
case 1:{
b[x].L+=a[i].val;
b[x].R+=a[i].val;
b[x].D+=a[i].val;
break;
}
case 2:{
b[x].L=min(b[x].L,a[i].val);
b[x].R=min(b[x].R,a[i].val);
break;
}
default:{
b[x].L=max(b[x].L,a[i].val);
b[x].R=max(b[x].R,a[i].val);
break;
}
}
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].opt>>a[i].val;
}
blen=sqrt(n);
bnum=(n+blen-1)/blen;
for(int i=1;i<=bnum;i++){
st[i]=ed[i-1]+1;
ed[i]=min(ed[i-1]+blen,n);
for(int j=st[i];j<=ed[i];j++){
bel[j]=i;
}
upd(i);
}
cin>>m;
while(m--){
int opt,x,val;
cin>>opt>>x;
if(opt==4){
for(int i=1;i<=bnum;i++){
x+=b[i].D;
x=min(x,b[i].R);
x=max(x,b[i].L);
}
cout<<x<<"\n";
}
else{
cin>>val;
a[x].opt=opt,a[x].val=val;
upd(bel[x]);
}
}
return 0;
}
}
signed main(){return asbt::main();}
浙公網安備 33010602011771號