GXOI/GZOI2019题解

P5300 [GXOI/GZOI2019]与或和

一眼题。。

显然枚举每个二进制位，答案就变成了全1子矩阵数量。

这个xjb推推，单调栈一下就行了。

#include<bits/stdc++.h>

#define il inline

#define vd void

#define mod 1000000007

typedef long long ll;

il ll gi(){

    ll x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch))f^=ch=='-',ch=getchar();

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int n,A[1010][1010],f[1010][1010];

bool B[1010][1010];

int stk[1010],stkp[1010],tp;

il int calc(bool p){

    for(int i=1;i<=n;++i)

        for(int j=n;j;--j)

            if(B[i][j]^p)f[i][j]=f[i][j+1]+1;

            else f[i][j]=0;

    int ret=0,res=0;

    for(int j=1;j<=n;++j){

        stkp[tp=0]=n+1;res=0;

        for(int i=n;i;--i){

            while(tp&&stk[tp]>=f[i][j])res=(res-1ll*(stkp[tp-1]-stkp[tp])*stk[tp]%mod+mod)%mod,--tp;

            stk[++tp]=f[i][j];stkp[tp]=i;

            res=(res+1ll*(stkp[tp-1]-stkp[tp])*stk[tp])%mod;

            ret=(ret+res)%mod;

        }

    }

    return ret;

}

int main(){

#ifdef XZZSB

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    n=gi();

    for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)A[i][j]=gi();

    int ans1=0,ans2=0,total=0;

    for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)total=(total+i*j)%mod;

    for(int o=0;o<32;++o){

        for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)B[i][j]=(A[i][j]>>o)&1;

        ans1=(ans1+(calc(0)*1ll<<o))%mod;

        ans2=(ans2+((1ll*(total-calc(1)+mod)%mod)*1ll<<o))%mod;

    }

    printf("%d %d\n",ans1,ans2);

    return 0;

}

P5301 [GXOI/GZOI2019]宝牌一大堆

牛皮！

国士无双显然可以暴力，7对子显然可以贪心，18张牌的胡牌显然没有用，可以用17张替代。

剩下的情况可以直接dp，设$f[i][j]$表示出完了前i种牌，有j个杠子k个面子l个雀头，而且有p个i-1,i,i+1的面子，q个i,i+1,i+2的面子的最大乘积。转移的时候枚举是否组成杠子/刻子/雀头，以及面子i+1,i+2,i+3的数量暴力转移即可。

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il ll gi(){

    ll x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch))f^=ch=='-',ch=getchar();

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

std::map<std::string,int>id;

int cnt[38],m,multi[38];

int C[5][5],p2[]={1,2,4,8,16};

ll f[36][4][5][2][3][3];

il vd chkmx(ll&a,ll b){if(b>a)a=b;}

int yes[40]={0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1};

//f[i][j][k][l][p][q] 出完了前i种牌 有j个杠子 k个面子 l个雀头 p个i-1,i,i+1的面子 q个i,i+1,i+2的面子

