首页 > 其他分享 >Oct. Training 6

Oct. Training 6

时间：2022-11-01 19:24:41浏览次数：66  
标签：Training const int ll long include Oct define

F - Trails and Glades

https://codeforces.com/problemset/problem/209/C

题意

给你一个图，你从1好点出发，每条边走且只走一遍，问你最少要添加多少条边。

思路

翻译一下题意其实就是找欧拉回路。
统计每个点的度数，每个点必须是偶数度否者肯定会有一条路径不走或者走一遍以上。
先可以把整张图变成多个连通块。
对于x有个奇数度点的连通块，我们最少可以添加\(cnt(奇数度数的点) / 2\)条边使得整个图变成欧拉回路。
如果多一个只含有偶数度的连通块，我们我们可以将已经是欧拉回路的连通块的一条边断开连到当前连通块 然后额外添加一条边跟断开的另一端相连。
总结就是，答案就是奇数度点的个数+只含偶数度的连通块个数
要注意：不是1的孤点可以省略计算

#include<bits/stdc++.h>
#include<unordered_map>
#include<array>
#define endl '\n'
#define ll long long
#define int ll
#define ull unsigned long long
#define all(a) a.begin(),a.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-4;
const ll mod = 998244353;
const int N = 2e6 + 5;
const int M = 1e6 + 5;

int n, m, head[N], etot, in[N], vis[N], cnt, f;

struct edge {
	int v, nxt;
}e[N];

void dfs(int x) {
	vis[x] = 1;
	cnt += in[x] % 2;
	if (in[x]) f = 1;
	for (int i = head[x]; ~i; i = e[i].nxt) {
		if (!vis[e[i].v]) dfs(e[i].v);
	}
}

void addedge(int u, int v) {
	e[etot] = { v, head[u] };
	head[u] = etot++;
	e[etot] = { u, head[v] };
	head[v] = etot++;
}

void solve()
{
	cin >> n >> m;

	if (!m) {
		cout << 0 << "\n";
		return;
	}

	for (int i = 1; i <= n; i++) head[i] = -1;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		addedge(u, v);
		in[u]++;
		in[v]++;
	}

	int ans = 0, x = 0, tot = 0;
	for (int i = 1; i <= n; i++) {
		cnt = 0;
		f = 0;
		if (!vis[i]) {
			dfs(i);
			if (i == 1 || f) {
				cnt ? ans += cnt / 2 : x++;
				tot++;
			}
		}
	}

	if(tot > 1) ans += x;
	cout << ans << "\n";
}

signed main()
{
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
	return 0;
}

K - Tourist Reform

https://codeforces.com/problemset/problem/732/F

题意

一张无向图，你需要将每条边定向，使得所有点中的最小出度点的出度最大。

思路

可以先按边双缩点，就变成了一颗数，同一个强连通块的点可以设置边使得互相可达。
对于缩点外的边，我们将边都指向最大连通块，答案就是最大强连通块的大小。
tarjan缩点的时候顺便将强连通块内的边一并处理了（就按搜索方向）
可以用dfn序确定树边的方向

#include<bits/stdc++.h>
#include<unordered_map>
#include<array>
#define endl '\n'
#define ll long long
#define int ll
#define ull unsigned long long
#define all(a) a.begin(),a.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-4;
const ll mod = 998244353;
const int N = 1e6 + 5;

int n, m;
vector<pair<int, int> >g[N];
vector<int>g2[N];
ll dfn[N], low[N], tot, ec, c[N], sz[N], ans[N], dfn2[N], in[N];
pair<int, int>p[N];
stack<int>st;
map<pair<int, int>, int>mp;

void tarjan(int x, int id) {
	dfn[x] = low[x] = ++tot;
	st.push(x);

	for (auto [to, id2] : g[x]) {
		if (!ans[id2]) p[id2].first == x ? ans[id2] = 1 : ans[id2] = -1;
		if (!dfn[to]) {
			tarjan(to, id2);
			low[x] = min(low[x], low[to]);
		}
		else if (id2 != id) low[x] = min(low[x], dfn[to]);
	}

	if (dfn[x] == low[x]) {
		ec++;
		while (1) {
			int now = st.top();
			st.pop();
			c[now] = ec;
			sz[ec]++;
			if (now == x) break;
		}
	}
}

