头部背景图片
星之所幸,尘之所哀。 |
星之所幸,尘之所哀。 |

string[BZOJ某题加强版]

2018-11-19

题目:

img

题解:

    用排除法,一个SabT,我们枚举abT,查找有多少个S能接上a。即abT与fail[abT]之间的差就是能接上的最短距离。而Sab T这种分段方式则会在枚举到bT的时候枚举到,因此每个只需与fail取差的那段即可。

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 1200000
using namespace std;
char s[N];
int ch[N][27],n,d[N],c[N],siz[N],tot,q[N],fail[N];
long long ans;
int build_trie(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        int m=strlen(s+1);
        int now=0;
        for(int i=1;i<=m;i++){
            if(ch[now][s[i]-'a'+1]==0)ch[now][s[i]-'a'+1]=++tot;
            d[ch[now][s[i]-'a'+1]]=d[now]+1;
            now=ch[now][s[i]-'a'+1];
        }
    }
}
int build_AC(){
    int head=0,tail=1;
    q[1]=0;
    while(head<tail){
        int now=q[++head];
        for(int i=1;i<=26;i++){
            int v=ch[now][i];
            if(v==0)continue;
            int x;
            for(x=fail[now];x&&!ch[x][i];x=fail[x]);
            if(now!=x)fail[v]=ch[x][i];
            q[++tail]=v;
        }
    }
    for(int i=tail;i;i--){
        siz[q[i]]++;
        siz[fail[q[i]]]+=siz[q[i]];
    }
}
int dfs(int x){
    if(fail[x]){
        int o=d[x]-d[fail[x]];
        if(o!=0)ans-=siz[c[o]]-1;
    }
    c[d[x]]=x;
    for(int i=1;i<=26;i++)if(ch[x][i])dfs(ch[x][i]);
}
int main(){
    int T;
    scanf("%d",&T);
    build_trie(); 
    ans=1LL*tot*tot;
    build_AC();
    dfs(0);
    printf("%lld\n",ans);
}

「雅礼集训 2018 Day10」贪玩蓝月

2018-10-25

题目:「雅礼集训 2018 Day10」贪玩蓝月

题解:

    维护两个栈,插入就直接插入,删除就出栈,如果其中一个栈清空了,那么就直接从另外那个栈暴力取一半来重构。

    统计答案就用线段树来暴力求最大值。(不知道为什么输入数据里有点的编号qwq)。

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 120000
using namespace std;
int P;
long long h[520],n,A,B,c[520];
struct illyasviel{
    int w,v;
    illyasviel(int _w=0,int _v=0){w=_w,v=_v;}
}a[N],b[N],d[N];
struct node{
    long long f[520];
    int clear(){
        memset(f,-1,sizeof(f));
        f[0]=0;
    }
    int add(int v,int w){
        memset(h,-1,sizeof(h));
        h[0]=0;
        for(int i=0;i<P;i++)if(f[i]!=-1)h[(i+v)%P]=max(h[(i+v)%P],f[i]+w);
        for(int i=0;i<P;i++)f[i]=max(f[i],h[i]);
    }
}g[N],f[N];
char s[10];
int add1(int v,int w){
    A++;
    a[A].v=v;
    a[A].w=w; 
    f[A]=f[A-1];
    f[A].add(v,w);
}
int add2(int v,int w){
    B++;
    b[B].v=v;
    b[B].w=w;
    g[B]=g[B-1];
    g[B].add(v,w);
}
int rebuild(){
    int cnt=0;
    for(int i=A;i>=1;i--)d[++cnt]=a[i];
    for(int i=1;i<=B;i++)d[++cnt]=b[i];
    A=cnt/2;
    B=cnt-A;
    int o=0;
    for(int i=A;i>=1;i--)a[i]=d[++o];
    for(int i=1;i<=A;i++)f[i]=f[i-1],f[i].add(a[i].v,a[i].w);
    for(int i=1;i<=B;i++)b[i]=d[++o];
    for(int i=1;i<=B;i++)g[i]=g[i-1],g[i].add(b[i].v,b[i].w);
}
int del1(){
    if(A==0)rebuild();
    if(A==0)B--;
    else A--;
}
int del2(){
    if(B==0)rebuild();
    if(B==0)A--;
    else B--;
}
namespace seg{
    long long t[5000];
    int build(int i,int l,int r){
        if(l==r)return t[i]=c[l];
        int mid=(l+r)/2;
        build(i*2,l,mid);
        build(i*2+1,mid+1,r);
        t[i]=max(t[i*2],t[i*2+1]); 
    }
    long long query(int i,int l,int r,int x,int y){
        if(x<=l&&y>=r)return t[i];
        int mid=(l+r)/2;
        long long ans=-100000000000LL;
        if(x<=mid)ans=max(ans,query(i*2,l,mid,x,y));
        if(y>mid)ans=max(ans,query(i*2+1,mid+1,r,x,y));
        return ans;
    }
}
long long cal(int x,int y){
    for(int i=0;i<P;i++)c[i+1]=f[A].f[i];
    for(int i=1;i<=P;i++)if(c[i]==-1)c[i]=-10000000000000LL; 
    long long ans=-1;
    seg::build(1,1,P);
    for(int i=0;i<P;i++){
        if(g[B].f[i]==-1)continue;
        int l=x-i,r=y-i;
        if(l<0)l+=P;
        if(r<0)r+=P;
        if(l<=r)ans=max(ans,g[B].f[i]+seg::query(1,1,P,l+1,r+1));
        else ans=max(ans,g[B].f[i]+max(seg::query(1,1,P,1,r+1),seg::query(1,1,P,l+1,P)));
    }
    return max(ans,-1LL);
}
int main(){
    int T;
    scanf("%d",&T);
    scanf("%d%d",&n,&P);
    int tot=1,cnt=0;
    f[0].clear();
    g[0].clear();
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        if(s[1]=='I'){
            int v,w;
            scanf("%d%d",&v,&w);
            v%=P;
            if(s[2]=='F')add1(v,w);
            if(s[2]=='G')add2(v,w);
        }
        if(s[1]=='D'){
            if(s[2]=='F')del1(); 
            if(s[2]=='G')del2();
        }
        if(s[1]=='Q'){
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",cal(x,y));
        }
    }
}