int main(){

#ifdef XZZSB

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    C[0][0]=1;for(int i=1;i<5;++i){C[i][0]=1;for(int j=1;j<=i;++j)C[i][j]=C[i-1][j-1]+C[i-1][j];}

    for(int i=1;i<10;++i)id[(char)(i+'0')+std::string("m")]=++m;

    for(int i=1;i<10;++i)id[(char)(i+'0')+std::string("p")]=++m;

    for(int i=1;i<10;++i)id[(char)(i+'0')+std::string("s")]=++m;

    id["E"]=++m;id["S"]=++m;id["W"]=++m;id["N"]=++m;

    id["Z"]=++m;id["B"]=++m;id["F"]=++m;

    int orzyyb=gi();

    while(orzyyb--){

        memset(multi,0,sizeof multi);

        for(int i=1;i<=m;++i)cnt[i]=4;

        ll ans=0;

        std::string s;

        while(std::cin>>s,s!="0")--cnt[id[s]];

        while(std::cin>>s,s!="0")++multi[id[s]];

        /* 国士无双 直接枚举多的一张牌 */

        {	int prz[]={1,9,10,18,19,27,28,29,30,31,32,33,34};

            ll res=1;

            for(int i=0;i<13;++i){

                if(multi[prz[i]])res*=2;

                res*=cnt[prz[i]];

            }

            if(res)

                for(int i=0;i<13;++i)

                    chkmx(ans,res/cnt[prz[i]]*C[cnt[prz[i]]][2]*(multi[prz[i]]?2:1)*13);

        }

        /* 7对子 直接贪心选最好的7个 */

        {	std::vector<ll>s;

            for(int i=1;i<=m;++i)s.push_back(C[cnt[i]][2]*(multi[i]?4:1));

            std::sort(s.begin(),s.end(),std::greater<int>());

            ll res=1;for(int i=0;i<7;++i)res*=s[i];

            chkmx(ans,res*7);

        }

        //剩下的情况，dp

        //18张牌没有用，显然把一个杠子换成面子不会更坏

        memset(f,0,sizeof f);

        f[0][0][0][0][0][0]=1;

        for(int i=1;i<=m;++i)

            for(int j=0;j<4;++j)

                for(int k=0;k<5-j;++k)

                    for(int l=0;l<2;++l)

                        for(int p=0;p<3;++p)

                            for(int q=0;q<3-p;++q){

                                if(!f[i-1][j][k][l][p][q])continue;

                                const ll nowf=f[i-1][j][k][l][p][q];

                                if(cnt[i]==4&&j!=3&&!p&&!q)chkmx(f[i][j+1][k][l][q][0],nowf*(multi[i]?16:1));//组成一个杠子

                                for(int s3=0;s3<2;++s3){//是否组成一个刻子

                                    for(int s2=0;s2<2-s3;++s2){//是否组成一个雀头

                                        for(int r=0;r<3;++r){//枚举顺子i,i+1,i+2的数量

                                            int total=s3*3+s2*2+r+p+q;

                                            if(cnt[i]<total)continue;

                                            if(k+s3+r>4-j)continue;

                                            if(cnt[i+1]<q+r)continue;

                                            if(cnt[i+2]<r)continue;

                                            if(l+s2>1)continue;

                                            if(r&&!yes[i])continue;//ctmd 顺子要求相同种类

                                            chkmx(f[i][j][k+s3+r][l+s2][q][r],nowf*C[cnt[i]][total]*(multi[i]?p2[total]:1));

                                        }

                                    }

                                }

                            }

        chkmx(ans,f[m][0][4][1][0][0]);

        chkmx(ans,f[m][1][3][1][0][0]);

        chkmx(ans,f[m][2][2][1][0][0]);

        chkmx(ans,f[m][3][1][1][0][0]);

        printf("%lld\n",ans);

    }

    return 0;

}

P5302 [GXOI/GZOI2019]特技飞行

二合一可还行

显然$a,b$的系数和$c$的系数是两个独立的问题，$c$的系数直接将坐标系转45度就变成sb扫描线了。

算$a,b$的系数是显然全都对向交换是一种合法的极端情况，还有一种极端情况就是尽量多的擦肩而过。

这个因为zsy博客里是这么写的，所以问题就是交换任意两个元素的排序使得交换次数最小。

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il ll gi(){

    ll x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch))f^=ch=='-',ch=getchar();

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int n,a,b,c,xst,xed,k;

int Y0[100010],Y1[100010];

int p[100010],q[100010],r[100010];

double lk[100010],lb[100010];

int Y[100010],_Y0[100010],_Y1[100010];

std::vector<std::pair<double,double>>nodes;

il std::pair<double,double>cross(int x,int y){

    double k1=lk[x],b1=lb[x],k2=lk[y],b2=lb[y];

    double X=(b1-b2)/(k2-k1),Y=k1*X+b1;

    return{X,Y};

}

