2022杭电多校7(总结+补题)

总结

今天这把一开始三个人一起做博弈论签到题，想了一个小时都没想出来，队友1看1004过的人也挺多就写了一发，我大概看了看之后就让他交，结果wa了，然后我就开始出样例hack，hack到了一个点后他把代码改了改又交了，结果又wa，遂继续hack，过了一会又hack到了一个点，这次改完之后ac了，遂一起看1003，三人推了半天，讨论了好久，都没有想到什么很好的办法， 最后队友2开启自闭模式写了半个多小时一发ac了（说是没有用到之前讨论的方法），队友1也想到了博弈论签到题的做法ac了，三题过后，还剩两个小时，我就和队友2一起做1002，思考了好一会后，队友2给出了一种解法，于是我就开写，写好后交上去tle了，改了改又交了几发，均是tle，上了趟厕所后，我和队友2换了个脑子重新想这道题，我发现一开始的做法虽然总的来说复杂度正确，但是建了很多多余的边，于是我简化了一下我们的建图方法，最后结束前五分钟终于写好ac了，四题结束，排名300+。

题解：

1002 - Independent Feedback Vertex Set

题意，给你一个初始图 {$1,2$}{$2,3$}{$1,3$} ，告诉你总共有 $n$ 个点，$1-3$ 为初始点，之后每次添加的点都在原来边的基础上添加，例如有一个点 $x$ 在原来边 {$u,v$} 的基础上添加，那么就将 $x$ 向 $u,v$ 各连一条边，以此类推构成一个 $n$ 个点， $3n-3$ 条边的有向图，让你将这个图划分为两个点集，其中一个点集构成森林，另外一个点集构成独立集，森林和独立集的含义如下。

森林：无环的无向图。
独立集：图中的一组顶点，使得对于每两个顶点，没有连接两者的边。

问：独立集中的顶点权重总和最大为多少。

以下是几个样例的图
样例1

样例2

样例3

做法：

我们可以看到，这个图由若干个三元环组成，为了能够将图划分为两种点集，我们必须在每个三元环中恰好选定一个点作为独立集中的点，因为一个点都不选则会破坏森林约束，选至少两个则会破坏独立集的约束，同时对于一对有至少两个公共点的三元环，确定了答案包含其中一个的某个点之后另一个也随之确定了。因此我们可以知道，答案只可能有三种情况，分别为包含1/2/3的独立集，通过题目中所给图的点—边—点性质我们可以建立一个图，分别从1/2/3开始跑 $bfs$ 即可得到这三个答案，取 $max$ 后输出即可。

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
struct hashfunc//pair哈希
{
    template<typename T, typename U>
    size_t operator() (const pair<T, U> &i) const
    {
        return hash<T>()(i.first) ^ hash<U>()(i.second);
    }
};
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        vector<ll> w(n+1);
        for(int i=1;i<=n;i++)
            cin>>w[i];
        vector<vector<int>> g(n+1);
        unordered_map<P,int,hashfunc> mp;
        auto add = [&](int u,int v)
        {
            g[u].emplace_back(v);
            g[v].emplace_back(u);
        };
        auto tag = [&](int u,int v,int idx)
        {
            mp[{u,v}]=idx;
        };
        tag(1,2,3);
        tag(2,3,1);
        tag(1,3,2);       
        for(int i=4;i<=n;i++)
        {
            int u,v;
            cin>>u>>v;
            if(u>v)swap(u,v);
            add(mp[{u,v}],i);
            tag(u,v,i);
            tag(u,i,v);
            tag(v,i,u);
        }
        ll ans=0;
        vector<int> vis(n+1,0);
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                ll num=0;
                queue<int> q;
                q.emplace(i);
                vis[i]=1;
                while(!q.empty())
                {
                    int now=q.front();
                    q.pop();
                    num+=w[now];
                    for(int x:g[now])
                    {
                        if(!vis[x])
                        {
                            vis[x]=1;
                            q.emplace(x);
                        }
                    }
                }
                ans=max(ans,num);
            }
        }
        cout<<ans<<endl;
    }   
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

1003 - Counting Stickmen

题意：

给你一棵树，问你在这个树中能够找到多少个火柴人，答案对 $998244353$ 取模，它有一条长度为 $1$ 的链作为头部，两条长度为 $2$ 的链作为手臂，一条长度为 $1$ 的链作为身体，两条长度为 $1$ 的链作为腿。

做法：

因为这是一棵树，所以我们可以选择枚举火柴人身体的两个端点(距离为1的两个点)，身体上部为 $x$ ，下部（与脚连接）为 $y$ ，这里先规定一个点 $i$ 的入度为 $in[i]$ ，我们可以知道

以 $x-y $ 为身体的火柴人:

脚的情况为 $leg=\left(\genfrac{}{}{0ex}{}{in[y]}{2}\right)$

头的情况为 $head=in[y]-3$

