又被打爆...
T1
\(n\leq 10^3,q\leq 3\times 10^5\)
签到。竖着和斜着差分一下，最后从左往右扫一遍做完。
T2
做不出来这个显得很弱智...其实可以将整个游戏看成二叉树，然后每次的分左右儿子取决于 \(b_i\) 的倍数与否，接下来每一层的取值就看奇偶是 \(\text{Alice}\) 还是 \(\text{Bob}\) 分别取 \(\min/\max\)。然后我就止步于此了...但最抽象的是，我实现出的二叉树直接模拟了在每一层 \(n\) 个点选取，相当于搜索，于是复杂度变成了 \(O(2^mn)\)。但是实际上只需要类似字典树，将每个 \(a_i\) 插入即可，这样复杂度是 \(O(nm)\) 的。
考虑优化之：结论就是他不可能递归超过 \(2\log n\) 次，那为什么对呢？考虑如果先手每次都选择集合大小较小的一边，那么至多 \(\log n\) 次后答案就会变成 \(0\)，考虑两个人轮流操作，那么至多 \(2\log n\) 次，如果有更多回合，那么答案不会大于 \(0\)，同样不会小于 \(0\)（因为后手同样可以采取这个策略），因此答案就是 \(0\)。这样时间复杂度就变成 \(O(n\log n)\)。
Code
#include<bits/stdc++.h>
#define il inline
#define rint register int
#define int long long
using namespace std;
const int N=2e5+10,INF=2147483647;
char *p1,*p2,buf[N];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
#define gc() getchar()
il int rd(){
int x=0,f=1;
char ch=gc();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=gc();
return x*f;
}
int n,m;
int a[N],b[N];
int tot,rt;
int ls[N<<5],rs[N<<5],sum[N<<5];
void ins(int &p,int dep,int val){
if(!p)p=++tot;
if(dep>m){sum[p]+=val;return;}
ins((val%b[dep])?ls[p]:rs[p],dep+1,val);
}
int query(int p,int dep){
if(!p)return 0;
if(dep>m)return sum[p];
int L=query(ls[p],dep+1),R=query(rs[p],dep+1);
return (dep&1)?min(L,R):max(L,R);
}
void Main(){
n=rd(),m=rd();
if(m>30){cout<<0;return;}
for(int i=1; i<=n; ++i)a[i]=rd();
for(int i=1; i<=m; ++i)b[i]=rd();
for(int i=1; i<=n; ++i)ins(rt,1,a[i]);
cout<<query(rt,1);
}
signed main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int T=1;
while(T--)Main();
return 0;
}
T3
\(n\leq 10^5,a_i\leq 10^7\)
这题挂成狗显得我很菜...怎么挂的呢？oh，妈妈我 \(\text{Tarjan}\) 写挂啦 ?
这题直接连边显然不可行，那我们不妨将其转化成每个同时和约数的虚点连接，这样同样有连通性。
于是这样建图复杂度就变为了 \(O(n\log^2 n)\)。
然后来考虑图中删除一个点对连通块的影响，显然只有割点才有影响，我们跑 \(\text{Tarjan}\) 即可。
Code
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define re register
using namespace std;
il int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
const int N=4e6+10,M=1e7+10;
int n;
int a[N];
int pr[M],pi[M],tot_pr,tot;
bool vis[M];
int id[N];
void pre(){
for(int i=2; i<M; ++i){
if(!vis[i]){
pr[++tot_pr]=i;
pi[i]=i;
}
for(int j=1; j<=tot_pr&&pr[j]*i<M; ++j){
vis[i*pr[j]]=1;
pi[i*pr[j]]=pr[j];
if(i%pr[j]==0)break;
}
}
tot=0;
for(int i=2; i<M; ++i)if(vis[i]&&!vis[i/pi[i]])id[i]=++tot;
}
struct Edge{
int to,nxt;
}e[M];
int tot_e,head[N];
void add_e(int x,int y){
e[++tot_e]={y,head[x]};
head[x]=tot_e;
}
bool v[N];
int S;
void dfs(int x){
v[x]=1;
if(x<=n)++S;
for(int i=head[x]; i; i=e[i].nxt){
int y=e[i].to;
if(v[y])continue;
dfs(y);
}
}
int dfn[N],low[N],cnt,rt,siz[N],top,st[N],Ans;
void Tarjan(int x){
dfn[x]=low[x]=++cnt;
st[++top]=x;siz[x]=0;
int g=0,ans=0;
for(int i=head[x]; i; i=e[i].nxt){
int y=e[i].to;
if(!dfn[y]){
Tarjan(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
++g;
int z,s=0;
do{
z=st[top--];
siz[x]+=siz[z];s+=siz[z];
}while(z!=y);
ans=max(ans,s);
}
}else{
low[x]=min(low[x],dfn[y]);
}
}
if(x<=n){
++siz[x];
if(g>1&&x==rt||g)Ans=min(Ans,max(ans,S-siz[x]));
}
}
void init(){
tot_e=0;
memset(head,0,sizeof(head));
memset(v,0,sizeof(v));
cnt=top=0;
memset(dfn,0,sizeof(dfn));
}
void Main(){
n=read();
for(int i=1; i<=n; ++i)a[i]=read();
for(int i=1; i<=n; ++i){
int p[20]={0},t[20]={0};
while(a[i]>1){
int q=pi[a[i]];
p[++p[0]]=q;
while(a[i]%q==0)a[i]/=q,++t[p[0]];
}
for(int j=1; j<=p[0]; ++j){
for(int k=j+(t[j]<=1); k<=p[0]; ++k){
if(p[j]*p[k]<M){
int v=id[p[j]*p[k]]+n;
add_e(i,v),add_e(v,i);
}
}
}
}
int ma=0,mma=0,p;
for(int i=1; i<=n; ++i){
if(!v[i]){
S=0;
dfs(i);
// cout<<S<<'s'<<endl;
if(S>=ma)mma=ma,p=i,ma=S;
else mma=max(mma,S);
}
}
rt=p;
Ans=ma-1;
S=ma;
Tarjan(p);
cout<<max(Ans,mma)<<endl;
}
int main(){
freopen("connect.in","r",stdin);
freopen("connect.out","w",stdout);
int T=read();
pre();
while(T--)init(),Main();
return 0;
}
T4
原题面：
简化题面：
