2021联合省选[A/B]卷总结

· · 个人记录

已完工 .

由于洛谷没有这些题目的难度评级 , 加入个人评级 .

难度评价

本次联合省选几乎用不到任何高级算法(指提高组的选手也可以看懂题解并解决问题) , 即使是支配也用不到支配树的 \mathcal O(n+m) 构建方法 . 但是思维难度较大 .

B卷D1T1 : 数对

个人难度评级 : 普及+

这是一道显题 , 但是我考场上甚至花了 15min 才想到正解 (想复杂了 , 还建图 , 建尼玛图)

显然 , 由于值域不大 , 记录每个数的出现次数 , \mathcal O(n\log n) 地枚举即可 . 只需要注意数字相同是的情况即可 . 

#define mp make_pair
#define pb push_back
#define Inf 0x3f3f3f3f
#define Lx (x<<1)
#define Rx (x<<1|1)
//#define mid ((l+r)>>1)
//#define INF 0x3f3f3f3f3f3f3f3f
//#define int long long 
#define N 505050

int n,mmax;
int A[N];
ll val[N],ans;

int main() {
    n=read();
    for(int i=1;i<=n;++i) {
        int x=read();
        mmax=max(mmax,x);
        val[x]++;
        A[i]=x;
    }
    for(int i=1;i<=mmax;++i) {
        for(int j=1;i*j<=mmax;++j) {
            if(val[i*j] and val[i]) {
                if(i*j == i) {
                    ans+=1ll*val[i]*(val[i]-1);
                }
                else {
                    ans+=1ll*val[i]*val[i*j];
                }
            }
        }
    }
    Writes(ans);

    return 0;
}

B卷D1T2/A卷D1T1 : 卡牌游戏

个人难度评级 : 提高

好想吗 ? 好想 . 算法一定对吗 ? 那可不一定 . 很可能大部分人的程序是无法通过所有数据的(指穷举所有可能性下的数据 , 一共 n*(2n)^{10^9} 种数据可能性) .

这里简述一下我的做法 . 使用双指针 (但是还要排序 , 所以复杂度仍然是 \mathcal O(n\log n)) .

首先对所有数排序 , 然后从大到小枚举极差中的最大数 M . 那么我们发现 , 原来的升序序列 A 中 , >M 的数全部需要翻过来 (=M 不需要也不能) ; 而小于 M 的数中 , 我们要让最小值最大 ; 于是我们选择翻转一段前缀 ; 要求是 : 这段前缀任意 A[i] < B[i] (否则你翻转个什么劲) , 且翻转后最大值小于 M . 这些要求和限制可以用两个指针维护 .

但是特殊数据情况下 , 很容易把这个算法卡掉 (指可能几百个数据错一两个点) , 边界情况属实难整 . 

#define N 1101010
#define Inf 0x3f3f3f3f

int n,m,ans=Inf;
struct node {
    int v,id;
    bool operator < (const node &b) const {return v>b.v;}
}arr[N<<1];
int maxloc,premax[N],premin[N],sufmax[N],sufmin[N];
int A[N],B[N];

int main() {
    n=read(),m=read();
    for(int i=1;i<=n;++i)
        A[i]=read(),arr[i]=(node){A[i],i};
    for(int i=1;i<=n;++i)
        B[i]=read(),arr[i+n]=(node){B[i],i+n};
    sort(arr+1,arr+1+2*n);
    premin[0]=Inf;
    for(int i=1;i<=n;++i)
        premin[i]=min(premin[i-1],B[i]);
    premax[0]=0;
    for(int i=1;i<=n;++i)
        premax[i]=max(premax[i-1],B[i]);
    for(int i=1;i<=n and A[i]<B[i];++i)
        maxloc=i;
    sufmax[n+1]=0;
    for(int i=n;i>=1;--i)
        sufmax[i]=max(sufmax[i+1],B[i]);
    sufmin[n+1]=Inf;
    for(int i=n;i>=1;--i)
        sufmin[i]=min(sufmin[i+1],B[i]);
    int p=n,pp=maxloc;

    for(int i=1;i<=2*n;++i) {
        int mmax=arr[i].v;
        while(p >= 1 and arr[i].v < A[p])
            --p;
        while(pp >= 1 and premax[pp] > arr[i].v)
            --pp;
        int del=0;
        if(arr[i].id > n)
            del=(arr[i].id > n)*(B[arr[i].id-n] > A[arr[i].id-n]);
        int mmin=Inf;
        if(sufmax[p+1] > mmax)
            continue;
        if(n-(p+1)+1 > m-del)
            continue;
        mmin=sufmin[p+1];
        int lim=min(pp,m-(n-(p+1)+1)-del);
        mmin=min(mmin,premin[lim]);
        mmin=min(mmin,A[lim+1]);
        ans=min(ans,mmax-mmin);
    }
    Writes(ans);
    return 0;
}

