多校A层冲刺NOIP2024模拟赛24
\(T1\) A. 选取字符串 \(100pts\)
-
考虑建出失配树，然后等价于询问 \(\sum\limits_{S \sube \{ 0,1,2, \dots ,n \},|S|=k}dep_{\operatorname{LCA}\{ S \}}^{2}\) 。
-
不妨从 \(\operatorname{LCA}\) 的角度考虑，统计 \(x\) 能作为多少个 \(|S|\) 的 \(\operatorname{LCA}\) 。但是这也不可做，考虑 \(x\) 对答案的贡献。
-
同 luogu P5305 [GXOI/GZOI2019] 旧词 ，将单个点深度平方的贡献 \(dep_{x}^{2}\) 差分成路径上所有点深度的贡献 \(\sum\limits_{i \in (0 \to x)}(dep_{i}^{2}-dep_{fa_{i}}^{2})=\sum\limits_{i \in (0 \to x)}(2dep_{i}-1)\) ，再乘以 \(\dbinom{siz_{x}}{k}\) 即可。
-
故 \(\sum\limits_{i=0}^{n}(2dep_{i}-1)\dbinom{siz_{i}}{k}\) 即为所求。
点击查看代码
const ll p=998244353; ll siz[1000010],dep[1000010],nxt[1000010],jc[1000010],inv[1000010],jc_inv[1000010],ans=0; char s[1000010]; vector<ll>e[1000010]; void add(ll u,ll v) { e[u].push_back(v); } ll C(ll n,ll m,ll p) { return (n>=m&&n>=0&&m>=0)?(jc[n]*jc_inv[n-m])%p*jc_inv[m]%p:0; } void dfs(ll x,ll fa,ll k) { siz[x]=1; dep[x]=dep[fa]+1; for(ll i=0;i<e[x].size();i++) { dfs(e[x][i],x,k); siz[x]+=siz[e[x][i]]; } ans=(ans+(2*dep[x]%p-1+p)%p*C(siz[x],k,p)%p)%p; } int main() { #define Isaac #ifdef Isaac freopen("string.in","r",stdin); freopen("string.out","w",stdout); #endif ll n,k,i,j; scanf("%lld%s",&k,s+1); n=strlen(s+1); for(i=2,nxt[1]=j=0;i<=n;i++) { while(j>=1&&s[i]!=s[j+1]) { j=nxt[j]; } j+=(s[i]==s[j+1]); nxt[i]=j; } inv[1]=jc[0]=jc_inv[0]=jc[1]=jc_inv[1]=1; for(i=2;i<=n+1;i++) { inv[i]=(p-p/i)*inv[p%i]%p; jc[i]=jc[i-1]*i%p; jc_inv[i]=jc_inv[i-1]*inv[i]%p; } for(i=1;i<=n;i++) { add(nxt[i],i); } dfs(0,n+1,k); printf("%lld\n",ans); return 0; }
\(T2\) B. 取石子 \(20pts\)
-
部分分
- \(20pts\) ：暴力建博弈树。
点击查看代码
int a[50010]; vector<pair<int,int> >ans; bool dfs(int last,int n) { for(int i=1;i<=n;i++) { for(int j=1;j<=min(a[i],last);j++) { a[i]-=j; bool tmp=dfs(j,n); a[i]+=j; if(tmp==false) { return true; } } } return false; } bool work(int k,int n) { for(int i=1;i<=n;i++) { for(int j=1;j<=min(a[i],k);j++) { a[i]-=j; bool tmp=dfs(j,n); a[i]+=j; if(tmp==false) { ans.push_back(make_pair(i,j)); } } } return ans.size(); } int main() { #define Isaac #ifdef Isaac freopen("nim.in","r",stdin); freopen("nim.out","w",stdout); #endif int n,k,i; scanf("%d%d",&n,&k); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } sort(a+1,a+1+n); if(work(k,n)==true) { printf("1\n"); sort(ans.begin(),ans.end()); for(i=0;i<ans.size();i++) { printf("%d %d\n",ans[i].first,ans[i].second); } } else { printf("0\n"); } return 0; } -
正解
- 正在改，你先别着急。
\(T3\) C. 均衡区间 \(25pts\)
-
部分分
-
测试点 \(1 \sim 2,4 \sim 6\)：模拟。
点击查看代码
int a[1000010],ans[1000010]; void work(int n) { memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++) { int minn=0x7f7f7f7f,maxx=0; for(int j=i;j<=n;j++) { minn=min(minn,a[j]); maxx=max(maxx,a[j]); if(minn!=min(a[i],a[j])&&maxx!=max(a[i],a[j])) { ans[i]++; } } } } int main() { #define Isaac #ifdef Isaac freopen("interval.in","r",stdin); freopen("interval.out","w",stdout); #endif int n,id,i; scanf("%d%d",&n,&id); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } work(n); for(i=1;i<=n;i++) { printf("%d ",ans[i]); } printf("\n"); reverse(a+1,a+1+n); work(n); reverse(ans+1,ans+1+n); for(i=1;i<=n;i++) { printf("%d ",ans[i]); } printf("\n"); return 0; } -
测试点 \(3\) ： 不横跨 \(i\) 时端点处一定同时为最值，横跨 \(i\) 时端点处一定有至少一个取到最小值，故输出 \(0\) 。
-
-
正解
- 以求解左端点为例。
- 设 \(xl_{i},nl_{i},xr_{i},nr_{i}\) 分别表示 \(i\) 左侧第一个比它大的数，左侧第一个比它小的数，右侧第一个比它大的数，右侧第一个比它小的数，单调栈预处理即可。
- 当 \(i\) 不为最值时，右端点 \(j\) 需满足 \((i,j]\) 中出现了 \(>a_{i}\) 和 \(<a_{i}\) 的数，即 \(j \ge \max(xr_{i},nr_{i})\) ；但又需要保证 \(a_{j}\) 不为最值，类似地有 \(i \le \min(xl_{j},nl_{j})\) 。
- 因空间略卡，使用扫描线加树状数组维护二维数点即可。
点击查看代码
struct BIT { int c[1000010]; int lowbit(int x) { return (x&(-x)); } void clear() { memset(c,0,sizeof(c)); } void add(int n,int x,int val) { for(int i=x;i<=n;i+=lowbit(i)) { c[i]+=val; } } int getsum(int x) { int ans=0; for(int i=x;i>=1;i-=lowbit(i)) { ans+=c[i]; } return ans; } }T; struct node { int pos,x,val,id; }q[2000010]; int a[1000010],L[1000010],R[1000010],ans[1000010],cnt; stack<int>s1,s2; bool cmp(node a,node b) { return a.pos<b.pos; } void add(int pos,int x,int val,int id) { cnt++; q[cnt].pos=pos; q[cnt].x=x; q[cnt].val=val; q[cnt].id=id; } void work(int n) { cnt=0; memset(q,0,sizeof(q)); memset(ans,0,sizeof(ans)); while(s1.empty()==0) { s1.pop(); } while(s2.empty()==0) { s2.pop(); } for(int i=1;i<=n;i++) { while(s1.empty()==0&&a[s1.top()]<=a[i]) { s1.pop(); } while(s2.empty()==0&&a[s2.top()]>=a[i]) { s2.pop(); } L[i]=min((s1.empty()==0)?s1.top():0,(s2.empty()==0)?s2.top():0); s1.push(i); s2.push(i); } while(s1.empty()==0) { s1.pop(); } while(s2.empty()==0) { s2.pop(); } for(int i=n;i>=1;i--) { while(s1.empty()==0&&a[s1.top()]<=a[i]) { s1.pop(); } while(s2.empty()==0&&a[s2.top()]>=a[i]) { s2.pop(); } R[i]=max((s1.empty()==0)?s1.top():n+1,(s2.empty()==0)?s2.top():n+1); s1.push(i); s2.push(i); if(R[i]<=n) { add(R[i]-1,i,-1,i); add(n,i,1,i); } } sort(q+1,q+1+cnt,cmp); for(int i=1,j=1;i<=cnt;i++) { for(;j<=q[i].pos;j++) { if(L[j]>=1) { T.add(n,L[j],1); } } ans[q[i].id]+=q[i].val*(T.getsum(n)-T.getsum(q[i].x-1)); } } int main() { #define Isaac #ifdef Isaac freopen("interval.in","r",stdin); freopen("interval.out","w",stdout); #endif int n,id,i; scanf("%d%d",&n,&id); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } work(n); for(i=1;i<=n;i++) { printf("%d ",ans[i]); } printf("\n"); reverse(a+1,a+1+n); work(n); reverse(ans+1,ans+1+n); for(i=1;i<=n;i++) { printf("%d ",ans[i]); } printf("\n"); return 0; }
\(T4\) D. 禁止套娃 \(10pts\)
-
部分分
- \(10pts\) ：爆搜求本质不同子序列个数。
点击查看代码
const ll p=1000000007; int a[5010],ans=0; vector<int>state,tmp; map<vector<int>,bool>s1,s2; void dfs2(int pos) { if(pos==state.size()) { if(s2.find(tmp)==s2.end()) { s2[tmp]=1; ans=(ans+1)%p; } } else { dfs2(pos+1); tmp.push_back(state[pos]); dfs2(pos+1); tmp.pop_back(); } } void dfs(int pos,int n) { if(pos==n+1) { if(s1.find(state)==s1.end()) { s2.clear(); dfs2(0); s1[state]=1; } } else { dfs(pos+1,n); state.push_back(a[pos]); dfs(pos+1,n); state.pop_back(); } } int main() { #define Isaac #ifdef Isaac freopen("nest.in","r",stdin); freopen("nest.out","w",stdout); #endif int n,i; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; } dfs(1,n); cout<<ans<<endl; return 0; } -
正解
总结
- \(T3\) 性质场上没推出来。
后记
- 下发题面和题解的 \(PDF\) 题面中的 \(\LaTeX\) 炸了。
- \(T1\) 题面 \(i,j\) 写反了。
- \(T3\) 题解 \(i \le L_{j}\) 打成了 \(i \ge L_{j}\) 。