2022“杭电杯”中国大学生算法设计超级联赛（10）签到题5题

Solved Problem ID Title Ratio (Accepted / Submitted)
1001 Winner Prediction 14.38% (391/2719)
1002 Photos 23.83% (107/449)
1003 Wavy Tree 37.31% (670/1796)
1004 Average Replacement 15.13% (303/2003)
1005 Apples 30.95% (26/84)
1006 Triangle Rotation 30.00% (18/60)
1007 Even Tree Split 41.73% (782/1874)
1008 Minimum Diameter 18.52% (75/405)
1009 Painting Game 26.44% (588/2224)
1010 Tree 14.78% (17/115)
1011 Maximum Triangles 14.05% (17/121)
1012 Expected Inversions 10.66% (29/272)

7.Even Tree Split

Problem Description
You are given an undirected tree with nn nodes. It’s guaranteed that nn is even.

You are going to delete some of the edges (at least 11), and have to let each of the remaining connected components have an even number of vertices.

Calculate the number of ways to delete the edges that satisfy such constraints, modulo 998244353998244353.

Input
The first line contains an integer T(1 \leq T \leq 30)T(1≤T≤30) - the number of test cases.

The first line of each test case contains an integer n(1 \leq n \leq 10^5)n(1≤n≤10
5
) - the number of vertices on the tree.

The next n-1n−1 lines of each test case contain two integers u,v(1 \leq u,v \leq n)u,v(1≤u,v≤n), representing an edge between uu and vv.

It is guaranteed that the input graph is a tree with even number of vertices.

Output
For each test case, output the number of ways to delete the edges that satisfy such constraints in a single line, modulo 998244353998244353.

Sample Input
2
2
1 2
4
1 2
2 3
3 4
Sample Output
0
1

题意：

• 给出一棵n个点的树，保证n为偶数。删除树中至少一条边，让剩下的联通分量中包含的点的个数都为偶数个。求方案数%998244353。

思路：

• 对每条边，如果删去该边后两棵树点数都为偶数，则称其为好边。显见一个边集是合法的当且仅当边集内都为好边。
• 则答案为$2^c-1$ ，其中 c为好边数量。时间复杂度O(n)。
• 预处理出每个点的子树大小siz[x]，再dfs遍历点，对于点x，若siz[x]%2=0, 显然x的父亲边为好边，原集合可以被划分为两个合法的边集。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const LL maxn = 1e5+10, mod = 998244353;
vector<int>G[maxn];
LL ans = 1;
int siz[maxn];
void dfs2(int x, int f){
    siz[x] = 1;
    for(int y : G[x]){
        if(y==f)continue;
        dfs2(y,x);
        siz[x] += siz[y];
    }
}
void dfs(int x, int f, int d){
    if(siz[x]%2==0 && x!=1){
        ans = (ans*2)%mod;
    }
    for(int y : G[x]){
        if(y==f)continue;
        dfs(y,x,d+1);
    }
}

int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        for(int i = 1; i <= n; i++)G[i].clear(), siz[i] = 0;
        ans = 1;
        for(int i = 1; i <n; i++){
            int u, v;  cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs2(1,-1);
        dfs(1,-1, 1);
        cout<<ans-1<<"\n";
    }
    return 0;
}

3.Wavy Tree

Wavy Tree
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 51 Accepted Submission(s): 20

Problem Description
An array a of length n is said to be wavy, if for each 1<imax{ai−1,ai+1} or ai<min{ai−1,ai+1} holds.

You are given an array b of length n (1≤bi≤109) , consisting of integers. You want to make the array wavy. To do that you can spend some coins, with each coin you can make one element in b increase or decrease by 1. Calculate the minimum number of coins you need to spend to make the array wavy.

Input
The first line contains the number of test cases T (1≤T≤103).

The first line of each test case contains one integer n (1≤n≤106) - the length of array b .

The second line contains n integers b1,b2,⋯,bn (1≤bi≤109) - the array b .

It’s guarantee that the sum of n among all test cases is not greater than 3×106 .

Output
For each test case, output one integer, the minimum number of coins you need to spend to make the array wavy.

Sample Input
3
4
1 7 6 5
6
1 2 3 4 5 6
6
1 1 4 5 1 4

Sample Output
2
4
4