void dfs(int x, int fa) {
	dfn2[x] = ++tot;
	for (auto to : g2[x])
		if (to != fa) dfs(to, x);
}

void solve()
{
	cin >> n >> m;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		g[u].push_back({ v, i });
		g[v].push_back({ u, i });
		p[i] = { u, v };
	}

	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) tarjan(i, 0);
	}

	int t = 0, mx = 0;
	for (int i = 1; i <= ec; i++) {
		if (sz[i] > mx) {
			mx = sz[i];
			t = i;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (auto [to, id] : g[i]) {
			if (c[to] != c[i] && !mp[{c[i], c[to]}]) {
				g2[c[i]].push_back(c[to]);
				mp[{c[i], c[to]}] = 1;
			}
		}
	}

	tot = 0;
	dfs(t, -1);

	cout << mx << '\n';
	for (int i = 1; i <= m; i++) {
		int u = p[i].first;
		int v = p[i].second;
		if (c[u] != c[v])
			dfn2[c[u]] > dfn2[c[v]] ? cout << u << " " << v << "\n" : cout << v << " " << u << '\n';
		else
			ans[i] == 1 ? cout << u << " " << v << '\n' : cout << v << " " << u << '\n';
	}
}

signed main()
{
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
	return 0;
}

L - Madoka and The First Session

题意

给长度为n的数组s,a,b,和若干条边, 一开始b数组的数全部为0， 对于每条边我们必须操作且仅操作一次，最后是的si为1的位置 ai = bi
可以用网络流
对于这个问题 对于一条边的操作，就相当于将两个点的值都先减一 然后选择一个点加1， 那么一个点出现几次，我们就要减几次。
我们假定 流进一单位流量就代表将一个点的值加2 那么对于位置i上的数就要加 \((a[i] + cnt[i]) / 2\) 如果不能整除2 就说明答案不存在。
然后就进行来连边：
1.s到每条边连一条流量为1的边 代表每条边都要操作一次
2.边和对应的连一条流量为一的边 代表边选择一个点让其权值加2
3.对于si为1的点 直接向t连一条流量为\((cnt[i] + a[i]) / 2\)的边
4.对于si为0的点 连向一个过渡点 流量为inf 这个过渡点再想t连一条 流量为 \(m -/sum((cnt[i] + a[i]) / 2)\)的边 来保证总流量为m
最后跑个最大流即可

#include<bits/stdc++.h>
#include<unordered_map>
#include<array>
#define endl '\n'
#define ll long long
#define int ll
#define ull unsigned long long
#define all(a) a.begin(),a.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-4;
const ll mod = 998244353;
const int N = 1e6 + 5;
const int M = 1e6 + 5;

int n, m;
int f[N], a[N], cnt[N];
int s, t, vtot;
int head[N], cur[N], ans[N];
int dis[N], etot;
pair<int, int>p[N];
struct edge {
	int v, nxt;
	int f;
}e[M * 2];
//复杂度 O(n^2*m)
//存图用前向星比较方便 有边的信息 
void addedge(int u, int v, int f) {
	//边序号从零开始
	e[etot] = { v, head[u], f }; head[u] = etot++;
	e[etot] = { u, head[v], 0 }; head[v] = etot++;
}

//s到t是否还有路径
bool bfs() {
	for (int i = 1; i <= vtot; i++) {
		dis[i] = 0;
		cur[i] = head[i];
	}
	queue<int>q;
	q.push(s); dis[s] = 1;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; ~i; i = e[i].nxt) {
			//有剩余流量且未被访问过
			if (e[i].f && !dis[e[i].v]) {
				int v = e[i].v;
				dis[v] = dis[u] + 1;
				if (v == t) return true;
				q.push(v);
			}
		}
	}
	return false;
}