A卷D1T2 : 矩阵游戏

个人难度评级 : 提高+ , 省选-

本题的关键不在于如何通过矩阵 B 直接构建矩阵 A (这样想的人都死了) , 而在于先构建一组不一定合法的矩阵 A , 然后如何通过调整 , 把 A 矩阵的数变到合法范围 .

于是乎问题变为 , 怎么变化 A 矩阵的值 , 才能使 B 矩阵的值不变 ? . 由于 B 矩阵中每个元素是 A 中 2\times 2 子矩阵内数的和 , 所以我们自然地考虑到 :

可以给一行(列)交替加上/减去一个数 .

+a & -a & +a & \dots \end{bmatrix}

所以我们可以设行 i 的"这个数"为 r_i , 列 j 的这个数为 c_j . 然后列出不等式 :

0\leq \pm r_i \pm c_j +a_{i,j}\leq 10^6

那么我们可以把 r_i,c_j 视为两个变量 , \pm 和行列有关 , 跑差分约束即可 ...

仔细发现 , 好像不对劲啊 , 好像还有"和分约束" ? 因为可能有这样的状态 :

+r_i+c_j \end{bmatrix}

两个变量都是 + , 无法差分约束 .

所以我们只要保证一个格子内 , r_i 和 c_j 符号相反即可 . 那么很简单 , 将期盼黑白染色 , 行是黑加白减 , 列是黑减白加 , 即可 .

而后并不用设置超级源点 , 因为这个图是一个完全图 , 任意一点作为起点都可以 . 

#define pb push_back
#define mp make_pair
#define Inf 0x3f3f3f3f
#define N 603
#define M 180909

int n,m;
int A[N][N],B[N][N];
int row[N],col[N];
bool type[N][N],vis[N];
int head[N],nxt[M],ver[M],edge[M],tot=1;
ll dis[N];
int ins[N];
queue <int> q;

void add(int x,int y,int z) {
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot,edge[tot]=z;
}
void Reset() {
    for(int i=1;i<=n+m;++i)
        head[i]=0,ins[i]=0;
    for(int i=2;i<=tot;++i)
        nxt[i]=ver[i]=edge[i]=0;
    tot=1;
}  
bool spfa() {
    while(!q.empty())q.pop();
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    memset(ins,0,sizeof ins);
    dis[1]=0;
    q.push(1),vis[1]=1;
    while(!q.empty()) {
        int x=q.front();q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=nxt[i]) {
            int y=ver[i],z=edge[i];
            if(dis[x]+z<dis[y]) {
                dis[y]=dis[x]+z;
                ins[y]++;
                if(!vis[y]) 
                    q.push(y),vis[y]=1;
                if(ins[y] > n+m)
                    return 0;
            }
        }
    }
    return 1;
}
void solve() {
    Reset();    
    n=read(),m=read();
    for(int i=1;i<=n-1;++i)
        for(int j=1;j<=m-1;++j)
            B[i][j]=read();
    for(int i=1;i<=n;++i)
        A[i][m]=0,row[i]=i;
    for(int j=1;j<=m;++j)
        A[n][j]=0,col[j]=n+j;
    for(int i=n-1;i>=1;--i)
        for(int j=m-1;j>=1;--j) 
            A[i][j]=B[i][j]-A[i+1][j]-A[i][j+1]-A[i+1][j+1];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            type[i][j]=(abs(i-j)&1);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j) {
            if(type[i][j] == 0) {
                add(row[i],col[j],A[i][j]);
                add(col[j],row[i],1e6-A[i][j]);
            }
            else {
                add(col[j],row[i],A[i][j]);
                add(row[i],col[j],1e6-A[i][j]);
            }
        }
    if(!spfa())
        puts("NO");
    else {
        puts("YES");
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                if(type[i][j] == 0)
                    A[i][j]+=dis[row[i]]-dis[col[j]];
                else
                    A[i][j]+=dis[col[j]]-dis[row[i]];
        for(int i=1;i<=n;++i,puts(""))
            for(int j=1;j<=m;++j)
                writes(A[i][j]);
    }

}
int main() {
    int T=read();
    while(T--) 
        solve();            
    return 0;
}

