首页 > 其他分享 >2022杭电多校10

2022杭电多校10

时间:2022-09-18 17:46:42浏览次数:103  
标签:杭电多校 return idx 10 int void flow 2022 include

G. Even Tree Split

题意:

给定一个节点数为偶数的树,请问有多少种方案使得切割开一条边使得剩余连通块的大小都是偶数。

分析:

我们发现断开一条边是独立的,因为如果两个连通块分开后都是偶数再断开仍然是偶数。因此我们只需要找到有多少个满足要求的边,再统计这个边选与不选即可。

如何判断该边是否满足要求呢?

先预处理出所有树的size,那么如果他的子树大小size是偶数,n也是偶数,上面部分也是偶数,说明这个边就是能够被分割的,暴力O(n)统计即可。

最后记得减去一个全都不选的情况。

void dfs(int u, int fa) {
    siz[u] = 1;
    for (int v : g[u]) {
        if (v == fa)continue;
        dfs(v, u);
        siz[u] += siz[v];
    }
}
void dfs1(int u, int fa) {
    for (int v : g[u]) {
        if (v == fa)continue;
        if ((siz[v] % 2) == 0)tot++;
        dfs1(v, u);
    }
}
void slove() {
    cin >> n;
    for (int i = 1; i <= n; i++)g[i].clear();
    for (int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    tot = 0;
    dfs(1, 0);
    for (int i = 1; i <= n; i++)if (siz[i] % 2 == 0)tot++;
    tot--;
    cout << (ksm(2, tot, mod) - 1 + mod)%mod<< endl;
}

B. Wavy Tree

题意:

定义一个特殊数组a,使得除了两个端点之外,所有的点都小于相邻的两个边或者大于相邻两个边,给定一个数组,你可以修改一个数的大小,代价就是你修

改的量,请最小化代价使得该数组变成特殊数组。

分析:

只有“W” 和“M” 形状 所以只要将两种情况分别考虑即可

ll fun1() {
    for (int i = 1; i <= n; i++)b[i] = d[i];
    ll res = 0;
    for (int i = 2; i <= n; i++) {
        if (i % 2 == 0) {
            // < 0
            if (b[i] >= 0) {
                res += (b[i] + 1);
                b[i + 1] += (b[i] + 1);
                b[i] = -1;
            }
        }
        else {
            // > 0
            if (b[i] <= 0) {
                res += (-b[i] + 1);
                b[i + 1] -= (-b[i] + 1);
                b[i] = 1;
            }
        }
    }
    return res;
}
ll fun2() {
    for (int i = 1; i <= n; i++)b[i] = d[i];
    ll res = 0;
    for (int i = 2; i <= n; i++) {
        if (i % 2 == 0) {
            // > 0
            if (b[i] <= 0) {
                res += (-b[i] + 1);
                b[i + 1] -= (-b[i] + 1);
                b[i] = 1;
            }

        }
        else {
            // < 0     
            if (b[i] >= 0) {
                res += (b[i] + 1);
                b[i + 1] += (b[i] + 1);
                b[i] = -1;
            }
        }
    }
    return res;
}
void slove() {
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++)d[i] = a[i] - a[i - 1];
    cout << min(fun1(), fun2()) << endl;
}

D. Average Replacement

题意:

有n人,其中有m对朋友关系。朋友的朋友并不算是朋友,现在,每个人的帽子上都有一个整数,每一轮游戏中,每个人帽子上的整数都会变成他

及其所有朋友的帽子上的整数的平均值,这个数可能不是整数,给定一个结论,当游戏次数足够多时,所有人的整数将会固定不变,求出这些最终值。

分析:

游戏轮次足够多时,容易想到同一个连通块里最终的值都是一样的

问题变为一个连通块最终的值为多少

结论为Σ(a[i]×(d[i]+1))/sz[x] 其中d[i]表示i节点的度数 sz[x]表示连通块x的大小

结论要大胆猜 怎么理解呢 a[i]被自己和朋友都算了一遍 类似期望概率里面的极限情况

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=3e5+10;
int a[N],fu[N],d[N],sz[N];
long long sum[N];
int find(int x)
{
	if(x!=fu[x]) return fu[x]=find(fu[x]);
	return fu[x];
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			sum[i]=d[i]=sz[i]=0;
			fu[i]=i;
		}
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			d[u]++;d[v]++;
			int fx=find(u),fy=find(v);
			if(fx!=fy)	fu[fy]=fx;
		}
		for(int i=1;i<=n;i++)
		{
			sum[find(i)]+=1ll*a[i]*(d[i]+1);
			sz[find(i)]+=d[i]+1;
		}
		for(int i=1;i<=n;i++)
			printf("%.6lf\n",1.0*sum[find(i)]/sz[find(i)]);
	}
	return 0;
}

A. Winner Prediction

题意:

有 n 个人参与比赛,已知m场比赛的结果,但是还有k场比赛没有结束。最终获胜场数最多的人(可能是多个人)会获的奖品,你是 1 号选手的亲爹,并且你能

够暗箱操作后 k 场比赛的结果,请问能否让 1 号选手获得胜利。

分析:

和之前有道题很像 都是比较裸的网络流 https://www.cnblogs.com/wzxbeliever/p/16099938.html

首先暗箱操作k场比赛 使得有1 参与的都赢

对每场比赛建图

这样就完了嘛?万一有人胜场比1多就不成立

假如i号选手目前赢了b场,1号选手赢了a场,那么他能够最多还能赢a - b场。