namespace solve1{

    int t[100010];

    std::vector<int>vec[100010];

    il vd update(int x,int i){while(x<=n)t[x]++,vec[x].push_back(i),x+=x&-x;}

    il int query(int x,int i){

        int r=0;

        while(x){

            for(auto j:vec[x])nodes.push_back(cross(i,j));

            r+=t[x];x-=x&-x;

        }

        return r;

    }

    il int work(){

        int ans=0;

        for(int i=1;i<=n;++i)Y[i]=std::lower_bound(_Y1+1,_Y1+n+1,Y1[i])-_Y1;

        for(int i=1;i<=n;++i)ans+=query(n-Y[i]+1,i),update(n-Y[i]+1,i);

        return ans;

    }

}

namespace solve2{

    bool vis[100010];

    int yy[100010];

    il int work(){

        for(int i=1;i<=n;++i)yy[Y[i]]=i;

        int ret=n;

        for(int i=1;i<=n;++i){

            if(vis[i])continue;

            for(int j=yy[i];!vis[j];j=yy[j])vis[j]=1;

            --ret;

        }

        return ret;

    }

}

namespace solve3{

    struct update{double x,l,r,d;}s[200010];

    struct query{double x,y;}qu[500010];

    int M,Q;

    double yy[400010];int sy,N;

    int t[800010];

    il vd _update(int x,int d){while(x<=N)t[x]+=d,x+=x&-x;}

    il int _query(int x){

        int r=0;

        while(x)r+=t[x],x-=x&-x;

        return r;

    }

    template<class T>il vd trans(T&a,T&b){

        T _a=a,_b=b;

        a=_a+_b,b=_a-_b;

    }

    il int work(){

        for(int i=1;i<=k;++i){

            double x1=p[i],y1=q[i]-r[i],x2=p[i],y2=q[i]+r[i];

            trans(x1,y1);trans(x2,y2);

            if(x1>x2)std::swap(x1,x2);

            if(y1>y2)std::swap(y1,y2);

            y1-=1e-7,y2+=1e-7;

            s[++M]={x1,y1,y2,1},s[++M]={x2+1e-7,y1,y2,-1};

            yy[++sy]=y1;yy[++sy]=y2;

        }

        std::sort(yy+1,yy+sy+1);sy=std::unique(yy+1,yy+sy+1)-yy-1;

        N=sy*2+2;

        for(int i=1;i<=M;++i)s[i].l=std::lower_bound(yy+1,yy+sy+1,s[i].l)-yy;

        for(int i=1;i<=M;++i)s[i].r=std::lower_bound(yy+1,yy+sy+1,s[i].r)-yy;

        for(auto i:nodes){double x=i.first,y=i.second;trans(x,y);qu[++Q]={x,y};}

        std::sort(s+1,s+M+1,[](const update&a,const update&b){return a.x<b.x;});

        std::sort(qu+1,qu+Q+1,[](const query&a,const query&b){return a.x<b.x;});

        int i=1,j=1,ret=0;

        while(i<=M||j<=Q)

            if((s[i].x<qu[j].x+1e-7&&(i<=M))||(j>Q))_update(s[i].l*2,s[i].d),_update(s[i].r*2+1,-s[i].d),++i;

            else{

                int p=std::lower_bound(yy+1,yy+sy+1,qu[j].y)-yy;

                if(fabs(qu[j].y-yy[p])<1e-7)p*=2;

                else p=p*2-1;

                if(_query(p))++ret;

                ++j;

            }

        return ret;

    }

}