BZOJ4676 Xor-Mul棋盘

2018-10-09

题目:

img

img

题解:

    考虑每个二进制位是相对独立的,那么就可以枚举每一行的状态然后暴力转移,预处理一些东西后,复杂度大概是O(22nmlog2106)O(2^{2n}m\log_{2}{10^6})。差不多是两亿。(之前有道题六亿longlong带取模2.3s能过,就没去思考进一步的复杂度了(还能通过类似插头DP的转移方式将其中2n2^n变为n)

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 12000
using namespace std;
long long f[N][(1<<5)+10];
int a[6][N],b[6][N],you[6][N],xia[6][N];
int A[N][(1<<5)+10],B[N][(1<<5)+10],C[N][(1<<5)+10];
int p[6][N];
int n,m,q[10];
int cal1(int i,int j){
    int ans=0;
    for(int k=1;k<=n;k++)q[k]=(j&(1<<(k-1)))>0;
    q[n+1]=q[1];
    for(int k=1;k<=n;k++)if(q[k]!=q[k+1])ans+=xia[k][i];
    return ans;
}
int cal2(int i,int j){
    int ans=0;
    for(int k=1;k<=n;k++)q[k]=(j&(1<<(k-1)))>0;
    q[0]=q[n];
    for(int k=1;k<=n;k++)if(q[k])ans+=you[k][i];
    return ans;
}
int cal3(int i,int j){
    int ans=0;
    for(int k=1;k<=n;k++)q[k]=(j&(1<<(k-1)))>0;
    q[0]=q[n];
    for(int k=1;k<=n;k++)ans+=(p[k][i]^q[k])*b[k][i];
    return ans;
}
long long cal(int x){
    memset(f,0x7f,sizeof(f));
    long long ans=f[0][0];
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)p[i][j]=(a[i][j]&(1<<x))>0;
    for(int i=1;i<=m;i++)for(int j=0;j<(1<<n);j++)A[i][j]=cal1(i,j);//竖着的 
    for(int i=1;i<m;i++)for(int j=0;j<(1<<n);j++)B[i][j]=cal2(i,j);//横着的 
    for(int i=1;i<=m;i++)for(int j=0;j<(1<<n);j++)C[i][j]=cal3(i,j);//本身的 
    for(int i=0;i<(1<<n);i++)f[1][i]=C[1][i]+A[1][i];
    for(int i=1;i<=m;i++){
        for(int j=0;j<(1<<n);j++){
            for(int k=0;k<(1<<n);k++){
                int l=j^k;
                f[i+1][l]=min(f[i][j]+B[i][k]+A[i+1][l]+C[i+1][l],f[i+1][l]);
            }
        }
    }
    for(int i=0;i<(1<<n);i++)ans=min(ans,f[m][i]);
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)scanf("%d",&b[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)scanf("%d",&you[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)scanf("%d",&xia[i][j]);
    long long ans=0;
    for(int i=0;i<=20;i++)ans+=cal(i)<<i;
    printf("%lld\n",ans);
}

BZOJ4675 点对游戏

2018-10-09

题目:

img

题解:

    考虑每个幸运点对都是相对独立的,就可以通过计算每个点对的概率来得到答案。

    统计幸运点对个数并乘上概率就是答案了。

官方题解:

题目来源:原创

考察要点:树的基于点/边的分治、概率与期望

涉及要点:动态规划、广度优先搜索

解题报告:

    对于某位玩家,其占据每个点的概率是相同的(因为点与点之间没有区别)。同样,其占据某对点对的概率也是固定的。不妨设这位玩家最终占据了n个点中的x个点,因为三人轮流选取的顺序固定,所以x可以简单求得。则该玩家占据某对点对的概率可以这么计算:

    该玩家从n个点中选取x个点的方案数为C(n,x)。

    在这些方案中,选取了某对点对的方案数为C(n-2,x-2)。

    与前面分析类似,易得每个方案的概率是相等的,故该玩家占据某对点对的概率为C(n2,x2)C(n,x)=x(x1)n(n1)\frac{C(n-2,x-2)}{C(n,x)}= \frac{x(x-1)}{n(n-1)}

    故问题转换为求距离为某个幸运数的点对对数,将其乘以x(x1)n(n1)\frac{x(x-1)}{n(n-1)}即为答案。

    对于数据点1,n <= 1000,bfs即可。

    对于数据点2、3、4,第i个幸运数为i,因为幸运数<=10,故可以使用树形动态规划求解。F[x][1…10]表示子树x中与节点x距离为1…10的点数,转移略。

    如果在bfs中加入剪枝优化(距离超过最大的幸运数后就不再搜索),亦可通过这三个数据点。

    对于数据点5、6、7,n为3的倍数,三人答案相同,方便选手计算。

    对于所有数据点,3 <= n <= 50000,m <= 10,幸运数大小 <= n,使用树的基于点/边的分治求解。其中树的基于边的分治需要重建树以防止星形图(数据点7和数据点10)时复杂度退化。另外在不开编译优化的情况下,使用vector等STL存图的程序也容易在这两个数据点超时。

出题思路:

    本题要求选手对期望与概率的独立性有最基本的认识,分析出藏在轮流选取背后的是每个点对相同的概率。之后本题的题目模型考察选手的硬编程实力,在所有树分治题目中,本题属于最简单的一类,熟练掌握的选手应可以在半小时至一小时内(关于这个表示赞同)解决。

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 120000
using namespace std;
int tot,Next[N],v[N],h[N];
int l[N],q[N],siz[N],dep[N];
int p[N],son[N],O,ill,cnt;
int m,luck[20],n;
long long ans;
int add(int x,int y){
    tot++;
    Next[tot]=h[x];
    v[tot]=y;
    h[x]=tot;
}
int get_siz(int x,int fa){
    siz[x]=1;
    for(int i=h[x];i;i=Next[i]){
        if(p[v[i]]==1)continue;
        if(v[i]==fa)continue;
        get_siz(v[i],x);
        siz[x]+=siz[v[i]];
    }
}
int get_son(int x,int fa,int OO){
    son[x]=OO-siz[x];
    for(int i=h[x];i;i=Next[i]){
        if(p[v[i]]==1)continue;
        if(v[i]==fa)continue;
        get_son(v[i],x,OO);
        son[x]=max(son[x],siz[v[i]]);
    }
    if(son[x]<son[O])O=x;
}
int get_son(int x){
    son[O]=10000000;
    O=0;
    get_siz(x,0);
    get_son(x,0,siz[x]);
    return O;
}
int lfs(int x,int fa){
    dep[x]=dep[fa]+1;
    if(dep[x]>ill)l[++ill]=0;
    if(dep[x]>cnt)q[++cnt]=0;
    l[dep[x]]++;
    for(int i=h[x];i;i=Next[i]){
        if(p[v[i]]==1)continue;
        if(v[i]==fa)continue;
        lfs(v[i],x);
    }
}
int solve(int x){
    p[x]=1;
    cnt=0,ill=0;
    dep[x]=0;
    for(int i=h[x];i;i=Next[i]){
        if(p[v[i]]==1)continue;
        ill=0;
        lfs(v[i],x);
        for(int j=1;j<=m;j++)if(luck[j]<=ill)ans+=l[luck[j]];
        for(int j=1;j<=ill;j++)
            for(int k=1;k<=m;k++)
                if(luck[k]>j&&luck[k]-j<=cnt)ans+=1LL*q[luck[k]-j]*l[j];
        for(int j=1;j<=ill;j++)q[j]+=l[j];
    }
     
    for(int i=h[x];i;i=Next[i]){
        if(p[v[i]]==1)continue;
        int o=get_son(v[i]);
        solve(o);
    }
}
int cal(long double x){
    long double k=ans;
    printf("%.2Lf\n",k*(x/n)*((x-1)/(n-1)));
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d",&luck[i]);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    solve(1);
    cal(n/3+(n%3>=1));
    cal(n/3+(n%3>=2));
    cal(n/3+(n%3>=3));
}

BZOJ4695 最假女选手

题目:

img

img

题解:

    吉利线段树板子题,利用父亲信息每次更新子节点,然后利用势能分析能证明其时间复杂度是O(nlog22n)O(nlog_2^2n)的(全靠脑补的我就写出了7k的代码(我无法用更短的代码表示我对这题的喜爱x。

    明明不是第一次写吉利线段树但我怎么一点印象都没有qwq。

    复制一时爽,调试火葬场(因为连着把一个错误复制了好多次导致重构代码。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 520000
using namespace std;
int a[N],n,m;
namespace seg{
    int mx[N*4],mi[N*4],mii[N*4],mxx[N*4],tag[N*4];
    int siz_min[N*4],siz_max[N*4];
    long long sum[N*4];
    int q[10];
    int down(int i,int l,int r){
        mii[i]+=tag[i];
        mi[i]+=tag[i];
        mxx[i]+=tag[i];
        mx[i]+=tag[i];
        sum[i]+=1LL*tag[i]*(r-l+1);
        if(l==r)return tag[i]=0;
        tag[i*2]+=tag[i];
        tag[i*2+1]+=tag[i];
        tag[i]=0;
    }
    int pushdown(int i,int l,int r){
        down(i,l,r);
        int mid=(l+r)/2;
        if(l!=r&&tag[i*2]!=0)down(i*2,l,mid);   
        if(l!=r&&tag[i*2+1]!=0)down(i*2+1,mid+1,r);
        if(l!=r){
            if(mi[i]==mx[i]){
                long long a=mi[i];
                siz_min[i]=siz_max[i]=r-l+1;
                siz_min[i*2]=siz_max[i*2]=mid-l+1;
                siz_min[i*2+1]=siz_max[i*2+1]=r-mid;
                mi[i*2]=a;
                mx[i*2]=a;
                mxx[i*2]=a;
                mii[i*2]=a;
                sum[i*2]=1LL*a*(mid-l+1);
                mi[i*2+1]=a;
                mx[i*2+1]=a;
                mxx[i*2+1]=a;
                mii[i*2+1]=a;
                sum[i*2+1]=1LL*a*(r-mid);
                return 0;
            }
            if(mi[i*2]==mx[i*2]){
                int mid=(l+r)/2;
                long long a=0;
                if(mi[i]>mi[i*2])a=mi[i];
                if(mx[i]<mx[i*2])a=mx[i];
                if(mi[i]<=mi[i*2]&&mx[i]>=mx[i*2])a=mi[i*2];
                mi[i*2]=a;
                mx[i*2]=a;
                mxx[i*2]=a;
                mii[i*2]=a;
                sum[i*2]=1LL*a*(mid-l+1);
                siz_min[i*2]=siz_max[i*2]=mid-l+1;
            }else{
                if(mi[i]>mi[i*2])sum[i*2]+=1LL*(mi[i]-mi[i*2])*siz_min[i*2];
                if(mx[i]<mx[i*2])sum[i*2]+=1LL*(mx[i]-mx[i*2])*siz_max[i*2];
                mx[i*2]=min(mx[i],mx[i*2]);
                mi[i*2]=max(mi[i],mi[i*2]);
                mxx[i*2]=max(mxx[i*2],mi[i*2]);
                mii[i*2]=min(mii[i*2],mx[i*2]);
            }
            if(mi[i*2+1]==mx[i*2+1]){
                int mid=(l+r)/2;
                int a=0;
                if(mi[i]>mi[i*2+1])a=mi[i];
                if(mx[i]<mx[i*2+1])a=mx[i];
                if(mi[i]<=mi[i*2+1]&&mx[i]>=mx[i*2+1])a=mx[i*2+1];
                mi[i*2+1]=a;
                mx[i*2+1]=a;
                mxx[i*2+1]=a;
                mii[i*2+1]=a;
                sum[i*2+1]=1LL*a*(r-mid);
                siz_min[i*2+1]=siz_max[i*2+1]=r-mid;
            }else{
                if(mi[i]>mi[i*2+1])sum[i*2+1]+=1LL*(mi[i]-mi[i*2+1])*siz_min[i*2+1]; 
                if(mx[i]<mx[i*2+1])sum[i*2+1]+=1LL*(mx[i]-mx[i*2+1])*siz_max[i*2+1]; 
                mx[i*2+1]=min(mx[i],mx[i*2+1]);
                mi[i*2+1]=max(mi[i],mi[i*2+1]);
                mxx[i*2+1]=max(mxx[i*2+1],mi[i*2+1]);
                mii[i*2+1]=min(mii[i*2+1],mx[i*2+1]);
            }
         }
    }
    int update(int i,int l,int r){
        int mid=(l+r)/2;
    //  pushdown(i,l,r);
        pushdown(i*2,l,mid);
        pushdown(i*2+1,mid+1,r);
        sum[i]=sum[i*2]+sum[i*2+1];
        q[1]=mi[i*2];
        q[2]=mi[i*2+1];
        q[3]=mx[i*2];
        q[4]=mx[i*2+1];
        q[5]=mii[i*2];
        q[6]=mii[i*2+1];
        q[7]=mxx[i*2];
        q[8]=mxx[i*2+1];
        sort(q+1,q+1+8);
        mi[i]=q[1];
        for(int j=2;j<=8;j++)if(q[j]!=q[1]){mii[i]=q[j];break;}
        if(q[8]==q[1])mii[i]=mi[i];
        mx[i]=q[8];
        for(int j=7;j>=1;j--)if(q[j]!=q[8]){mxx[i]=q[j];break;}
        if(q[8]==q[1])mxx[i]=mx[i];
        siz_min[i]=0;
        siz_max[i]=0;
        if(mi[i*2]==mi[i])siz_min[i]+=siz_min[i*2];
        if(mi[i*2+1]==mi[i])siz_min[i]+=siz_min[i*2+1];
        if(mx[i*2]==mx[i])siz_max[i]+=siz_max[i*2];
        if(mx[i*2+1]==mx[i])siz_max[i]+=siz_max[i*2+1];
        sum[i]=sum[i*2]+sum[i*2+1];
    }
    int build(int i,int l,int r){
        if(l==r){
            mx[i]=a[l];
            mxx[i]=a[l];
            mi[i]=a[l];
            mii[i]=a[l];
            sum[i]=a[l];
            siz_max[i]=1;
            siz_min[i]=1;
            return 0;
        }
        int mid=(l+r)/2;
        build(i*2,l,mid);
        build(i*2+1,mid+1,r);
        update(i,l,r);
    }
    int insert(int i,int l,int r,int x,int y,int a){
        pushdown(i,l,r);
        if(x<=l&&y>=r){
            tag[i]+=a;
            pushdown(i,l,r);
            return 0;
        }
        int mid=(l+r)/2;
        if(x<=mid)insert(i*2,l,mid,x,y,a);
        if(y>mid)insert(i*2+1,mid+1,r,x,y,a);
        update(i,l,r);
    }
    int insert_min(int i,int l,int r,int x,int y,int a){
        pushdown(i,l,r);
        if(x<=l&&y>=r){
            if(a>=mx[i])return 0;
            if(a<mi[i]){
                mx[i]=mi[i]=mxx[i]=mii[i]=a;
                sum[i]=1LL*a*(r-l+1);
                siz_max[i]=siz_min[i]=(r-l+1);
                return 0;
            }
            if(a>mxx[i]&&a<mx[i]){
                sum[i]-=1LL*mx[i]*siz_max[i];
                sum[i]+=1LL*a*siz_max[i];
                mx[i]=a;
                mii[i]=min(mii[i],a);
                mxx[i]=min(mxx[i],a);
                mx[i]=min(mx[i],a);
                return 0;
            }
            if(l==r)return 0;
            int mid=(l+r)/2;
            if(x<=mid)insert_min(i*2,l,mid,x,y,a);
            if(y>mid)insert_min(i*2+1,mid+1,r,x,y,a);
            update(i,l,r);
        }
        int mid=(l+r)/2;
        if(x<=mid)insert_min(i*2,l,mid,x,y,a);
        if(y>mid)insert_min(i*2+1,mid+1,r,x,y,a);
        update(i,l,r);
    }
    int insert_max(int i,int l,int r,int x,int y,int a){
        pushdown(i,l,r);
        if(x<=l&&y>=r){
            if(a<=mi[i])return 0;
            if(a>mx[i]){
                mx[i]=mi[i]=mxx[i]=mii[i]=a;
                sum[i]=1LL*a*(r-l+1);
                siz_max[i]=siz_min[i]=(r-l+1);
                return 0;
            }
            if(a<mii[i]&&a>mi[i]){
                sum[i]-=1LL*mi[i]*siz_min[i];
                sum[i]+=1LL*a*siz_min[i];
                mi[i]=a;
                mii[i]=max(mii[i],a);
                mxx[i]=max(mxx[i],a);
                mx[i]=max(mx[i],a);
                return 0;
            }
            if(l==r)return 0;
            int mid=(l+r)/2;
            if(x<=mid)insert_max(i*2,l,mid,x,y,a);
            if(y>mid)insert_max(i*2+1,mid+1,r,x,y,a);
            update(i,l,r);
        }
        int mid=(l+r)/2;
        if(x<=mid)insert_max(i*2,l,mid,x,y,a);
        if(y>mid)insert_max(i*2+1,mid+1,r,x,y,a);
        update(i,l,r);
    }
    long long query(int i,int l,int r,int x,int y){
        pushdown(i,l,r);
        if(x<=l&&y>=r)return sum[i];
        long long ans=0;
        int mid=(l+r)/2;
        if(x<=mid)ans+=query(i*2,l,mid,x,y);
        if(y>mid)ans+=query(i*2+1,mid+1,r,x,y);
//      printf("%d %d %d\n",max(l,x),min(y,r),ans);
        return ans;
    }
    int query_min(int i,int l,int r,int x,int y){
        pushdown(i,l,r);
        if(x<=l&&y>=r)return mi[i];
        int ans=0x7fffffff;
        int mid=(l+r)/2;
        if(x<=mid)ans=min(ans,query_min(i*2,l,mid,x,y));
        if(y>mid)ans=min(ans,query_min(i*2+1,mid+1,r,x,y));
        return ans;
    }
    int query_max(int i,int l,int r,int x,int y){
        pushdown(i,l,r);
        if(x<=l&&y>=r)return mx[i];
        int ans=-0x7fffffff;
        int mid=(l+r)/2;
        if(x<=mid)ans=max(ans,query_max(i*2,l,mid,x,y));
        if(y>mid)ans=max(ans,query_max(i*2+1,mid+1,r,x,y));
        return ans;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    seg::build(1,1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int type;
        scanf("%d",&type);
        if(type==1){
            int x,y,a;
            scanf("%d%d%d",&x,&y,&a);
            seg::insert(1,1,n,x,y,a);
        }
        if(type==2){
            int x,y,a;
            scanf("%d%d%d",&x,&y,&a);
            seg::insert_max(1,1,n,x,y,a);
        }
        if(type==3){
            int x,y,a;
            scanf("%d%d%d",&x,&y,&a);
            seg::insert_min(1,1,n,x,y,a);
        }
        if(type==4){
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",seg::query(1,1,n,x,y));
        }
        if(type==5){
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",seg::query_max(1,1,n,x,y));
        } 
        if(type==6){
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",seg::query_min(1,1,n,x,y));
        }
    }
}

「雅礼集训 2017 Day2」线段游戏

2018-10-07

题意:

    给出若干条线段,用 (x1,y2)(x_1,y_2) , (x2,y2)(x_2,y_2)表示其两端点坐标,现在要求支持两种操作:

    0,x1,y1,x2,y20,x_1,y_1,x_2,y_2 表示加入一条新的线段 (x1,y2)(x_1,y_2) , (x2,y2)(x_2,y_2)

    11 , x0x_0 询问所有线段中,xx坐标在 x0x_0 处的最高点的yy坐标是什么,如果对应位置没有线段,则输出 00

题解:

    线段树维护区间中位数值最大,可易证最终答案一定是线段树上某个区间的最大值。(注意数据中有竖线

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 1200000
#define O 320000
#define inf 10000000000
#define get(x,k,b) (x*k+b) 
using namespace std;
int n,m;
namespace seg{
	long double tk[N],tb[N],ans;
	int build(int i,int l,int r){
		tb[i]=-inf;
		if(l==r)return 0;
		int mid=(l+r)/2;
		build(i*2,l,mid);
		build(i*2+1,mid+1,r);
	}
	int insert(int i,int l,int r,long double k,long double b,int x,int y){
		if(x<=l&&y>=r){
			int mid=(l+r)/2;
			if(get(l,tk[i],tb[i])<get(l,k,b)&&get(r,tk[i],tb[i])<get(r,k,b)){
				tk[i]=k;
				tb[i]=b;
				return 0;
			}
			if(get(l,tk[i],tb[i])>get(l,k,b)&&get(r,tk[i],tb[i])>get(r,k,b))return 0;
			long double ll=get(mid,k,b);
			long double rr=get(mid,tk[i],tb[i]);
			if(ll>rr){
				if(l==r)return 0;
				if(k>tk[i])insert(i*2,l,mid,tk[i],tb[i],x,y);
				else insert(i*2+1,mid+1,r,tk[i],tb[i],x,y);
				tk[i]=k;
				tb[i]=b;
				return 0;
			}else{
				if(l==r)return 0;
				if(k>tk[i])insert(i*2+1,mid+1,r,k,b,x,y);
				else insert(i*2,l,mid,k,b,x,y);
				return 0;
			}
			return 0;
		}
		int mid=(l+r)/2;
		if(x<=mid)insert(i*2,l,mid,k,b,x,y);
		if(y>mid)insert(i*2+1,mid+1,r,k,b,x,y);
	}
	int query(int i,int l,int r,int x){
		if(i==1)ans=-inf;
		ans=max(ans,get(x,tk[i],tb[i]));
		if(l==r)return 0;
		int mid=(l+r)/2;
		if(x<=mid)query(i*2,l,mid,x);
		else query(i*2+1,mid+1,r,x);
	}
}
int insert(){
	int xa,ya,xb,yb;
	scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
	xa++;
	xb++;
	if(xa>xb){
		swap(xa,xb);
		swap(ya,yb);
	}
	long double k=(long double)(yb-ya+0.0)/(xb-xa);
	long double b=ya-k*xa;
	if(xa==xb)k=0,b=max(ya,yb);
	xa=max(1,xa);
	xa=min(xa,O);
	xb=max(1,xb);
	xb=min(xb,O);
	seg::insert(1,1,O,k,b,xa,xb);
}
int main(){
	scanf("%d%d",&n,&m);
	seg::build(1,1,O);
	for(int i=1;i<=n;i++)insert();
	for(int i=1;i<=m;i++){
		int type;
		scanf("%d",&type);
		if(type==0)insert();
		if(type==1){
			int x;
			scanf("%d",&x);
			x++;
			seg::query(1,1,O,x);
			if(seg::ans<=-inf+1){
				printf("0.0000000\n");
				continue;
			}
			printf("%5Lf\n",seg::ans);
		}
	}
} 

K相等

2018-10-07

题目:img

题解:

    大分类讨论加上大人类智慧(大概就是用人类智慧锁定哪k位不变,再用人类智慧来找后继,最后再上下波动搜索一下就能解决。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
long long n,k,bns;
long long cal(long long x){
    long long ans=0;
    while(x){
        long long o=x%10;
        if(o==4||o==7)ans++;
        x/=10;
    }
    return ans;
}
long long check(long long x,long long y){
    for(long long i=1;i<=k;i++){
        if(cal(x)!=cal(y))return 0;
        x++;
        y++;
    } 
    return 1;
}
long long Next(long long x,int p){
    long long y=x+1;
    long long o=cal(y)-cal(x)+p;
    if(x==0&&p!=0)return 10000;
    if(o==0)return y;
    if(o>0){
        long long z=y,k=1;
        while(z){
            long long p=z%10;
            if(p!=0)
                return y+k;
            k*=10;
            z/=10;
        }
    }
    if(o<0){
        int flag=0;
        if(x%10<4&&p<=-1)return x-x%10+4;
        if(x%10<7&&p<=-1)return x-x%10+7;
        if(x%10==4)return x-x%10+7;
        if(x%10==7)flag=1;
        long long Ans=Next(x/10,p-flag+1)*10+4;
        long long Bns=Next(x/10,p-flag)*10;
        if(cal(Bns)!=cal(x))return Ans;
        return min(Ans,Bns);
        return Ans;
    }
}
long long a[20];
int solve(){
    scanf("%lld%lld",&n,&k);
    long long m=n+k-1,l=1,L=0,c=n,flag=0,cns,o=0,O=0,f=k;
    bns=0;
    while(m>0){
        long long x=n%10,y=m%10;
        if(y!=0)flag=1;
        if(x!=y){
            L=l; 
            O=o;
        }
        bns=bns+l*x;
        o++;
        a[o]=x;
        n/=10;
        m/=10;
        l*=10;
        if(l>k)break;
    }
    L=max(1LL,L);
    n=c/L;
    k=(c+f-1)/L-(c)/L+1;
    if(f<=10&&f>=3&&(c%10==4||c%10==7)){
        k=1;
        for(int i=c-c%10+10;i<=c+f;i++)if(cal(i/10)!=cal(c/10))k=2;
        n=c/10;
        O++;
    }
    long long A=0,tot=0;
    for(long long i=Next(n,0);i;i=Next(i,0)){
        tot++;
        if(check(i,n)){
            A=i;
            for(long long i=O;i>=1;i--)A=A*10+a[i];
            k=f;
            for(int i=max(c+1,A-40);i<=A;i++)if(k<=100&&check(i,c)){
                printf("%lld\n",i);
                return 0;
            }
            printf("%lld\n",A);
            return 0;
        }
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--)solve();
}

Illyasviel的图游戏

2018-10-05

题意:

    Alice和Bob在玩游戏。

    他们有一张n个点m条边的带正权的简单无向图,其中除了1号点和n号点每个点度数小于等于2。

    Alice和Bob轮流操作,Alice先手,每次操作的人可以选择一条仍然存在的边,并且使得边权减一。如果有一条边边权减为了零,它会立即消失。

    在这张图上有一只Illyasviel想要从1号点走到n号点,如果在某个时刻Illyasviel不能从1号点走到n号点,他会十分生气并且判定上一个操作的玩家输。

    假设Alice和Bob都采取最优策略,请输出Alice是否可以获胜,是输出“Yes”, 否则输出“No”

题解:

    题目中对于图的限制可以看做 1 到 n 的所有简单路径互不相交。在结束游戏前的最后一步一定是剩下一条 1 到 n 的路径,并且路径上的权值全都是一。如果剩下的最后一条路径确定了,游戏的总步数也确定了,那么先后手的胜负也确定了。那么双方的策略就使尽可能使最后留下的路径是使自己必胜的路径,即尽可能切断使对方必胜的路径。切断一条路径需要的步数是这条路径上的权值的最小值。我们只需要比较双方切断对方必胜的路径所需要的步数即可。(此处是官方题解)

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 720000
using namespace std;
int tot,Next[N],v[N],h[N],w[N];
int n,p[N],m,bns;
long long L,R;
long long ans;
int add(int x,int y,int z){
    tot++;
    Next[tot]=h[x];
    v[tot]=y;
    w[tot]=z;
    h[x]=tot;
    return 0;
}
int dfs(int x,int a,int len){//L 奇 R 偶
    if(x==n){
        if(len&1)L+=a;
        else R+=a;
        return 1;
    }
    p[x]=1;
    int flag=0;
    for(int i=h[x];i;i=Next[i]){
        if(p[v[i]]==1&&v[i]!=n)continue;
        dfs(v[i],min(a,w[i]),len+1);
    }
    return flag;
}
int main(){
    tot=1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
        ans+=z;
    }
    dfs(1,0x7fffffff,0);
    if((((ans-1)&1)&&(L>=R))||(((ans)&1)&&(R>=L)))printf("Yes\n");
    else printf("No\n");
}

题目链接:Illyasviel的图游戏

复活

2018-10-05

    中间因为一些奇奇怪怪的系统和奇奇怪怪的事情停更了,今天又重新修好了√。从今天开始复更。

2018暑假计划

2018-08-01

总进度:(300/300)

总错误:

    MLE:1

    RE:1

    精度:1

    细节错误:2

    struct数组大会不稳定,namespace比较稳定:1

    树的重心:1

    可持久化的继承状态:1

2018-8-7

    SS(0/100)(构造+KMP)

    Tree Game(100/100) (博弈论)

    二元运算(100/100)(分治+FFT)

2018-8-6

    Tree(100/100)(树形DP)

    异或运算(100/100) (可持久化trie)

    Tree Restoring(10/100)(构造)

    Tree Restoring(10/100)(构造)

2018-7-31

    JLOI2015 战争调度(100/100)(树形DP)

    CQOI2015 选数(100/100)(莫比乌斯反演+杜教筛)

    YNOI2017 由乃的OJ(30/100)(树链剖分+贪心)场上没写完。

    总体而言没有大的失误,但C题没写完还是有点可惜,场后不到二十分钟就A掉了。

2018-7-31

    Mushroom 追妹纸(100/100)(二分加hash)

    抵制克苏恩(100/100)(概率与期望)

    烁烁的游戏(30/100)(可持久化线段树)一开始以为是n2n^2暴力乱搞题,后面发现不对,然后写可持久化线段树(最后场上没写出来的原因是新增的一条链没继承之前的状态)。没调出来就没敢交(幸亏没交)。

    终于又有训练赛打了。

2018-7-23

    礼物(100/100)

    小奇的博弈(20/100)(逻辑语句写错)

    烁烁的游戏(10/100)打的就是暴力,然后学了动态树分治,觉得这题蛮ok。

2018-7-22

(这场训练赛太水了,全部人都ak了,就不写了)

2018-7-21

训练赛:

    Division expression(100/100)

    清理雪道(100/100)

    奇数国(50/100)发现struct开大数组会不稳定,以后改用namespace

    场上得分(250/300)

    今天还去看了看前两天被卡技能树的拓展crt(我还是更喜欢抽出质因子直接crt),写了道模板题。

2018-7-20

NOI网络同步赛:

    第一题写了很久才过了大样例,但因为用了set以及crt合并时三个数直接乘在一起,再加上用的是lower_bound,从一百崩成五十,第二题没交上去。(CCF的服务器是真的垃圾。)

    总观这次同步赛,现在最大的问题不是我想不到,而是我眼高手低,手速跟不上自己的思维,并且没有完全理顺就开始写,以及注释加的不够,导致写的过程中较为混乱(场上大家都会进水,只是进多少的问题了。)。还有就是受环境干扰太大。接下来的训练中还得加强对代码复杂度较高的题的训练,并且还得再了解多一些编译原理,避免系统之间的误差出错。

    心中想到的做法是能进集训队的分,打出来的是却是铜牌靠前得分。从前路一直看过来,我的问题一直都不是思维不严谨,也不是粗心什么的,更不是运气。而是一个眼高手低的问题,学东西过于偏向于理论,而轻视实践。接下来的训练就是要排掉自己写的不熟的东西,加快自己的写码速度。

NOI2018 屠龙勇士

2018-7-19

训练赛:

    PRZ(100/100)

    Race(37/100)错因:求重心时返回值出错

    Milk Patterns(100/100)

    场上得分(237/300)

2018-7-18

NOI网络同步赛:

    A了一题,剩下的暴力一分没拿,算上送的笔试(140/350),不过比较不擅长的字符串考完了(68分送的,然而最后一小时自闭了,没写出来。)希望后天能翻盘吧。

NOI 2018归程

2018-7-17

训练赛:

    Find the outlier(0/100)eps精度出错

    征服王(0/100)想当然地写然后思路错误

    相似字串(0/100)模板打错

    场上得分(0/300)

    今天的情绪不是很高,文化课炸了,虽然早就有预计,但这样下去不太行。接下来的日子里不仅是OI得搞,文化课也得补了,计划暑假得把理综的知识点和英语的单词语法给搞定了。

    在课堂上觉得十分没有效率,所以索性就放弃了,或许是不适应课堂的那种节奏吧。接下来全都是自学,也没有什么借口能给自己找了。总之按照之前布置的作业,把本该做的做了吧。

    今天还爆了0,真是充满负能量的一天,一晚上啥也没做,满脑子都是挥之不去的负面想法,后路是自己断的,现在想要重新准备后路的也是自己,相当于是把前段时间的工作都推到了暑假,策略上有点失误了。现在自己满脑子都是自己彻底失败的后果,也不是太清醒,明天就是网络同步赛,愿能给自己前段时间的一点交代吧。我不想否定我考前一个月逃各种课写码的时间,所以明天这种错误一定不能犯了啊。

    文化课炸了我找的借口是去搞OI了,而今天OI暴零了,我又想给自己找去文化课状态没回过来的借口。但这样应该是不行的啊。找再多借口也不能改变暴零的事情,找再多借口也挽回不了文化课已经远远落下,愿自己不再找借口,别人也不再帮我找借口,以后考砸了,只有一个原因,就是实力太垃圾。

    在qq里跟父母讲了近况,得到了理解和支持,虽然眼前是一片迷茫,但摸着黑也要走下去。我相信我的智商和付出。

    今天还刷了几题水题,但都觉得没有写题解的意义,不加入做题数。

2018-7-16

    大包子的完美组合

    等差子序列

    普通平衡树

训练赛:

    gcd(100/100)

    次小生成树 tree(100/100)

    k个串 kstring(10/100)失分原因:NM打反导致线段树节点不够。

    场上得分:(210/300)

2018-7-15

    JSOI2008 火星人prefix

    Bracket

    zuma

训练赛:

    兔子与樱花(100/100)

    矩阵乘法(100/100)

    聪聪可可(100/100)

    场上得分(300/300)

2018-7-14

    rank

    sequence

    string

训练赛:

    game with probability(100/100)

    病毒(100/100)

    Count on a tree(0/100)失分原因:MLE

    场上得分(200/300)