Source
2022“杭电杯”中国大学生算法设计超级联赛（10）

题意：

• 给出一个长为n的数组，你每次操作可以将其中的一个数字加一或减一，求最少操作次数让该数组成为一个波形数组。
• 波形数组的判定为，数组中除了第一个和最后一个外的元素a[i]，都满足两边的元素同时大于a[i]或小于a[i]。

思路：

• 首先波形数组最多只要两种，奇数位大或者偶数位大，没有其他情况。
• 因此，分两类，先确定是奇数位为大数还是偶数位为大数。接着从左往右贪心，对每个i=2,3,4,n ，如果 ai与ai-1的大小关系不符合条件，则调整 。最后取个min即可。
• 复杂度O(n)。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
typedef long long LL;
LL a[maxn], b[maxn];
int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        LL ans1 = 0, ans2 = 0;
        for(int i = 1; i <= n; i++)cin>>a[i], b[i]=a[i];
        //1大2小
        for(int i = 2; i <= n; i++){
            if(i%2==0){
                if(a[i]>=a[i-1]){          //波谷,不满足就调整为a[i-1]-1
                    ans1 += a[i]-(a[i-1]-1);
                    a[i] = a[i-1]-1;
                }
            }else{
                if(a[i]<=a[i-1]){          //波峰,不满足就调整为a[i-1]+1
                    ans1 += a[i-1]+1-a[i];
                    a[i] = a[i-1]+1;
                }
            }
        }
        //1小2大
        for(int i = 2; i <= n; i++){
            if(i%2==0){
                if(b[i]<=b[i-1]){          //波峰,不满足就调整为b[i-1]+1
                    ans2 += b[i-1]+1-b[i]; 
                    b[i] = b[i-1]+1;
                }
            }else{
                if(b[i]>=b[i-1]){          //波谷,不满足就调整为b[i-1]-1
                    ans2 += b[i]-(b[i-1]-1);
                    b[i] = b[i-1]-1;
                }
            }
        }
        cout<<min(ans1,ans2)<<"\n";
    }
    return 0;
}

9.Painting Game

Painting Game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 57 Accepted Submission(s): 23

Problem Description
There is a paper strip divided into n blank grids. For each i(1≤i<n), grid i and i+1 are considered adjacent.

Alice and Bob are going to play a game on the strip. They take turns to make move. In one move the player must paint one of the remaining blank grids black, while keeping the rule that no two black grids are adjacent.

The game ends when one of the players is unable to paint any grid, and the score of the game is defined as the total number of grids painted black. Alice wants to minimize the score, while Bob wants to maximize it.

Given n and the side starting the game, find out the final score when both players play optimally.

Input
The first line contains an integer T(1≤T≤105) - the number of test cases.

The first line of each test case contains an integer n(1≤n≤109) and a string s(s∈{Alice,Bob}) - the number of grids and the starting player of this game.

Output
For each test case, output the final score when both players play optimally in a single line.

Sample Input
4
3 Alice
3 Bob
19 Alice
23 Bob

Sample Output
1
2
8
10

Source
2022“杭电杯”中国大学生算法设计超级联赛（10）

题意：

• 有n个空白网格，A和B轮流操作，每次需要将一个涂为黑色，同时保持没有两个黑色网格相邻。无法涂黑时游戏结束。
• Alice 想要最小化黑格数，而Bob想要最大化它。给定n和先手是谁，求两人都最佳策略下最后的黑格子数量。

思路：

• 我们把涂黑操作想象成剪掉连续的三个格子。如果每个连续段长度都<=2 ，那么结果就确定了。
  在此之前，可以发现，Alice 的一种最优策略是：选某个连续段的左数第二个格子涂黑。
  Bob 的一种最优策略是：选某个连续段的左数第三个格子涂黑。
