2020牛客NOIP赛前集训营-提高组（第二场）总结&题解

文章目录

$Result$$Hyperlink$$Description$T1 GCDT2 包含T3 前缀T4 移动 $Summary$$Solutions$T1T2T3T4 $Codes$T1T2T3T4$20pts$$85pts$

$Result$

---

$Hyperlink$

https://ac.nowcoder.com/acm/contest/7607

---

$Description$

T1 GCD

设$f(x)$表示$x$除了1以外的所有因数的$gcd$，求${\sum }_{i=a}^{b}f(x)$ 数据范围：$1<a<b\le 10^7$

---

T2 包含

定义元素$b$包含于二进制集合$A$当且仅当$\exists a\in A,a\&b=b$，现给定大小为$n$的集合$A$，有$m$组询问，每次询问一个元素$b$是否包含于$A$集合 数据范围：$n,m\le 10^5,x,a_i\le 10^6$

---

T3 前缀

有$n$组询问，每次给出一个$t$，再给定一个无限长的字符串，它的循环节是$s$，试求这个串的一个最短前缀$s^{‘}$，使得$t$是$s^{‘}$的一个子序列。其中$t$的某些位置可能是 KaTeX parse error: Undefined control sequence: \* at position 1: \̲*̲，表示这个位置可以是任意字符。 数据范围：$|s|\le 10^4,t\text{的真正长度}\le 10^{10^5}$

---

T4 移动

有$n$扇门，你要从第0扇门出发，到达第$n+1$个位置，位移出一个位置需要1s 有$m$个限制，每个限制$(a,b,c)$告诉你，第$a$扇门将在$[b,c]$时段中关闭 问到达$n+1$的最小时间

数据范围：$n,m\le 10^5$

---

$Summary$

T1看到题目应该是要$O(n)$的复杂度做出来的，然后考虑到$gcd$与线性筛有关，就改一改线性筛就切了 T2的话做过上周刚做过一个类似的题，这题也是一样开个桶解决即可 T3题目谜语人，pass了 T4感觉很可做，先写出了一个跟题解一样的$dp$，设$f_{i,j}$表示到离散化后的第$i$个时刻，能否到达第$j$个位置，然后状态写炸了就去写了贪心 贪心大样例都过不了，害 然后就刚T3，我自己认为我是能过30%的数据的，但不知为何有锅QwQ

最后就只有100+100+0+35=235了

---

$Solutions$

T1

容易发现质数的$f(x)=x$ 只含有一个质因子的数的$f(x)$等于它的最小质因子 其它数的$f(x)=1$【1除外】 容易发现这些都可以在线性筛中做出来，时间复杂度$O(max\{a,b\})$

---

T2

设$t_i$表示$i$这个元素是否属于$A$，倒序扫描数组，将$i$去除每一位的结果重新放入桶中 然后直接扫描即可，时间复杂度$O(n+m+a_i\log a_i)$

---

T3

大模拟题 记录$tot$表示各个字母每次出现的次数 记录每个字母第几次出现在哪里

注意%的时候要边乘边模，类似于高精度 不然会炸

时间复杂度：$O(26|s|+n|t|)$

---

T4

$85pts$的贪心 将每个点的限制压入一个$vector$，设$t$表示到达$i+1$的最短时间，扫描限制转移即可 时间复杂度：$O(n+m)$ $100pts$ $dp$

---

$Codes$