我判负环的时候傻傻逼逼把入队次数的统计搞错了 , 应该是访问到一次加一次 , 而不是入队了才加一次 ...

还是判负环 , 注意是 > n+m ... 我是傻逼

B卷D1T3/A卷D1T3 : 图函数

个人难度评级 : 省选

这题啊 ... 这题啊 ... (对我而言 , 想到这个点 , 就可以从 16pts \rightarrow 100pts) .

首先手玩一下 , 对于 f(u,G) 而言 , 仅有 1 \leq v\leq u 的点有效 . (因为 > u 的点在 u 点被删除后无论如何也无法到达) . 这是第一个限制 .

而后 , 一个 v 在什么条件下能和 u 互相到达 ? 如果 , 存在条路径 , 使得 u,v 能经过且仅经过 \geq v 的点互相到达 , 那么 (u,v) 一定能产生贡献 .

那么现在有了一个 44pts 的做法 . 枚举删掉的每条边 , 然后正反图 \mathcal O(n^2) 跑 , 一共 \mathcal O(n^2m) .

继续观察 . 一对 (u,v) 对 h(G) 产生的贡献 , 会有一个临界 : 删除了某条边后 , 其贡献为 0 ; 在此之前 , 贡献为 1 . 于是乎 , 我们可以尝试找到这条边 .

设 f[v][u][k] 为 v 到 u 只经过 \geq k 的点 (除了 u) , 所经过的编号最小的边的最大值 . 那么这样就可以 floyd 来跑一波了 . 

for(int i=1;i<=m;++i)
        f[e[i].u][e[i].v]=i;
    for(int k=n;k>=1;--k)
        for(int i=1;i<k;++i)
            for(int j=1;j<=n;++j)
                f[i][j]=max(f[i][j],min(f[i][k],f[k][j]));

你以为这里很简单 ? 当然不是 . 为什么上面会有 "(除了 u)" 这个东西 ? 因为你当然可以从 v 到 u' (u'> u) , 再从 u' 到 u . 而如果我们没有这个东西 , 在转移时就会有锅 ; 同时也不能限制 v < u , 同样的转移有锅 ; 最后 , 转移中的 i < k 保证了 f[v][u] 被更新时 , 中间结点都 >v .

#define N 1010 
#define M 202020

int n,m;
struct edge {int u,v;}e[M];
int g[N][N],f[N][N],f1[N][N],f2[N][N];
int ans[M];

inline int max(int x,int y) {return x>y?x:y;}
inline int min(int x,int y) {return x<y?x:y;}


int main(){
    n=read(),m=read();
    for(register int i=1;i<=m;++i) {
        int u=read(),v=read();
        e[i]=(edge){u,v};
    }
    for(int i=1;i<=m;++i)
        f1[e[i].u][e[i].v]=i;
    for(register int k=n;k>=1;--k)
        for(register int i=1;i<k;++i)
            for(register int j=1;j<=n;++j)
                f1[i][j]=max(f1[i][j],min(f1[i][k],f1[k][j]));
    for(register int i=1;i<=m;++i)
        f2[e[i].v][e[i].u]=i;
    for(register int k=n;k>=1;--k)
        for(register int i=1;i<k;++i)
            for(register int j=1;j<=n;++j)
                f2[i][j]=max(f2[i][j],min(f2[i][k],f2[k][j]));

    for(register int i=1;i<=n;++i)
        for(register int j=i;j<=n;++j) {
            f[i][j]=min(f1[i][j],f2[i][j]);
            //cnt+=(f[i][j]>0);
            //writes(f[i][j]);
            if(i == j)
                ans[m]++;
            else if(f[i][j])
                ans[f[i][j]-1]++;
        } 
    for(register int i=m-1;i>=0;--i)
        ans[i]+=ans[i+1];
    for(register int i=0;i<=m;++i)
        writes(ans[i]);
    return 0;
}

