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

总结

今天这把多校应该是这个暑假打的最爽的一把多校了（虽然排名不是很高），开局队友发现树形dp签到题1009，我想了想猜了个”找子节点为偶数的边“，我盯着队友写了十几分钟一发A了，然后我们又去看1003，队友跟我说完题之后我猜了个贪心结论“第一个是顶或者底扫两次”，队友2想了想觉得没啥问题就跑去写了，我和队友1去看1009的小博弈论，在博弈了几次之后我们得出了个假结论，直接莽了一发wa，这时队友2写完1003，跑过来跟我们一起hack之前的假结论，我推了一会发现狡猾的Bob可以每次多给自己预留一个位置，队友2得到hack样例直接开写，最后因为一些小细节t了2发（我让他检查他不检查）后ac了，接着我们又一起看1001，队友1看了一会说是网络流，作为图论选手的我一开始并没有马上想出怎么建图，但队友说完网络流之后直接给我造了个样例就跑了，我只能埋头苦想，想了一会之后发现好像是一个有源汇上下界网络流问题，在调出板子建好图跑完样例之后，又把队友之前造的样例跑了，过了队友的样例后我直接提交ac了。此时两个队友已经对着1004捣鼓了一个多小时了，我遂加入讨论，经过我们自己造的数据多次（长达两个多小时）与暴力对拍后，我们推出了一个自我感觉非常对的式子，写好后交结果显示tle（这题卡cin），遂改来改去，最后我发现队友因为换成scanf后没开long long导致有个地方爆int，改了之后终于通过了。

题解

1007 - Even Tree Split

题意：

给你一个 $n$ 节点的树（$n$是偶数），你可以从树中删除至少一条边，使得删除后各个连通块节点的个数为偶数，问有多少种删除方案。答案对 $998244353$ 取模。

做法：

由观察我们可以知道，包含一条边所连的点在内的子树节点个数为偶数是，这条边是可删边，我们可以用 $dfs$ 找出所有的这些边，答案即为 $2^{num}-1$

代码：

