20联赛集训day2 题解

Author： RainAir
发布时间：October 13, 2020
768views
No comments
728 words
Categories：题解

A

发现限制形如选了一条边之后，不能选和它端点相同的边。

我们建一张新图，新图中的点代表原图中的边，如果两个边不能同时选就连边。首先可以证明问题一定有解：因为这个问题等价于对于每个弱连通分量找出一个环，而只要出度入度都为 $1$ 就一定有环，所以这种情况下更有环。

我们发现原图的一种答案对应了新图的一种二分图染色方式，所以我们可以得到新图的每个连通块都是一个二分图，每个连通块有 $2$ 种染色方式，总方案数就是 $2^{C}$，$C$ 是连通块大小。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;
const int ha = 998244353;
int n;
int f[MAXN];
std::vector<P> G[MAXN],rG[MAXN];

inline int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}

inline void merge(int x,int y){
    x = find(x);y = find(y);
    if(x == y) return;
    f[x] = y;
}

int main(){
    scanf("%d",&n);
    FOR(i,1,2*n) f[i] = i;
    FOR(i,1,2*n){
        int u,v;scanf("%d%d",&u,&v);
        G[u].pb(MP(v,i));
        rG[v].pb(MP(u,i));
    }
    FOR(v,1,n){
        merge(G[v][0].se,G[v][1].se);
        for(auto x:G[v]){
            for(auto y:rG[x.fi]){
                if(y.se != x.se){
                    merge(x.se,y.se);
                }
            }
        }
    }
    int t = 1;
    FOR(i,1,2*n) if(find(i) == i) t = 2ll*t%ha;
    printf("%d\n",t);
    return 0;
}

B

设 $t_i$ 表示交换 $A_i,A_{i+1}$ 的时间，如果存在 $a_i=i$ 一定无解。

如果有位置满足 $a_i < i$，那么相当于有限制 $t_{a_i} > t_{a_i+1} > \ldots > t_{i-1}$，$a_i > i$ 也是类似的。

可以用差分（或者直接暴力）处理处相邻两个数的限制，现在变成了相邻两个数有限制 < 或者 > ，求排列方案数。

设 $f_{i,j}$ 表示考虑前 $i$ 个数，最后一个数的排名是 $j$ 的方案数，前缀和优化转移即可。

另一种做法是我们考虑容斥，将 > 容斥为 <，那么新的序列形如若干连通块，大小为 $s_1,s_2,\ldots,s_m$，那么方案就是 $\binom {n}{s_1,s_2,\ldots,s_m}$。可以写个 dp：设 $f_{i}$ 表示前缀 $i$ 的答案，转移枚举最后一段连续段是啥，算上容斥系数一起转移就好了。可以用分治 NTT 优化。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5000+5;
const int ha = 1e9 + 7;
bool vis[MAXN];
int ans = 1;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int fac[MAXN],inv[MAXN];

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    if(n < 0 || m < 0 || n < m) return 0;
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

int n,a[MAXN];
char str[MAXN];// i和i+1的关系
int f[MAXN][MAXN],pre[MAXN],suf[MAXN];

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

int main(){
    prework();scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i),++a[i];
    FOR(i,1,n){
        if(a[i] == i){
            puts("0");exit(0);
        }
        if(a[i] < i){
            FOR(j,a[i],i-2){
                if(str[j] == '<'){
                    puts("0");
                    exit(0);
                }
                str[j] = '>';
            }
        }
        else{
            FOR(j,i,a[i]-2){
                if(str[j] == '>'){
                    puts("0");exit(0);
                }
                str[j] = '<';
            }
        }
    }
    f[1][1] = 1;
    FOR(i,2,n-1){
        pre[0] = suf[i] = 0;
        FOR(j,1,i-1) pre[j] = pre[j-1],add(pre[j],f[i-1][j]);
        ROF(j,i-1,1) suf[j] = suf[j+1],add(suf[j],f[i-1][j]);
        FOR(j,1,i){
            if(str[i-1] == '<'){
                f[i][j] = pre[j-1];
            }
            else if(str[i-1] == '>'){
                f[i][j] = suf[j];
            }
            else{
                f[i][j] = pre[i-1];
            }
        }
    }
    int ans = 0;
    FOR(i,1,n-1) add(ans,f[n-1][i]);
    printf("%d\n",ans);
    return 0;
}

