NAN DAY 3

Posted on By 张, 高畅 NAN DAY 3无评论

其实本来有很多能写的但是现在时间不够了（大悲

因此以下内容全部都将简述.

[T1]

注意到 a_i \leq 100 ，因此可以使用 DP 来做。

但是如果这题值域很大的话，就没有办法了。

LXL给的算法是采用分治/扫描线（其实不太像)

具体地，因为对于每一个数 x，最多只会有 \log x 级别的 \gcd 个数，因此用队列（数组）维护这 \log x 不同的数，并记录答案。

DP 的复杂度为 O(100n)，代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=105,K=100;
int n,res,f[2][M],st[M];
int gcd(int a,int b)
{
    if(!b)return a;
    else return gcd(b,a%b);
}
int main()
{
    freopen("set.in","r",stdin);
    freopen("set.out","w",stdout);
    scanf("%d",&n);
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        for(int j=1;j<=K;j++)
        {
            f[i&1][j]=0;
            if(f[i-1&1][j])
            {
                st[j]=1;
                f[i&1][gcd(j,x)]=1;
            }
        }
        f[i&1][x]=1;
    }
    for(int i=1;i<=K;i++)
    {
        if(st[i]||f[n&1][i])res++;
    }
    printf("%d",res);
    return 0;
}

[T2]

找规律题。

对于 y坐标轴右侧呈现了一个上下震荡式的东西，y轴左侧则是正常逆时针分布。

代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long LL;
int n,m;
LL ABS(LL x)
{
    if(x>=0)return x;
    else return -x;
}
int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    scanf("%d%d",&n,&m);
    while(n--)
    {
        LL x,y;
        scanf("%lld%lld",&x,&y);
        if(!x&&!y)
        {
            puts("0");
            continue;
        }
        LL round=ABS(x)+ABS(y);
        LL cnt=(round-1)*round*2;
        if(x>0)
        {
            if(!y)cnt++;
            else
            {
                if(y>0)cnt+=(round-x)*2;
                else cnt+=(round-x)*2+1;
            }
        }
        else 
        {
            if(y>=0)cnt+=2*round+ABS(x);
            else cnt+=4*round-ABS(x);
        }
        printf("%lld\n",cnt); 
    }
    while(m--)
    {
        LL p;
        scanf("%lld",&p);
        if(!p)
        {
            puts("0 0");
            continue;
        }
        LL round=(sqrt(2*p)-1)/2;
        round++;
        p-=(round-1)*round*2;
        if(p<=2*round)
        {
            if(p==1)printf("%lld %lld\n",round,0);
            else if(p&1)printf("%lld %lld\n",round-(p/2),-(p/2));
            else printf("%lld %lld\n",round-(p/2),(p/2));
        }
        else
        {
            p-=2*round;
            if(p<=round)printf("%lld %lld\n",-p,round-p);
            else
            {
                p-=round;
                printf("%lld %lld\n",p-round,-p);
            }
        }
    }
    return 0;
}

[T3]

最难泵的一题，出题人甚至把读入文件输入错了。

但是这题本身也挺难泵的。

首先考虑普通贪心。

将 a_i-b_i 后我们来看怎么选。

对于正数，我们肯定要按照 ABBA 这样选最优，

对于负数与 0 ，我们则需要交替取最优。

然后考虑怎么办这东西扔到数据结构上维护。

考虑建立两棵值域线段树。

对于正数，按排名模 4 余 0/1/2/3 分类求和。
对于负数与 0，按排名模 2 余 0/1 分类求和。

最终答案一定是一定是正数树上的0/3减去上1/2，再加/减负数树上的 0 减去 负数树上的 1。

具体细节见代码，注意由于负数树上还需要维护零因此要注意值域。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,D=1e5;
typedef long long LL;
struct node
{
    LL w[4];
    int Size;
}tr[2][N<<2];
int n,m;
LL w[N];
void pushup(int op,node &u,node &l,node &r)
{
    u.Size=l.Size+r.Size;
    int S=op?2:4;
    for(int i=0;i<S;i++)u.w[i]=l.w[i]+r.w[((i-l.Size)%S+S)%S];
}
void modify(int op,int u,int l,int r,int pos,int w)
{
    if(l==r)
    {
        tr[op][u].Size+=w;
        int S=op?2:4;
        for(int i=0;i<S;i++)tr[op][u].w[i]=(tr[op][u].Size/S)*pos;
        for(int i=0;i<tr[op][u].Size%S;i++)tr[op][u].w[i]+=pos;
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid)modify(op,u<<1,l,mid,pos,w);
    else modify(op,u<<1|1,mid+1,r,pos,w);
    if(!op)pushup(op,tr[op][u],tr[op][u<<1|1],tr[op][u<<1]);
    else pushup(op,tr[op][u],tr[op][u<<1],tr[op][u<<1|1]);
}
int main()
{
    freopen("xiaovid.in","r",stdin);
    freopen("xiaovid.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        LL a,b;
        scanf("%lld%lld",&a,&b);
        w[i]=a-b;
        if(w[i]>0)modify(0,1,1,D,w[i],1);
        else modify(1,1,0,D,-w[i],1);
    }
    while(m--)
    {
        int x;
        LL y,z;
        scanf("%d%lld%lld",&x,&y,&z);
        if(w[x]>0)modify(0,1,1,D,w[x],-1);
        else modify(1,1,0,D,-w[x],-1);
        w[x]=y-z;
        if(w[x]>0)modify(0,1,1,D,w[x],1);
        else modify(1,1,0,D,-w[x],1);
        node POS=tr[0][1],NEG=tr[1][1]; 
        LL res=POS.w[0]+POS.w[3]-POS.w[1]-POS.w[2];
        if(POS.Size&1)res+=NEG.w[0]-NEG.w[1];
        else res+=NEG.w[1]-NEG.w[0];
        printf("%lld\n",res);
    }
    return 0;
}