//找最优路径
int dfs(int u, int m) {
	if (u == t) return m;
	int flow = 0;
	//cur[]当前弧优化 保证增广过了不再增广
	for (int i = cur[u]; ~i; cur[u] = i = e[i].nxt) {
		//如果流量还有剩余 且该边方向是对的
		if (e[i].f && dis[e[i].v] == dis[u] + 1) {
			int f = dfs(e[i].v, min(m, e[i].f));
			e[i].f -= f;
			e[i ^ 1].f += f;
			m -= f;
			flow += f;
			if (!m) break;//保证复杂度
		}
	}
	if (!flow) dis[u] = -1;
	return flow;
}

int dinic() {
	int flow = 0;
	while (bfs()) flow += dfs(s, INF);
	return flow;
}

void init(int s_, int t_, int vtot_) {
	s = s_;
	t = t_;
	vtot = vtot_;
	//etot = 1;
	for (int i = 1; i <= vtot; i++) head[i] = -1;
}

void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> f[i];
	for (int i = 1; i <= n; i++) cin >> a[i];
	init(n + m + 2, n + m + 3, n + m + 3);

	vector<pair<int, int> >ve;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		addedge(s, i, 1);
		ve.push_back({ etot, i });
		addedge(i, u + m, 1);
		ve.push_back({ etot, i });
		addedge(i, v + m, 1);
		cnt[u]++;
		cnt[v]++;
		p[i] = { u, v };
	}

	int sum = 0;
	for (int i = 1; i <= n; i++) {
		if (!f[i]) {
			addedge(i + m, m + n + 1, inf);
			continue;
		}
		if ((a[i] + cnt[i]) % 2 || a[i] + cnt[i] < 0) {
			cout << "NO\n";
			return;
		}
		addedge(i + m, t, (a[i] + cnt[i]) / 2);
		sum += (a[i] + cnt[i]) / 2;
	}
	addedge(n + m + 1, t, m - sum);
	int flow = dinic();
	if (sum > m || flow != m) {
		cout << "NO\n";
		return;
	}

	cout << "YES\n";
	for (auto it : ve) 
		if (!e[it.first].f) ans[it.second] = e[it.first].v - m;
	
	for (int i = 1; i <= m; i++) {
		int u = p[i].first;
		int v = p[i].second;
		ans[i] == v ? cout << u << " " << v << "\n" : cout << v << " " << u << "\n";
	}
}

signed main()
{
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
	return 0;
}

J - Longest Sequences

题意

给定n a b要求构造一个只包含(1~n)的序列 使得这个序列的最长上升子序列和最长下降子序列分别是a b

思路

根号构造
选定一个a行 b列的矩阵
先从最大到小 填好第一行 之后，按遍历列从上到下填（也是大的先填）然后取的时候 就一列一列从下往上去即可
这样构造出来的一定最优
如果第一行第一列都没填满 即x + y > n + 1 或者矩阵满出了 即x * y < n就代表无解

#include<bits/stdc++.h>
#include<unordered_map>
#include<array>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define all(a) a.begin(),a.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-4;
const ll mod = 998244353;
const int N = 5e3 + 5;
const int maxn = 2e5 + 5;

int n, x, y, a[N][N];

void solve()
{
	cin >> n >> x >> y;
	if (x * y < n || (x + y) > n + 1) {
		cout << -1 << '\n';
		return;
	}

	int num = n;
	for (int i = 1; i <= y; i++) a[1][i] = num--;
	for (int i = 1; i <= y; i++) {
		for (int j = 2; j <= x; j++) {
			if (num < 1) break;
			a[j][i] = num--;
		}
		if (num < 1) break;
	}

	for (int i = 1; i <= y; i++)
		for (int j = x; j >= 1; j--)
			if (a[j][i] > 0) cout << a[j][i] << " ";


}

signed main()
{
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
	return 0;
}

I - Perfect Groups

题意

给你长度为n的数组
对于一个区间你可以做一下操作：
将区间中的数分成几组 使得每组组内任意的两个数相乘是完全平方数。 k代表最少要分k组使得某个区间符合分组条件
需要输出k等于1到n的区间数

思路