/*
 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;
const int mod = 998244353;
int n,m,k;long long POW(long long a,long long b,long long p)
{
    a%=p;
    long long res=1;
    while(b){
    if(b&1)
        res=res*a%p;
        a=a*a%p;
        b=b>>1;
    }
    return res%p;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        vector<vector<int>> g(n);
        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);
        }
        vector<int> vis(n,0);
        int ans=0;
        function<int(int)> dfs = [&](int now)
        {
            int num = 1;
            vis[now]=1;
            for(auto x:g[now])
            {
                if(!vis[x])
                {
                    int son = dfs(x);
                    if(son%2==0)
                        ans++;
                    num+=son;
                }
            }
            return num;
        };
        dfs(1);
        cout<<POW(2,ans,mod)-1<<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

1003 - Wavy Tree

题意：

给你一个长度为 $n$ 的数组，你可以对数组中任一一个元素进行+1/-1的操作，问至少要做多少次操作才能使数组变成波浪数组，波浪数组，即对于每一个数 $i$ 都有 $a[i]<min(a[i-1],a[i+1])$ 或 $a[i]>max(a[i+1],a[i-1])$

做法：

贪心，我们假设第一个元素为波浪的顶峰或低谷，直接扫两遍去最小值即可

代码：

/*
 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--)   
    {
        cin>>n;
        vector<int> a(n),b(n);
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            b[i]=a[i];
        }
        int cnt1=0,cnt2=0;
        for(int i=1;i<n;i++)
        {
            if(i%2==0)
            {
                if(a[i]>=a[i-1])
                {
                    cnt1+=a[i]-a[i-1]+1;
                    a[i]=a[i-1]-1;
                }
                if(b[i]<=b[i-1])
                {
                    cnt2+=b[i-1]-b[i]+1;
                    b[i]=b[i-1]+1;
                }
            }
            else
            {
                if(a[i]<=a[i-1])
                {
                    cnt1+=a[i-1]-a[i]+1;
                    a[i]=a[i-1]+1;
                }
                if(b[i]>=b[i-1])
                {
                    cnt2+=b[i]-b[i-1]+1;
                    b[i]=b[i-1]-1;
                }
            }
        }
        cout<<min(cnt1,cnt2)<<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

1001 - Winner Prediction

题意：

有 $n$ 个人在打比赛，现在已经有 $m1$ 场比赛胜负已定， 有 $m2$ 场比赛胜负未知，一个人获得冠军的条件是没有人赢得比赛的次数大于他，问 $1$ 号选手是否有可能赢得冠军

做法：

我们可以先将 $m2$ 场比赛中有 $1$ 号选手的比赛判 $1$ 号赢，然后将剩下的胜负未知的比赛建图跑有源汇上下界网络流。

我们知道，如果 $1$ 号选手想要获得冠军，那么其他选手的胜利次数是不能大于 $1$ 号选手的胜利次数的，因此我们可以对每个胜负未定的比赛 $(u,v)$ 建这么一个图，源点S向v连一条下界为 $0$，上界为 $num[1]-num[v]$ 的边，$u,v$ 分别向比赛 $i(gamei)$ 连一条下界为 $0$ ，上界为 $1$ 的边，比赛 $i(gamei)$ 再向汇点连一条上下界均为 $1$ 的边（这样我们就可以保证每个比赛都有一个人获胜），最后我们再源点S向u连一条下界为 $0$ ，上界为 $num[1]-num[i](2\le i\le n)$ 的边（这条边保证了把剩余比赛比完之后每个人的获胜次数都不会大于 $1$ 号选手）

建好图后，我们对这个图跑一个有源汇上下界可行流判断是否有可行流即可。

代码：

/*
 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;
struct dinic{
    const int nn;
    int INF = inf*inf;
    struct Edge{
        int to,cap,flow;
        Edge(int to,int cap,int flow):to(to),cap(cap),flow(flow){}
    };
    vector<int> dis,cur;
    vector<Edge> e;
    vector<vector<int>> g;
    dinic(int n1):nn(n1),dis(n1+1),cur(n1+1),g(n1+1){}
    void add(int u,int v,int w)
    {
        g[u].emplace_back((int)e.size());
        e.emplace_back(v,w,0);
        g[v].emplace_back((int)e.size());
        e.emplace_back(u,0,0);
    }
    void add1(int u,int v,int w)
    {
        g[u].emplace_back((int)e.size());
        e.emplace_back(v,w,0);
    }
    bool bfs(int st,int end)
    {
        fill(dis.begin(),dis.end(),-1);
        dis[st]=0;
        queue<int> q;
        q.push(st);
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int i:g[u])
            {
                // auto [v,w,fo]=e[i];
                int v=e[i].to,w=e[i].cap,fo=e[i].flow;
                // tie(v,w,fo)=e[i];
                if(dis[v]==-1&&w>0)
                {
                    q.push(v);
                    dis[v]=dis[u]+1;
                }
            }
        }
        return dis[end]!=-1;//若不可以到终点（起点）就返回false 
    }
    int dfs(int st,int end,int flo)//dfs就是求节点u在残量为flo时的最大增量
    {
        if(st==end)
            return flo;
        int delta=flo;
        for(int i=cur[st];i<(int)g[st].size();i++)
        {
            int j=g[st][i];
            // auto [v,w,fo]=e[j];
            int v=e[j].to,w=e[j].cap,fo=e[j].flow;
            cur[st]++;
            if((dis[v]==dis[st]+1)&&w>0)
            {
                int d=dfs(v,end,min(delta,w));
                e[j].cap-=d;
                e[j^1].cap+=d;
                e[j].flow+=d;
                e[j^1].flow-=d;
                delta-=d;
                if(delta==0)
                    break;
            }
        }
        return flo-delta;
    }
    int max_flow(int st,int end)
    {
        int maxflow=0;
        while(bfs(st,end))
        {
            fill(cur.begin(),cur.end(),0);
            maxflow+=dfs(st,end,INF);
        }
        return maxflow;
    }
};
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    int m1,m2,u,v,z;
    while(t--)
    {
        cin>>n>>m1>>m2;
        vector<int> num(n+1);
        for(int i=1;i<=m1;i++)
        {
            cin>>u>>v>>z;
            if(z==1)
                num[u]++;
            else
                num[v]++;
        }
        int st1=n+m2+1,end1=n+m2+2;
        int st=n+m2+3,end=n+m2+4;
        dinic solve(n+m2+10);
        vector<int> sum(n+m2+10);
        auto ad1 = [&](int u,int v,int w,int low)
        {
            solve.add(u,v,w);
            sum[u]-=low;
            sum[v]+=low;
        };
        for(int i=1;i<=m2;i++)
        {
            cin>>u>>v;
            if(u==1||v==1)
                num[1]++;
            else
            {
                ad1(u+m2,i,1,0);
                ad1(v+m2,i,1,0);
                ad1(i,end1,1,1);
            }
        }
        if(num[1]<*max_element(num.begin(),num.end()))
        {
            cout<<"NO"<<endl;
            continue;
        }
        for(int i=2;i<=n;i++)
            ad1(st1,i+m2,num[1]-num[i],0);
        ad1(end1,st1,inf,0);
        int tot=0;
        for(int i=1;i<=n+m2+2;i++)
        {
            if(sum[i]<0)
                solve.add(i,end,-sum[i]);
            else
            {
                solve.add(st,i,sum[i]);
                tot+=sum[i];
            }
        }
        int flow = solve.max_flow(st,end);
        if(flow!=tot)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

1009 - Painting Game

题意：

给一个 $1\times n$ 的网格，Alice 和 Bob 轮流给一个网格涂成黑色，要求不能在已经涂成黑色的网格旁涂色，Alice 想最小化黑色网格数量，Bob想最大化黑色网格数量，给出 $n$ 和先手的人，输出黑色网格数量。

做法：

通过模拟他俩的博弈可以知道，每七个网格都会有三个被涂成黑色，因此我们可以先对答案进行 $ans+=(n/7)\ast 3,n\%=7$ 再对剩余的 $n$ 进行特判即可。

代码：

/*
 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);
    vector<int> a(7),b(7);
    a[1]=a[2]=a[3]=1;a[4]=2;
    b[1]=b[2]=1;b[3]=b[4]=2;
    for(int i=5;i<=6;i++)
    {
        a[i]=b[i-3]+1;
        b[i]=a[i-4]+2;
    }
    cin>>t;
    while(t--)
    {
        string ss;
        cin>>n>>ss;
        int ans=n/7*3;
        n%=7;
        if(ss[0]=='A')
            ans+=a[n];
        else
            ans+=b[n];
        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