[T4]

最讨厌线段树的一集。

首先可用并查集乱搞得到 45pts。

考虑在以上基础上优化，比如用hash来快速判断是否相等。

我们发现对于操作二可行了，但是操作一怎么维护呢？

考虑类似并查集式的按大小合并，我们发现复杂度是启发式合并的 n\log n 级别。

然而每次我们寻找哪些点要被改也需要 \log n 级别的二分。

最终复杂度 O(n \log n)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=1e5+3,Base=131,mod=1e9+7;
int n,m,par[N];
struct node
{
    int l,r;
    LL w[2];
}tr[N<<2];
LL power[N];
inline void pushup(node &u,node &l,node &r)
{
    u.l=l.l;
    u.r=r.r;
    u.w[0]=(l.w[0]*power[r.r-r.l+1]%mod+r.w[0])%mod;
    u.w[1]=(r.w[1]*power[l.r-l.l+1]%mod+l.w[1])%mod;
}
void build(int u,int l,int r)
{
    tr[u]={l,r};
    if(l==r)
    {
        tr[u].w[0]=tr[u].w[1]=l;
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void modify(int u,int pos,int w)
{
    if(tr[u].l==tr[u].r)
    {
        tr[u].w[0]=tr[u].w[1]=w;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(pos<=mid)modify(u<<1,pos,w);
    else modify(u<<1|1,pos,w);
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
node query(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r)return tr[u];
    int mid=tr[u].l+tr[u].r>>1;
    node res={0,0,0},left,right;
    if(l<=mid&&mid<r)
    {
        left=query(u<<1,l,r),right=query(u<<1|1,l,r);
        pushup(res,left,right);
        return res;
    }
    else if(l<=mid)return query(u<<1,l,r);
    else if(mid<r)return query(u<<1|1,l,r);
    else return res;
}
vector<int>S[N];
void merge(int s,int t)
{
    if(s==t)return;
    if(S[s].size()>S[t].size())
    {
        while(S[t].size())
        {
            S[s].push_back(S[t].back());
            modify(1,S[t].back(),s);
            par[S[t].back()]=s;
            S[t].pop_back();
        }
    }
    else
    {
        while(S[s].size())
        {
            S[t].push_back(S[s].back());
            modify(1,S[s].back(),t);
            par[S[s].back()]=t;
            S[s].pop_back();
        }
    }
}
void work(int x,int y)
{
    int L=x+y>>1,R=x+y>>1,len=0;
    if((x+y)&1)R++;
    do
    {
        int l=len+1,r=(y-x+2)/2;
        while(l<r)
        {
            int mid=l+r>>1;
            if(query(1,L-mid+1,L).w[0]!=query(1,R,R+mid-1).w[1])r=mid;
            else l=mid+1;
        }
        merge(par[L-l+1],par[R+l-1]);
        len=l;
    }
    while(len<(y-x+2)/2);
}
int main()
{
    freopen("tiao.in","r",stdin);
    freopen("tiao.out","w",stdout);
    scanf("%d%d",&n,&m);
    power[0]=1;
    for(int i=1;i<=n;i++)
    {
        power[i]=power[i-1]*Base%mod;
        par[i]=i;
        S[i].push_back(i);
    }
    build(1,1,n);
    while(m--)
    {
        int op,l,r,x,y;
        scanf("%d%d%d",&op,&l,&r);
        if(op==1)work(l,r);
        else if(op==2)
        {
            scanf("%d%d",&x,&y);
            if(y-x+1!=r-l+1)puts("Not equal");
            else puts(query(1,l,r).w[0]==query(1,x,y).w[0]?"Equal":"Unknown");
        }
    }
    return 0;
 }
训练日志

发表回复