难度:省选+?

Problem A: string

题目描述:

题解:

其实就是二合一

第一个还可以用hash做,对于要比较大小的两个串,二分最长前缀比较下一位就可以比较大小了。

代码:

代码调不出来,只用40pts

40pts代码:

#include <bits/stdc++.h>
#define il inline
#define Max 500005
#define ll unsigned long long
using namespace std;
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
char In[Max],*ss=In,*tt=In;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char a[Max],b[Max];
int q,n,m,ans,rk[Max],sa[Max],f[Max];
ll ha[Max],hb[Max],bs=23339,h[Max];
il ll suba(int i,int j)
{
    if(i<j) swap(i,j);
    return ha[i]-ha[j-1]*h[i-j+1];
}
il ll subb(int i,int j)
{
    if(i<j) swap(i,j);
    return hb[i]-hb[j-1]*h[i-j+1];
}
il ll get1(int mid,int i,int j)
{
    if(mid<=m) return hb[mid];
    ll lena=mid-m;
    return hb[m]*h[lena]+suba(i+1,i+lena);
}
il ll get2(int mid,int i,int j)
{
    if(!mid) return 0;
    if(mid<=j-i) return suba(i+1,i+mid);
    ll lenb=mid-j+i;
    return suba(i+1,j)*h[lenb]+subb(1,lenb);
}
il bool check(int mid,int i,int j)
{
    ll s1=get1(mid,i,j);
    ll s2=get2(mid,i,j);
    //cout<<mid<<' '<<s1<<' '<<s2<<' '<<suba(i+1,i+mid)<<endl;
    return s1==s2;
}
il bool cmp(int i,int j)
{
    if(i>j) return !cmp(j,i);
    int l=0,r=j-i+m,res=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid,i,j)) res=mid,l=mid+1;//,puts("cg!!!!!");
        else r=mid-1;
    }
    if(res==j-i+m) return i<j;
    char p1,p2;
    if(res<m) p1=b[res+1];
    if(res>=m) p1=a[res-m+1];
    if(res<j-i) p2=a[res+i+1];
    if(res>=j-i) p2=b[res-j+i+1];
    //cout<<res<<' '<<p1<<' '<<p2<<" resqwq\n";
    return p1<p2;
}
int main()
{
    scanf("%s %s",a+1,b+1);
    q=read();
    n=strlen(a+1),m=strlen(b+1);
    h[0]=1;
    //puts("qwq");
    for(int i=1;i<=n;i++) ha[i]=(ha[i-1]*bs+a[i]-'a'+1),h[i]=h[i-1]*bs;
    for(int i=1;i<=m;i++) hb[i]=(hb[i-1]*bs+b[i]-'a'+1),h[i]=h[i-1]*bs;
    for(int i=0;i<=n;i++) sa[i]=i;
    sort(sa,sa+1+n,cmp);
    for(int i=0;i<=n;i++) rk[sa[i]]=i;//,cout<<i<<' '<<sa[i]<<" qwq\n";
    //cout<<suba(3,3)<<" qwq";
    //cout<<suba(1,3)<<' '<<suba(3,5)<<' '<<cmp(4,3)<<" qwqwqwq\n";
    //cout<<cmp(4,8)<<endl;
    //puts(" qwqwq!");
    while(q--)
    {
        int l=read(),r=read(),k=read(),x=read(),y=read();
        while(y<l) x+=k,y+=k;
        if(x>r)
        {
            puts("-1");
            continue;
        }
        int ans=-1;
        while(max(l,x)<=min(y,r))
        {
            int mx=max(l,x),my=min(y,r);
            for(int i=mx;i<=my;i++)
            {
                if(rk[i]<rk[ans]||ans==-1) ans=i;
            }
            x+=k,y+=k;
            //cout<<"qwq:"<<mx<<' '<<my<<' '<<ans<<endl;
        }
        printf("%d\n",ans);
    }
    puts("");
}

100pts by ezoixx118

/*
把getsize去掉约600ms
事实证明二维数组寻址太慢
改成指针快了5s
*/
//#pragma GCC optimize(3)
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#define inf 200001
#define infm 100001
#define INF 1e9
char buf[9000001],*Hd,*Tl;
#define getchar(ch) {ch=(*Hd++);}
#define rd(n) {n=0;char ch;int f=0;do{getchar(ch);if(ch=='-'){f=1;}}while(ch<'0'||ch>'9');while('0'<=ch&&ch<='9'){n=(n<<1)+(n<<3)+ch-48;getchar(ch);}if(f)n=-n;}
using namespace std;