史诗级优化 : 将 \max 和 \min 重载 .

(反正这减少了我一半的总用时)

B卷D2T1 : 取模

个人难度评级 : 提高

并非正解 , 可以水过 .

首先将 a 数组排序 , 然后从大到小枚举 . 这样固定了模数 m , 只需要求出 a_i+a_j 对 m 取模的最大值 . 那么 , 先令所有 a_i \%= m , 这样所有 a_i < m . 然后考虑 m \leq a_i+a_j < 2m 和 0 \leq a_i+a_j < m 两种情况 ; 第一种相当于求 a_i+a_j 最大值 ; 第二种排序后用双指针就可以了 ; 每一遍复杂度为 \mathcal O(n\log n) .

有两个剪枝 , 一个是当前答案 ans \geq m 时 , 可以退出循环 ; 另一个是下一个 m 和当前 m 相同时 , 跳过枚举(就是去重) ; 这样可以通过 . 这样在随机数据下一定表现良好 , 貌似很难造数据卡掉 ? 

#define mp make_pair
#define pb push_back
#define Inf 0x3f3f3f3f
#define Lx (x<<1)
#define Rx (x<<1|1)
//#define mid ((l+r)>>1)
//#define Inf 0x3f3f3f3f3f3f3f3f
//#define int long long
#define N 202020

int n;
int arr[N];
int A[N],cnt;
int ans1,ans2;

int main() {
    n=read();
    for(int i=1;i<=n;++i)
        arr[i]=read();
    sort(arr+1,arr+1+n);
    for(int k=n;k>=1;--k) {
        if(arr[k] == arr[k+1])
            continue;
        if(max(ans1,ans2) >= arr[k]-1)
            break;
        cnt=0;
        int Max[2]={0,0};
        for(int i=1;i<=n;++i)
            if(i != k) {
                A[++cnt]=arr[i]%arr[k];
                if(A[cnt] >= Max[0])
                    Max[1]=Max[0],Max[0]=A[cnt];
                else if(A[cnt] >= Max[1])
                    Max[1]=A[cnt];
            }
        ans1=max(ans1,(Max[0]+Max[1])%arr[k]);
        sort(A+1,A+1+cnt);
        int l=1,r=cnt;
        while(l <= cnt and r >= 1) {
            while(A[l]+A[r] >= arr[k] and r >= 1)
                --r;
            if(l == r)
                --r;
            if(r < 1)   break;
            ans2=max(ans2,A[l]+A[r]);
            ++l;
        }
    }
    Writes(max(ans1,ans2));

    return 0;
}

B卷D2T2/A卷D2T1 : 宝石

个人难度评级 : 省选

(我是傻逼)

有显然转化 , 我们将 P_1,\dots , P_c 重新编号为 1,\dots , c , 剩下的全部置为 0 . 而后考虑暴力 , 枚举每一个点为根节点 , 按匹配子序列一样匹配就好 .

那么怎么优化这个过程 ? 该过程可以分成两个部分 , u\rightarrow \mathcal{}lca 和 lca \rightarrow v . 对于第一个过程 , 我们可以不用一个一个匹配 , 而是倍增地匹配 ! 设 anc[x][i] 为 x 成功向上连续匹配 2^i 个颜色 , 到达的深度最深的节点 . 这样可以很容易 \mathcal O(n\log n) 地求出 u\rightarrow lca 时已经匹配的颜色 .