C

我们考虑一下不变量：发现任意 $3 \times 3$ 的矩阵中，$a_{1,1}+a_{2,3}+a_{3,2}-a_{1,2}-a_{2,1}-a_{3,3}$ 是不变的。

这样的矩阵形如：

+ - 0
- 0 +
0 + -

发现无论做什么操作，这个值都不变。

所以我们只要能把前两行前两列都消成 $0$ ，如果满足条件，剩下的格子都能推出来是 $0$。

先考虑如何消两行：从左往右考虑每一列，每次先用列操作消去下面的数，再用对角线操作消去上面的数。

消两列同理。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1000+5;

int n,m;LL a[MAXN][MAXN];

struct Node{
    int opt,x;LL k;
    Node(int opt=0,int x=0,LL k=0) : opt(opt),x(x),k(k) {}
};

std::vector<Node> S;

inline void gao(int opt,int x,LL k){
    S.pb(Node(opt,x,k));
    if(opt == 1){
        FOR(i,1,m) a[x][i] += k;
    }
    else if(opt == 2){
        FOR(i,1,n) a[i][x] += k;
    }
    else{
        // j-i = x
        FOR(i,1,n){
            int j = i+x;
            if(j >= 1 && j <= m) a[i][j] += k;
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,n) FOR(j,1,m) scanf("%lld",&a[i][j]);
    ROF(i,n,1){
        gao(1,i,-a[i][1]);
        gao(3,2-i,-a[i][2]);
    }
    FOR(i,3,m){
        gao(2,i,-a[2][i]);
        gao(3,i-1,-a[1][i]);
    }
    bool flag = 1;
    FOR(i,1,n) FOR(j,1,m) flag &= (a[i][j] == 0);
    if(!flag) puts("-1");
    else{
        printf("%d\n",(int)S.size());
        for(auto x:S) printf("%d %d %lld\n",x.opt,x.x,x.k);
    }
    return 0;
}

D

考试差一点优化。。

首先写出 dp 然后是个经典的斜率优化形式就不用说了。

但是这都不单调，如果直接做是 $O(n^2 \log n)$ 的。但是我们注意到询问点只有 $O(n)$ 个，所以预先对可能的询问点排序，每建完凸包就直接用单调性扫过去回答所有询问即可。$O(n^2+n\log n)$

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5000+5;

struct Node{
    LL x,y;
    Node(LL x=0,LL y=0) : x(x),y(y) {}
    
    inline Node operator + (const Node &t) const {
        return Node(x+t.x,y+t.y);
    }
    
    inline Node operator - (const Node &t) const {
        return Node(x-t.x,y-t.y);
    }
    
    inline LL operator * (const Node &t) const {
        return x*t.y-y*t.x;
    }
    
    inline bool operator < (const Node &t) const {
        return x == t.x ? y > t.y : x < t.x;
    }
};

int n,a[MAXN];LL sm[MAXN];
LL f[MAXN][MAXN];
std::vector<P> S;
LL w[MAXN][MAXN];

inline LL calc(Node a,LL x){
    return -a.x*x+a.y;
}

inline void build(int id){
    std::vector<Node> v;
    std::deque<Node> tb;
    for(auto x:S){
        if(x.se < id){
            v.pb(Node(sm[x.se],f[id][x.se]-sm[id]*sm[id]+sm[id]*sm[x.se]));
        }
    }
    std::reverse(all(v));
    for(auto x:v){
        while(tb.size() >= 2 && (tb.back()-tb[(int)tb.size()-2])*(x-tb.back()) >= 0) tb.pop_back();
        tb.pb(x);
    }
    for(auto x:S){
        while(tb.size() >= 2 && calc(tb[0],x.fi) <= calc(tb[1],x.fi)) tb.pop_front();
        w[id][x.se] = calc(tb[0],x.fi);
    }
}

inline void trans(int id){
    f[id][0] = 0;
    FOR(i,1,id-1){
        f[id][i] = w[i][id]+sm[id]*sm[i];
    }
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i),sm[i] = sm[i-1]+a[i];
    FOR(i,0,n) S.pb(MP(sm[i],i));std::sort(all(S));std::reverse(all(S));
    f[1][0] = 0;build(1);
    FOR(i,2,n){
        trans(i);
        build(i);
    }
    LL ans = 0;
    FOR(i,0,n-1) ans = std::max(ans,f[n][i]);
    printf("%lld\n",ans);
    return 0;
}