最终判断流向T节点的流的大小 如果与场数不符合即不成立

int n, m, S, T;
int idx;
int h[N], e[M], f[M], ne[M];
int d[N], cur[M];
void add(int a, int b, int w) {
    e[idx] = b, f[idx] = w, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}
bool bfs() {
    memset(d, -1, sizeof d);
    queue<int> q;
    q.push(S), d[S] = 0, cur[S] = h[S];
    while (q.size()) {
        auto u = q.front(); q.pop();
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (d[v] == -1 && f[i]) {
                d[v] = d[u] + 1;
                cur[v] = h[v];
                if (v == T) return 1;
                q.push(v);
            }
        }
    }
    return 0;
}
int found(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        cur[u] = i;
        int v = e[i];
        if (d[v] == d[u] + 1 && f[i]) {
            int t = found(v, min(f[i], limit - flow));
            if (!t) d[v] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}
int dinic() {
    int res = 0, flow;
    while (bfs()) {
        while (flow = found(S, inf)) res += flow;
    }
    return res;
}
void init() {
    memset(h, -1, sizeof h);
    idx = 0;
}

void solve() {
    init();
    cin >> n;
    int m1, m2; cin >> m1 >> m2;
    S = 0, T = n + m2 + 1;
    vector<int> a(n + 1);
    int cnt = 0;
    for (int i = 1; i <= m1; i++) {
        int u, v, z; cin >> u >> v >> z;
        if (z == 1) a[u]++;
        else if (z == 0) a[v]++;
    }
    for (int i = 1; i <= m2; i++) {
        int u, v; cin >> u >> v;
        if (u == 1 || v == 1) cnt++;
        else {
            add(S, i, 1);
            // cout << S << ' ' << cnt << endl;
            add(i, m2 + u, 1);
            add(i, m2 + v, 1);
        }
    }
    int st = m2 - cnt;//还剩下几场比赛
    cnt = cnt + a[1];
    for (int i = 2; i <= n; i++) {
        if (a[i] > cnt) {
            cout << "NO" << endl;
            return;
        }
    }
    for (int i = m2 + 2; i <= m2 + n; i++) {
        add(i, T, cnt - a[i - m2]);
    }
    int ans = dinic();
    if (ans == st) cout << "YES" << endl;
    else cout << "NO" << endl;
}

I. Painting Game

题意:

有一个长度为n的棋盘,Alice和Bob在棋盘上下棋,要求所有棋都不能相邻,每次告诉你棋盘长度和先手,Alice希望最后棋数量最少,Bob希望棋数量最多,

请问最终棋盘上会有多少棋。

分析:

此时会有疑问 为什么是n-4?不是分析的是三个格子嘛?

因为此时可能转移会有两个黑格子相邻的情况 所以不成立

但是如果bob转移变成n-4就能完全避免这种情况

原先的xox 变成了oxox

不得不说这个题很妙

标签:杭电多校,return,idx,10,int,void,flow,2022,include
From: https://www.cnblogs.com/wzxbeliever/p/16705302.html

相关文章

  • [心得] ALPHA camp 学期一2022/8
    [心得]ALPHAcamp学期一2022/8程式小白的第一篇心得文,文长,请随意浏览喜欢的部分^^方向开学前的周六举办了线上的开学典礼,是传说中的GatherTown!终于有机会可以玩了(兴......
  • 2022-2023-1 20221313《计算机基础与程序设计》第三周学习总结
    班级的链接:https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP作业要求的链接:https://www.cnblogs.com/rocedu/p/9577842.html#WEEK03作业的目标:学习《计算机基础与程......
  • 「比赛游记」CSP2022游记
    「比赛游记」CSP2022游记点击查看目录目录「比赛游记」CSP2022游记先咕着,有时间补。......
  • #100daysofcode
    #100daysofcodeR1D3问题在html中创建样式元素是否意味着我现在正在输入CSS?<style>元素{适当的价值;</style><style>h1{文本对齐:居中;</......
  • 20201317-第10章学习笔记
    第十章shell编程程序设计语言必备的要素和技能程序设计语言的含义程序设计语言是用于书写计算机程序的语言。语言的基础是一组记号和一组规则。根据规则由记号构成的......
  • 都2022年了!!!不要再用Setting Sync插件来同步VScode的配置了!!!
    推荐使用设置同步。需要之前电脑的VScode的版本与新电脑的版本相同这里有可能报无法更新的错误,只要找到报错的那个文件夹,将下面名称为_的文件夹的内容移到上一级目录......
  • 2022.9.17 Java第二次课总结
    以下是本节课后的问题首先是关于静态变量在类中,使用static修饰符修饰的属性(成员变量)称为静态变量,也可以称为类变量,常量称为静态常量,方法称为静态方法或类方法,它们统称......
  • 2022-2023-1 20221313 《计算机基础与程序设计》第三周学习总结
    2022-2023-120221313《计算机基础与程序设计》第三周学习总结作业信息班级的链接:https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP作业要求的链接:https://www.c......
  • 104规约标准
    104规约标准1、远动系统是指对广阔地区的生产过程进行监视和控制的系统,它包括对必需的过程信息的采集、处理、传输和显示、执行等全部的设备与功能。构成远动系统的设......
  • 创新实战|高转化网站首页设计的10大关键要素
    设计开发一个好的网站首页并不像造火箭一样难,但它确实也需要费一番功夫。我们需要学习怎么做能够满足客户需求的网站首页设计。那么,到底应该如何做?本文将从首页的十个要素......