2022 Hangzhou Electric Power Multi-School 9 (Summary + Supplement)

summary

Today, this multi-school should be the best one to hit this summer vacation (although the ranking is not very high). My starting teammate found that the tree dp was signed in for question 1009. I thought about guessing an even-numbered side. I stared at my teammate and wrote A for ten minutes. Then we went to see 1003 again. After my teammate told me the question, I guessed a greedy conclusion, "The first one is top or bottom sweep twice". Team-mate 2 thought it was OK to run and write. I went to see the game theory of 1009 with teammate 1. After several games, we reached a false conclusion and immediately jumped to wa. When teammate 2 finished 1003 and came to the false conclusion before hack with us, I guessed that cunning Bob could reserve a place for himself each time. Teammate 2 got hack-like example to write directly. Finally, because some small details t2 hair (I asked him to check him without checking) after acs, then we looked at 1001 together, teammate 1 looked and said it would be network streaming. As a graph theorist, I did not think about how to build the map right away at first, but after the teammate said network streaming, he built a sample for me and ran away. I could only bury my head in thought, after thinking for a while, I found it seemed to be an active network streaming problem in the upper and lower boundaries. After drawing the board and running the sample, I ran the sample my teammate had made before and submitted the ACS directly after passing the teammate's sample. At this time, two teammates have been making trouble for 1004 for more than an hour, so I joined the discussion. After making our own data (up to more than two hours) and taking violent shots several times, we put forward a formula that feels very right to ourselves, wrote the result and showed tle (the card cin), then changed it. Finally, I found that my teammate did not open long long after changing to scanf, which caused a local explosion int. It was changed and passed at last.

Problem

1007 - Even Tree Split

Topic:

Give you one n n n-node tree( n n n is even), you can delete at least one edge from the tree so that each connected block node is even after deletion and ask how many deletion schemes there are. Answer pair 998244353 998244353 998244353.

Practice:

From observation, we can see that the number of subtree nodes including the points connected by an edge is even. This edge is a deletable edge, and we can use d f s dfs dfs finds all these edges and the answer is 2 n u m − 1 2^{num}-1 2num−1

Code:

/*
 author:wuzx
 */

#include<bits/stdc++.h>
#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;
}

1003 - Wavy Tree

Topic:

Give you a length of n n n array, you can do a + 1/-1 operation on any of the elements in the array, and ask how many operations you need to do at least to make the array a wave array, a wave array, for each number i i i have both a [ i ] < m i n ( a [ i − 1 ] , a [ i + 1 ] ) a[i]<min(a[i-1],a[i+1]) A[i]<min (a[i_1],a[i+1]) or a [ i ] > m a x ( a [ i + 1 ] , a [ i − 1 ] ) a[i]>max(a[i+1],a[i-1]) a[i]>max(a[i+1],a[i−1])

Practice:

Greedy, let's assume that the first element is the crest or trough of the wave and simply sweep the minimum twice.

Code:

/*
 author:wuzx
 */

#include<bits/stdc++.h>
#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;
}

1001 - Winner Prediction

Topic:

Yes n n n people are playing, and now there are m 1 m1 The m1 match has been decided, there are m 2 m2 The winner or loser of the m2 match is unknown. A person can win the championship only if no one wins the match more than he does. Ask 1 1 Is it possible for runner 1 to win the championship

Practice:

We can start with m 2 m2 In m2 games 1 1 Competition Decision of Player 1 1 1 Win No. 1, and then run the remaining unknown wins and losses to the upper and lower active sink network streams.

We know that if 1 1 No. 1 wants to win the championship, so the number of wins for other players cannot be greater than 1 1 Number 1 wins, so we can play every game with an indeterminate winner ( u , v ) (u,v) (u,v) Build a graph where the source point S connects a lower bound to V 0 0 0, the upper bound is n u m [ 1 ] − n u m [ v ] num[1]-num[v] Edges of num[1]num[v], u , v u,v u,v compete against each other i   ( g a m e i ) i\space (gamei) i (gamei) with a lower bound of 0 0 0, the upper bound is 1 1 1 side, race i   ( g a m e i ) i\space (gamei) i (gamei) Connect a lower and upper bounds to the sink 1 1 1 side (so that we can guarantee one winner in each match), and finally, from point S to point u, we connect a lower bound to 0 0 0, the upper bound is n u m [ 1 ] − n u m [ i ] ( 2 ≤ i ≤ n ) num[1]-num[i](2\le i\le n) Edge of num[1]num[i](2 < I < n), which guarantees that no one will win more than the rest of the game 1 1 Player 1)

After the graph is built, we run an active sink upper and lower bounds feasible flow to determine if there is a feasible flow.

Code:

/*
 author:wuzx
 */

#include<bits/stdc++.h>
#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;//Return false if the end point (starting point) cannot be reached 
    }
    int dfs(int st,int end,int flo)//dfs is to find the maximum increment of node u at residual 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;
}

Tags: C++ Algorithm Graph Theory greedy algorithm dfs

Posted by thomasgrant on Thu, 18 Aug 2022 22:30:52 +0300