而手的情况较复杂，首先我们可以知道手的长度需要为 $2$，因此我们可以知道与 $x$ 距离为 $2$ 的点的个数为 $ {\textstyle \sum_{u\in neighbor(x)}} in[u]-in[x]$

我们还要考虑作为手的点不能与 $y$ 点相连（不然就是脚了，因此我们需要减去 $in[y]-1$ ，在这些点中任取两个作为手，则方案数为

$\left(\genfrac{}{}{0ex}{}{({\sum }_{u\in neighbor(x)}in[u]-in[x])-(in[y]-1)}{2}\right)$

我们还要去掉两个手臂相同的情况（即手的父节点为同一个点），方案数为 ${\sum }_{u\in neighbor(x),u\ne y}\left(\genfrac{}{}{0ex}{}{in[u]-2}{2}\right)$

因此脚的情况为 $hand=\left(\genfrac{}{}{0ex}{}{({\sum }_{u\in neighbor(x)}in[u]-in[x])-(in[y]-1)}{2}\right)-{\sum }_{u\in neighbor(x),u\ne y}\left(\genfrac{}{}{0ex}{}{in[u]-1}{2}\right)$

那么身体为 $x-y$ 时对答案的贡献为 $(leg\times head\times hand)MOD998244353$

我们只需要在枚举 $x-y$ 之前 $O(n)$ 预处理每个点的 $in[x]{\sum }_{u\in neighbor(x),u\ne y}\left(\genfrac{}{}{0ex}{}{i}{n}\right)[u]-1{\sum }_{u\in neighbor(x),u\ne y}\left(\genfrac{}{}{0ex}{}{in[u]-2}{2}\right)$ 以及组合数即可。

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
const int mod =998244353;
const int maxn = 500010;
//先要init_c()
int ksm(int a,int b,int p=mod,int res=1)
{
    for( ; b ; a=a*a%p, b>>=1) if(b&1) res=res*a%p;
        return res; 
}
int fac[maxn],inv[maxn];
void init_c(int n=maxn-2)
{
    inv[0]=fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
        inv[n]=ksm(fac[n],mod-2);
    for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int n,int m)
{
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    init_c();
    cin>>t;
    while(t--)
    {
        cin>>n;
        vector<vector<int>> g(n);
        vector<int> in(n,0),son(n),hand(n,0);
        for(int i=1;i<n;i++)
        {
            int u,v;
            cin>>u>>v;
            u--;v--;
            g[u].emplace_back(v);
            g[v].emplace_back(u);
            in[u]++;
            in[v]++;
        }
        for(int i=0;i<n;i++)
        {
            for(int x:g[i])
            {
                son[i]+=in[x];
                if(in[x]-1>=2)
                    hand[i]=(hand[i]+C(in[x]-1,2))%mod;
            }
        }
        int ans=0;
        for(int i=0;i<n;i++)
        {
            if(in[i]>3)
            {
                for(int x:g[i])
                {
                    if(in[x]>2)
                    {
                        int leg=C(in[x]-1,2);
                        int han=(son[i]-in[i]-in[x]+1);
                        han=han>=2?C(han,2):0;
                        han=(han-hand[i]+C(in[x]-1,2)+mod*mod)%mod;
                        ans=(ans+((leg*han%mod)*(in[i]-3))%mod)%mod;
                    }
                }
            }
        }
        cout<<ans<<endl;
    }   
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

1004 - Black Magic

题意：

给你四种积木以及每种积木的个数 $E,L,R,B$ ，其中 E 代表积木的两边都是白色，L 代表积木做白右黑，R 代表左黑右白，B 代表两边都是黑色。要将所有积木都放到一排，其中对于任意两个相邻的块，如果左侧块的右侧和右侧块的左侧都涂成黑色，则将两侧粘贴在一起，使两个块合二为一。问：积木最后最少和最多能变成多少块？

做法：

对于最少的情况，我们尽量让较多的 $L$ 和 $R$ 匹配，最后将 $B$ 放入任意一组 $L,R$ 之中即可

而对于最多的情况，我们将所有的 $L$ 放在最左边，再将所有的 $R$ 放在最右边，再尽量用 $E$ 将 $B$ 隔开即可

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        int e,l,r,b;
        cin>>e>>l>>r>>b;
        n=e+l+r+b;
        int mi=min(l,r);
        if(max(l,r)>0)
            mi+=b;
        else
            mi+=max(0ll,b-1);
        int ma=max(0ll,b-e-1);
        cout<<n-mi<<" "<<n-ma<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

1008 - Triangle Game

题意：

给你三条边，边长分别为 $a,b,c$ 。现 Kate 和 Emilico 二人做游戏，每轮需要令三角形的一边长度减去一正整数，使这个三角形退化的一方负。Kate 先手，双方均采用最优策略，问 Kate 是否会获胜。

做法：

若 $(a-1)\oplus (b-1)\oplus (c-1)\ne 0$ 则先手必胜，反之则先手必败，证明略

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(((a-1)^(b-1)^(c-1))!=0)
            cout<<"Win"<<endl;
        else
            cout<<"Lose"<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31