#7

无心随笔 / 2023-09-03 / 原文

电压

题面

JOISC的一道不错的题。

首先如果一条边在偶环上,这条边是不可能成为答案的。因为偶环黑白染色后一定是黑白相间的。反过来对于奇环,则必然有一条边两端颜色相同。因为题目要求有且只存在一条,所以可以为答案的边一定在所有奇环上,求出一棵生成树,对于一条非树边,如果构成奇环,则将树上对应的边和自己的边权加 \(1\),反之减 \(1\)。如果一条边边权等于构成的奇环的个数则可以为答案,反之不行。权值加减可以用树上差分或树剖+线段树。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=5e5+10,M=1e6+10;
int n,m,flag[M],edge_id[N];
struct edge{
    int u,v;
}e[M];
vector<pii>G[N];
namespace build{
    int fa[N];
    int getfa(int u){
        if(fa[u]!=u){
            fa[u]=getfa(fa[u]);
        }
        return fa[u];
    }
    void solve(){
        for(int i=1;i<=n;i++){
            fa[i]=i;
        }
        for(int i=1;i<=m;i++){
            int u=getfa(e[i].u),v=getfa(e[i].v);
            if(u!=v){
                fa[v]=u;
                G[e[i].u].pb(mp(e[i].v,i));
                G[e[i].v].pb(mp(e[i].u,i));
                flag[i]=1;
            }
        }
    }
}
int fa[N],dep[N],id[N],top[N],idx,siz[N],heavy[N],cnt[N];
void make_tree(int u,int father){
    fa[u]=father;
    dep[u]=dep[father]+1;
    siz[u]=1;
    for(auto x:G[u]){
        int v=x.first,ID=x.second;
        if(v==father){
            continue;
        }
        edge_id[v]=ID;
        make_tree(v,u);
        siz[u]+=siz[v];
        if(siz[heavy[u]]<siz[v]){
            heavy[u]=v;
        }
    }
}
void dfs(int u,int topf){
    top[u]=topf;
    id[u]=++idx;
    if(heavy[u]){
        dfs(heavy[u],topf);
    }
    for(auto x:G[u]){
        int v=x.first;
        if(v==fa[u]||v==heavy[u]){
            continue;
        }
        dfs(v,v);
    }
}
namespace Seg_Tree{
    int ans[N<<2],tag[N<<2];
    int ls(int p){
        return p<<1;
    }
    int rs(int p){
        return p<<1|1;
    }
    void f(int p,int l,int r,int val){
        ans[p]+=(r-l+1)*val;
        tag[p]+=val;
    }
    void push_down(int p,int l,int r){
        int mid=(l+r)>>1;
        f(ls(p),l,mid,tag[p]);
        f(rs(p),mid+1,r,tag[p]);
        tag[p]=0;
    }
    void push_up(int p){
        ans[p]=ans[ls(p)]+ans[rs(p)];
    }
    void update(int p,int l,int r,int q_l,int q_r,int val){
        if(q_l>q_r){
            return;
        }
        if(q_l<=l&&r<=q_r){
            ans[p]+=val*(r-l+1);
            tag[p]+=val;
            return;
        }
        int mid=(l+r)>>1;
        push_down(p,l,r);
        if(q_l<=mid){
            update(ls(p),l,mid,q_l,q_r,val);
        }
        if(q_r>mid){
            update(rs(p),mid+1,r,q_l,q_r,val);
        }
        push_up(p);
    }
    int query(int p,int l,int r,int pos){
        if(l==r){
            return ans[p];
        }
        push_down(p,l,r);
        int mid=(l+r)>>1;
        if(pos<=mid){
            return query(ls(p),l,mid,pos);
        }
        else{
            return query(rs(p),mid+1,r,pos);
        }
    }
}
void update(int u,int v,int val){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]){
            swap(u,v);
        }
        Seg_Tree::update(1,1,n,id[top[u]],id[u],val);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]){
        swap(u,v);
    }
    if(u!=v){
        Seg_Tree::update(1,1,n,id[u]+1,id[v],val);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    read(n),read(m);
    for(int i=1;i<=m;i++){
        read(e[i].u),read(e[i].v);
    }
    build::solve();
    for(int i=1;i<=n;i++){
        if(!dep[i]){
            make_tree(i,0);
            dfs(i,i);
        }
    }
    int tot=0;
    for(int i=1;i<=m;i++){
        if(flag[i]){
            continue;
        }
        int u=e[i].u,v=e[i].v;
        if((dep[u]+dep[v])%2==0){
            tot++;
            update(u,v,1);
            cnt[i]++;
        }
        else{
            update(u,v,-1);
            cnt[i]--;
        }
    }
    for(int i=1;i<=n;i++){
        cnt[edge_id[i]]=Seg_Tree::query(1,1,n,id[i]);
    }
    int ans=0;
    for(int i=1;i<=m;i++){
        if(cnt[i]==tot){
            ans++;
        }
    }
    write_endl(ans);
    // cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
    return 0;
}