Last modification：July 11th, 2022 at 06:08 pm

如果觉得我的文章对你有用，请随意赞赏

20联赛集训day2 题解

RainAir • 2020 年 10 月 13 日

A

发现限制形如选了一条边之后，不能选和它端点相同的边。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;
const int ha = 998244353;
int n;
int f[MAXN];
std::vector<P> G[MAXN],rG[MAXN];

inline int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}

inline void merge(int x,int y){
    x = find(x);y = find(y);
    if(x == y) return;
    f[x] = y;
}

int main(){
    scanf("%d",&n);
    FOR(i,1,2*n) f[i] = i;
    FOR(i,1,2*n){
        int u,v;scanf("%d%d",&u,&v);
        G[u].pb(MP(v,i));
        rG[v].pb(MP(u,i));
    }
    FOR(v,1,n){
        merge(G[v][0].se,G[v][1].se);
        for(auto x:G[v]){
            for(auto y:rG[x.fi]){
                if(y.se != x.se){
                    merge(x.se,y.se);
                }
            }
        }
    }
    int t = 1;
    FOR(i,1,2*n) if(find(i) == i) t = 2ll*t%ha;
    printf("%d\n",t);
    return 0;
}

B

设 $t_i$ 表示交换 $A_i,A_{i+1}$ 的时间，如果存在 $a_i=i$ 一定无解。

如果有位置满足 $a_i < i$，那么相当于有限制 $t_{a_i} > t_{a_i+1} > \ldots > t_{i-1}$，$a_i > i$ 也是类似的。

可以用差分（或者直接暴力）处理处相邻两个数的限制，现在变成了相邻两个数有限制 < 或者 > ，求排列方案数。

设 $f_{i,j}$ 表示考虑前 $i$ 个数，最后一个数的排名是 $j$ 的方案数，前缀和优化转移即可。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5000+5;
const int ha = 1e9 + 7;
bool vis[MAXN];
int ans = 1;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int fac[MAXN],inv[MAXN];

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    if(n < 0 || m < 0 || n < m) return 0;
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

int n,a[MAXN];
char str[MAXN];// i和i+1的关系
int f[MAXN][MAXN],pre[MAXN],suf[MAXN];

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

int main(){
    prework();scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i),++a[i];
    FOR(i,1,n){
        if(a[i] == i){
            puts("0");exit(0);
        }
        if(a[i] < i){
            FOR(j,a[i],i-2){
                if(str[j] == '<'){
                    puts("0");
                    exit(0);
                }
                str[j] = '>';
            }
        }
        else{
            FOR(j,i,a[i]-2){
                if(str[j] == '>'){
                    puts("0");exit(0);
                }
                str[j] = '<';
            }
        }
    }
    f[1][1] = 1;
    FOR(i,2,n-1){
        pre[0] = suf[i] = 0;
        FOR(j,1,i-1) pre[j] = pre[j-1],add(pre[j],f[i-1][j]);
        ROF(j,i-1,1) suf[j] = suf[j+1],add(suf[j],f[i-1][j]);
        FOR(j,1,i){
            if(str[i-1] == '<'){
                f[i][j] = pre[j-1];
            }
            else if(str[i-1] == '>'){
                f[i][j] = suf[j];
            }
            else{
                f[i][j] = pre[i-1];
            }
        }
    }
    int ans = 0;
    FOR(i,1,n-1) add(ans,f[n-1][i]);
    printf("%d\n",ans);
    return 0;
}

C

我们考虑一下不变量：发现任意 $3 \times 3$ 的矩阵中，$a_{1,1}+a_{2,3}+a_{3,2}-a_{1,2}-a_{2,1}-a_{3,3}$ 是不变的。

这样的矩阵形如：

+ - 0
- 0 +
0 + -

发现无论做什么操作，这个值都不变。

