naaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaayyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyz daaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaayyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy 3

Posted on By 陈麒润 naaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaayyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyz daaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaayyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy 3无评论

非常唐网络。
非常唐搬题人。
非常唐 \LaTeX。

A

做法很多，说下我的

令 w=max{a_i }，容易发现固定左端点的话最大公约数最多只有 O(\log w) 种。

于是直接二分这么多次，开个桶记录一下即可。

复杂度大概是 O(n\log n\log w)。

#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define MX 100005
#define K 18
using namespace std;
const int CHECK=0,FIL=1;int read();
int bgcd(int x,int y){
    if(!y) return x;
    return bgcd(y,x%y);
} 
int n,a[MX],f[K][MX],g[105];
signed main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    FRE freopen("set.in","r",stdin);
    FRE freopen("set.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=f[0][i]=read();
    }
    for(int i=1;i<K;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            f[i][j]=bgcd(f[i-1][j],f[i-1][j+(1<<(i-1))]);
    for(int I=1;I<=n;I++){
        int nw=a[I],i=I;
        while(i<=n){
            nw=bgcd(nw,a[i]);g[nw]=1;
            //cout<<i<<&#039;,&#039;<<nw<<&#039; &#039;;
            //cout<<nw<<&#039; &#039;;
            int j=i;
            for(int o=K-1;o>=0;o--){
                int u=f[o][j+1];
                if(u && u%nw==0) j+=(1<<o);
            }i=j+1;
        }//cout<<&#039;\n&#039;;
    }
    int res=0;
    for(int i=1;i<=100;i++) res+=g[i];
    printf("%d\n",res);
    return 0;
}
int read(){
    int Ca=0;char Cr=&#039; &#039;;int Cf=1;
    while(Cr<&#039;0&#039; || Cr>&#039;9&#039;){Cr=getchar();if(Cr==&#039;-&#039;){Cf=-1;}}
    while(Cr>=&#039;0&#039; && Cr<=&#039;9&#039;){Ca=Ca*10+Cr-48;Cr=getchar();}
    return Ca*Cf;
}

B

相似题目：Gym-102803L。

找规律：

         18         
      19 08 16        
   20 09 02 06 14     
21 10 03 00 01 05 13  
   22 11 04 07 15     
      23 12 17        
         24

每一层 x>0 和 x\leq 0 分类讨论一下即可。

复杂度 O(n+m\log L)。

#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define int __int128
#define INF 800000000
using namespace std;
const int CHECK=0,FIL=1;
int read();void write(int o);
int q,Q,x,y;
int Abs(int o){return max(o,-o);}
int w(int o){return o*(o+1ll)*2ll;}
signed main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    FRE freopen("number.in","r",stdin);
    FRE freopen("number.out","w",stdout);
    q=read();Q=read();
    while(q--){
        x=read();y=read();
        if(!x && !y){printf("0\n");continue;}
        int o=Abs(x)+Abs(y);int res=w(o-1);
        if(x>0){
            if(y>0) res+=y*2;
            else res-=(y*2-1);
        }else{
            res+=(o*2-1);
            if(y>0) res+=(1-x);
            else res+=(o-y+1);
        }
        write(res);putchar(&#039;\n&#039;); 
    }
    while(Q--){
        x=read();
        if(!x){printf("0 0\n");continue;}
        int o=0,r=INF;
        while(o<r){
            int mid=(o+r+1)>>1;
            if(w(mid)<x) o=mid;
            else r=mid-1;
        }
        //cout<<(long long)x<<&#039;,&#039;<<(long long)o<<&#039;\n&#039;;
        int res=x-w(o);o++;
        if(res<o*2){
            x=o-(res/2);
            if(res&1) y=-(res/2);
            else y=res/2;
        }else{
            res-=o*2;
            if(res<=o) x=-res,y=o-res;
            else{
                res-=o;
                x=-o+res,y=-res;
            }
        }
        write(x);putchar(&#039; &#039;);
        write(y);putchar(&#039;\n&#039;); 
    }
    return 0;
}
int read(){
    int Ca=0;char Cr=&#039; &#039;;int Cf=1;
    while(Cr<&#039;0&#039; || Cr>&#039;9&#039;){Cr=getchar();if(Cr==&#039;-&#039;){Cf=-1;}}
    while(Cr>=&#039;0&#039; && Cr<=&#039;9&#039;){Ca=Ca*10+Cr-48;Cr=getchar();}
    return Ca*Cf;
}
void wrt(int o){
    if(!o) return;
    wrt(o/10);putchar(&#039;0&#039;+o%10);
}
void write(int o){
    if(o<0){putchar(&#039;-&#039;);o=-o;}
    if(!o) putchar(&#039;0&#039;);
    else wrt(o);
}

C

HDU-7323 严格加强加强加强。

懒得写数据结构是这样的。

$a_i-b_i$ 的正负分别考虑（$0$ 算负数里）。

正

自己先拿就可以拉开 a_i-b_i 的差距，所以肯定要抢着拿。

按照题意就是每人两次。

负

自己先拿就会让对方和自己的差距减小，所以两个人肯定是不愿意去拿的。

所以自己会优先把前面的坑填上（先手拿了后手没拿的），实在不行再拿负的。

手搓一下发现是交替的。

带修应该是可以上个数据结构维护的，但是我懒了。

所以每次直接按 a_i-b_i 排序按上面的方式算即可，复杂度 O(nq\log n)。

期望得分 60，实际得分 70。

#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define int long long
#define MX 200005
using namespace std;
const int CHECK=0,FIL=1;int read();
int n,q,x,y,z,p[2],a[MX],b[MX];
signed main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    FRE freopen("xiaovid.in","r",stdin);
    FRE freopen("xiaovid.out","w",stdout);
    n=read();q=read();
    for(int i=1;i<=n;i++){
        a[i]=read();a[i]=read()-a[i];}
    while(q--){
        x=read();y=read();z=read();
        a[x]=z-y;
        for(int i=1;i<=n;i++) b[i]=a[i];
        sort(b+1,b+1+n);z=0;
        for(int i=1;i<=n;i++){
            if(b[i]>=0){
                if(i&1) z-=b[i];
                else z+=b[i];
            }else{
                if(i%4<2) z-=b[i];
                else z+=b[i];
            }
            //cout<<b[i]<<&#039;,&#039;<<z<<&#039; &#039;;
        }
        printf("%lld\n",z);
    }
    return 0;
}
int read(){
    int Ca=0;char Cr=&#039; &#039;;int Cf=1;
    while(Cr<&#039;0&#039; || Cr>&#039;9&#039;){Cr=getchar();if(Cr==&#039;-&#039;){Cf=-1;}}
    while(Cr>=&#039;0&#039; && Cr<=&#039;9&#039;){Ca=Ca*10+Cr-48;Cr=getchar();}
    return Ca*Cf;
}

D

Gym-104030K，完全一样。

非常好线段树！

考虑正着反着各建一个线段树，支持单点修改区间求哈希。

初始第 i 个位置值即为 i。

然后对于操作二：

  • 如果区间长度不一样显然不相等。
  • 如果区间长度一样：
    • 直接线段树上算哈希，如果相等那就是始终相等
    • 否则就是可能不等。

对于操作一：

  • 其实就是给定很多个“某两个位置的值相等”的条件，可以使用并查集。
  • 最多合并 n-1 次，按秩合并可以做到只要 O(n\log n) 次修改。
  • 问题是如何精准找到这 n-1 次合并在哪呢？
    • 考虑二分找到两端往里第一个不等的字符。
    • 二分到一个值 p 可以比较 [l,l+p]（正序） 和 [r,r-p]（倒序）是否相等。
    • 如果相等显然这一段都是相等，不等说明里面至少有一个不等。
    • 有单调性可以二分。
    • 如果二分到了一个位置那更新后继续往下二分知道没有不同的为止。
    • 每次二分必定造成一次合并，所以最多只有 n+m-1 次二分。

然后就做完了，我太弱了导致线段树调了近 1h。

#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define int long long
#define MX 100005
using namespace std;
const int base=100019,mod=1000000087;
const int CHECK=0,FIL=1;int read();
int n,q,qp[MX],fa[MX],col[MX];
vector<int> v[MX];
int find(int i){return fa[i]=(fa[i]==i)?i:find(fa[i]);}
class SegmentTree{
    public:
    int tr[MX*4];
    void add(int t,int w){tr[t]=w;}
    void pu(int t,int l,int r){
        int mid=(l+r)>>1;
        tr[t]=(tr[t<<1]*qp[r-mid]+tr[t<<1|1])%mod;}
    void Set(int t,int l,int r,int L,int w){
        if(l>=r){add(t,w);return;}
        int mid=(l+r)>>1;
        if(L<=mid) Set(t<<1,l,mid,L,w);
        else Set(t<<1|1,mid+1,r,L,w);
        pu(t,l,r);
    }
    int Hash(int t,int l,int r,int L,int R){
        if(L<=l && r<=R) return tr[t];
        int mid=(l+r)>>1,res=0;
        if(L<=mid) res=Hash(t<<1,l,mid,L,R);
        if(R>mid){
            res=(res*qp[min(r,R)-mid])%mod;
            res=(res+Hash(t<<1|1,mid+1,r,L,R))%mod;
        }
        //cout<<l<<&#039; &#039;<<r<<&#039; &#039;<<mid<<&#039; &#039;<<res<<&#039;\n&#039;;
        return res;
    }
}A,B;
void merge(int i,int j){
    //cout<<"merge: "<<i<<&#039; &#039;<<j<<&#039;\n&#039;;
    i=find(i),j=find(j);
    if(i==j){
        printf("what\n");
        exit(0);
    }
    if(col[i]<col[j]) swap(i,j);
    col[i]+=col[j];
    for(auto p:v[j]){
        A.Set(1,1,n,p,i);
        B.Set(1,1,n,n-p+1,i);
        v[i].push_back(p);
        //cout<<p<<&#039; &#039;<<i<<&#039;\n&#039;;
        fa[p]=i;
    }
    /*for(auto p:v[i])
        printf("%lld, ",p);
    printf("\n");
    printf("complete\n");*/
}
signed main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    FRE freopen("tiao.in","r",stdin);
    FRE freopen("tiao.out","w",stdout);
    n=read();q=read();
    qp[0]=1;for(int i=1;i<=n;i++) qp[i]=qp[i-1]*base%mod;
    for(int i=1;i<=n;i++){
        A.Set(1,1,n,i,i);
        B.Set(1,1,n,n-i+1,i);
        fa[i]=i;col[i]=1;
        v[i].push_back(i);
    }
    while(q--) if(read()==1){
        int l=read();int r=read();
        while(l<r){
            int L=0,R=(r-l+1)/2;
            while(L<R){
                int mid=(L+R)>>1;
                if(A.Hash(1,1,n,l,l+mid) != B.Hash(1,1,n,n-r+1,n-(r-mid)+1)) R=mid;
                else L=mid+1;
            }
            if(R==(r-l+1)/2) break;
            merge(l+R,r-R);l+=R;r-=R;
        }
        //for(int i=1;i<=n;i++) printf("%lld ",A.Hash(1,1,n,i,i));printf("\n");
        //for(int i=1;i<=n;i++) printf("%lld ",B.Hash(1,1,n,i,i));printf("\n");
    }else{
        int l=read();int r=read();
        //printf("%lld\n",A.Hash(1,1,n,l,r));continue;
        int L=read();int R=read();
        if(r-l != R-L){printf("Not equal\n");}
        else if(A.Hash(1,1,n,l,r)!=A.Hash(1,1,n,L,R)){printf("Unknown\n");}
        else{printf("Equal\n");}
    }
    return 0;
}
int read(){
    int Ca=0;char Cr=&#039; &#039;;int Cf=1;
    while(Cr<&#039;0&#039; || Cr>&#039;9&#039;){Cr=getchar();if(Cr==&#039;-&#039;){Cf=-1;}}
    while(Cr>=&#039;0&#039; && Cr<=&#039;9&#039;){Ca=Ca*10+Cr-48;Cr=getchar();}
    return Ca*Cf;
}
训练日志

发表回复