邮戳拉力赛

题面

非常神秘的dp。

对于一个车站,有 \(4\) 种情况:

  1. 上行 \(\rightarrow\) 车站 \(\rightarrow\) 下行,贡献为 \(u+e\)
  2. 上行 \(\rightarrow\) 车站 \(\rightarrow\) 上行,贡献为 \(u+v\)
  3. 下行 \(\rightarrow\) 车站 \(\rightarrow\) 上行,贡献为 \(d+v\)
  4. 下行 \(\rightarrow\) 车站 \(\rightarrow\) 下行,贡献为 \(e+d\)

因为最后一定是往上走,所以 \(1\)\(3\) 一定是以一组的情况出现,且 \(3\) 一定在 \(1\) 下面。将 \(1\) 看作左括号,\(3\) 看作右括号,最后这个序列一定是个合法括号序。令 \(f_{i,j}\) 表示前 \(i\) 个里有 \(j\) 个右括号未匹配的最小代价。

先处理这 \(j\) 个右括号往上再走一层的贡献,这部分为 \(2\times j\times t\)

上面四种情况分别得到转移方程:
\(f_{i,j}=\min(f_{i-1,j+1}+u_i+e_i,f_{i,j})\)
\(f_{i,j}=\min(f_{i-1,j}+u_i+v_i,f_{i,j})\)
\(f_{i,j}=\min(f_{i-1,j-1}+d_i+v_i,f_{i,j})\)
\(f_{i,j}=\min(f_{i-1,j}+e_i+d_i,f_{i,j})(j>0)\)

因为一个车站可能不止穿过一次,所以可以在同层中再做一遍完全背包,处理穿过多次的情况。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=3010;
int t,u[N],v[N],d[N],e[N],f[N][N],n;
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    read(n),read(t);
    for(int i=1;i<=n;i++){
        read(u[i]),read(v[i]),read(d[i]),read(e[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i-1][j]=f[i-1][j]+j*t*2;
        }
        for(int j=1;j<=n;j++){
            f[i][j]=min(f[i][j],f[i-1][j-1]+d[i]+v[i]);
        }
        for(int j=0;j<n;j++){
            f[i][j]=min(f[i][j],f[i-1][j+1]+u[i]+e[i]);
        }
        for(int j=1;j<=n;j++){
            f[i][j]=min(f[i][j],f[i-1][j]+d[i]+e[i]);
        }
        for(int j=0;j<=n;j++){
            f[i][j]=min(f[i][j],f[i-1][j]+u[i]+v[i]);
        }
        for(int j=1;j<=n;j++){
            f[i][j]=min(f[i][j],f[i][j-1]+d[i]+v[i]);
        }
        for(int j=n-1;j>=0;j--){
            f[i][j]=min(f[i][j],f[i][j+1]+u[i]+e[i]);
        }
    }
    write_endl(f[n][0]+(n+1)*t);
    // cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
    return 0;
}