所以我们只要能把前两行前两列都消成 $0$ ，如果满足条件，剩下的格子都能推出来是 $0$。

先考虑如何消两行：从左往右考虑每一列，每次先用列操作消去下面的数，再用对角线操作消去上面的数。

消两列同理。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1000+5;

int n,m;LL a[MAXN][MAXN];

struct Node{
    int opt,x;LL k;
    Node(int opt=0,int x=0,LL k=0) : opt(opt),x(x),k(k) {}
};

std::vector<Node> S;

inline void gao(int opt,int x,LL k){
    S.pb(Node(opt,x,k));
    if(opt == 1){
        FOR(i,1,m) a[x][i] += k;
    }
    else if(opt == 2){
        FOR(i,1,n) a[i][x] += k;
    }
    else{
        // j-i = x
        FOR(i,1,n){
            int j = i+x;
            if(j >= 1 && j <= m) a[i][j] += k;
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,n) FOR(j,1,m) scanf("%lld",&a[i][j]);
    ROF(i,n,1){
        gao(1,i,-a[i][1]);
        gao(3,2-i,-a[i][2]);
    }
    FOR(i,3,m){
        gao(2,i,-a[2][i]);
        gao(3,i-1,-a[1][i]);
    }
    bool flag = 1;
    FOR(i,1,n) FOR(j,1,m) flag &= (a[i][j] == 0);
    if(!flag) puts("-1");
    else{
        printf("%d\n",(int)S.size());
        for(auto x:S) printf("%d %d %lld\n",x.opt,x.x,x.k);
    }
    return 0;
}

D

考试差一点优化。。

首先写出 dp 然后是个经典的斜率优化形式就不用说了。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5000+5;

struct Node{
    LL x,y;
    Node(LL x=0,LL y=0) : x(x),y(y) {}
    
    inline Node operator + (const Node &t) const {
        return Node(x+t.x,y+t.y);
    }
    
    inline Node operator - (const Node &t) const {
        return Node(x-t.x,y-t.y);
    }
    
    inline LL operator * (const Node &t) const {
        return x*t.y-y*t.x;
    }
    
    inline bool operator < (const Node &t) const {
        return x == t.x ? y > t.y : x < t.x;
    }
};

int n,a[MAXN];LL sm[MAXN];
LL f[MAXN][MAXN];
std::vector<P> S;
LL w[MAXN][MAXN];

inline LL calc(Node a,LL x){
    return -a.x*x+a.y;
}

inline void build(int id){
    std::vector<Node> v;
    std::deque<Node> tb;
    for(auto x:S){
        if(x.se < id){
            v.pb(Node(sm[x.se],f[id][x.se]-sm[id]*sm[id]+sm[id]*sm[x.se]));
        }
    }
    std::reverse(all(v));
    for(auto x:v){
        while(tb.size() >= 2 && (tb.back()-tb[(int)tb.size()-2])*(x-tb.back()) >= 0) tb.pop_back();
        tb.pb(x);
    }
    for(auto x:S){
        while(tb.size() >= 2 && calc(tb[0],x.fi) <= calc(tb[1],x.fi)) tb.pop_front();
        w[id][x.se] = calc(tb[0],x.fi);
    }
}

inline void trans(int id){
    f[id][0] = 0;
    FOR(i,1,id-1){
        f[id][i] = w[i][id]+sm[id]*sm[i];
    }
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i),sm[i] = sm[i-1]+a[i];
    FOR(i,0,n) S.pb(MP(sm[i],i));std::sort(all(S));std::reverse(all(S));
    f[1][0] = 0;build(1);
    FOR(i,2,n){
        trans(i);
        build(i);
    }
    LL ans = 0;
    FOR(i,0,n-1) ans = std::max(ans,f[n][i]);
    printf("%lld\n",ans);
    return 0;
}

20联赛集训day2 题解

A

B

C

D

Leave a Comment Cancel reply

NOI2021 退役记

SDOI2020 退役记

I'm back

点双连通分量 & 圆方树学习笔记

CSP2019 游记

DDP 学习笔记

「CF860E」Arkady and a Nobody-men

「Luogu1137」旅行计划

CF 1336 题解

此内容被密码保护

20联赛集训day2 题解

A

B

C

D