int main(){

#ifdef XZZSB

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    n=gi(),a=gi(),b=gi(),c=gi(),xst=gi(),xed=gi();

    for(int i=1;i<=n;++i)Y0[i]=gi();

    for(int i=1;i<=n;++i)Y1[i]=gi();

    for(int i=1;i<=n;++i)lk[i]=1.0*(Y0[i]-Y1[i])/(xst-xed),lb[i]=Y1[i]-xed*lk[i];

    k=gi();

    for(int i=1;i<=k;++i)p[i]=gi(),q[i]=gi(),r[i]=gi();

    for(int i=1;i<=n;++i)_Y0[i]=Y0[i],_Y1[i]=Y1[i];

    std::sort(_Y0+1,_Y0+n+1);std::sort(_Y1+1,_Y1+n+1);

    std::unique(_Y0+1,_Y0+n+1),std::unique(_Y1+1,_Y1+n+1);

    ll ans1,ans2;ans1=ans2=solve1::work();ans1=1ll*ans1*a;

    ans2=1ll*a*ans2+1ll*(b-a)*(ans2-solve2::work());

    if(ans1>ans2)std::swap(ans1,ans2);

    ll ans3=1ll*solve3::work()*c;

    printf("%lld %lld\n",ans1+ans3,ans2+ans3);

    return 0;

}

P5303 [GXOI/GZOI2019]逼死强迫症

设$f_n$表示$n$列的答案，那么考虑在左边放些什么东西。可以放一个$1\times 2$的竖块或者两个$2\times 1$的横块，或者放$1\times 1$的块。

如果放$1\times 1$的块，显然就要考虑另一个放哪。显然第$1$列不行，第$2$列也不行，不过第$3$到$n$列都可以找到一个地方可以（根据奇偶而定），而且如果放好了另一个，那么这两个块中间的$1\times 2$放法是确定的，只要考虑右边这一块的方案数，右边这一块显然是个斐波那契数。所以转移方程是$f_n=f_{n-1}+f_{n-2}+\sum_{i=0}^{n-3}fib_i(fib_0=fib_1=1)$。$\sum fib$在矩阵快速幂的时候顺便记一下就好了。

#include<bits/stdc++.h>

#define il inline

#define vd void

#define mod 1000000007

typedef long long ll;

il ll gi(){

    ll x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch))f^=ch=='-',ch=getchar();

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

struct matrix{int s[5][5];matrix(){memset(s,0,sizeof s);}}I,F,begin;

il matrix operator*(const matrix&a,const matrix&b){

    matrix ret;

    for(int j=0;j<5;++j)

        for(int i=0;i<5;++i)

            for(int k=0;k<5;++k)

                ret.s[i][k]=(ret.s[i][k]+1ll*a.s[i][j]*b.s[j][k])%mod;

    return ret;

}

il matrix operator^(matrix a,int b){

    matrix ret=I;

    while(b){

        if(b&1)ret=ret*a;

        a=a*a;b>>=1;

    }

    return ret;

}

struct ques{int n,i;}q[510];

int ans[510];

int main(){

#ifdef XZZSB

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    I.s[0][0]=I.s[1][1]=I.s[2][2]=I.s[3][3]=I.s[4][4]=1;

    F.s[0][1]=1;

    F.s[1][0]=F.s[1][1]=1;

    F.s[2][3]=F.s[2][4]=1;

    F.s[3][2]=F.s[3][3]=F.s[3][4]=1;

    F.s[4][1]=F.s[4][4]=1;

    begin.s[0][2]=1;

    int n=gi();

    for(int i=1;i<=n;++i)q[i].n=gi(),q[i].i=i;

    std::sort(q+1,q+n+1,[](const ques&a,const ques&b){return a.n<b.n;});

    matrix now=begin;

    q[0].n=1;for(int i=1;i<=n;++i)now=now*(F^(q[i].n-q[i-1].n)),ans[q[i].i]=now.s[0][1]*2%mod;

    for(int i=1;i<=n;++i)printf("%d\n",ans[i]);

    return 0;

}

P5304 [GXOI/GZOI2019]旅行者

一开始看见这题想到了cf1146c，可以用那种方法分治得到任意两个的最短路，复杂度$O(n\log^2n)$。