T1

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define MAXN 10000010 using namespace std;LL a,b,s[MAXN]; int prime[MAXN],m,vis[MAXN],tot; inline LL read() { char c;LL d=1,f=0; while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } inline void prework(LL N) { for(register int i=2;i<=N;i++) { if(vis[i]==0) { s[i]=vis[i]=i;prime[++m]=i; } for(register int j=1;j<=m&&prime[j]*i<=N;j++) { if(prime[j]>vis[i]) break; vis[i*prime[j]]=prime[j]; if(!s[i*prime[j]]) //没有计算 { if(s[i]==1||s[prime[j]]==1) {s[i*prime[j]]=1;continue;}//如果转移的质因子已经互质了，那么乘起来显然还是会互质 if(vis[i]==vis[prime[j]]) s[i*prime[j]]=vis[i];//如果是同一质因子，可以转移 else s[i*prime[j]]=1;//否则，说明它出现了别的质因子，则赋值为1 } } } for(register int i=1;i<=N;i++) s[i]+=s[i-1];//求前缀和 return; } signed main() { a=read();b=read(); prework(max(a,b)); printf("%lld",s[b]-s[a-1]); }

T2

最短代码QwQ

#include<cstdio> int n,m,a; bool t[1<<20]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a),t[a]=true; for(int i=(1<<20)-1;i;i--) if(t[i]) for(int j=0;j<20;j++) if((i>>j)&1) t[i^(1<<j)]=true; for(int i=1;i<=m;i++) scanf("%d",&a),puts(t[a]?"yes":"no"); }

T3

#include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define mod 998244353 using namespace std;char s[10010],st[100010],ybd; int len,n,appear[26+150][10010]; LL xh,need,tot[26+150],qz[10010][26+150],once,ans,last; inline LL read() { char c;LL d=1,f=0; while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } inline LL ksm(LL x,LL y) { LL res=1; for(;y;y>>=1,(x*=x)%=mod) if(y&1) (res*=x)%=mod; return res; } inline bool tp() { for(register int i=1;i<=strlen(st+1);i++) if(st[i]!='*'&&!isdigit(st[i])&&tot[st[i]]==0) return true; return false; } signed main() { scanf("%s",s+1);len=strlen(s+1);s[len+1]=s[1]; for(register int i=1;i<=len;i++) { tot[s[i]]++; memcpy(qz[i],qz[i-1],sizeof(qz[i-1])); appear[s[i]][++appear[s[i]][0]]=i; qz[i][s[i]]++; } n=read(); while(n--) { scanf("%s",st+1); if(tp()) {puts("-1");continue;} ans=0;last=1; for(register int i=1;i<=strlen(st+1);i++) { ybd=st[i]; once=st[i]=='*'?len:tot[st[i]]; xh=0;need=0; if(isdigit(st[i+1])) { while(isdigit(st[i+1])) { xh=((xh<<3)+(xh<<1))%mod; need=((need<<3)+(need<<1)+st[++i]-48)%mod; (xh+=need/once)%=mod;need%=once; } } else need=1; if(ybd=='*') need+=once-(len-last+1); else need+=once-(tot[ybd]-qz[last-1][ybd]); if(need>once) need-=once,xh++; if(xh==0) xh=mod; if(need==0) need+=once,xh--; if(ybd!='*') { ans+=appear[ybd][need]-last+1; last=appear[ybd][need]%len+1; } else { ans+=need-last+1; last=need%len+1; } (ans+=len*xh%mod)%=mod; } printf("%lld\n",ans); } }

T4

$20pts$

#include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std;int n,m; LL now,ans; struct node{int id;LL L,R;}p[100010]; inline bool cmp(node x,node y){return x.id<y.id;} inline LL read() { char c;LL d=1,f=0; while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } signed main() { n=read();m=read(); for(register int i=1;i<=m;i++) p[i].id=read(),p[i].L=read(),p[i].R=read(); sort(p+1,p+1+m,cmp); for(register int i=1;i<=m;i++) { if(p[i].id>now) { ans+=p[i].id-1-now; now=p[i].id-1; } if(ans+1<p[i].L) { ans++; now=p[i].id; } else { if(ans>p[i].R) { ans++; now=p[i].id; } else { ans=p[i].R+1; now=p[i].id; } } } if(now<n+1) ans+=(n+1)-now; printf("%lld",ans); }

$85pts$

#include<cctype> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #define LL long long using namespace std;int n,m,a,b,c,ti,t; vector<int>L[200010],R[200010]; inline LL read() { char c;LL d=1,f=0; while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } signed main() { n=read();m=read(); for(register int i=1;i<=m;i++) a=read(),b=read(),c=read(),L[a].push_back(b),R[a].push_back(c); t=1; for(register int i=1;i<=n;i++) { ti=t; for(register int j=0;j<L[i].size();j++) if(t>=L[i][j]&&t<=R[i][j]) t=R[i][j]+1; if(t==ti) t++; } printf("%d",t+1); }