• 设f(n) , g(n) 分别为 Alice、Bob 面对长度为n的空纸带时的答案。则有f(n) = g(n-3)+1, g(n) = f(n-3)+2，注意到f(n) = f(n-7)+3, g(n) = g(n-7)+3，因此可以快速算出答案。
• 对于<=7内的边界情况可以枚举以后特判一下。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int T;  cin>>T;
    while(T--){
        int n;  string op;  cin>>n>>op;
        int ans = n/7*3;
        if(op[0]=='A'){
            if(n%7>=1) ans++;
            if(n%7>=4) ans++;
            if(n%7>=6) ans++;
        }else{
            if(n%7>=1) ans++;
            if(n%7>=3) ans++;
            if(n%7>=5) ans++;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

1.Winner Prediction

Winner Prediction
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 187 Accepted Submission(s): 52

Problem Description
A tournament consisting of n participants is currently taking place. The players are numbered from 1 to n. Every match is between two participants, and there are no draws. The participant who wins the most matches wins the entire tournament; if there are multiple participants tied at the first place, all of them win the tournament.

At the current state, some matches have ended, and others are yet to start. You are given the results of all ended matches. Write a program to determine whether it is possible for player 1 to win the tournament.

You are given T independent test cases. Solve each of them.

Input
The first line of input consists of a single integer T(1≤T≤100), indicating the number of test cases. Then T test cases follow.

Each of the T test cases consists of multiple lines.

The first line contains three integers n,m1,m2(1≤n≤500,1≤m1,m2≤1000), indicating the number of participants, the number of ended matches and the number of upcoming matches.

Each of the next m1 lines contains three space-separated integers x,y,z(1≤x,y≤n,x≠y,0≤z≤1), indicating an ended match between player x and player y , z=1 means player x won the match and z=0 means player y won the match.

Each of the next m2 lines contains two space-separated integers x,y(1≤x,y≤n,x≠y), indicating an upcoming match between player x and player y.

Output
For each test case, if it is possible of player 1 to win the tournament, print a line YES; otherwise print a line NO.

Sample Input
2
4 2 1
2 3 1
3 2 1
1 4
4 2 2
2 3 1
2 4 1
1 2
3 4

Sample Output
YES
NO

Source
2022“杭电杯”中国大学生算法设计超级联赛（10）

题意：

• 有n个人在进行比赛，现在有m1场已经结束的比赛，给出x和y比，z表示谁赢。还有m2场尚未进行的比赛，给出x和y将要比。 每个人获胜就可以获得1分。
• 现在可以自由安排未进行的比赛的胜负，求最优情况下1能否成为最高分（可以有其他同分）

思路：

• 注意未进行的比赛可以有1和3比试很多场，是独立的，如果算在一起可能会TLE。
• 先让 1 号选手赢下所有和他有关的比赛，设此时选手i 赢了 ai场比赛。如果存在某个 ai>a1则 1号选手不可能成为冠军。因此选手 i至多还能再赢 bi = a1-ai场比赛。
• 说实话，最大流是我未曾设想过的道路（考虑建立一张网络流图：每场未进行的比赛在图中用一个点表示，源点向它连容量为 1的边，它向它的两个参赛选手的对应点各自连容量为 1 的边，选手i 的对应点向汇点连容量为 bi的边。）计算该图最大流，若源点出发的边满流则答案为 YES ，否则为 NO 。

#include<bits/stdc++.h>
using namespace std;

//最大流模板
namespace Flow{
    struct Edge{
        int To, Val, Nxt;
    } Ed[10005];
    int n, S, T, Head[2005], cur[2005], dis[2005], cnt;
    void AddEdge(int x, int y, int val){
        Ed[++cnt] = (Edge){y, val, Head[x]};
        Head[x] = cnt;
        Ed[++cnt] = (Edge){x, 0, Head[y]};
        Head[y] = cnt;
    }
    bool bfs(){
        for (int i = 1; i <= n; i++)dis[i] = 1e9;
        queue<int> Q;
        Q.push(S);
        dis[S] = 0;
        while (!Q.empty()){
            int Now = Q.front();
            Q.pop();
            for (int i = Head[Now]; i != -1; i = Ed[i].Nxt){
                if (dis[Ed[i].To] == 1e9 && Ed[i].Val){
                    Q.push(Ed[i].To);
                    dis[Ed[i].To] = dis[Now] + 1;
                }
            }
        }
        return dis[T] != 1e9; //汇点不可达，已求出最大流
    }
    int dfs(int x, int val){
        if (x == T || val == 0){
            return val;
        }
        int Out = 0;
        for (int &i = cur[x]; i != -1; i = Ed[i].Nxt){
            if (dis[Ed[i].To] != dis[x] + 1 || !Ed[i].Val)
                continue;
            int tmp = dfs(Ed[i].To, min(val, Ed[i].Val));
            val -= tmp;
            Out += tmp;
            Ed[i].Val -= tmp;
            Ed[i ^ 1].Val += tmp;
            if (val == 0)
                break;
        }
        return Out;
    }
    int Dinic(){
        int ans = 0;
        while (bfs()){  //bfs增广路
            memcpy(cur, Head, sizeof(cur));
            ans += dfs(S, 1e9);
        }
        return ans;
    }
}

int n, m1, m2, s[510];  //分数
int main(){
    int T;  scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n, &m1, &m2);
        for(int i = 1; i <= n; i++)s[i] = 0;
        for(int i = 1; i <= m1; i++){
            int x, y, z;  cin>>x>>y>>z;
            if(z==1)s[x]++;
            else s[y]++;
        }
        Flow::n = n+m2+2; //n个选手+m2场比赛+源点汇点
        Flow::S = n+m2+1;  Flow::T = n+m2+2;
        Flow::cnt = -1;
        for(int i = 1; i <= Flow::n; i++)Flow::Head[i] = -1;
        int cc = 0;
        for(int i = 1; i <= m2; i++){
            int x, y;  cin>>x>>y;
            if(x==1 || y==1){ s[1]++; continue;}else cc++;
            Flow::AddEdge(Flow::S, n+i, 1);      //源点到比赛连一条边
            Flow::AddEdge(n+i, x, 1);            //比赛到选手x连一条边
            Flow::AddEdge(n+i, y, 1);            //比赛到选手y连一条边
        }
        int ok = 1;
        for(int i = 2; i <= n; i++){
            if(s[i] > s[1])ok = 0;
            Flow::AddEdge(i,Flow::T, s[1]-s[i]); //选手到汇点连一条边,容量为最多能再赢的场次
        }
        //若源点出发的边满流，则代表存在能安排不会溢出s1-si的方案。
        if(ok==0)cout<<"NO\n";
        else cout<<(Flow::Dinic() == cc ? "YES" : "NO")<<"\n";
    }
    return 0;
}