inline int Min(int x,int y){
    return x>y?y:x;
}
inline int Max(int x,int y){
    return x>y?x:y;
}

int n,m,N;
int lg2[inf];

struct STgraph{

int cnt;    
int f[18][inf];

void init(int ct){
    cnt=ct;
    for (int j=1;j<=17;j++){
        for (int i=0;i<=cnt-(1<<j)+1;++i){
            f[j][i]=Min(f[j-1][i],f[j-1][i+(1<<(j-1))]);
        }
    }
    return;
}

int query(int l,int r){
    if (l>r){
        return INF;
    }
    int k=lg2[r-l+1];
    int *tmp=f[k];
    return Min(*(tmp+l),*(tmp+r-(1<<k)+1));
}

};

int tx[inf],ty[inf],s[inf];
int sa[inf],rnk[inf],h[inf];
int C[28],mxv=27;
STgraph minh;

void C_sort(void){
    for (int i=0;i<=mxv;++i){
        C[i]=0;
    }
    for (int i=1;i<=N;++i){
        C[tx[i]]++;
    }
    for (int i=1;i<=mxv;++i){
        C[i]+=C[i-1];
    }
    for (int i=N;i>=1;i--){
        sa[C[tx[ty[i]]]--]=ty[i];
    }
    return;
}

bool comp(int pos,int l){
    return ty[sa[pos]]==ty[sa[pos-1]] && ty[sa[pos]+l]==ty[sa[pos-1]+l];
}

void SA_getsa(void){
    for (int i=1;i<=N;++i){
        tx[i]=s[i];
        ty[i]=i;
    }
    C_sort();
    int cnt=-1;
    for (int l=1;l<=N && cnt<N;l*=2,mxv=cnt){
        cnt=0;
        for (int i=N-l+1;i<=N;++i){
            ty[++cnt]=i;
        }
        for (int i=1;i<=N;++i){
            if (sa[i]>l){
                ty[++cnt]=sa[i]-l;
            }
        }
        C_sort();
        swap(tx,ty);
        cnt=tx[sa[1]]=1;
        for (int i=2;i<=N;++i){
            if (!comp(i,l)){
                cnt++;
            }
            tx[sa[i]]=cnt;
        }
    }
    return;
}

void SA_getheight(void){
    int last=0;
    for (int i=1;i<=N;++i){
        if (rnk[i]==1){
            continue;
        }
        if (last){
            last--;
        }
        int j=sa[rnk[i]-1];
        while (i+last<=N && j+last<=N && s[i+last]==s[j+last]){
            last++;
        }
        h[rnk[i]]=last;
    }
    return;
}

void SA_build(void){
    SA_getsa();
    for (int i=1;i<=N;++i){
        rnk[sa[i]]=i;
    }
    SA_getheight();
    for (int i=1;i<=N;++i){
        minh.f[0][i]=h[i];
    }
    minh.init(N);
    return;
}

int SA_getlcp(int x,int y){
    x=rnk[x],y=rnk[y];
    if (x>y){
        swap(x,y);
    }
    return minh.query(x+1,y);
}

bool SA_cmp(int i,int j){
    if (i==j){
        return 0;
    }
    int flag=0,lcp;
    if (i>j){
        flag=1;
        swap(i,j);
    }
    if (j-i>=m){
        lcp=SA_getlcp(n+1,i+1);
        if (lcp<m){
            return flag^(rnk[n+1]<rnk[i+1]);
        }
        lcp=SA_getlcp(i+1,i+m+1);
        if (lcp<j-i-m){
            return flag^(rnk[i+1]<rnk[i+m+1]);
        }
        lcp=SA_getlcp(j-m+1,n+1);
        if (lcp<m){
            return flag^(rnk[j-m+1]<rnk[n+1]);
        }
    }
    else{
        lcp=SA_getlcp(n+1,i+1);
        if (lcp<j-i){
            return flag^(rnk[n+1]<rnk[i+1]);
        }
        lcp=SA_getlcp(n+j-i+1,n+1);
        if (lcp<m-(j-i)){
            return flag^(rnk[n+j-i+1]<rnk[n+1]);
        }
        lcp=SA_getlcp(i+1,n+m-(j-i)+1);
        if (lcp<j-i){
            return flag^(rnk[i+1]<rnk[n+m-(j-i)+1]);
        }
    }
    return !flag;
}

struct query{
    int l,r,k,x,y;
    int id;
    query(){}
    query(int L,int R,int K,int X,int Y,int I){
        l=L,r=R,k=K,x=X,y=Y,id=I;
    }
}a[infm],b[infm];

