偶然看这一场的题目，忽然很有感觉，于是写了一下
A
题面
考虑每一位可以单独分开考虑
考虑单独的一位，每次要选 \(m\) 个位置，可能产生贡献的位置就是这位为 1 的数，设数量为 \(x\)，则 \(m|x\)
最后显然合法的 \(m\) 满足 \(m| \gcd_{i=0}^{29} M_i\)
记得特判全为 \(0\) 的情况
Code
#include<bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
inline int read(){
int k=1,x=0;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') k=-1; ch=getchar();}
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();
return k*x;
}
inline int cmin(reg int x,reg int y){return x<y?x:y;}
inline int cmax(reg int x,reg int y){return x>y?x:y;}
const int N=2e5+10,INF=1e18;
int n,a[N];
inline int gcd(reg int x,reg int y){return y==0?x:gcd(y,x%y);}
inline bool check(){for (reg int i=1;i<=n;i++) if (a[i]) return false; return true;}
signed main(){reg int _=read(); while (_--){
n=read();for (reg int i=1;i<=n;i++) a[i]=read();
if (check()){for (reg int i=1;i<=n;i++) printf("%lld ",i);puts("");continue;}
reg int d=-1;
for (reg int t=0;t<=30;t++){
reg int cnt=0;
for (reg int i=1;i<=n;i++) if (a[i]>>t&1) cnt++;
if (d<0) d=cnt; else d=gcd(d,cnt);
}
for (reg int i=1;i<=d;i++) if (d%i==0) printf("%lld ",i); puts("");
}
return 0;
}
B
题面
一个直接的想法是建图跑最短路
考虑没有"下滑 \(b_i\)" 的限制应该怎么做，可以直接线段树优化建图。
考虑加入这个限制，对 \([0,n]\) 建立一个虚点，每个 \(i\) 和对应的虚点区间 \([i-a_i,i]\) 连边，然后再由虚点的 \(i\) 连向 \(i-b_i\)
使用 01bfs 优化复杂度。
Code
#include<bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
inline int read(){
int k=1,x=0;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') k=-1; ch=getchar();}
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();
return k*x;
}
inline int cmin(reg int x,reg int y){return x<y?x:y;}
inline int cmax(reg int x,reg int y){return x>y?x:y;}
const int N=(4e5+10)*5,INF=1e18,mod=998244353;
int n,a[N],b[N],idx,id[N],vis[N],pre[N],dis[N];
#define mp make_pair
vector<pair<int,int> > G[N];
inline void add(reg int u,reg int v,reg int w){G[u].push_back(mp(v,w));}
inline void build(reg int p,reg int l,reg int r){
if (l==r) return (void)(id[p]=l+n+1);id[p]=++idx; reg int mid=l+r>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r); add(id[p],id[p<<1],0),add(id[p],id[p<<1|1],0);
}
inline void modify(reg int p,reg int l,reg int r,reg int L,reg int R,reg int node){
if (L<=l&&r<=R) return add(node,id[p],1); reg int mid=l+r>>1;
if (L<=mid) modify(p<<1,l,mid,L,R,node); if (R>mid) modify(p<<1|1,mid+1,r,L,R,node);
}deque<int> q;
signed main(){
n=read(); idx=2*n+1;
for (reg int i=1;i<=n;i++) a[i]=read();for (reg int i=1;i<=n;i++) b[i]=read();
for (reg int i=0;i<=n;i++) add(i+n+1,i+b[i],0); build(1,0,n);
for (reg int i=1;i<=n;i++) modify(1,0,n,i-a[i],i,i);
memset(dis,0x3f,sizeof(dis)); dis[n]=0; q.push_back(n);
while(!q.empty()){
reg int u=q.front(); q.pop_front();
if (vis[u]) continue; vis[u]=1;
for (auto it:G[u]) if (dis[it.first]>dis[u]+it.second){ reg int v=it.first;
dis[v]=dis[u]+it.second;
if (!vis[v]){if (it.second) q.push_back(v); else q.push_front(v); pre[v]=u;}
}
}
if (dis[0]>=INF) return !printf("-1");
printf("%lld\n",dis[0]);
vector<int> path; reg int now=0;
while(now!=n){
if (n+1<=now&&now<=2*n+1) path.push_back(now-n-1);
now=pre[now];
}
reverse(path.begin(), path.end());
for (auto x:path) printf("%lld ",x);
return 0;
}