题面

题目中 BFS 顺序会将图划分为若干层,原有的边不能从第 \(i-2\) 层转移到第 \(i\) 层。

\(f_{i,j}\) 表示将 \([i,j]\) 划到一个层中,枚举转移 \(f_{k,j-1}\rightarrow f_{j,k}\),得到 \(O(n^3)\) 做法。

\(f_i\) 表示前 \(i\) 个点分为若干段的最小权值,可以发现能转移到的 \(j\) 满足是一段后缀。设 \(mx_i\) 表示 \([1,i]\rightarrow v\) 的最大 \(v\),限制变成了 \(j\ge mx_i\),且 \(j\) 每增大 \(1\),权值增大 \(1\),代价连续,所以只向 \(mx_i\) 转移,后继进行 \(f_{i-1}\rightarrow f_i\) 的转移即可。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2e5+10;
int vis[N],mx[N],f[N],n,m,sum;
vector<int>e[N];
void add(int u){
    sum+=(!vis[u]);
    vis[u]=1;
}
void solve(){
    read(n),read(m);
    for(int i=1;i<=m;i++){
        int u,v;
        read(u),read(v);
        mx[u]=max(mx[u],v);
        mx[v]=max(mx[v],u);
        e[min(u,v)].pb(max(u,v));
    }
    for(int i=1;i<=n;i++){
        mx[i]=max(mx[i],mx[i-1]);
    }
    memset(f,63,sizeof(f));
    for(int i=1;i<n;i++){
        f[i]=min(f[i],f[i-1]+1);
        int nowf=(i==1?0:f[i]); 
        add(i);
        for(auto v:e[i]){
            add(v);
        }
        int nxt=max(mx[i],i+1);
        f[nxt]=min(f[nxt],nowf+nxt-sum);
    }
    write_endl(f[n]);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

[POI2011] IMP-Party

题面

对于在团中的两个点,之间必然有边相连,所以对于之间没有边的两个点,必然一个在团内,一个在团外,删掉这两个点,剩下团的大小为 \(\frac{n}{3}\)

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=3010;
int n,m,deg[N],u[N*N],v[N*N],id[N],vis[N],e[N][N],ans_cnt,ans[N];
bool cmp(int x,int y){
    return deg[x]>deg[y];
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    read(n),read(m);
    for(int i=1;i<=m;i++){
        read(u[i]),read(v[i]);
        e[u[i]][v[i]]=e[v[i]][u[i]]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(vis[i]||vis[j]||e[i][j]){
                continue;
            }
            vis[i]=vis[j]=1;
            break;
        }
    }
    int cnt=0;
    // write_endl(n/3);
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            write_space(i);
            cnt++;
            if(cnt==n/3){
                break;
            }
        }
    }
    // cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
    return 0;
}

PermuTree (hard version)

题面