bool operator<(query _1,query _2){
    return _1.k<_2.k;
}

int Ans[infm];
int rk[infm],pos[infm];

STgraph s1,s2;
int id[infm];

int ST_query1(query q){
    int ans=INF;
    for (int i=0;i*q.k<=q.r;++i){
        int tmp=s1.query(Max(q.l,i*q.k+q.x),Min(q.r,i*q.k+q.y));
        ans=Min(ans,tmp);
    }
    return ans==INF?-1:ans;
}

void ST_build2(query q){
    int cnt=0;
    for (int i=0;i<q.k;++i){
        for (int j=0;j*q.k+i<=n;j++){
            s2.f[0][cnt]=pos[j*q.k+i];
            id[j*q.k+i]=cnt;
            cnt++;
        }
    }
    s2.init(cnt);
    return;
}

int ST_query2(query q){
    int ans=INF;
    for (int i=q.x;i<=q.y;++i){
        int l=q.l/q.k*q.k+i,r=q.r/q.k*q.k+i;
        while (l<q.l){
            l+=q.k;
        }
        while (r>q.r){
            r-=q.k;
        }
        if (l<=r){
            ans=Min(ans,s2.query(id[l],id[r]));
        }
    }
    return ans==INF?-1:ans;
}

int acnt,bcnt,qcnt;
int size=78;

inline void getstring(void){
    char ch;
    int Cnt=0;
    do{getchar(ch);}while(ch<'a'||ch>'z');
    while('a'<=ch&&ch<='z'){s[++N]=ch-'a'+1,++Cnt;getchar(ch);}
    n=Cnt;

    Cnt=0;
    do{getchar(ch);}while(ch<'a'||ch>'z');
    while('a'<=ch&&ch<='z'){s[++N]=ch-'a'+1,++Cnt;getchar(ch);}
    m=Cnt;
    return;
}

void getsize(void){
    if (s[1]==1){
        size=(s[3]==1?72:10);
    }
    else{
        if (s[2]==2){
            size=(s[3]==1?10:78);
        }
        else if (s[3]==2){
            size=78;
        }
        else{
            size=(s[4]==1?10:78);
        }
    }
    return;
}

int main(){
    int len=fread(buf,1,9000000,stdin);Hd=buf,Tl=Hd+len;
    getstring();
    getsize();
    for (int i=2;i<=n+m;++i){
        lg2[i]=lg2[i/2]+1;
    }
    SA_build();

    for (int i=1;i<=n;++i){
        rk[i]=i;
    }
    sort(rk,rk+n+1,SA_cmp);
    for (int i=0;i<=n;++i){
        pos[rk[i]]=i;
    }
    for (int i=0;i<=n;++i){
        s1.f[0][i]=pos[i];
    }
    s1.init(n);

    rd(qcnt)
    int l,r,k,x,y;
    for (int i=1;i<=qcnt;++i){
        rd(l) rd(r) rd(k) rd(x) rd(y)
        (k>size)?(a[++acnt]=query(l,r,k,x,y,i)):(b[++bcnt]=query(l,r,k,x,y,i));
        Ans[i]=-2;
    }

    for (int i=1;i<=acnt;++i){
        Ans[a[i].id]=ST_query1(a[i]);
    }
    sort(b+1,b+bcnt+1);
    for (int i=1;i<=bcnt;){
        ST_build2(b[i]);
        int j=i;
        while (j<=bcnt && b[j].k==b[i].k){
            Ans[b[j].id]=ST_query2(b[j]);
            j++;
        }
        i=j;
    }

    for (int i=1;i<=qcnt;++i){
        printf("%d ",Ans[i]==-1?-1:rk[Ans[i]]);
    }
    puts("");
    return 0;
}

Problem B: mex

题目描述:

题解:

我写的不是官方题解,但是也可以过

我是先离散化,然后用动态开点线段树做就没了。

代码:

#include <bits/stdc++.h>
#define il inline
#define Max 1000005
#define int long long
#define ll long long
#define inf 1e18+1
#define lim 1e18
using namespace std;
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
char In[Max],*ss=In,*tt=In;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int ls[Max<<2],rs[Max<<2],mn1[Max<<2],mn2[Max<<2],tg[Max<<2],cnt,tg2[Max<<2];
il void crt(int &x,int l)
{
    if(x) return;
    x=++cnt;
    mn1[x]=l;
    mn2[x]=inf;
}
il void pushup(int x)
{
    mn1[x]=min(mn1[ls[x]],mn1[rs[x]]);
    mn2[x]=min(mn2[ls[x]],mn2[rs[x]]);
}
il void pushdown(int x,int l,int r)
{
    if(tg2[x])
    {
        int mid=(l+r)>>1;
        mn1[x]=inf;
        mn2[x]=l;
        if(tg2[x]==2) swap(mn1[x],mn2[x]);
        if(l==r) tg2[x]=0;
        if(l==r) return;
        crt(ls[x],l);
        crt(rs[x],mid+1);
        tg2[ls[x]]=tg2[x];
        tg[ls[x]]=0;
        tg2[rs[x]]=tg2[x];
        tg[rs[x]]=0;
        tg2[x]=0;
    }
    if(tg[x]==1)
    {
        //puts("qwq!");
        int mid=(l+r)>>1;
        tg[x]=0;
        swap(mn1[x],mn2[x]);
        if(l==r) return;
        crt(ls[x],l);
        crt(rs[x],mid+1);
        tg[ls[x]]^=1;tg[rs[x]]^=1;
    }
}
il void ins(int &x,int l,int r,int ql,int qr,int k)
{
    int mid=(l+r)>>1;
    crt(x,l);
    if(l!=r) crt(ls[x],l),crt(rs[x],mid+1);
    //cout<<l<<' '<<r<<' '<<mn1[x]<<' '<<mn2[x]<<" qwq1\n";
    pushdown(x,l,r);
    pushdown(ls[x],l,mid);
    pushdown(rs[x],mid+1,r);
    //cout<<l<<' '<<r<<' '<<mn1[x]<<' '<<mn2[x]<<" qwq2\n";
    if(ql<=l&&r<=qr)
    {
        tg2[x]=k;
        pushdown(x,l,r);
        return;
    }
    if(ql<=mid) ins(ls[x],l,mid,ql,qr,k);
    if(qr>mid) ins(rs[x],mid+1,r,ql,qr,k);
    pushdown(x,l,r);
    pushdown(ls[x],l,mid);
    pushdown(rs[x],mid+1,r);
    pushup(x);
    //cout<<l<<' '<<r<<' '<<mn1[x]<<' '<<mn2[x]<<" qwq\n";
}
il void mdf(int &x,int l,int r,int ql,int qr)
{
    int mid=(l+r)>>1;
    crt(x,l);
    if(l!=r) crt(ls[x],l),crt(rs[x],mid+1);
    pushdown(x,l,r);
    pushdown(ls[x],l,mid);
    pushdown(rs[x],mid+1,r);
    if(ql<=l&&r<=qr)
    {
        //cout<<l<<' '<<r<<' '<<tg2[x]<<endl;
        //puts("qwqwq");
        tg[x]^=1;
        pushdown(x,l,r);
        //cout<<mn1[x]<<' '<<mn2[x]<<' '<<tg[x]<<endl;
        return;
    }
    if(ql<=mid) mdf(ls[x],l,mid,ql,qr);
    if(qr>mid) mdf(rs[x],mid+1,r,ql,qr);
    pushdown(x,l,r);
    pushdown(ls[x],l,mid);
    pushdown(rs[x],mid+1,r);
    pushup(x);
    //cout<<l<<' '<<r<<' '<<mn1[x]<<' '<<mn2[x]<<" qwq\n";
    //cout<<l<<' '<<r<<' '<<mn1[ls[x]]<<' '<<mn1[x]<<" qwq\n";
}
int n,mxr,rt,opt[Max],flg,rk[Max],tot;
struct node
{
    int x,id,opt,p;
}e[Max<<2];
il bool cmp1(node a,node b)
{
    return a.x<b.x;
}
il bool cmp2(node a,node b)
{
    if(a.id!=b.id) return a.id<b.id;
    return a.x<b.x;
}
signed main()
{
    n=read();
    crt(rt,1);
    for(int i=1;i<=n;i++)
    {
        e[i*3-2].id=e[i*3-1].id=e[i*3].id=i;
        e[i*3-1].opt=e[i*3-2].opt=read();
        e[i*3-1].x=read();
        e[i*3-2].x=read();
        //if(e[i*3-1].x==1||e[i*3-2].x==1) flg=1;
        e[i*3].x=e[i*3-2].x+1;
        mxr=max(mxr,e[i*3].x);
    }
    e[n*3+1].x=1;e[n*3+1].id=n+1;
    sort(e+1,e+2+n*3,cmp1);
    for(int i=1;i<=n*3+1;i++)
    {
        if(e[i].x!=e[i-1].x) ++tot;
        e[i].p=tot;
    }
    sort(e+1,e+2+n*3,cmp2);
    for(int i=1;i<=n*3+1;i++) rk[e[i].p]=e[i].x;
    for(int i=1;i<=n;i++)
    {
        int opt=e[i*3-1].opt,l=e[i*3-2].p,r=e[i*3-1].p;
        if(opt!=3) ins(rt,1,tot,l,r,opt);
        else mdf(rt,1,tot,l,r);
        printf("%lld\n",rk[mn1[rt]]);
    }
}