然后翻了一下提交记录好像他们都跑的飞快+代码巨短就去膜题解了。

stm。。。每一个点记录最近的关键点$dist_i$和反图上最近的关键点$dist2_i$，然后枚举每一条边直接算就行了。对于$(u,v,w)$就一定存在一条$dist2_u+dist_v+w$的路径。

如果一条边两个点最近的关键点相同就不能计入答案。所以我不知道这个方法为啥对，但确实是对的，也叉不掉。

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il ll gi(){

    ll x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch))f^=ch=='-',ch=getchar();

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int fir[100010],dis[1000010],nxt[1000010],w[1000010],id;

il vd link(int a,int b,int c){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;}

ll dist[100010];int d[100010];

ll dist2[100010];int d2[100010];

bool vis[100010];

std::priority_queue<std::pair<ll,int>>que;

int main(){

#ifdef XZZSB

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    int T=gi();

    while(T--){

        id=0;memset(fir,0,sizeof fir);

        int n=gi(),m=gi(),k=gi(),a,b,c;

        memset(dist+1,63,8*n);memset(dist2+1,63,8*n);

        while(m--)a=gi(),b=gi(),c=gi(),link(a,b,c),link(b,a,c);

        while(k--)a=gi(),dist[a]=dist2[a]=0,d[a]=d2[a]=a,que.push({0,a});

        memset(vis,0,sizeof vis);

        while(!que.empty()){

            int x=que.top().second;que.pop();

            if(vis[x])continue;vis[x]=1;

            for(int i=fir[x];i;i=nxt[i])

                if((i&1)&&dist[dis[i]]>dist[x]+w[i]){

                    dist[dis[i]]=dist[x]+w[i];d[dis[i]]=d[x];

                    que.push({-dist[dis[i]],dis[i]});

                }

        }

        for(int i=1;i<=n;++i)if(!dist[i])que.push({0,i});

        memset(vis,0,sizeof vis);

        while(!que.empty()){

            int x=que.top().second;que.pop();

            if(vis[x])continue;vis[x]=1;

            for(int i=fir[x];i;i=nxt[i])

                if(!(i&1)&&dist2[dis[i]]>dist2[x]+w[i]){

                    dist2[dis[i]]=dist2[x]+w[i];d2[dis[i]]=d2[x];

                    que.push({-dist2[dis[i]],dis[i]});

                }

        }

        ll ans=1e18;

        for(int i=1;i<=n;++i)

            for(int j=fir[i];j;j=nxt[j])

                if((j&1)&&d[i]!=d2[dis[j]])ans=std::min(ans,w[j]+dist[i]+dist2[dis[j]]);

        printf("%lld\n",ans);

    }

    return 0;

}

P5305 [GXOI/GZOI2019]旧词

[LNOI]LCA

[HNOI]开店

#include<bits/stdc++.h>

#define il inline

#define vd void

#define mod 998244353

typedef long long ll;

il ll gi(){

    ll x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch))f^=ch=='-',ch=getchar();

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

il int pow(int x,int y){

    int ret=1;

    while(y){

        if(y&1)ret=1ll*ret*x%mod;

        x=1ll*x*x%mod;y>>=1;

    }

    return ret;

}

int fir[50010],dis[50010],nxt[50010],id;

il vd link(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}

struct ques{int x,y,i;}s[50010];

il bool operator<(const ques&a,const ques&b){return a.x<b.x;}

int pk[50010],dfn[50010],dep[50010],son[50010],siz[50010],top[50010],dep_dfn[50010];

il vd dfs(int x){

    siz[x]=1;

    for(int i=fir[x];i;i=nxt[i]){

        dep[dis[i]]=dep[x]+1,dfs(dis[i]);

        siz[x]+=siz[dis[i]];

        if(siz[son[x]]<siz[dis[i]])son[x]=dis[i];

    }

}

