头像

lucky


访客:6921

离线:11小时前


活动打卡代码 AcWing 256. 最大异或和

lucky
4天前
#include<cstdio>
#include<cstring>
using namespace std;
int ri()
{
    char c=getchar();int s=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
const int maxn=300010;
int n,m,a,b[25];
struct node
{
    int son[2],id;
}tr[maxn*50];int trlen,rt[maxn*2];
void get(int x)
{
    int len=25;
    while(x)
    {
        b[--len]=x&1;
        x>>=1;
    }
    while(len>1)b[--len]=0;
}
void add(int i){tr[++trlen]=(node){0,0,i};}
void ins(int id)
{
    int len=24,p=rt[id-1],q=rt[id]=trlen+1;
    add(id);
    for(int i=1;i<=len;i++)
    {
        if(p)
        {
            int w=b[i]^1;
            if(tr[p].son[w])tr[q].son[w]=tr[p].son[w];
        }
        add(id);
        tr[q].son[b[i]]=trlen;
        tr[q=trlen].id=id;
        p=tr[p].son[b[i]];
    }
}
int find(int l,int x)
{
    int ans=0,len=24;
    for(int i=1;i<=len;i++)
    {
        int w=b[i]^1,ns=tr[x].son[w];
        if(ns&&tr[ns].id>=l)
        {
            ans|=(1<<(len-i));
            x=ns;
            goto end;
        }
        ns=tr[x].son[b[i]];
        if(ns&&tr[ns].id>=l)
        {
            x=ns;
            goto end;
        }
        return ans;
        end:;
    }
    return ans;
}
int main()
{
    n=ri();m=ri();
    trlen=-1;add(0);rt[0]=a=0;
    for(int i=1;i<=n;i++)
    {
        a=ri()^a;
        get(a);
        ins(i);
    }
    int q=n;
    for(int i=1;i<=m;i++)
    {
        char ss[2];scanf("%s",ss);
        if(ss[0]=='A')
        {
            a=ri()^a;
            get(a);
            ins(++q);
        }
        else
        {
            int l=ri()-1,r=ri()-1,x=ri()^a;
            if(r==0)printf("%d\n",x);
            else
            {
                get(x);
                printf("%d\n",find(l,rt[r]));
            }
        }
    }
    return 0;
}


活动打卡代码 AcWing 311. 月之谜

lucky
5天前
#include<cstdio>
#include<cstring>
using namespace std;
int mymin(int x,int y){return x<y?x:y;}
int l,r,f[11][82][82][81],len,shi[10],ans,b[11];
int get(int x)
{
    int s=0;
    while(x)
    {
        b[++s]=x%10;
        x/=10;
    }
    return s;
}
void solve(int x)
{
    if(x==0)return;
    int ed=mymin(len*9,81);
    for(int k=1;k<=ed;k++)
    {
        for(int fi=0;fi<b[len];fi++)
        {
            if(k-fi<0)break;
            ans+=f[len-1][k-fi][k][((k-fi*shi[len-1])%k+k)%k];
        }
        int mo=b[len]*shi[len-1]%k,ls=b[len];
        for(int i=len-1;i>=1;i--)
        {
            for(int p=0;p<b[i];p++)
            {
                if(k-ls-p<0)break;
                ans+=f[i-1][k-ls-p][k][((k-mo-p*shi[i-1])%k+k)%k];
            }
            mo=(mo+b[i]*shi[i-1])%k;ls+=b[i];
            if(ls>k)break;
        }
    }
    int sum=0;
    for(int i=1;i<=len;i++)sum+=b[i];
    if(x%sum==0)ans++; 
}
int main()
{
    freopen("mystery5.in","r",stdin);
    freopen("a.out","w",stdout);
    shi[0]=1;for(int i=1;i<=9;i++)shi[i]=shi[i-1]*10;
    memset(f,0,sizeof(f));
    for(int j=1;j<=81;j++)f[0][0][j][0]=1;
    for(int i=1;i<=10;i++)
    {
        int ed=mymin(i*9,81);
        for(int j=0;j<=ed;j++)
        for(int k=1;k<=81;k++)
        for(int o=0;o<k;o++)
        for(int p=0;p<=9;p++)
        {
            if(j<p)break;
            f[i][j][k][o]+=f[i-1][j-p][k][((o-p*shi[i-1])%k+k)%k];
        }
    }
    while(scanf("%d%d",&l,&r)!=EOF)
    {
        len=get(r);
        ans=0;
        solve(r);
        int ans1=ans;ans=0;
        len=get(l-1);solve(l-1);
        printf("%d\n",ans1-ans);
    }
    return 0;
}


活动打卡代码 AcWing 310. 启示录

lucky
6天前
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int ri()
{
    char c=getchar();int s=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
ll shi[20],f[20][4],n,sum[20];
int ans[20];
int main()
{
    int T=ri();
    f[3][0]=900;f[3][1]=90;f[3][2]=9;
    for(int i=4;i<=10;i++)
    {
        f[i][0]=9*(f[i-1][2]+f[i-1][1]+f[i-1][0]);
        f[i][1]=f[i-1][0];
        f[i][2]=f[i-1][1];
    }
    shi[0]=1;for(int i=1;i<=10;i++)shi[i]=shi[i-1]*10;
    sum[2]=0;sum[3]=1;
    for(int i=4;i<=10;i++)sum[i]=sum[i-1]*10+f[i-1][2];
    while(T--)
    {
        n=ri();
        int len;
        for(int i=3;i<=10;i++)if(sum[i]>=n){len=i;n-=sum[i-1];break;}
        ll ls=sum[len-1];
        for(int j=1;j<6;j++)
        {
            if(ls>=n){ans[1]=j;goto ed;}
            else n-=ls;
        }
        if(ls+f[len-1][2]>=n){ans[1]=6;goto ed;}
        else n-=ls+f[len-1][2];
        for(int j=7;j<=9;j++)
        {
            if(ls>=n){ans[1]=j;goto ed;}
            else n-=ls;
        }
        ed:;
        int la=(ans[1]==6)?(1):(0);
        for(int i=len-1;i>=4;i--)
        {
            ls=sum[i-1];
            for(int j=0;j<6;j++)
            {
                if(ls>=n){ans[len-i+1]=j;la=0;goto end;}
                else n-=ls;
            }
            ll cc;
            if(la==0)cc=f[i-1][2];
            else if(la==1)cc=f[i-1][2]+f[i-1][1];
            else cc=f[i-1][2]+f[i-1][1]+f[i-1][0];
            if(ls+cc>=n){ans[len-i+1]=6;la++;goto end;}
            else n-=ls+cc;
            for(int j=7;j<=9;j++)
            {
                if(ls>=n){ans[len-i+1]=j;la=0;goto end;}
                else n-=ls;
            }
            end:;
            if(la==3)
            {
                ll sss=0;
                for(int j=1;j<=len-i+1;j++)sss=sss*10+ans[j];
                sss=sss*shi[i-1]+n-1;
                printf("%lld\n",sss);
                goto eend;
            }
        }
        for(int i=1;i<=len-3;i++)printf("%d",ans[i]);
        if(la==0)puts("666");
        else if(la==1)printf("66%lld\n",n-1);
        else
        {
            if(--n<10)printf("60%lld\n",n);
            else printf("6%lld\n",n);
        }
        eend:;
    }
    return 0;
}


活动打卡代码 AcWing 309. 装饰围栏

lucky
7天前
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll rll()
{
    char c=getchar();ll s=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,ans[25];
ll c,f[25][25][2],sum[25],T,v[25];
int main()
{
    T=rll();
    memset(v,0x7f,sizeof(v));
    while(T--)
    {
        n=(int)rll();c=rll();
        memset(f,0,sizeof(f));
        f[1][1][0]=f[1][1][1]=1;
        for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
        {
            for(int k=1;k<j;k++)f[i][j][1]+=f[i-1][k][0];
            for(int k=j;k<i;k++)f[i][j][0]+=f[i-1][k][1];
        }
        ll ss=0;int op,la;
        for(int i=1;i<=n;i++)
        for(int t=1;t>=0;t--)
        {
            if(ss+f[n][i][t]>=c)
            {
                v[ans[1]=la=i]=T;
                op=t^1;c-=ss;
                goto end;
            }
            ss+=f[n][i][t];
        }
        end:;
        for(int i=n-1;i>=1;i--)
        {
            int k=0;ss=0;
            if(op==1)
            {
                for(int j=1;j<=n;j++)
                if(v[j]!=T)
                {
                    if(++k>i)break;
                    if(k>=la)
                    {
                        if(ss+f[i][k][1]>=c)
                        {
                            v[ans[n-i+1]=j]=T;
                            la=k;op^=1;c-=ss;
                            break;
                        }
                        ss+=f[i][k][1];
                    }
                }
            }
            else
            {
                for(int j=1;j<=n;j++)
                if(v[j]!=T)
                {
                    if(++k>=la)break;
                    if(ss+f[i][k][0]>=c)
                    {
                        v[ans[n-i+1]=j]=T;
                        la=k;op^=1;c-=ss;
                        break;
                    }
                    ss+=f[i][k][0];
                }
            }
        }
        for(int i=1;i<n;i++)printf("%d ",ans[i]);
        printf("%d\n",ans[n]);
    }
    return 0;
}


活动打卡代码 AcWing 304. 诗人小G

lucky
10天前
#include<cstdio>
#include<cstring>
using namespace std;
typedef long double ll;
int ri()
{
    char c=getchar();int s=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
const ll inf=(ll)(1e18)+1;
const int maxn=100010;
ll myabs(ll x){return x>0?x:-x;}
ll mymin(ll x,ll y){return x<y?x:y;}
int n;
ll L,a[maxn],sum[maxn],f[maxn];
long long p;
struct node
{
    int x,y,p;
}q[maxn];int l,r;
char si[35];
ll val(ll a,long long b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans*=a;
        a*=a;
        b>>=1;
    }
    return ans;
}
ll get(int i,int j)
{
    return f[j]+val(myabs(sum[i]-sum[j]+i-j-1-L),p);
}
int find(int i)
{
    int lll=q[r].x,rr=q[r].y,mid;
    while(lll<rr)
    {
        mid=(lll+rr)>>1;
        if(get(mid,i)>get(mid,q[r].p))lll=mid+1;
        else rr=mid;
    }
    if(lll==q[r].y&&get(lll,i)>get(lll,q[r].p))return q[r+1].x;
    return lll;
}
int main()
{
    int T=ri();
    while(T--)
    {
        n=ri();L=ri();p=ri();
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",si);
            a[i]=strlen(si);
            sum[i]=sum[i-1]+a[i];
        }
        memset(f,0,sizeof(f));
        q[l=r=1]=(node){1,n,0};
        for(int i=1;i<=n;i++)
        {
            int j=q[l].p;
            f[i]=get(i,j);
            if(++q[l].x>q[l].y)l++;
            if(l<=r&&get(q[r].y,i)>get(q[r].y,q[r].p))continue;
            while(l<=r&&get(q[r].x,i)<=get(q[r].x,q[r].p))r--;
            if(l<=r)
            {
                int now=find(i);
                q[r].y=now-1;
                q[++r]=(node){now,n,i};
            }
            else q[++r]=(node){i+1,n,i};
        }
        if(f[n]>=inf)puts("Too hard to arrange");
        else printf("%.0Lf\n",f[n]);
        puts("--------------------");
    }
    return 0;
}


活动打卡代码 AcWing 303. 运输小猫

lucky
11天前
/*
f[i][p]=f[j][p-1]+a[i]*(i-j)-(sum[i]-sum[j])
f[i][p]=(f[j][p-1]+sum[j])+(a[i]*i-sum[i])-a[i]*j

if (f[j][p-1]+sum[j])+(a[i]*i-sum[i])-a[i]*j<(f[k][p-1]+sum[k])+(a[i]*i-sum[i])-a[i]*k
   (f[j][p-1]+sum[j])+(a[t]*t-sum[t])-a[t]*j<(f[k][p-1]+sum[k])+(a[t]*t-sum[t])-a[t]*k
   (a[t]*t-sum[t])-(a[i]*i-sum[i])-a[t]*j+a[i]*j<(a[t]*t-sum[t])-(a[i]*i-sum[i])-a[t]*k+a[i]*k
   -a[t]*j+a[i]*j<-a[t]*k+a[i]*k
   a[t]*(k-j)<a[i]*(k-j)
   a[t]>a[i]

   (f[j][p-1]+sum[j])+(a[i]*i-sum[i])-a[i]*j<(f[k][p-1]+sum[k])+(a[i]*i-sum[i])-a[i]*k
   (f[j][p-1]+sum[j])-a[i]*j<(f[k][p-1]+sum[k])-a[i]*k
   (f[j][p-1]+sum[j])-(f[k][p-1]+sum[k])<a[i]*(j-k)
   (f[j][p-1]+sum[j])-(f[k][p-1]+sum[k])
   --------------------------- < a[i]
               j-k
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int ri()
{
    char c=getchar();int s=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
typedef long long ll;
const int maxn=100010;
const int maxp=110;
int n,m,p,q[maxn],l,r;
ll d[maxn],t[maxn],sum[maxn],f[2][maxn];
double xl(int j,int i,int k)
{
    return (double)(f[1-k][i]+sum[i]-f[1-k][j]-sum[j])/(i-j);
}
int main()
{
    n=ri();m=ri();p=ri();d[1]=sum[0]=0;
    for(int i=2;i<=n;i++)d[i]=ri()+d[i-1];
    for(int i=1;i<=m;i++)
    {
        t[i]=ri();
        t[i]=ri()-d[t[i]];
    }
    sort(t+1,t+m+1);
    for(int i=1;i<=m;i++)sum[i]=sum[i-1]+t[i];
    memset(f,0,sizeof(f));
    for(int i=1;i<=m;i++)f[1][i]=t[i]*i-sum[i];
    for(int k=2;k<=p;k++)
    {
        int w=k&1;
        q[l=r=1]=0;
        for(int i=1;i<=m;i++)
        {
            while(l<r&&xl(q[l],q[l+1],w)<=t[i])l++;
            int j=q[l];
            f[w][i]=f[1-w][j]+t[i]*(i-j)-(sum[i]-sum[j]);
            while(l<r&&xl(q[r-1],q[r],w)>=xl(q[r],i,w))r--;
            q[++r]=i;
        }
    }
    printf("%lld\n",f[p&1][m]);
    return 0;
}


活动打卡代码 AcWing 314. 低买

lucky
14天前
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll rll()
{
    char c=getchar();ll s=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
const ll inf=0x7f7f7f7f7f7f7f7f;
int mymax(int x,int y){return x>y?x:y;}
int n,f[5100],v[5100],who[5100];
struct gjd
{
    char a[210];
    int len;
}s[5100];
void clear(int x)
{
    memset(s[x].a,0,sizeof(s[x].a));s[x].len=0;
}
void add(int x,int y)
{
    int ed=mymax(s[x].len,s[y].len);
    for(int i=1;i<=ed;i++)s[x].a[i]+=s[y].a[i];
    for(int i=1;i<=ed;i++)
    {
        if(s[x].a[i]>9)
        {
            s[x].a[i+1]+=s[x].a[i]/10;
            s[x].a[i]%=10;
        }
    }
    int i=ed;
    while(s[x].a[++i]>9)
    {
        s[x].a[i+1]+=s[x].a[i]/10;
        s[x].a[i]%=10;
    }
    if(s[x].a[i]==0)i--;
    s[x].len=i;
}
void del(int x,int y)
{
    int ed=s[x].len;
    for(int i=1;i<=ed;i++)s[x].a[i]-=s[y].a[i];
    for(int i=1;i<=ed;i++)
    {
        if(s[x].a[i]<0)
        {
            s[x].a[i+1]--;
            s[x].a[i]+=10;
        }
    }
    while(s[x].a[ed]==0)ed--;
    s[x].len=ed;
}
struct node
{
    ll x;int p;
}a[5100];int ys[5100],z;
bool cmp(node x,node y){return x.x<y.x;}
int main()
{
    n=(int)rll();
    for(int i=1;i<=n;i++)a[i].x=rll(),a[i].p=i;
    sort(a+1,a+n+1,cmp);
    a[z=0].x=inf;
    for(int i=1;i<=n;i++)
    {
        if(a[i].x!=a[i-1].x)ys[a[i].p]=++z;
        else ys[a[i].p]=z;
    }
    ys[0]=z+1;
    int now=0;
    memset(v,0,sizeof(v));
    memset(f,0,sizeof(f));
    memset(s,0,sizeof(s));
    clear(0);s[0].a[s[0].len=1]=1;
    for(int i=1;i<=n;i++)
    for(int j=0;j<i;j++)if(ys[j]>ys[i])
    {
        if(f[j]+1>f[i])
        {
            f[i]=f[j]+1;
            s[i]=s[j];
            v[ys[j]]=++now;
            who[ys[j]]=j;
        }
        else if(f[j]+1==f[i])
        {
            if(v[ys[j]]!=now)
            {
                v[ys[j]]=now;
                who[ys[j]]=j;
                add(i,j);
            }
            else
            {
                del(i,who[ys[j]]);
                add(i,j);
                who[ys[j]]=j;
            }
        }
    }
    int ans=1;s[0]=s[1];
    v[ys[1]]=++now;
    who[ys[1]]=1;
    for(int i=2;i<=n;i++)
    {
        if(f[ans]<f[i])
        {
            s[0]=s[ans=i];
            v[ys[i]]=++now;
            who[ys[i]]=i;
        }
        else if(f[ans]==f[i])
        {
            if(v[ys[i]]!=now)
            {
                v[ys[i]]=now;
                who[ys[i]]=i;
                add(0,i);
            }
            else
            {
                del(0,who[ys[i]]);
                add(0,i);
                who[ys[i]]=i;
            }
        }
    }
    printf("%d ",f[ans]);
    for(int i=s[0].len;i>=1;i--)printf("%c",s[0].a[i]+'0');
    puts("");
    return 0;
}


活动打卡代码 AcWing 313. 花店橱窗

lucky
15天前
#include<cstdio>
#include<cstring>
using namespace std;
int ri()
{
    char c=getchar();int s=0,zf=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')zf=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s*zf;
}
const int inf=0x3f3f3f3f;
int mymax(int x,int y){return x>y?x:y;}
int n,m,a[110][110],f[110][110],pr[110][110],pl[110];
int main()
{
    n=ri();m=ri();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)a[i][j]=ri();
    memset(f,-0x3f,sizeof(f));f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        int maxf=i-1;
        for(int j=i;j<=m;j++)
        {
            f[i][j]=f[i-1][maxf]+a[i][j];
            pr[i][j]=maxf;
            if(f[i-1][j]>f[i-1][maxf])maxf=j;
        }
    }
    int ans=n;
    for(int i=n+1;i<=m;i++)if(f[n][ans]<f[n][i])ans=i;
    printf("%d\n",f[n][ans]);
    int now=n;
    while(now)
    {
        pl[now]=ans;
        ans=pr[now--][ans];
    }
    for(int i=1;i<n;i++)printf("%d ",pl[i]);
    printf("%d\n",pl[n]);
    return 0;
}


活动打卡代码 AcWing 312. 乌龟棋

lucky
15天前
#include<cstdio>
#include<cstring>
using namespace std;
int ri()
{
    char c=getchar();int s=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int mymax(int x,int y){return x>y?x:y;}
int n,m,a[360],sum[5],f[41][41][41][41];
int get(int a,int b,int c,int d){return a+b*2+c*3+d*4+1;}
int main()
{
    n=ri();m=ri();
    for(int i=1;i<=n;i++)a[i]=ri();
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=m;i++)sum[ri()]++;
    memset(f,0,sizeof(f));
    for(int i=0;i<=sum[1];i++)
    for(int j=0;j<=sum[2];j++)
    for(int k=0;k<=sum[3];k++)
    for(int l=0;l<=sum[4];l++)
    {
        int &x=f[i][j][k][l];
        if(i>0)x=mymax(x,f[i-1][j][k][l]);
        if(j>0)x=mymax(x,f[i][j-1][k][l]);
        if(k>0)x=mymax(x,f[i][j][k-1][l]);
        if(l>0)x=mymax(x,f[i][j][k][l-1]);
        x+=a[get(i,j,k,l)];
    }
    printf("%d\n",f[sum[1]][sum[2]][sum[3]][sum[4]]);
    return 0;
}


活动打卡代码 AcWing 162. 黑盒子

lucky
26天前
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int ri()
{
    char c=getchar();int s=0,zf=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')zf=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s*zf;
}
int m,n,a[30100],u[30100];
priority_queue<int,vector<int>,greater<int> >q;
priority_queue<int>q2;
int main()
{
    m=ri();n=ri();
    for(int i=1;i<=m;i++)a[i]=ri();
    for(int i=1;i<=n;i++)u[i]=ri();
    int nowa=0,nowu=0;
    while(++nowu<=n)
    {
        while(nowa<u[nowu])
        {
            q.push(a[++nowa]);
            if(!q2.empty()&&q2.top()>q.top())
            {
                int x=q.top();q.pop();
                int y=q2.top();q2.pop();
                q.push(y);q2.push(x);
            }
        }
        int x=q.top();q.pop();
        printf("%d\n",x);
        q2.push(x);
    }
    return 0;
}