先考虑 \(O(n^2)\) dp 如何实现,对于一个节点,以它为 lca 的贡献为将子树分为两组,子树大小和的最大乘积。即对于每个节点,对所有子树大小做一遍01背包。可以发现不同的子树大小最多有 \(\sqrt{n}\) 种,将同种大小的子树合并,做多重背包,复杂度为 \(O(n\sqrt{n})\)

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=1e6+10;
int n,m,fa[N],siz[N],f[N],vis[N];
vector<int>e[N];
ll ans;
void query(int u){
    if(!e[u].size()){
        return;
    }
    for(auto v:e[u]){
        if(siz[v]>=(siz[u]-1)/2){
            ans+=1ll*siz[v]*(siz[u]-1-siz[v]);
            return;
        }
    }
    for(int i=0;i<=siz[u];i++){
        vis[i]=0;
    }
    vis[0]=1;
    map<int,int>cnt;
    for(auto v:e[u]){
        cnt[siz[v]]++;
    }
    for(auto x:cnt){
        int w=x.first,c=x.second;
        for(int i=0;i<=siz[u];i++){
            f[i]=0;
        }
        for(int i=w;i<=siz[u];i++){
            if(!vis[i]&&vis[i-w]&&f[i-w]<c){
                vis[i]=1;
                f[i]=f[i-w]+1;
            }
        }
    }
    ll sum=0;
    for(int i=0;i<=siz[u];i++){
        if(vis[i]){
            sum=max(sum,1ll*i*(siz[u]-1-i));
        }
    }
    ans+=sum;
}
void solve(){
    read(n);
    for(int i=2;i<=n;i++){
        read(fa[i]);
        e[fa[i]].pb(i);
    }
    for(int i=1;i<=n;i++){
        siz[i]=1;
    }
    for(int i=n;i>=2;i--){
        siz[fa[i]]+=siz[i];
    }
    for(int i=1;i<=n;i++){
        query(i);
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

Counting Graphs

题面

如果一条新增的边会影响最小生成树,那么这条边会在原图生成树两端点连通前加入最小生成树。我们考虑对于原树,一条边加入到最小生成时,带来的贡献。根据上述分析,这条边的答案为此时两端点所处连通块的大小的乘积减 \(1\)。因为各边独立,所以总答案为各条边答案的乘积。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2e5+10,mod=998244353;
int n,mx,fa[N],siz[N];
struct edge{
    int u,v,w;
}e[N];
bool cmp(edge x,edge y){
    return x.w<y.w;
}
int getfa(int u){
    if(fa[u]!=u){
        fa[u]=getfa(fa[u]);
    }
    return fa[u];
}
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void solve(){
    read(n),read(mx);
    for(int i=1;i<n;i++){
        read(e[i].u),read(e[i].v),read(e[i].w);
    }
    sort(e+1,e+n,cmp);
    for(int i=1;i<=n;i++){
        fa[i]=i;
        siz[i]=1;
    }
    int ans=1;
    for(int i=1;i<n;i++){
        int u=getfa(e[i].u),v=getfa(e[i].v);
        ans=ans*qpow(mx-e[i].w+1,siz[u]*siz[v]-1)%mod;
        fa[v]=u;
        siz[u]+=siz[v];
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

Vika and Wiki

题面

\(f_{i,j}\) 表示操作 \(i\) 次后,\(j\) 位置答案。显然可能存在于答案中的位置必然在 \([j,j+i]\) 中,一个位置要存在答案中,需要满足这个位置在得到答案的过程中异或了奇数次。我们可以得到 \(f_{i,j}=\oplus_{k=0}^i[\binom{i}{k}\equiv 1 \pmod 2]a_{j+k}\),根据 kummer 定理,我们可以得到 \(\binom{i}{k}\equiv 1\pmod 2\) 要满足在二进制位上,\(k\)\(i\) 的子集。

假定答案为 \(i\),则存在 \(f_{ans,0}=f_{ans,1}=f_{ans,2}=\dots=f_{ans,n-1}=0\),即 \(\forall i\ge ans,j\in[0,n-1],f_{i,j}=0\),我们可以进行一次高维前缀异或和,得到所有的 \(f_{i,0}\)。从后往前找就能找到答案。

因为 \(n\)\(2\) 的若干次方,所以一定有解。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=(1<<20)+10;
int n,a[N];
void solve(){
    read(n);
    for(int i=0;i<n;i++){
        read(a[i]);
    }
    for(int k=1;k<(1ll<<20);k*=2){
        for(int i=0;i<(1ll<<20);i+=k*2){
            for(int j=i;j<i+k;j++){
                a[j+k]^=a[j];
            }
        }
    }
    for(int i=n-1;i>=0;i--){
        if(a[i]){
            write_endl(i+1);
            return;
        }
    }
    write_endl(0);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}