il vd dfs(int x,int tp){

    top[x]=tp;dfn[x]=++dfn[0];dep_dfn[dfn[x]]=dep[x];

    if(son[x])dfs(son[x],tp);

    for(int i=fir[x];i;i=nxt[i])if(dis[i]!=son[x])dfs(dis[i],dis[i]);

}

int ans[50010];

#define mid ((l+r)>>1)

int sum[200010],val[200010],lz[200010],fa[200010];

il vd build(int x,int l,int r){

    if(l==r){val[x]=(pk[dep_dfn[l]]-pk[dep_dfn[l]-1]+mod)%mod;return;}

    build(x<<1,l,mid),build(x<<1|1,mid+1,r);

    val[x]=(val[x<<1]+val[x<<1|1])%mod;

}

il vd upd(int x,int d){lz[x]+=d;sum[x]=(sum[x]+1ll*d*val[x])%mod;}

il vd down(int x){if(lz[x])upd(x<<1,lz[x]),upd(x<<1|1,lz[x]),lz[x]=0;}

il vd update(int x,int l,int r,const int&L,const int&R){

    if(L<=l&&r<=R)return upd(x,1);

    down(x);

    if(L<=mid)update(x<<1,l,mid,L,R);

    if(mid<R)update(x<<1|1,mid+1,r,L,R);

    sum[x]=(sum[x<<1]+sum[x<<1|1])%mod;

}

il int query(int x,int l,int r,const int&L,const int&R){

    if(L<=l&&r<=R)return sum[x];

    down(x);

    if(L<=mid)

        if(mid<R)return(query(x<<1,l,mid,L,R)+query(x<<1|1,mid+1,r,L,R))%mod;

        else return query(x<<1,l,mid,L,R);

    else return query(x<<1|1,mid+1,r,L,R);

}

#undef mid

int main(){

#ifdef XZZSB

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    int n=gi(),Q=gi(),k=gi();

    for(int i=1;i<=n;++i)pk[i]=pow(i,k);

    for(int i=2;i<=n;++i)link(fa[i]=gi(),i);

    for(int i=1;i<=Q;++i)s[i].x=gi(),s[i].y=gi(),s[i].i=i;

    std::sort(s+1,s+Q+1);

    dep[1]=1;dfs(1);dfs(1,1);

    build(1,1,n);

    for(int i=1,p=1;i<=Q;++i){

        while(p<=s[i].x){

            for(int x=p;x;x=fa[top[x]])update(1,1,n,dfn[top[x]],dfn[x]);

            ++p;

        }

        for(int x=s[i].y;x;x=fa[top[x]])ans[s[i].i]=(ans[s[i].i]+query(1,1,n,dfn[top[x]],dfn[x]))%mod;

    }

    for(int i=1;i<=Q;++i)printf("%d\n",ans[i]);

    return 0;

}

GXOI/GZOI2019题解的更多相关文章

