Oct. Training 6

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;
}

原文地址：http://www.cnblogs.com/yaqu-qxyq/p/16848558.html