20191102 「HZOJ NOIP2019 Round #12」20191102模拟

先开坑。

md原题写挂我也真是。。。

100+20+10

白夜

打表大法吼

显然，不在环上的点对答案的贡献是 \((k-cycle)^{k-1}\) 。

打表得到环上的递推式，矩阵一下乘起来就好了。

#include<bits/stdc++.h>
using namespace std;

#define int long long

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=100007;
const int maxm=200007;
const int mod=998244353;

int n,T;
int Head[maxn],to[maxm],Next[maxm],tot=1;
int aa,bb,k;
bool vis[maxn];
int col[maxn];

int size[maxn],top[maxn],dep[maxn],fa[maxn];
int son[maxn];

void add(int x,int y){
    to[++tot]=y,Next[tot]=Head[x],Head[x]=tot;
}

namespace baoli{
    bool check(int x){
        vis[x]=1;
        for(int i=Head[x];i;i=Next[i]){
            int y=to[i];
            if(col[y]==col[x]) return false;
            if(vis[y]) continue;
            bool tmp=check(y);
            if(tmp==false) return false;
        }
        if(x==aa){
            if(col[aa]==col[bb]) return false;
            if(!vis[bb]){
                bool tmp=check(bb);
                if(tmp==false) return false;
            }
        }
        if(x==bb){
            if(col[aa]==col[bb]) return false;
            if(!vis[aa]){
                bool tmp=check(aa);
                if(tmp==false) return false;
            }
        }
        return true;
    }
    int dfs(int step){
        if(step==n+1){
            memset(vis,0,sizeof(vis));
            if(check(1)) return 1;
            else return 0;
        }
        int res=0;
        for(int i=1;i<=k;i++){
            col[step]=i;
            res=(res+dfs(step+1))%mod;
        }
        return res;
    }
    void MAIN(){
        while(T--){
            read(aa);read(bb);read(k);
            if(k==1&&n!=1){
                puts("0");continue;
            }
            printf("%lld\n",dfs(1));
        }
    }
}

namespace Try{
    struct Matrix{
        int mat[4][4],n;
        Matrix(){
            memset(mat,0,sizeof(mat));
            n=2;
        }
        void reset(){
            for(int i=1;i<=n;i++) mat[i][i]=1;
        }
    };
    Matrix Mul(Matrix a,Matrix b){
        Matrix c;c.n=a.n;
        int l=a.n;
        for(int i=1;i<=l;i++){
            for(int j=1;j<=l;j++){
                for(int k=1;k<=l;k++){
                    c.mat[i][j]+=(a.mat[i][k]*b.mat[k][j]%mod);
                    c.mat[i][j]%=mod;
                }
            }
        }
        return c;
    }
    Matrix fpow(Matrix x,int p){
        Matrix res;res.reset();
        while(p){
            if(p&1) res=Mul(res,x);p>>=1;
            x=Mul(x,x);
        }
        return res;
    }
    int ksm(int x,int p){
        int res=1;
        while(p){
            if(p&1) res=res*x%mod;p>>=1;
            x=x*x%mod;
        }
        return res;
    }
    void dfs1(int x,int f,int dp){
        dep[x]=dp,fa[x]=f,size[x]=1;
        int mx=-1;
        for(int i=Head[x];i;i=Next[i]){
            int y=to[i];
            if(y==f) continue;
            dfs1(y,x,dp+1);
            size[x]+=size[y];
            if(size[y]>mx) son[x]=y,mx=size[y];
        }
    }
    void dfs2(int x,int tp){
        top[x]=tp;
        if(!son[x]) return;
        dfs2(son[x],tp);
        for(int i=Head[x];i;i=Next[i]){
            int y=to[i];
            if(y==son[x]||y==fa[x]) continue;
            dfs2(y,y);
        }
    }
    int lca(int x,int y){
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            x=fa[top[x]];
        }
        if(dep[x]>dep[y]) swap(x,y);
        return x;
    }
    int calc(int cyc){
        if(cyc==1) return 0;
        if(cyc==2){
            return k*(k-1)%mod;
        }
        Matrix base,ans;
        base.mat[1][1]=k-2,base.mat[1][2]=k-1,base.mat[2][1]=1;
        ans.mat[1][1]=k*(k-1)%mod;
        ans=Mul(ans,fpow(base,cyc-2));
        return ans.mat[1][1];
    }
    void MAIN(){
        dfs1(1,0,1);dfs2(1,1);
        int x,y,ans=0;
        while(T--){
            read(x);read(y);read(k);
            int lc=lca(x,y);int cyc=dep[x]+dep[y]-2*dep[lc]+1;
            ans=ksm(k-1,n-cyc);
            ans=(ans*calc(cyc))%mod;
            printf("%lld\n",ans);
        }
    }
}

signed main(){
    freopen("night.in","r",stdin);freopen("night.out","w",stdout);
    read(n);
    for(int x,i=2;i<=n;i++){
        read(x);
        add(x,i);add(i,x);
    }
    read(T);
    Try::MAIN();
    fclose(stdin);fclose(stdout);
    return 0;
}