「GXOI / GZOI2019」简要题解
「GXOI / GZOI2019」简要题解 LOJ#3083. 「GXOI / GZOI2019」与或和 https://loj.ac/problem/3083 题意:求一个矩阵的所有子矩阵的与和和 ...
题解-GXOI/GZOI2019 特技飞行
Problem loj3085 bzoj不放题面差评题意概要:给出两条竖直直线,再给出 $n$ 架飞机的初始航线:一条接通这两条直线的线段,保证航线交点不在两条直线上.现要求安排所有飞机在航线相 ...
【BZOJ5505】[GXOI/GZOI2019]逼死强迫症（矩阵快速幂）
[BZOJ5505][GXOI/GZOI2019]逼死强迫症(矩阵快速幂) 题面 BZOJ 洛谷题解如果没有那两个$1*1$的东西,答案就是斐波那契数,可以简单的用$dp$得到. 大概是设 ...
P5305 [GXOI/GZOI2019]旧词
题目地址:P5305 [GXOI/GZOI2019]旧词这里是官方题解 \[\sum_{i \leq x}^{}\ depth(lca(i,y))^k\] $k = 1$ 求的是 \(\sum_ ...
P5304 [GXOI/GZOI2019]旅行者
题目地址:P5304 [GXOI/GZOI2019]旅行者这里是官方题解一个图 $n$ 点 $m$ 条边,里面有 $k$ 个特殊点,问这 $k$ 个点之间两两最短路的最小值是多少? ...
P5303 [GXOI/GZOI2019]逼死强迫症
题目地址:P5303 [GXOI/GZOI2019]逼死强迫症这里是官方题解初步分析从题目和数据范围很容易看出来这是一个递推 + 矩阵快速幂,那么主要问题在于递推的过程. 满足条件的答案一定是以 ...
P5302 [GXOI/GZOI2019]特技飞行
题目地址:P5302 [GXOI/GZOI2019]特技飞行这里是官方题解(by lydrainbowcat) 题意给 $10^5$ 条直线,给 $x = st$ 和 $x = ed$ ...
P5301 [GXOI/GZOI2019]宝牌一大堆
题目地址:P5301 [GXOI/GZOI2019]宝牌一大堆这里是官方题解(by lydrainbowcat) 部分分直接搜索可以得到暴力分,因为所有和牌方案一共只有一千万左右,稍微优化一下数据 ...
【BZOJ5502】[GXOI/GZOI2019]与或和（单调栈）
[BZOJ5502][GXOI/GZOI2019]与或和(单调栈) 题面 BZOJ 洛谷题解看到位运算就直接拆位,于是问题变成了求有多少个全$0$子矩阵和有多少个全$1$子矩阵. 这两个操 ...

随机推荐

【程序员技术练级】熟悉Unix/Linux Shell和常见的命令行（一）文件系统结构和基本操作
作为程序猿,熟悉一些unix/linux命令行是非常必要的,因为部署服务的服务器现在基本上用的都是unix/linux系统,很少在windows上部署服务的. 今天我们就介绍一些在linux上的文件系 ...
用80x86汇编语言编程：1 + 2 + 3 + 4 + 5 + …… + n，和小于100，在屏幕上显示次数和结果。
;============================================== ;1+...+n < 100 ;--------------------------------- ...
鼠标移入移出div div会消失的处理
<!DOCTYPE html> <html> <head lang="en"> <meta charset="UTF-8&quo ...
vector中删除第k个元素的巧妙方法
假设我们定义了一个vector如下: vector<int> v;v.push_back(1);...v.push_back(255); 如果要删除第k个元素的话,应该这样写: (1)如果 ...
ConcurrentModificationException异常出现的原因
原因:对list .map 等迭代的时进行修改就会抛出java.util.ConcurrentModificationException异常比如: public synchronized void ...
UDA机器学习基础—误差原因
1.模型误差产生的原因 (1)模型无法表示基本数据的复杂度,而造成偏差. (2)因模型对训练它所用到的数据过度敏感造成的方差. 2.由偏差造成的误差--准确率和欠拟合有足够数据表示模型,但是由于模型 ...
jQuery 让input里面的内容可以布局到页面上
<div id="selectBox"> </div> <div class="make"> <span class= ...
Spring Caching集成Ehcache
Ehcache可以对页面.对象.数据进行缓存,同时支持集群/分布式缓存.在应用中用于常常需要读取的数据交换,而不是通过DB DAO数据交换(cache不占用DB宝贵的NIO,直接交换堆内存). 整合S ...
详解 Redis 应用场景及应用实例
redis(二)高级用法详解 Redis 应用场景及应用实例 Redis 它是什么?它用来做什么?它的优势与短板如何? 告诉你Redis是一个牛逼货
input onchange事件
//输入帐号,默认赋值给员工电话和后台登录帐号$('#mobile_phone_').bind('input propertychange', function() { var phone = $(' ...