那么 lca\rightarrow v 呢 ? 貌似难整 , 实则不然 . 我们可以可以把 lca \rightarrow v 的匹配转化为 v\rightarrow lca 的匹配 , 把从 1\sim c 的匹配反过来 ! 具体地说 , 设当前已经求出 u\rightarrow lca 最多能匹配的颜色为 col ; 然后二分最终颜色 col' , 尝试从 v 向上倒着匹配到 lca ; 若能匹配到的颜色 <col (即匹配到 col 前面) , 那么成功 . 这部分的复杂度为 \mathcal O(n\log^2 n) . 于是问题得到解决 .

(然而我补题时傻傻逼逼的写了整体二分)

顺便谈一谈整体二分的适用条件 ; 当二分的 check 函数复杂度较大时 , 可以尝试将信息整合来整体地二分 . 本题的 check 函数复杂度为 \mathcal O(\log n) , 不需要优化 . 

#define N 201010
#define M 404040
#define Log 20
#define pb push_back
#define mp make_pair
#define Lx T[x].l
#define Rx T[x].r
#define Ly T[y].l
#define Ry T[y].r

int n,m,c,q;
int Map[N];
int type[N];
int head[N],nxt[M],ver[M],tot=1;
int anc[N][Log];vector <int> stk[N];
struct tree {
    int l,r,node;
}T[N*Log];int cnt,root[N];
int st[N<<1][Log],idx,dep[N],pos[N];
void add(int x,int y) {ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
struct query {
    int u,v,num,id;
}qry[N],Lq[N],Rq[N];int ans[N];

void Update(int x,int y,int l,int r,int loc,int k) {
    if(l == r) {T[x].node=k;return ;}
    int mid=(l+r)>>1;
    if(loc <= mid) 
        Lx=++cnt,Rx=Ry,Update(Lx,Ly,l,mid,loc,k);
    else
        Lx=Ly,Rx=++cnt,Update(Rx,Ry,mid+1,r,loc,k);
}
int Find(int x,int l,int r,int loc) {
    if(!x)  return 0;
    if(l == r)  return T[x].node;
    int mid=(l+r)>>1;
    return loc<=mid ? Find(Lx,l,mid,loc) : Find(Rx,mid+1,r,loc);
}

void dfs1(int x,int fa) {
    stk[type[x]].pb(x);
    if(type[x]) {
        if(type[x]+1 <= c)
            anc[x][0]=stk[type[x]+1].empty() ? 0 : stk[type[x]+1].back();
        for(int j=1;j<Log;++j)
            anc[x][j]=anc[anc[x][j-1]][j-1];
    }
    dep[x]=dep[fa]+1;
    root[x]=++cnt;
    Update(root[x],root[fa],1,c,type[x],x);
    st[++idx][0]=x,pos[x]=idx;  
    for(int i=head[x];i;i=nxt[i]) {
        int y=ver[i];
        if(y == fa) continue;
        dfs1(y,x),st[++idx][0]=x;
    }
    stk[type[x]].pop_back();
}
void dfs2(int x,int fa) {
    stk[type[x]].pb(x);
    if(type[x]) {
        if(type[x]-1 >= 1)
            anc[x][0]=stk[type[x]-1].empty() ? 0 : stk[type[x]-1].back();
        for(int j=1;j<Log;++j)
            anc[x][j]=anc[anc[x][j-1]][j-1];
    }   
    for(int i=head[x];i;i=nxt[i]) {
        int y=ver[i];
        if(y == fa) continue;
        dfs2(y,x);
    }
    stk[type[x]].pop_back();
}
void get_st() {
    for(int j=1;j<Log;++j)
        for(int i=1;i+(1<<j)-1<=idx;++i)
            st[i][j]=dep[st[i][j-1]] < dep[st[i+(1<<(j-1))][j-1]] ? st[i][j-1] : st[i+(1<<(j-1))][j-1] ;
}
int get_lca(int x,int y) {
    int l=pos[x],r=pos[y];
    if(l > r)   swap(l,r);
    int k=log2(r-l+1);
    return dep[st[l][k]] < dep[st[r-(1<<k)+1][k]] ? st[l][k] : st[r-(1<<k)+1][k];   
}
int get_match(int x,int to,int st_num) {
    x=Find(root[x],1,c,st_num);
    if(!x or dep[x] < dep[to])  return 0;
    int num=1;
    for(int i=Log-1;i>=0;--i)
        if(anc[x][i] == 0)  
            continue;
        else if(dep[anc[x][i]] < dep[to])   
            continue;
        else {
            x=anc[x][i];
            num+=1<<i;
        }
    return num;
} 
void solve(int l,int r,int ql,int qr) {
    int mid=(l+r+1)>>1;
    if(l == r) {
        for(int i=ql;i<=qr;++i) {
            ans[qry[i].id]=qry[i].num+mid;
        }
        return ;
    } 
    int lcnt=0,rcnt=0;
    for(int i=ql;i<=qr;++i) {
        int u=qry[i].u,v=qry[i].v,num=qry[i].num;
        if(num+mid>c) {Lq[++lcnt]=qry[i];continue;}
        u=Find(root[u],1,c,num+mid);
        if(!u) {Lq[++lcnt]=qry[i];continue;}
        int len=get_match(u,v,num+mid);
        if(len < mid)
            Lq[++lcnt]=qry[i];
        else
            Rq[++rcnt]=qry[i];
    }
    for(int i=1;i<=lcnt;++i)
        qry[ql+i-1]=Lq[i];
    for(int i=1;i<=rcnt;++i)
        qry[ql+lcnt+i-1]=Rq[i];
    solve(l,mid-1,ql,ql+lcnt-1);
    solve(mid,r,ql+lcnt,qr);
} 

int main() {
    n=read(),m=read(),c=read();
    for(int i=1;i<=c;++i)
        Map[read()]=i;
    for(int i=1;i<=n;++i) 
        type[i]=Map[read()];
    for(int i=1;i<n;++i) {
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    dfs1(1,0),get_st();
    q=read();
    for(int i=1;i<=q;++i) {
        int u=read(),v=read();
        int lca=get_lca(u,v);
        int num=get_match(u,lca,1);
        qry[i]=(query){v,lca,num,i};
    }
    memset(anc,0,sizeof anc);
    dfs2(1,0),solve(0,c,1,q);
    for(int i=1;i<=q;++i)
        Writes(ans[i]);
    return 0;
}

B卷D2T3/A卷D2T2 : 滚榜

个人难度评级 : 省选

滚 ! 滚 ! 滚 !

(考场上压根没看清楚题目 , 瞎写一通只有 40pts)

我们并不关心 \{b\} 的分布 , 只需要知道一个排列是否可能成为最终的排行榜序列即可 .

所以可以尝试枚举排列 , 然后判定排列是否可行 . 我们对于一个排列 , 对每一个元素 a_i 都尝试给他赋予最小的合法的 b_i 即可 . 至于 \sum b_i = m 的限制 , 我们可以把多出来的 b 都丢给最后一个元素 . 所以复杂度为 \mathcal O(n*n!) , 可以拿到 60pts .

那么 , 我们不能枚举排列了 . 考虑到 n 很小 , 所以可以尝试状态压缩 . (我考场上一开始也是这样想的) . 设 f[S][i][b_i][j] 表示 S 内的人已经更新排行 , 其中 i 现在居于榜首 , b_i 是它封榜后的过题数 , j 是集合内所有队伍封榜后的过题数之和 , 这样的方案总数是多少 .

注意到这是很难 dp 的 . 因为这样会导致排列算重复 .

考虑优化这个该死的 dp , 考虑 a_i 能替代 a_j 冲到第一名的最优条件 (即让 b_i 最小) :

a_i+b_i= a_j+b_j,i<j a_i+b_i=a_j+b_j+1,i>j b_i\geq b_j

此时让 b_i 最小 , 就是 :

a_i+b_i=a_j+b_j+[i>j],b_i\geq b_j

得到 :

b_i=\max(a_j-a_i+[i>j]+b_j,b_j)

可以提出来 :

b_i=b_j+\max(a_j-a_i+[i>j],0)

这也就意味着 :

\\ &= \sum_{i=1}^q \Big((n-i+1)*\max(a_{p_{j-1}}-a_{p_j}+[p_j>p_{j-1}],0)\Big) \end{aligned}

于是乎设 t_{i,j}=\max(a_j-a_i+[i>j],0) , 那么状态只需要设成 f[S][i][j] , 可得转移方程 :

f[S][i][j]=f[S-(1<<i)][k][j-(n-|S|+1)*t_{k,i}]

同时 , 这样的方案不会算重 , 因为一个排列一定对应唯一的 b 的总和 . (因为每次 b 都取最小 , 而这个值是固定的) .

时间复杂度 \mathcal O(n^2m2^n) , 约为 6e8 级别 ; 当然很难跑满 , 所以大约是跑得过的 . 

#define pb push_back
#define mp make_pair
#define Inf 0x3f3f3f3f
#define N 14
#define M 510

int n,m,top;
int f[1<<N][N][M];
int t[N][N];
int a[N];
int cnt[1<<N];
ll sum;

int main() {
    n=read(),m=read();
    for(int i=0;i<n;++i)
        a[i]=read(),top=a[i]>a[top]?i:top;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            if(i^j)
                t[i][j]=max(0,a[i]-a[j]+(j>i));
    for(int i=1;i<1<<n;++i)
        cnt[i]=cnt[i-(i&-i)]+1;
    for(int i=0;i<n;++i)
        if(n*t[top][i] <= m)
            f[1<<i][i][n*t[top][i]]=1;
    for(int i=1;i<1<<n;++i) {
        if(cnt[i] == 1) continue;
        for(int j=0;j<n;++j) {
            if(!(i>>j&1))   continue;
            for(int k=0;k<n;++k) {
                if(j == k or !(i>>k&1)) continue;
                int v=t[k][j]*(n-cnt[i]+1);
                for(int l=v;l<=m;++l) {
                    f[i][j][l]+=f[i-(1<<j)][k][l-v];
                }
            }
        }
    }
    for(int i=0;i<n;++i)
        for(int j=0;j<=m;++j) 
            sum+=f[(1<<n)-1][i][j];
    Writes(sum);            
    return 0;
}

(再次提示) , 我把维度设反了自己却不知道 , 结果白白调了一个小时 ...

A卷D2T3 : 支配

个人难度评级 : 省选

我们当然可以考虑每次重新构建一棵支配树 , 然后用哈希来判断哪些点的受支配集被改变 . 这样的复杂度是大常数的 \mathcal O((n+m)q) , 不能通过 .

那么我们可以考虑对这棵支配树做点文章嘛 . 考虑新边是 u\rightarrow v , 他们在支配树上的最近公共祖先是 lca .

考虑最特殊的情况 , v 是 lca . 那么这条边显然没用 , 因为从 lca 到达 v 仍然需要经过所有 v 的祖先 .

那么 u 是 lca 呢 ? 好像无法直接判断 , 先放着 .

接下来考虑一般情况 . 设 v' 是 lca 的儿子 , 满足 v 在 v' 为根的子树内 . 考虑以 v' 为根的子树之外的点 . 我们断言他们的受支配集不会受到影响 . 考虑子树外的一点 x , 本来是不存在不经过其支配集 S_x 就能到达 x 的路径 ; 也就是不存在从 1 到 v , 再从 v 到 x 而不经过 S_x 的路径 ; 更详细的 , 设 lca 与 x 的最近公共祖先为 lca' , 那么链 1\rightarrow lca' 上的点集 S 是 1\rightarrow v 必须经过的 , 同时也是 1 \rightarrow u 必须经过的 ; 那么这意味着 lca'\rightarrow v\rightarrow x 必须经过 S_x-S ; 但是 lca'\rightarrow v 不会经过 S_x 中的任何一个点 (x 在 v' 子树之外) , 所以 v\rightarrow x 必须经过 S_x-S ; 现在新增 u\rightarrow v , 那么 1\rightarrow u\rightarrow v\rightarrow x 必须经过的点集为 S+(S_x-S)=S_x . 证毕 .

那么以 v' 为根的子树内呢 ? 首先 , v' 的受支配集不会被改变 (因为到达 v 一定会经过 1\rightarrow lca) ; 那么由于新增了 u\rightarrow v , 那么我们可以求出 v 不经过 v' 可以到达哪些 v' 子树内的点 S (因为如果到达了 v' , 显然可以到达 v' 子树内的所有点) . 那么 1\rightarrow u\rightarrow v\rightarrow x(x\in S) 可以绕过 v' , 从而 S 内的点的受支配集被改变 ; 同时 , x(x\in S) 为根的子树内的所有点的受支配集也被改变 . 至此 , 问题得到解决 . u 是 lca 的情况 , 与当前讨论并不冲突 . 

#define N 3030
#define pb push_back

int n,m,q;
vector <int> g[N],ng[N],tr[N],son[N];
int dfn[N],ord[N],idx;
int sdom[N],idom[N],father[N];
int par[N],low[N];

bool vis[N];
int dep[N],sz[N];

int find(int x) {
    if(x == par[x]) return x;
    int rt=find(par[x]);
    if(dfn[sdom[low[par[x]]]] < dfn[sdom[low[x]]])
        low[x]=low[par[x]];
    return par[x]=rt;
}

void dfs(int x) {
    ord[dfn[x]=++idx]=x;
    for(ui i=0;i<g[x].size();++i) { 
        int y=g[x][i];
        if(!dfn[y])
            father[y]=x,dfs(y);
    }
}
void dfs2(int x) {
    sz[x]=1,dep[x]=dep[father[x]]+1;
    for(ui i=0;i<tr[x].size();++i) { 
        int y=tr[x][i];
        father[y]=x,dfs2(y),sz[x]+=sz[y];
    }
}


void get_tree() {
    dfs(1);
    for(int i=1;i<=n;++i)
        sdom[i]=i,par[i]=i,low[i]=i;
    for(int i=idx;i>=2;--i) {
        int x=ord[i];
        for(ui j=0;j<ng[x].size();++j) {
            int y=ng[x][j];
            if(!dfn[y]) continue;
            find(y);
            if(dfn[sdom[low[y]]] < dfn[sdom[x]])
                sdom[x]=sdom[low[y]];
        }
        int fx=father[x];
        par[x]=fx,son[sdom[x]].pb(x);
        for(ui j=0;j<son[fx].size();++j) {
            int y=son[fx][j];
            find(y);
            idom[y]=sdom[low[y]] == fx?fx:low[y];
        }
    }
    for(int i=2;i<=idx;++i) {
        int x=ord[i];
        if(idom[x] ^ sdom[x])
            idom[x]=idom[idom[x]];
        tr[idom[x]].pb(x);
    }
}
void get_vis(int del,int x) {
    if(x == del)    return ;
    vis[x]=1;
    for(int i=0;i<g[x].size();++i) {
        int y=g[x][i];
        if(!vis[y] and y != del)
            get_vis(del,y);
    }
}
int get_lca(int x,int y) {
    if(dep[x] < dep[y])
        swap(x,y);
    while(dep[x] ^ dep[y])
        x=father[x];
    while(x ^ y)
        x=father[x],y=father[y];
    return x;
}
int get_sub(int x,int y) {
    while(father[x] != y)
        x=father[x];
    return x;
}
int get_ans(int rt,int x) {
    if(x != rt and vis[x]) {
        return sz[x];
    }
    int res=0;
    for(ui i=0;i<tr[x].size();++i) {
        int y=tr[x][i];
        res+=get_ans(rt,y);
    }
    return res;
}

int main() {
    n=read(),m=read(),q=read();
    for(int i=1;i<=m;++i) {
        int x=read(),y=read();
        g[x].pb(y),ng[y].pb(x);
    }
    get_tree();

    dfs2(1);
    while(q--) {
        int u=read(),v=read();
        int lca=get_lca(u,v);
        if(lca == v) {puts("0");continue;}
        if(lca == father[v]) {puts("0");continue;}
        int sub=get_sub(v,lca);
        memset(vis,0,sizeof vis);
        get_vis(sub,v);
        int ans=get_ans(sub,sub);
        Writes(ans);
    }

    return 0;
}