光明

区间最大字段和

GSS系列

样例太弱了...

这题被 \(O(n^2)\) 氧化钙过去了。。。

订正后代码：

using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=100007;

int n,T;
int w[maxn];
int xx[maxn],yy[maxn];
#define lfc (x<<1)
#define rgc ((x<<1)|1)
#define mid ((l+r)>>1)

struct node{
    int sum,lf,rg,val;
};

int sum[maxn<<2],val[maxn<<2],rg[maxn<<2],lf[maxn<<2];

void pushup(int x){
    sum[x]=sum[lfc]+sum[rgc];
    lf[x]=max(lf[lfc],sum[lfc]+lf[rgc]);
    rg[x]=max(rg[rgc],sum[rgc]+rg[lfc]);
    val[x]=max(max(val[lfc],val[rgc]),lf[rgc]+rg[lfc]);
}

void build(int x,int l,int r){
    if(l==r){
        int fff=1;
        if(xx[l]%2==1&&yy[l]%2==1) fff=-1;
        val[x]=sum[x]=lf[x]=rg[x]=fff*w[l];return;
    }
    build(lfc,l,mid);build(rgc,mid+1,r);
    pushup(x);
}

int L,R,need;

node query(int x,int l,int r){
    if(L<=l&&r<=R) return (node){sum[x],lf[x],rg[x],val[x]};
    if(L>mid) return query(rgc,mid+1,r);
    if(R<=mid) return query(lfc,l,mid);
    node res,a1=query(lfc,l,mid),a2=query(rgc,mid+1,r);
    res.sum=a1.sum+a2.sum;
    res.lf=max(a1.lf,a1.sum+a2.lf);
    res.rg=max(a2.rg,a1.rg+a2.sum);
    res.val=max(max(a1.val,a2.val),a1.rg+a2.lf);
    return res;
}

void change_val(int x,int l,int r){
    if(l==r){
        int fff=1;
        if(xx[l]%2==1&&yy[l]%2==1) fff=-1;
        val[x]=sum[x]=lf[x]=rg[x]=fff*need;
        return;
    }
    if(L<=mid) change_val(lfc,l,mid);
    else change_val(rgc,mid+1,r);
    pushup(x);
}

int fffff;

void change_qf(int x,int l,int r){
    if(l==r){
        sum[x]=lf[x]=rg[x]=val[x]=-w[l]*fffff;
        return;
    }
    if(L<=mid) change_qf(lfc,l,mid);
    else change_qf(rgc,mid+1,r);
    pushup(x);
}

void cz1(){
    int a,b;
    read(L);read(a);read(b);
    if(a%2==1&&b%2==1){fffff=1;
        change_qf(1,1,n);}
    else{
        fffff=-1;
        change_qf(1,1,n);
    }
    xx[L]=a,yy[L]=b;
}

void cz2(){
    read(L);read(need);
    change_val(1,1,n);
    w[L]=need;
}

void cz3(){
    read(L);read(R);
    printf("%d\n",query(1,1,n).val);
}

int main(){
    freopen("light.in","r",stdin);freopen("light.out","w",stdout);
    read(n);
    for(int i=1;i<=n;i++) read(w[i]);
    for(int i=1;i<=n;i++){
        read(xx[i]);read(yy[i]);
    }
    build(1,1,n);
    read(T);int op;
    while(T--){
        read(op);
        if(op==1) cz1();
        if(op==2) cz2();
        if(op==3) cz3();
    }
    return 0;
}

暗雪

区间Dp+四边形不等式优化

这题数据被 \(O(n^4)\) 氧化钙过去了。

#include<bits/stdc++.h>
using namespace std;

#define int long long

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=407;
const int INF=1e18;

int n,kk,a[maxn];
int dp[maxn][maxn][maxn];
int opt[maxn][maxn],s[maxn];

void Init(){
    read(n);read(kk);
    if(kk<=9&&(1<<kk)<n){
        puts("-1");exit(0);
    }
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
}

void Work(){
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if(i==j) dp[i][j][0]=0;
            else dp[i][j][0]=INF;
        }
    }
    for(int k=1;k<=kk;k++){
        for(int i=1;i<=n;i++) opt[i][i]=i;
        for(int len=2;len<=n;len++){
            for(int l=1;l+len-1<=n;l++){
                int r=l+len-1;
                dp[l][r][k]=INF;
                for(int p=opt[l][r-1];p<=opt[l+1][r];p++){
                    if(p+1>r) continue;
                    int val=dp[l][p][k-1]+dp[p+1][r][k-1]+s[r]-s[l-1];
                    if(val<dp[l][r][k]){
                        dp[l][r][k]=val;opt[l][r]=p;
                    }
                }
            }
        }
    }
    int div=__gcd(dp[1][n][kk],s[n]);
    printf("%lld/%lld\n",dp[1][n][kk]/div,s[n]/div);
}

signed main(){
    freopen("snow.in","r",stdin);freopen("snow.out","w",stdout);
    Init();
    Work();
    return 0;
}