我们可以得出一个结论：
a和b相乘是完全平方数 a和c相乘是完全平方数 那么b和c相乘也是完全平方数
我们可以开个数组记录离 a[i]最近的位置j 满足a[i] * a[j]是完全平方数
然后枚举区间的左区间 向后遍历每次判断是否要新加组 且记录贡献
要特别注意的一点是 0
如果0在第一个位置那么它可以和一个没有组过的点组一次 如果0是新遍历的点那么它可以被分到前面任意一个组中去。

#include<bits/stdc++.h>
#include<unordered_map>
#include<array>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define all(a) a.begin(),a.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-4;
const ll mod = 998244353;
const int N = 5e3 + 5;
const int maxn = 2e5 + 5;

int n, x, y, a[N], mx[N], ans[N];
void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		mx[i] = 0;
		for (int j = i - 1; j >= 1; j--) {
			int num = a[i] * a[j];
			if (num == 0) continue;
			if ((int)sqrt(num) * (int)sqrt(num) == num) {
				mx[i] = j;
				break;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		int pre = 1;
		ans[1]++;
		int f = 0;
		for (int j = i + 1; j <= n; j++) {
			if (a[j] == 0 || mx[j] >= i) ans[pre]++;
			else {
				if (a[i] == 0 && !f) ans[pre]++, f = 1;
				else ans[++pre]++;
			}
		}
	}

	for (int i = 1; i <= n; i++)
		cout << ans[i] << " \n"[i == n];
}

signed main()
{
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
	return 0;
}

标签：Training,const,int,ll,long,include,Oct,define
From： https://www.cnblogs.com/yaqu-qxyq/p/16848558.html

相关文章

  • BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generatio
    BART:DenoisingSequence-to-SequencePre-trainingforNaturalLanguageGeneration,Translation,andComprehensionBART：用于自然语言生成、翻译和理解的seq2seq去噪......
  • [单片机框架][driver层][ioctl] MCU模拟Linux注册驱动
    概念ioctl是设备驱动程序中设备控制接口函数，一个字符设备驱动通常会实现设备打开、关闭、读、写等功能，在一些需要细分的情境下，如果需要扩展新的功能，通常以增设ioctl()命......
  • Oct. Training 5
    E-Escapehttps://codeforces.com/gym/102361/problem/E题意若干个机器人从矩阵第一行上方要走到矩阵最后一行下方，一个机器人对应一个出口，机器人只能直走，现在可以设置......
  • Oct. Training 4
    L-Airportshttps://codeforces.com/gym/100959题意给定n个点，第i个点为（\(x_i,y_i\)）,对于曼哈顿距离小于D的两个点可以建一条边，问最大的D使得整个图联通。思路这就相......
  • 修改Octave编辑器为vim
    Octave的默认编辑器一般是emacs，该编辑器虽然强大，但是对于新手来说并不友好，并且我在macOS中使用时，发现Octave中的emacs的快捷键有失效的现象，因此为了避免麻烦，自己修改了......
  • 中文美句_Oct.28
    "我爱在黎明前起床，在山顶牧场上召唤太阳，云雀的歌声便是我异想天开的翅膀，朝露便是我晨起的浴缸。   ......
  • Basil: A Fast and Byzantine-Resilient Approach for Decentralized Training 阅读笔
    Basil:AFastandByzantine-ResilientApproachforDecentralizedTraining阅读笔记ProblemStatementDecentralizedSystemModel所有训练数据样本存储在分布式节......
  • Oct 24 2022 学习日志
    Dijkstra用pair实现$edge$（struct）建立edge数组$E$来记录每个点的出边$pair<int,int>$（struct）用来给优先队列服务，$first$为$dis[u]$,$second$为$u$初始化：$dis[u]=......
  • 补题记录——Oct. Training 1-图论、集合哈希
    H-BoboniuWalksonGraphhttps://codeforces.com/problemset/problem/1394/B题意给n个点m条有向边，么个点的出度不超过k（k<=9），每条边都有一个边权在（\(1<=w<=m\)）且每条边......
  • Windows 10, version 22H2 (released Oct 2022) 简体中文版、英文版下载
    请访问原文链接：https://sysin.org/blog/windows-10/，查看最新版。原创作品，转载请保留出处。Windows10版本信息2022/10/19从Windows10版本21H2开始，Windows10版......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99