20241023 模拟赛（GCD，包含，前缀，移动）
看题戳这里
总结
20min 自习。
上来 30min 先把 t1 写了。
然后 t2 没看明白，先打了个暴力？然后发现值域很离谱，dfs就行了。
t3 t4看了一眼就跑路了。
解析
A. GCD
难度：黄
注意到只有当 \(n=\) 素数 \(p\) 的正整数次幂时，有 \(f(n)=p\)，
其他情况都是 \(f(n)=1\)。
所以用欧拉筛筛一遍的同时求答案就行了。
#include<bits/stdc++.h>
#define mxn 10000010
#define ll long long
#define pb push_back
using namespace std;
bool isp[mxn],vis[mxn];
ll a,b,cnt;
ll ans;
vector<ll> prime;
void euler(){
isp[1]=1;
for(int i=2;i<=b;i++){
if(!isp[i]){
prime.pb(i);
for(ll j=i;j<=b;j*=i)
if(j>=a)ans+=i,vis[j]=1;
cnt++;
}
else if(i>=a&&!vis[i])ans++;
for(int j=0;j<cnt&&i*prime[j]<=b;j++){
isp[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
int main(){
freopen("gcd.in","r",stdin);
freopen("gcd.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>a>>b;
euler();
cout<<ans;
return 0;
}
B. 包含
难度：黄
一开始脑子抽了，居然想到了 01trie。
然后发现值域只到 \(10^6\)，所以暴力 \(dfs\) 预处理，然后 \(O(1)\) 查询就行了。
#include<bits/stdc++.h>
#define ll long long
#define mxn 100010
using namespace std;
int n,m,mp[mxn*10];
int a[mxn],b;
void dfs(int x){
if(mp[x])return;
mp[x]=1;
for(int i=0;i<=20;i++)
if((x>>i)&1)
dfs(x^(1<<i));
return;
}
int main(){
freopen("include.in","r",stdin);
freopen("include.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
dfs(a[i]);
}
for(int i=1;i<=m;i++){
int x;cin>>x;
if(mp[x])cout<<"yes\n";
else cout<<"no\n";
}
return 0;
}
C. 前缀
难度：蓝
我们发现这玩意相当于一个序列自动机。
设 \(nxt[i][j][k]\) 为第 \(i\) 位上后面 \(2^k\) 个字符 \(j\) 的位置。
而 \(nxtlen[i][j][k]\) 为当前位置到后 \(2^k\) 个字符 \(j\) 的长度。
\(O(n\log n)\) 倍增预处理一下 \(nxt\) 和 \(nxtlen\) 就行了。
然后对于带数字的，还要搞一个高精除低精，处理出商和余数。
注意若无余数，最后一轮是不能跑满的。
#include<bits/stdc++.h>
#define mxm 100010
#define mxn 10010
#define mod 998244353
#define ll long long
using namespace std;
ll T,n,len,cnt[30];
ll first[mxn],last[mxn],nxt[mxn][30][20];
ll nxtlen[mxn][30][20];
char s[mxn],t[mxm];
int Int(char c){
if(c=='*')return 26;
else return c-'a';
}
void init(){
memset(first,-1,sizeof(first));
memset(last,-1,sizeof(last));
for(int i=1;i<=len;i++){
cnt[Int(s[i])]++,cnt[26]++;
if(first[Int(s[i])]==-1)
first[Int(s[i])]=i;
}
for(int i=0;i<=26;i++){
last[i]=first[i];
nxt[0][i][0]=first[i];
if(first[i]!=-1)
nxtlen[0][i][0]=first[i];
}
nxt[0][26][0]=1,nxtlen[0][26][0]=1;
for(int i=len;i;i--){
for(int j=0;j<=26;j++)
nxt[i][j][0]=last[j];
nxt[i][26][0]=(i==len)?1:i+1;
last[Int(s[i])]=i;
for(int j=0;j<=26;j++)
if(cnt[j])
nxtlen[i][j][0]=nxt[i][j][0]-i+len*(nxt[i][j][0]<=i);
}
for(int i=1;i<16;i++)
for(int j=0;j<=len;j++)
for(int k=0;k<=26;k++)
nxt[j][k][i]=nxt[nxt[j][k][i-1]][k][i-1],
nxtlen[j][k][i]=(nxtlen[j][k][i-1]+nxtlen[nxt[j][k][i-1]][k][i-1])%mod;
}
ll solve(){
ll l=1,r=1,ret=0,pos=0;
while(l<=strlen(t+1)){
r++;
while(t[r]>='0'&&t[r]<='9')r++;
if(!cnt[Int(t[l])])return -1;
if(r-l==1){
ret=(ret+nxtlen[pos][Int(t[l])][0])%mod;
pos=nxt[pos][Int(t[l])][0];
}
else{
ll res=0,less=0;
for(int i=l+1;i<r;i++){
res=(res*10+(less*10+t[i]-'0')/cnt[Int(t[l])])%mod;
less=(less*10+t[i]-'0')%cnt[Int(t[l])];
}
if(!less)
res=(res+(mod-1))%mod,less=cnt[Int(t[l])];
ret=(ret+res*len)%mod;
ll bit=0;
while(less){
if(less&1){
ret=(ret+nxtlen[pos][Int(t[l])][bit])%mod;
pos=nxt[pos][Int(t[l])][bit];
}
bit++,less>>=1;
}
}
l=r;
}
return ret;
}
int main(){
freopen("pre.in","r",stdin);
freopen("pre.out","w",stdout);
cin>>s+1>>T;
len=strlen(s+1);
init();
while(T--){
cin>>t+1;
cout<<solve()<<'\n';
}
return 0;
}
D. 移动
难度：蓝
机房大佬随手贪心成功拿到85pts。（数据真水啊）
考虑用最短路的思想。
首先把能通过闸门的时间段存起来标号（就是离散化啦），然后设 \(dp_i\) 为到达第 \(i\) 个时间段内的最快用时。
将（闸门的标号，时间段的标号，时间）放到一个结构体，然后每次向两边更新新的状态放到优先队列里，输出 \(dp_{id_{n+1}}\) 就行了。
具体看代码。
#include<bits/stdc++.h>
#define ll int
#define pb push_back
#define mp make_pair
#define pll pair<int,int>
#define mxn 200010
using namespace std;
ll n,m,idsum[mxn],dp[mxn];
vector<pll> t[mxn],tmp;
struct node{
ll id,num,tim;
};
bool operator<(node &x,node &y){
return x.tim<y.tim;
}
bool operator>(node x,node y){
return y.tim>x.tim;
}
priority_queue<node,vector<node>,greater<node> > q;
void init(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
t[a].pb(mp(b,c));
}
t[0].pb(mp(0,2e9)),t[n+1].pb(mp(0,2e9));
idsum[1]=1;
for(int i=1;i<=n;i++){
sort(t[i].begin(),t[i].end());
ll l=-1;
tmp.clear();
for(int j=0;j<t[i].size();j++){
pll v=t[i][j];
if(v.first>l+1)
tmp.pb(mp(l+1,v.first-1));
l=max(l,v.second);
}
tmp.pb(mp(l+1,2e9));
t[i]=tmp;
idsum[i+1]=idsum[i]+t[i].size();
}
memset(dp,0x3f,sizeof(dp));
return;
}
void qush(node u,int pos){
if(pos<0||pos>n+1)return;
ll p=t[u.num][u.id-idsum[u.num]].second;
ll rnk=lower_bound(t[pos].begin(),t[pos].end(),pair<ll,ll>(u.tim+1,0))-t[pos].begin()-1;
if(t[pos][rnk].second>=u.tim+1){
if(dp[idsum[pos]+rnk]>u.tim+1){
dp[idsum[pos]+rnk]=u.tim+1;
q.push(node{idsum[pos]+rnk,pos,u.tim+1});
}
}
rnk++;
while(rnk<t[pos].size()&&t[pos][rnk].first<=p+1){
if(dp[idsum[pos]+rnk]>t[pos][rnk].first){
dp[idsum[pos]+rnk]=t[pos][rnk].first;
q.push(node{idsum[pos]+rnk,pos,t[pos][rnk].first});
}
rnk++;
}
return;
}
void solve(){
dp[0]=0;
q.push(node{0,0,0});
while(!q.empty()){
node u=q.top();q.pop();
if(u.tim>dp[u.id])continue;
qush(u,u.num+1),qush(u,u.num-1);
}
}
int main(){
freopen("move.in","r",stdin);
freopen("move.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
init();
solve();
cout<<dp[idsum[n+1]];
return 0;
}