Problem C: MST

题目描述:

题解:

就是这样,没什么好说的。

不过当时写到自闭,有些细节看代码就好。

代码:

#include <bits/stdc++.h>
#define il inline
#define Max 400005
#define ll int
using namespace std;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node
{
    int t,nt,w,id;
}e[Max<<1];
int head[Max],tot;
il void add(int u,int v,int w,int id)
{
    e[++tot].t=v;
    e[tot].nt=head[u];
    e[tot].w=w;
    e[tot].id=id;
    head[u]=tot;
}
struct edge
{
    int u,v,id,w,ans;
}ed[Max<<1];
il bool cmp1(edge x,edge y)
{
    return x.w<y.w;
}
int n,m,ff[Max],ans[Max],vst[Max],f[Max][25],d[Max],g[Max][25],rk[Max];
il int getf(int x)
{
    if(ff[x]==x) return x;
    else return ff[x]=getf(ff[x]);
}
il void merge(int x,int y)
{
    int fx=getf(x),fy=getf(y);
    if(fx!=fy)
        ff[fx]=fy;
}
il void dfs(int u,int fa,int x)
{
    d[u]=d[fa]+1;
    g[u][0]=x;
    f[u][0]=fa;
    for(int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1],g[u][i]=max(g[u][i-1],g[f[u][i-1]][i-1]);
    for(int i=head[u];i;i=e[i].nt)
    {
        int v=e[i].t,w=e[i].w;
        if(v==fa) continue;
        rk[v]=e[i].id;
        dfs(v,u,w);
    }
}
il int lca(int u,int v)
{
    if(d[u]<d[v]) swap(u,v);
    for(int i=20;i>=0;i--) if(d[f[u][i]]>=d[v]) u=f[u][i];
    if(u==v) return u;
    for(int i=20;i>=0;i--)
        if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
    return f[u][0];
}
il int qry(int u,int k)
{
    int res=0;
    for(int i=20;i>=0;i--)
    {
        if(k>=(1<<i))
        {
            k-=(1<<i);
            res=max(res,g[u][i]);
            u=f[u][i];
        }
    }
    return res;
}
il int qmax(int u,int v,int lc)
{
    if(d[u]>d[v]) swap(u,v);
    if(lc==u) return qry(v,d[v]-d[u]);
    return max(qry(u,d[u]-d[lc]),qry(v,d[v]-d[lc]));
}
il void calc(int u,int v,int k)
{
    u=getf(u);
    while(d[u]>d[v])
    {
        //puts("qwq");
        //cout<<u<<' '<<rk[u]<<' '<<v<<" qwqwq\n";
        ans[rk[u]]=min(ans[rk[u]],k);
        ff[u]=getf(f[u][0]);
        u=getf(u);
    }
}
signed main()
{
    n=read(),m=read();
    memset(ans,63,sizeof(ans));
    for(int i=1;i<=m;i++)
    {
        ed[i].u=read(),ed[i].v=read();ed[i].w=read();
        ed[i].id=i;
    }
    for(int i=1;i<=n;i++) ff[i]=i;
    sort(ed+1,ed+1+m,cmp1);
    int nw=1;
    for(int i=1;i<n;i++)
    {
        while(getf(ed[nw].u)==getf(ed[nw].v)) nw++;
        int u=ed[nw].u,v=ed[nw].v;
        merge(u,v);
        vst[nw]=1;
        //cout<<"add:"<<u<<' '<<v<<endl;
        add(u,v,ed[nw].w,ed[nw].id),add(v,u,ed[nw].w,ed[nw].id);
    }
    dfs(1,0,0);
    for(int i=1;i<=n;i++) ff[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(vst[i]) continue;
        //puts("qwq");
        int u=ed[i].u,v=ed[i].v,id=ed[i].id,w=ed[i].w,lc=lca(u,v);
        //cout<<u<<' '<<v<<' '<<lc<<endl;
        ans[id]=qmax(u,v,lc)-1;
        calc(u,lc,w-1);
        calc(v,lc,w-1);
    }
    for(int i=1;i<=m;i++) printf("%d ",ans[i]==ans[0]?-1:ans[i]);
    puts("");
}
//write you mother