Codeforces Round #482 (Div. 2)

Link

签到

分析

自以为写的很right

漏了一种情况啊，当它所有字符都相同并且可修改次数为1的情况

分析

赛时AC，x，y一定是在一条链上的，两次dfs分别从x和y出发，分别统计x，y挂的点的数量即可

题意

有一个空的数组a，现给出q个询问，询问有两种，① 给a中添加一个数u，②给出xi，ki，si，问你从a中选一个数v，要求ki | gcd(xi, v) 并且 v<=si-xi ,并且v^xi的值尽可能大，不存在-1 (q<=1e5，1<=u，xi，ki，si <= 1e5)

分析

由ki|gcd(xi,v)，直接看出xi和v都必须是ki的倍数才行，考虑对于每个询问的ki，我们需要找到它所有的倍数去选取，故我们可以把每个询问的v，把v插入到v的所有因子中，对于条件v<=si-xi，我们可以在每个字典树的节点维护到当前节点的最小值来判断可不可以走，v^xi最大值在树上爬的时候贪心维护即可，故一共建了1e5颗字典树，1e5的约数大概为100个

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=100000+7;

int n,q,t,u,v,x,k,s;
int root[maxn],tot,rt[maxn*200][2],minx[maxn*200];

int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}

int newnode()
{
    ++tot;
    memset(rt[tot],0,sizeof(rt[tot]));
    minx[tot]=1e6;
    return tot;
}

void build(int xx)
{
    int fa=root[xx];
    for(int i=20;i>=0;i--){
        int id=(u>>i)&1;
        if(!rt[fa][id]) rt[fa][id]=newnode();
        fa=rt[fa][id];
        minx[fa]=min(minx[fa],u);
    }
}

int query()
{
    int fa=root[k];
    if(fa==0)
        return -1;
    int ans=0;
    for(int i=20;i>=0;i--){
        int id=(x>>i)&1;
        if(rt[fa][!id] && ((minx[rt[fa][!id]]+x)<=s))
        {
            ans=minx[rt[fa][!id]];
            fa=rt[fa][!id];
        }
        else if(rt[fa][id] && ((minx[rt[fa][id]]+x)<=s))
        {
            ans=minx[rt[fa][id]];
            fa=rt[fa][id];
        }
        else
            return -1;

    }
    return ans;
}

int main()
{
    scanf("%d",&q);
    while(q--){
        scanf("%d",&t);
        if(t==1){
            scanf("%d",&u);
            for(int i=1;i*i<=u;i++)
            {
                if(u%i==0)
                {
                    if(!root[i]) root[i]=newnode();
                    if(!root[u/i]) root[u/i]=newnode();
                    build(i);
                    build(u/i);
                }
            }
        }
        else{
            scanf("%d%d%d",&x,&k,&s);
            int t=gcd(x,k);
            if(t!=k)
            printf("-1
");
            else{
                printf("%d
",query());
            }
        }
    }
    return 0;
}