多校A层冲刺NOIP2024模拟赛04
\(T1\) A. 02表示法 \(0pts/100pts\)
-
递归模拟即可，二进制分解时需要写高精除低精。
点击查看代码
int r[810],t[810]; char s[810],id[810][10]; string a; int chu(char s[]) { int n=strlen(s+1),x=0,tmp; for(int i=1;i<=n;i++) { t[i]=s[n-i+1]-'0'; } r[0]=0; while(n>=1) { r[0]++; r[r[0]]=t[1]%2; x=0; for(int i=n;i>=1;i--) { tmp=(t[i]+x*10)%2; t[i]=(t[i]+x*10)/2; x=tmp; } while(t[n]==0&&n>=1) { n--; } } return r[0]; } void divide(char s[]) { int tmp[710],n=chu(s),flag=0; for(int i=1;i<=n;i++) { tmp[i]=r[i]; } for(int i=n;i>=3;i--) { if(tmp[i]==1) { if(flag==1) { cout<<"+"; } cout<<"2("; divide(id[i-1]); cout<<")"; flag=1; } } for(int i=2;i>=1;i--) { if(tmp[i]==1) { if(flag==1) { cout<<"+"; } if(i==2) { cout<<"2"; } else { cout<<"2(0)"; } flag=1; } } } int main() { freopen("power.in","r",stdin);//freopen("pow.in","r",stdin); freopen("power.out","w",stdout);//freopen("pow.out","w",stdout); for(int i=0;i<=800;i++) { a=to_string(i); for(int j=0;j<a.size();j++) { id[i][j+1]=a[j]; } } cin>>(s+1); divide(s); fclose(stdin); fclose(stdout); return 0; }
\(T2\) B. 子串的子串 \(100pts/100pts\)
-
弱化版： luogu P2408 不同子串个数 | SP694 DISUBSTR - Distinct Substrings | SP705 SUBST1 - New Distinct Substrings
-
部分分
- \(70 \sim 100 pts\) ：对于每一组询问暴力重建后缀数组，时间复杂度为 \(O(nq \log n)\) 或 \(O(nq)\) 。
-
点击查看代码
int sa[6010],rk[6010],oldrk[6010],id[6010],cnt[6010],key[6010],height[6010]; char s[6010],t[6010]; int val(char x) { return (int)x; } void counting_sort(int n,int m) { for(int i=1;i<=m;i++) { cnt[i]=0; } for(int i=1;i<=n;i++) { cnt[key[i]]++; } for(int i=1;i<=m;i++) { cnt[i]+=cnt[i-1]; } for(int i=n;i>=1;i--) { sa[cnt[key[i]]]=id[i]; cnt[key[i]]--; } } void init(char s[],int len) { int m=130,tot=0,num=0; for(int i=1;i<=len;i++) { rk[i]=val(s[i]); id[i]=i; key[i]=rk[id[i]]; } counting_sort(len,m); for(int w=1;tot!=len;w<<=1,m=tot) { num=0; for(int i=len;i>=len-w+1;i--) { num++; id[num]=i; } for(int i=1;i<=len;i++) { if(sa[i]>w) { num++; id[num]=sa[i]-w; } } for(int i=1;i<=len;i++) { key[i]=rk[id[i]]; } counting_sort(len,m); for(int i=1;i<=len;i++) { oldrk[i]=rk[i]; } tot=0; for(int i=1;i<=len;i++) { tot+=(oldrk[sa[i]]!=oldrk[sa[i-1]]||oldrk[sa[i]+w]!=oldrk[sa[i-1]+w]); rk[sa[i]]=tot; } } for(int i=1,j=0;i<=len;i++) { j-=(j>=1); while(s[i+j]==s[sa[rk[i]-1]+j]) { j++; } height[rk[i]]=j; } } ll ask(int l,int r) { ll n=r-l+1,ans=n*(n+1)/2; memset(t,0,sizeof(t)); for(int i=l;i<=r;i++) { t[i-l+1]=s[i]; } init(t,n); for(int i=1;i<=r-l+1;i++) { ans-=height[i]; } return ans; } int main() { freopen("substring.in","r",stdin); freopen("substring.out","w",stdout); int n,q,l,r,i; scanf("%d%d%s",&n,&q,s+1); for(i=1;i<=q;i++) { scanf("%d%d",&l,&r); printf("%lld\n",ask(l,r)); } fclose(stdin); fclose(stdout); return 0; } -
\(hack\) 倍增进行后缀排序的数据生成器，生成的数据本地跑了 \(4s\) 。
点击查看代码
int main() { int n=3000,q=20000; cout<<n<<" "<<q<<endl; for(int i=1;i<=n;i++) { cout<<"a"; } cout<<endl; for(int i=1;i<=q;i++) { cout<<1<<" "<<n<<endl; } return 0; }
-
- \(70 \sim 100 pts\) ：对于每一组询问暴力重建后缀数组，时间复杂度为 \(O(nq \log n)\) 或 \(O(nq)\) 。
-
正解
- 观察到 \(n\) 较小，考虑预处理出所有区间的答案，然后 \(O(1)\) 处理询问。
- 设 \(ans_{l,r}\) 表示 \([l \sim r]\) 内本质不同的子串个数。不妨先处理出 \(ans\) 的差分数组再进行二维前缀和处理。
- 类似区间 \(DP\) 的写法，枚举 \(s_{l \sim r}\) 这一子串，并得到它的哈希值。首先有 \(ans_{l,r}++\) ，又因为这一子串对上一次出现位置 \([l',r']\) 到 \([l,r]\) 的区间都有贡献，所以让 \(ans_{l',r'}--\) 。
- 挑个好点的哈希模数和进制，数据略卡（尽管 \(std\) 写的是自然溢出）。
- 在使用
unordered_map后时间复杂度为 \(O(n^{2}+q)\) 。
点击查看代码
const ull base=13331; ull a[3010],jc[3010]; int ans[3010][3010],w[3010][3010]; char s[3010]; unordered_map<ull,int>last; void sx_hash(char s[],ull a[],int len) { for(int i=0;i<=len;i++) { a[i]=(i==0)?0:(a[i-1]*base+s[i]); } } ull ask_hash(int l,int r) { return a[r]-a[l-1]*jc[r-l+1]; } int main() { freopen("substring.in","r",stdin); freopen("substring.out","w",stdout); int n,q,l,r,i,len; cin>>n>>q>>(s+1); for(i=0;i<=n;i++) { jc[i]=(i==0)?1:jc[i-1]*base; } sx_hash(s,a,n); for(len=1;len<=n;len++) { last.clear(); for(l=1,r=l+len-1;r<=n;l++,r++) { ans[last[ask_hash(l,r)]][r]--; ans[l][r]++; last[ask_hash(l,r)]=l; } } for(l=n;l>=1;l--) { for(r=l;r<=n;r++) { ans[l][r]+=ans[l+1][r]+ans[l][r-1]-ans[l+1][r-1]; } } for(i=1;i<=q;i++) { cin>>l>>r; cout<<ans[l][r]<<endl; } fclose(stdin); fclose(stdout); return 0; }
\(T3\) C. 魔法咒语 \(20pts/20pts\)
-
部分分
-
\(20pts\) ：模拟，时间复杂度为 \(O(n^{2}|s|^{3})\) 。
点击查看代码
string s[10010],pre,suf,tmp; unordered_map<string,bool>vis; int main() { freopen("magic.in","r",stdin); freopen("magic.out","w",stdout); int n,i,j,k,h; cin>>n; for(i=1;i<=n;i++) { cin>>s[i]; } for(i=1;i<=n;i++) { pre.clear(); for(j=0;j<s[i].size();j++) { pre+=s[i][j]; for(k=1;k<=n;k++) { suf.clear(); for(h=s[k].size()-1;h>=0;h--) { suf+=s[k][h]; tmp=pre; reverse(suf.begin(),suf.end()); tmp+=suf; vis[tmp]=1; reverse(suf.begin(),suf.end()); } } } } cout<<vis.size()<<endl; fclose(stdin); fclose(stdout); return 0; } -
\(30pts\) ：枚举所有的分割情况进行哈希判断，时间复杂度为 \(O(n^{2}|s|^{2})\) 。
-
-
正解
- 考虑将所有单词顺序插入第一棵 \(Trie\) 树上，倒序插入第二棵 \(Trie\) 树上。
- 一个特别假的做法是在第一棵 \(Trie\) 树上访问的一个节点 \(x\) 时，若它的子节点中没有某个字母（假设为 \(c\) ），那么就加上第二棵 \(Trie\) 树的大小。
- 问题在于可能会重复统计。
- 解决重复统计的一个比较假的做法是在第一棵 \(Trie\) 树上访问的一个节点 \(x\) 时，若它的子节点中没有某个字母（假设为 \(c\) ），那么就加上以 \(c\) 开头的不同后缀数量。
- 问题在于若存在一个以 \(c\) 结尾的单词，那么即使 \(x\) 的子节点中包含 \(c\) 也能拼出这个前缀
-c，而对于上述做法统计不到这个贡献。 - 例如
abc,dc无法在上述做法通过ab+c得到的是abc。
- 问题在于若存在一个以 \(c\) 结尾的单词，那么即使 \(x\) 的子节点中包含 \(c\) 也能拼出这个前缀
- 手动记录下上述贡献（不一定来自一个单词内部）即可。需要特判 \(|s|=1\) 。
点击查看代码
ll ed[30],flag[30]; char s[50]; ll val(char x) { return x-'a'+1; } struct Trie { ll son[400010][30],cnt[30],rt_sum=0; void insert(char s[],ll len) { ll x=0; for(ll i=1;i<=len;i++) { if(son[x][val(s[i])]==0) { rt_sum++; son[x][val(s[i])]=rt_sum; cnt[val(s[i])]++; } x=son[x][val(s[i])]; } } }T[2]; int main() { freopen("magic.in","r",stdin); freopen("magic.out","w",stdout); ll n,len,ans=0,i,j; cin>>n; for(i=1;i<=n;i++) { cin>>(s+1); len=strlen(s+1); T[0].insert(s,len); ed[val(s[len])]=1; if(len==1) { ans+=(flag[val(s[len])]==0); flag[val(s[len])]=1; } reverse(s+1,s+1+len); T[1].insert(s,len); } for(i=1;i<=T[0].rt_sum;i++) { for(j=1;j<=26;j++) { if(T[0].son[i][j]==0) { ans+=T[1].cnt[j]; } else { ans+=ed[j]; } } } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
\(T4\) D. 表达式 \(25pts/25pts\)
-
部分分
-
测试点 \(1 \sim 3\) ：模拟，在使用扩展欧拉定理优化后时间复杂度为 \(O(nm \log \sqrt{p})\) ，实测可以额外通过测试点 \(14,17\) 。
点击查看代码
int a[200010],b[200010][2]; char op[200010],s[200010]; int get_phi(int n) { int ans=n; for(int i=2;i<=sqrt(n);i++) { if(n%i==0) { ans=ans/i*(i-1); while(n%i==0) { n/=i; } } } if(n>1) { ans=ans/n*(n-1); } return ans; } int gcd(int a,int b) { return b?gcd(b,a%b):a; } ll qpow(ll a,int b,int p) { ll ans=1; while(b) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } int qadd(int a,int b,int p) { return a+b>=p?a+b-p:a+b; } void read(int pos,int p,int phi) { scanf("%s",s+1); int n=strlen(s+1); op[pos]=s[1]; a[pos]=0; if(op[pos]!='^') { for(int i=2;i<=n;i++) { a[pos]=qadd(a[pos]*10%p,s[i]-'0',p); } } else { for(int i=2;i<=n;i++) { a[pos]=(a[pos]*10+s[i]-'0'); } b[pos][0]=(a[pos]>=phi)?a[pos]%phi+phi:a[pos]; b[pos][1]=a[pos]%phi; } } int main() { freopen("expr.in","r",stdin); freopen("expr.out","w",stdout); int t,n,m,p,phi,pd,pos,last,flag,i,j; ll x; scanf("%d%d%d%d",&t,&n,&m,&p); phi=get_phi(p); for(i=1;i<=n;i++) { read(i,p,phi); } for(i=1;i<=m;i++) { scanf("%d",&pd); if(pd==1) { scanf("%lld",&x); last=flag=0; for(j=1;j<=n;j++) { if(op[j]=='+') { x=qadd(x,a[j],p); last=0; } if(op[j]=='*') { x=(x*a[j])%p; last=0; } if(op[j]=='^') { if(last==0) { flag=(gcd(x,p)==1); } x=qpow(x,b[j][flag],p); last=1; } } printf("%lld\n",x); } else { scanf("%d",&pos); read(pos,p,phi); } } fclose(stdin); fclose(stdout); return 0; }
-
-
正解
- 观察到只有 \(1 \sim 3\) 的 \(p\) 比较大，而其他数据点的 \(p \le 46189\) ，且多为合数（例如 \(\begin{cases} 50=2 \times 5^{2} \\ 100=2^{2} \times 5^{2} \\ 10800=2^{4} \times 3^{3} \times 5^{2} \\ 12673=19 \times 23 \times 29 \\ 46189=11 \times 13 \times 17 \times 19 \\ 1001=7 \times 11 \times 13 \\ 29393=7 \times 13 \times 17 \times 19 \end{cases}\) ），考虑面向数据点分治，以下只讲解测试点 \(4 \sim 20\) 。
- 考虑线段树的每个节点 \([l,r]\) 维护一个 \(\{ val \}\) ，且 \(val_{x}\) 表示将 \(x\) 放在 \([l,r]\) 的表达式开头最终能得到的结果。
- 接着充分利用 \(p\) 多为合数的性质，将 \(p\) 质因数分解后线段树求出对 \(p_{i}^{c_{i}}\) 取模后的结果，使用 \(CRT\) 合并即可。
点击查看代码
总结
- \(T1\) 浪费的时间太多了（写了约 \(2h\) ），导致没有时间写 \(T4\) 的测试点 \(10\) 了；没有注意到 accoders NOI 和学校 \(OJ\) 的文件 \(IO\) 不一样，挂了 \(100pts\) 。
- \(T4\) 以为对于大部分 \(p\) 都有通用性做法，所以没想到数据点分治；但看到后面测试点的指数远大于 \(p\) 就一眼想到扩展欧拉定理优化了，挺好。
后记
- \(7:05\) 去吃早饭时 accoders NOI 上开始时间还是 \(7:30\) ，吃完饭回来后就发现改成了 \(7:15\) ，而学校 \(OJ\) 还是 \(7:30\) 开始，遂“被迫”提前开题。
- \(T4\) 数据范围没写在下发的题面 PDF 里，而是单独作为 jpg 在学校 \(OJ\) 下发了二次而且不一样（第一次的直接提示了 \(\sigma(p)\) 很小，但因为是刚开题导致没有细想）。