多校A层冲刺NOIP2024模拟赛05
\(T1\) A. 好数（number） \(100pts/100pts\)
-
枚举两数之和，开个桶维护即可。
点击查看代码
int a[5010]; unordered_map<int,bool>s; int main() { freopen("number.in","r",stdin); freopen("number.out","w",stdout); int n,ans=0,i,j; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; for(j=i;j>=1;j--) { if(s.find(a[i]-a[j])!=s.end()) { ans++; break; } } for(j=i;j>=1;j--) { s[a[i]+a[j]]=1; } } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
\(T2\) B. SOS字符串（sos） \(20pts/20pts\)
-
观察到仅需统计
SOS出现次数 \(\ge 3\) 。正难则反，考虑用总方案数减去SOS出现次数 \(<3\) 的方案数。 -
总方案数显然为 \(26^{n}\) 。
-
部分分
- \(20pts\) ：打表加手摸。
点击查看代码
const ll p=1000000007; int ans=0; string s; vector<char>e; unordered_map<string,bool>vis; void dfs1(int pos) { if(pos==e.size()) { if(vis.find(s)==vis.end()) { ans++; ans-=(ans>=p); vis[s]=1; } } else { if(e[pos]=='*') { for(char i='A';i<='Z';i++) { s[pos]=i; dfs1(pos+1); } } else { s[pos]='S'; s[pos+1]='O'; s[pos+2]='S'; dfs1(pos+3); } } } void dfs2(int pos,int n,int sum) { if(pos<=n+1) { if(pos==n+1) { if(sum>=3) { dfs1(0); } } else { e.push_back('*'); dfs2(pos+1,n,sum); e.pop_back(); e.push_back('S'); e.push_back('O'); e.push_back('S'); dfs2(pos+3,n,sum+1); e.pop_back(); e.pop_back(); e.pop_back(); } } } int main() { freopen("sos.in","r",stdin); freopen("sos.out","w",stdout); int n; cin>>n; if(n==13) { cout<<15973496<<endl; } else { s.resize(n+1); dfs2(1,n,0); cout<<ans<<endl; } fclose(stdin); fclose(stdout); return 0; } -
正解
- 将
S,O和其他 \(24\) 个字符分开考虑。 - 设 \(f_{i,j,k}\) 表示前 \(i\) 个字符中已经出现了 \(j\) 个
SOS，现在匹配到SOS的第 \(k\) 个字符（因为有SOSOS只算一次的要求，所以把 \(k=3\) 同样看做 \(k=0\) ）的方案数。状态转移方程为 \(\begin{cases} f_{i,j,0}=25(f_{i-1,j,0}+f_{i-1,j,2})+24f_{i-1,j,1}+f_{i-1,j-1,2} \\ f_{i,j,1}=f_{i-1,j,0}+f_{i-1,j,1} \\ f_{i,j,2}=f_{i-1,j,1} \end{cases}\) ，边界为 \(f_{0,0,0}=1\) 。 - 最终，有 \(26^{n}-\sum\limits_{j=0}^{2}\sum\limits_{k=0}^{2}f_{n,j,k}\) 即为所求。
点击查看代码
const ll p=1000000007; ll f[2][5][5]; ll qpow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } int main() { freopen("sos.in","r",stdin); freopen("sos.out","w",stdout); ll n,ans,i,j; cin>>n; ans=qpow(26,n,p); f[0][0][0]=1; for(i=1;i<=n;i++) { for(j=0;j<=2;j++) { f[i&1][j][0]=((f[(i-1)&1][j][0]+f[(i-1)&1][j][2])%p*25%p+f[(i-1)&1][j][1]*24%p)%p; if(j-1>=0) { f[i&1][j][0]=(f[i&1][j][0]+f[(i-1)&1][j-1][2])%p; } f[i&1][j][1]=(f[(i-1)&1][j][0]+f[(i-1)&1][j][1])%p; f[i&1][j][2]=f[(i-1)&1][j][1]; } } for(j=0;j<=2;j++) { ans=(ans-f[n&1][j][0]+p)%p; ans=(ans-f[n&1][j][1]+p)%p; ans=(ans-f[n&1][j][2]+p)%p; } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; } - 将
\(T3\) C. 集训营的气球（balloon） \(50pts/50pts\)
-
观察到 \(c \le 20\) 。正难则反，考虑用总方案数减去顾客中有 \(<c\) 个人购买一血气球的方案数。
-
总方案数显然为 \(\prod\limits_{i=1}^{n}(a_{i}+b_{i})\) 。
-
部分分
- \(50pts\)
-
测试点 \(3 \sim 5\)
- 设 \(f_{i,j}\) 表示前 \(i\) 个人中共有 \(j\) 个人买一血气球的方案数，状态转移方程为 \(f_{i,j}=a_{i}f_{i-1,j-1}+b_{i}f_{i-1,j}\) ，边界为 \(f_{0,0}=1\) 。
- 最终有 \(\prod\limits_{i=1}^{n}(a_{i}+b_{i})-\sum\limits_{i=0}^{\min(c-1,n)}f_{n,i}\) 即为所求。
- 时间复杂度为 \(O(nqc)\) 。
-
测试点 \(1 \sim 2\)
- 因为 \(c=1\) ，所以每个人都只能买普通气球。故 \(\prod\limits_{i=1}^{n}(a_{i}+b_{i})-\prod\limits_{i=1}^{n}b_{i}\) 即为所求。
- 时间复杂度为 \(O((n+q)\log p)\) 。
点击查看代码
const ll p=1000000007; ll a[1000010],b[1000010],inv[1000010],invb[1000010],f[2][30]; ll qpow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } ll qadd(ll a,ll b,ll p) { return a+b>=p?a+b-p:a+b; } int main() { freopen("balloon.in","r",stdin); freopen("balloon.out","w",stdout); ll n,q,c,mul=1,sum,pos,i,j,k; scanf("%lld%lld",&n,&c); c--; for(i=1;i<=n;i++) { scanf("%lld",&a[i]); } for(i=1;i<=n;i++) { scanf("%lld",&b[i]); inv[i]=qpow(a[i]+b[i],p-2,p); mul=mul*(a[i]+b[i])%p; } scanf("%lld",&q); if(c==0) { sum=1; for(i=1;i<=n;i++) { invb[i]=qpow(b[i],p-2,p); sum=sum*b[i]%p; } for(k=1;k<=q;k++) { scanf("%lld",&pos); mul=mul*inv[pos]%p; sum=sum*invb[pos]%p; scanf("%lld%lld",&a[pos],&b[pos]); invb[pos]=qpow(b[pos],p-2,p); inv[pos]=qpow(a[pos]+b[pos],p-2,p); mul=mul*(a[pos]+b[pos])%p; sum=sum*b[pos]%p; printf("%lld\n",(mul-sum+p)%p); } } else { for(k=1;k<=q;k++) { scanf("%lld",&pos); mul=mul*inv[pos]%p; scanf("%lld%lld",&a[pos],&b[pos]); inv[pos]=qpow(a[pos]+b[pos],p-2,p); mul=mul*(a[pos]+b[pos])%p; sum=0; memset(f,0,sizeof(f)); f[0][0]=1; for(i=1;i<=n;i++) { for(j=0;j<=min(i,c);j++) { f[i&1][j]=f[(i-1)&1][j]*b[i]%p; if(j-1>=0) { f[i&1][j]=qadd(f[i&1][j],f[(i-1)&1][j-1]*a[i]%p,p); } } } for(i=0;i<=min(n,c);i++) { sum=qadd(sum,f[n&1][i],p); } printf("%lld\n",(mul-sum+p)%p); } } fclose(stdin); fclose(stdout); return 0; }
-
- \(80pts\)
-
\(\{ f \}\) 的转移本质是一个背包求方案数的转移过程，使用动态开点线段树或 查理线段树 （否则空间开不下）优化合并背包的过程即可。
-
时间复杂度为 \(O((n+q)c^{2})\) 。
点击查看动态开点线段树代码
const ll p=1000000007; int a[1000010],b[1000010]; struct SMT { int root,rt_sum; struct SegmentTree { int ls,rs,f[25],mul; }tree[2000010]; #define lson(rt) (tree[rt].ls) #define rson(rt) (tree[rt].rs) void pushup(int rt,int c) { memset(tree[rt].f,0,sizeof(tree[rt].f)); for(int i=0;i<=c;i++) { for(int j=0;i+j<=c;j++) { tree[rt].f[i+j]=(tree[rt].f[i+j]+1ll*tree[lson(rt)].f[i]*tree[rson(rt)].f[j]%p)%p; } } tree[rt].mul=1ll*tree[lson(rt)].mul*tree[rson(rt)].mul%p; } int build_rt() { rt_sum++; return rt_sum; } void build(int &rt,int l,int r,int c) { rt=build_rt(); if(l==r) { tree[rt].f[0]=b[l]; tree[rt].f[1]=a[l]; tree[rt].mul=a[l]+b[l]; return; } int mid=(l+r)/2; build(lson(rt),l,mid,c); build(rson(rt),mid+1,r,c); pushup(rt,c); } void update(int rt,int l,int r,int pos,int c) { if(l==r) { tree[rt].f[0]=b[l]; tree[rt].f[1]=a[l]; tree[rt].mul=a[l]+b[l]; return; } int mid=(l+r)/2; if(pos<=mid) { update(lson(rt),l,mid,pos,c); } else { update(rson(rt),mid+1,r,pos,c); } pushup(rt,c); } }T; int main() { freopen("balloon.in","r",stdin); freopen("balloon.out","w",stdout); int n,c,q,pos,ans,i,j; scanf("%d%d",&n,&c); c--; for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=1;i<=n;i++) { scanf("%d",&b[i]); } T.build(T.root,1,n,c); scanf("%d",&q); for(j=1;j<=q;j++) { scanf("%d",&pos); scanf("%d%d",&a[pos],&b[pos]); T.update(T.root,1,n,pos,c); ans=T.tree[T.root].mul; for(i=0;i<=c;i++) { ans=(ans-T.tree[T.root].f[i]+p)%p; } printf("%d\n",ans); } fclose(stdin); fclose(stdout); return 0; }点击查看查理线段树代码
const ll p=1000000007; int a[1000010],b[1000010]; struct SMT { struct SegmentTree { int f[25],mul; }tree[2000010]; #define lson(rt) (mid<<1) #define rson(rt) (mid<<1|1) void pushup(int rt,int c,int l,int r) { int mid=(l+r)/2; memset(tree[rt].f,0,sizeof(tree[rt].f)); for(int i=0;i<=c;i++) { for(int j=0;i+j<=c;j++) { tree[rt].f[i+j]=(tree[rt].f[i+j]+1ll*tree[lson(rt)].f[i]*tree[rson(rt)].f[j]%p)%p; } } tree[rt].mul=1ll*tree[lson(rt)].mul*tree[rson(rt)].mul%p; } void build(int rt,int l,int r,int c) { if(l==r) { tree[rt].f[0]=b[l]; tree[rt].f[1]=a[l]; tree[rt].mul=a[l]+b[l]; return; } int mid=(l+r)/2; build(lson(rt),l,mid,c); build(rson(rt),mid+1,r,c); pushup(rt,c,l,r); } void update(int rt,int l,int r,int pos,int c) { if(l==r) { tree[rt].f[0]=b[l]; tree[rt].f[1]=a[l]; tree[rt].mul=a[l]+b[l]; return; } int mid=(l+r)/2; if(pos<=mid) { update(lson(rt),l,mid,pos,c); } else { update(rson(rt),mid+1,r,pos,c); } pushup(rt,c,l,r); } }T; int main() { freopen("balloon.in","r",stdin); freopen("balloon.out","w",stdout); int n,c,q,pos,ans,i,j; scanf("%d%d",&n,&c); c--; for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=1;i<=n;i++) { scanf("%d",&b[i]); } T.build(1,1,n,c); scanf("%d",&q); for(j=1;j<=q;j++) { scanf("%d",&pos); scanf("%d%d",&a[pos],&b[pos]); T.update(1,1,n,pos,c); ans=T.tree[1].mul; for(i=0;i<=c;i++) { ans=(ans-T.tree[1].f[i]+p)%p; } printf("%d\n",ans); } fclose(stdin); fclose(stdout); return 0; }
-
- \(50pts\)
-
正解
- 对于修改操作，使用回退背包维护即可，做法详见 luogu P4141 消失之物 。
- 以 luogu P4141 消失之物 为例，滚动数组下倒序插入背包预处理代码如下。
for(j=m;j>=w[i];j--) { f[j]+=f[j-w[i]]; } - 在少了第 \(i\) 件物品的情况下，等价于少了一轮上面的转移。需要正序撤销背包的影响，画个图会更好理解。
memcpy(g,s,sizeof(f));//新开数组的写法比较通用 for(j=w[i];j<=m;j++) { g[j]-=g[j-w[i]]; }
- 以 luogu P4141 消失之物 为例，滚动数组下倒序插入背包预处理代码如下。
点击查看代码
const ll p=1000000007; ll a[1000010],b[1000010],f[30],g[30]; ll qpow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } int main() { freopen("balloon.in","r",stdin); freopen("balloon.out","w",stdout); ll n,q,c,mul=1,sum,inv,pos,i,j,k; scanf("%lld%lld",&n,&c); c--; for(i=1;i<=n;i++) { scanf("%lld",&a[i]); } f[0]=1; for(i=1;i<=n;i++) { scanf("%lld",&b[i]); mul=mul*(a[i]+b[i])%p; for(j=c;j>=0;j--) { f[j]=f[j]*b[i]%p; if(j-1>=0) { f[j]=(f[j]+f[j-1]*a[i]%p)%p; } } } scanf("%lld",&q); for(k=1;k<=q;k++) { scanf("%lld",&pos); mul=mul*qpow(a[pos]+b[pos],p-2,p)%p; inv=qpow(b[pos],p-2,p); g[0]=1; for(j=0;j<=c;j++) { if(j-1>=0) { g[j]=((f[j]-g[j-1]*a[pos]+p)%p)*inv%p; } else { g[j]=f[j]*inv%p; } } for(j=0;j<=c;j++) { f[j]=g[j]; } scanf("%lld%lld",&a[pos],&b[pos]); mul=mul*(a[pos]+b[pos])%p; for(j=c;j>=0;j--) { f[j]=f[j]*b[pos]%p; if(j-1>=0) { f[j]=(f[j]+f[j-1]*a[pos]%p)%p; } } sum=0; for(i=0;i<=c;i++) { sum=(sum+f[i])%p; } printf("%lld\n",(mul-sum+p)%p); } fclose(stdin); fclose(stdout); return 0; } - 对于修改操作，使用回退背包维护即可，做法详见 luogu P4141 消失之物 。
\(T4\) D. 连通子树与树的重心（tree） \(0pts/0pts\)
总结
- \(T2\)
- 一直在想通配符
*(A-Z)的贡献怎么考虑，没有想到把S,O,和其他 \(24\) 个字符分开考虑统计贡献。 - 没想到正难则反了，挺好。
- 一直在想通配符
- \(T3\)
- Alt 加方向键的拖拽有点害人，检查 \(T3\) 代码时再次发现把
粘成了scanf("%lld%lld",&n,&c); c--;c--; scanf("%lld%lld",&n,&c); - 想到正难则反了，挺好。
- 感觉之前学了假的背包，没想到能够转化为背包合并。
- Alt 加方向键的拖拽有点害人，检查 \(T3\) 代码时再次发现把
- \(T4\) 全程没读明白题，没搞懂为啥样例 \(3\) 的答案是 \(6\) ，手摸出来结果是 \(5=\{ \{ 2 \}, \{ 1,2,3 \} , \{ 1,2,4 \} , \{ 1,2,5 \} , \{ 1,2,4,5 \} \}\) 。
- 看到原版题面后发现子树包括原树。
后记
- \(T2\) 初始数据仅有 \(10 \%\) 的数据符合 \(n \le 12\) ，与数据范围中“对于 \(20 \%\) 的数据，\(n \le 12\)” 不符。赛后更改了 \(n \le 12\) 的数据进行重测。