• 这题也可以用可反悔贪心做

#include<bits/stdc++.h>
using namespace std;

int n, m1, m2, s[510];  //分数
int main(){
    int T;  scanf("%d",&T);
    while(T--){
        //数据读入+特判
        scanf("%d%d%d",&n, &m1, &m2);
        for(int i = 1; i <= n; i++)s[i] = 0;
        for(int i = 1; i <= m1; i++){
            int x, y, z;  cin>>x>>y>>z;
            if(z==1)s[x]++;
            else s[y]++;
        }
        vector<pair<int,int> >bs;
        for(int i = 1; i <= m2; i++){
            int x, y;  cin>>x>>y;
            if(x==1 || y==1)s[1]++;
            else bs.push_back({x,y});
        }
        int ok = 1;
        for(int i = 1; i <= n; i++){
            if(s[i]>s[1]){ ok = 0; break;}
        }
        if(ok==0){ cout<<"NO\n"; continue; }
        
        //函数定义与初始化
        vector<vector<int>>win(n+10);           //win[x]=y, 表示x赢了y
        function<int(int)>check = [&](int x){
            return win[x].size()+s[x]+1<=s[1];  //让x再赢一局不会让1输掉
        };
        vector<int>vis(n+10,0);
        function<void()>init_vis = [&]{
            for(int i = 1; i <= n; i++)vis[i] = 0;
        };
        //能否在不影响1的情况下，让x赢得和y的比赛 (有点像找增广路)
        function<int(int, int)>insert = [&](int x, int y){
            if(vis[x]) return 0;
            if(check(x)){                        //边界，如果可以再赢一局，那就赢
                win[x].push_back(y);
                return 1;
            }
            vis[x] = 1;
            int kk = -1, len = win[x].size();
            for(int i = 0; i < len; i++){        //遍历x赢过的人
                if(insert(win[x][i], x)){        //反悔：尝试让那个人赢掉x
                    kk = i;  break;              //成功了，就返回那个人的id
                }
            }
            if(kk >= 0)win[x][kk] = y;           //成功把曾经赢的kk换成了y
            kk = kk>=0;
            return kk;                           //成功换掉
        };

        //可反悔贪心
        ok = 1;
        for(auto x : bs){      //遍历所有的比赛 x vs y
            if(check(x.first)){
                //如果x获胜不会让1输，就先暂时让x赢
                win[x.first].push_back(x.second);
            }else if(check(x.second)){
                //如果y获胜不会让1输，就先暂时让y赢
                win[x.second].push_back(x.first);
            }else {
                //尝试在不影响1的情况下，反悔让x之前赢的某次输掉，然后替换成赢了y
                if(!insert(x.first, x.second)){
                    init_vis();
                    //尝试在不影响1的情况下，反悔让y之前赢的某次输掉，然后替换成赢了x
                    if(!insert(x.second,x.first)){
                        ok = 0; break;
                    }
                    init_vis();
                }
            }
        }
        if(ok==1)cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

4.Average Replacement

Average Replacement
Time Limit: 6000/6000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 202 Accepted Submission(s): 54

Problem Description
There are n people in a group and m pairs of friends among them. Currently, each person writes an integer on his hat. They plan to play the following game many times: everyone replaces his number on his hat with the average number of his number and all of his friends’ numbers. That is, if before the game the person has a0 written on his hat and a total of k friends, each having number a1,…,ak, then after the game the number on his hat becomes a0+⋯+akk+1. Note that numbers may become non-integers.

It can be proved that by playing more and more games, each number converges to a certain value. Given the initial numbers written on the hats, your task is to calculate these values.

Input
The first line contains the number of test cases T (1≤T≤100).

For each test case, the first line contains two integers n,m (1≤n,m≤105) .

The second line contains n integers a1,a2,⋯,an (1≤ai≤108) , indicating the number on each hat.

Each of the following m lines contains two integers u,v (1≤u,v≤n) , indicating a pair of friends.

It’s guaranteed that there are no self-loop or multiple edges on the graph, and there are at most 20 test cases such that n>1000 or m>1000.

Output
For each test case, output n integers in n lines, indicating the value of each person at last, and the result are reserved with 6 digits after the decimal point.

Sample Input
2
2 1
1 2
1 2
4 2
1 2 3 4
1 2
3 4

Sample Output
1.500000
1.500000
1.500000
1.500000
3.500000
3.500000

Source
2022“杭电杯”中国大学生算法设计超级联赛（10）

题意：

• 有n个人，m对朋友关系，每个人初始有一个数字ai。
• 现在开始玩游戏，对于一轮游戏，每个人的数字都会变为他和他所有的朋友（与它直接相连）的数字之和的平均值（浮点数）。
• 求无数轮游戏之后每个人的数字（最终会收敛到一个固定值）。

思路：

• 结论1：显然，每个连通块内的数最后会趋于同一个值。
  因为假设若干轮次之后，某个联通块内还有一个人的数字跟其他数字不一样，那么他就会与他再进行一轮游戏，将数字平均下来。
• 结论2：对于第i个人的朋友数量deg[i]， 每个联通块内$\sum a_i(deg[i]+1)$为定值。
• 所以答案，每个点的值为所在联通块 $\frac{\sum (in[i]+1)\ast a[i]}{\sum (in[i]+1)}$ 的均值。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 2e5+10;

int fa[maxn+10];
void init(int n){for(int i = 0; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int count(int n){int cnt=0; for(int i = 1; i <= n; i++)if(fa[i]==i)cnt++;return cnt;}

LL a[maxn], in[maxn], s1[maxn], s2[maxn];

int main(){
    int T;  scanf("%d",&T);
    while(T--){
        int n, m;  scanf("%d%d",&n,&m);
        for(int i = 1; i <= n; i++)scanf("%d",&a[i]), in[i]=s1[i]=s2[i]=0;
        init(n+1);
        for(int i = 1; i <= m; i++){
            int u,v;  scanf("%d%d",&u,&v);
            in[u]++;  in[v]++;
            merge(u,v);
        }
        for(int i = 1; i <= n; i++){
            int x = find(i);
            s1[x] += (in[i]+1)*a[i];
            s2[x] += (in[i]+1);
        }
        for(int i = 1; i <= n; i++){
            int x = find(i);
            printf("%.6lf\n", double((long double)s1[x]/s2[x]));
        }
    }
    return 0;
}

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/126412439