2024.3.14 训练记录（16）

这几天发生了一些不好的事情效率低下也没怎么做题，要尽快调整恢复状态了

文章目录

CF 1941F Rudolf and Imbalance
CF 25D Roads not only in Berland
CF 61E Enemy is weak
CF 1400D Zigzags
CF 300C Beautiful Numbers
CF 1375D Replace by MEX
CF 1328E Tree Queries

CF 1941F Rudolf and Imbalance

赛后一发过f但一到比赛就小脑缺失。。。

就是很无脑的二分，一定要在差距最大的两题中间插入，记录一下倒数第二大的，处理一下插入后的最大差距就可以

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> a(n), b(m), c(k);
	for (int i = 0; i < n; i ++ ) cin >> a[i];
	for (int i = 0; i < m; i ++ ) cin >> b[i];
	for (int i = 0; i < k; i ++ ) cin >> c[i];
	sort(b.begin(), b.end());
	sort(c.begin(), c.end());
	int l, r, maxx1 = -1, maxx2 = -2;
	for (int i = 1; i < n; i ++ )
	{
		if (a[i] - a[i - 1] >= maxx1)
		{
			maxx2 = maxx1;
			maxx1 = a[i] - a[i - 1];
			l = a[i - 1], r = a[i];
		}
		else if (a[i] - a[i - 1] >= maxx2) maxx2 = a[i] - a[i - 1];
	}
	int ans = maxx1;
	int mid = l + r >> 1;
	for (int i = 0; i < m; i ++ )
	{
		int pos = lower_bound(c.begin(), c.end(), mid - b[i]) - c.begin();
		if (pos != k) ans = min(ans, max({maxx2, max(abs(c[pos] + b[i] - l), abs(r - (c[pos] + b[i])))}));
		if (pos != 0)
		{
			pos -- ;
			ans = min(ans, max({maxx2, max(abs(c[pos] + b[i] - l), abs(r - (c[pos] + b[i])))}));
		}
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 25D Roads not only in Berland

题目链接

这题一开始路走偏了，想用dfs判断连通分量，但是最后取边的时候出现问题，如果有一个连通分量里有很多条多余边，就不知道该取哪些条了

收获是学到了一个新的判环方式：并查集判环，每给出一条边就查一下两个顶点在不在同一个并查集里，如果在的话说明已经有别的边把这两个点连起来了，现在的这条边就是多余的，记录一下一会儿可以把这条边换掉

然后可以通过判断 p[x] == x 来在每个连通分量里取一个代表点，把每一条多余的边换成不同连通分量的代表点之间的边

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n;
	cin >> n;
	vector<vector<int>> g(n + 1);
	vector<int> p(n + 1);
	for (int i = 1; i <= n; i ++ ) p[i] = i;
	function<int(int)> find = [&](int x)
	{
		if (p[x] != x) p[x] = find(p[x]);
		return p[x];
	};
	auto merge = [&](int x, int y)
	{
		int xp = find(x), yp = find(y);
		if (xp == yp) return false;
		else
		{
			p[xp] = yp;
			return true;
		}
	};
	vector<PII> edge;
	for (int i = 0; i < n - 1; i ++ )
	{
		int u, v;
		cin >> u >> v;
		if (!merge(u, v)) edge.push_back({u, v});
	}
	vector<int> ver;
	int cnt = 0;
	for (int i = 1; i <= n; i ++ )
	{
		if (p[i] == i)
		{
			cnt ++ ;
			ver.push_back(i);
		}
	}
	cout << cnt - 1 << '\n';
	int idx = 1;
	for (int i = 0; i < edge.size(); i ++ )
	{
		cout << edge[i].first << ' ' << edge[i].second << ' ';
		cout << ver[0] << ' ' << ver[idx ++ ] << '\n';
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 61E Enemy is weak

题目链接

很容易想到的思路是枚举中间的那个数，然后看它前面有多少比它大的，后面多少比它小的，具体怎么查，直接上线段树了，需要离散化

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

int a[N];

struct Node
{
	int l, r, cnt;
} tr[N * 4];

void pushup(Node& u, Node& l, Node& r)
{
	u.l = l.l, u.r = r.r;
	u.cnt = l.cnt + r.cnt;
}

void pushup(int u)
{
	pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
	tr[u] = {l, r};
	if (l == r) return;
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void modify(int u, int pos)
{
	if (tr[u].l == pos && tr[u].r == pos)
	{
		tr[u].cnt ++ ;
		return;
	}
	int mid = tr[u].l + tr[u].r >> 1;
	if (pos <= mid) modify(u << 1, pos);
	else modify(u << 1 | 1, pos);
	pushup(u);
}

Node query(int u, int l, int r)
{
	if (tr[u].l >= l && tr[u].r <= r) return tr[u];
	int mid = tr[u].l + tr[u].r >> 1;
	if (r <= mid) return query(u << 1, l, r);
	else if (l > mid) return query(u << 1 | 1, l, r);
	else
	{
		Node res;
		auto lt = query(u << 1, l, mid);
		auto rt = query(u << 1 | 1, mid + 1, r);
		pushup(res, lt, rt);
		return res;
	}
}

void solve()
{
	int n;
	cin >> n;
	build(1, 1, n);
	vector<int> a(n + 1);
	vector<int> nums;
	nums.push_back(0);
	for (int i = 1; i <= n; i ++ ) cin >> a[i], nums.push_back(a[i]);
	sort(nums.begin(), nums.end());
	nums.erase(unique(nums.begin(), nums.end()), nums.end());
	map<int, int> mp;
	for (int i = 1; i < nums.size(); i ++ ) mp[nums[i]] = i;
	int ans = 0;
	vector<int> lt(n + 1), rt(n + 1);
	for (int i = 1; i < n; i ++ )
	{
		modify(1, mp[a[i]]);
		if (i == 1 || mp[a[i]] + 1 > n) continue;
		auto res = query(1, mp[a[i]] + 1, n);
		lt[i] = res.cnt;
	}
	for (auto& t : tr) t.cnt = 0;
	for (int i = n; i > 1; i -- )
	{
		modify(1, mp[a[i]]);
		if (i == n || 1 > mp[a[i]] - 1) continue;
		auto res = query(1, 1, mp[a[i]] - 1);
		rt[i] = res.cnt;
	}
	for (int i = 1; i <= n; i ++ ) ans += lt[i] * rt[i];
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 1400D Zigzags

题目链接

很好的一题，虽然没写出来

要求的是四元组的个数，这种题一般来说是枚举中间的元素，下面的代码枚举第三个元素，首先把当前枚举的这个元素后面出现的数字次数计算一下，然后再从当前这个元素往前找，每找一个元素就让sum加上这个元素在当前遍历元素之后出现的次数，一旦发现有哪个元素和当前这个元素相等，就把sum加到答案里

看代码应该很好理解

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	int ans = 0;
	for (int i = 1; i <= n; i ++ ) // 枚举第三个
	{
		int sum = 0;
		vector<int> cnt(n + 1);
		for (int j = i + 1; j <= n; j ++ ) cnt[a[j]] ++ ;
		for (int j = i - 1; j > 0; j -- )
		{
			if (a[j] == a[i]) ans += sum;
			sum += cnt[a[j]];
		}
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 300C Beautiful Numbers

题目链接

很弱智的一题，看题目应该想到其实最终答案和不同数字的排列顺序无关，所以只需要枚举每个数字出现多少次即可，组合数套个模板就行

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

int Jc[maxn];

void calJc()	//求 maxn 以内的数的阶乘 不知道开多少就1e6吧爆不了
{
    Jc[0] = Jc[1] = 1;
    for(int i = 2; i < maxn; i++) Jc[i] = Jc[i - 1] * i % mod;
}

int pow(int a, int n, int p) // 快速幂取模
{
    int ans = 1;
    while (n)
    {
        if (n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}

int niYuan(int a, int b)	//费马小定理求逆元
{
    return pow(a, b - 2, b);
}

int C(int a, int b) // 组合数
{
    if(a < b) return 0;
    return Jc[a] * niYuan(Jc[b], mod) % mod * niYuan(Jc[a - b], mod) % mod;
}

void solve()
{
	int a, b, n;
	cin >> a >> b >> n;
	int ans = 0;
	for (int i = 0; i <= n; i ++ ) // 枚举a的个数
	{
		int sum = i * a + (n - i) * b;
		string s = to_string(sum);
		bool flag = true;
		for (auto t : s)
		{
			if (t - '0' != a && t - '0' != b)
			{
				flag = false;
				break;
			}
		}
		if (flag) ans = (ans + C(n, i)) % mod;
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	calJc();

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 1375D Replace by MEX

题目链接

这题被卡住的一个点是没反应过来数据范围其实很小，每次求mex都是可以直接暴力去求的

很容易想到是让 a[i] = i

那每次求出mex，如果mex==n的话，直接赋给最后一个数，否则让a[mex] = mex

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i ++ ) cin >> a[i];
	vector<bool> st(n + 1);
	auto find = [&]()
	{
		for (auto t : st) t = false;
		for (auto t : a) st[t] = true;
		for (int i = 0; i <= n + 1; i ++ )
		{
			if (!st[i]) return i;
		}
	};
	int mex;
	vector<int> ans;
	while (n)
	{
		mex = find();
		if (mex == n)
		{
			a[n - 1] = mex;
			ans.push_back(n - 1);
			n -- ;
		}
		else
		{
			a[mex] = mex;
			ans.push_back(mex);
		}
	}

	cout << ans.size() << '\n';
	for (auto t : ans) cout << t + 1 << ' ';
	cout << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 1328E Tree Queries

题目链接

很有收获的一道题，学会了用dfs序判断子树关系的方法

首先预处理每个结点的深度、父结点、子树大小、dfs序

然后感性理解一下很容易发现题目现有条件可以改编成经过给出结点的父结点，所以把除了根结点之外的点都换成父结点，然后将给出的点按深度排序，每次判断后一个点是不是在前一个点的子树中，如果结点 v 的 dfs 序 dfn[v] 处于 [dfn[u], dfn[u] + sz[u] - 1]，则说明 v 在 u 的子树中

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n + 1);
	for (int i = 0; i < n - 1; i ++ )
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	vector<int> dep(n + 1), fa(n + 1, -1), sz(n + 1), dfn(n + 1);
	dep[0] = 0;
	int idx = 0;
	function<void(int, int)> dfs = [&](int u, int father)
	{
		dep[u] = dep[father] + 1;
		fa[u] = father;
		sz[u] = 1;
		dfn[u] = ++ idx;
		for (int i = 0; i < g[u].size(); i ++ )
		{
			int j = g[u][i];
			if (j == father) continue;
			dfs(j, u);
			sz[u] += sz[j];
		}
	};
	auto cmp = [&](int u, int v)
	{
		return dep[u] < dep[v];
	};
	auto check = [&](int u, int v)
	{
		if (dfn[u] <= dfn[v] && dfn[u] + sz[u] - 1 >= dfn[v]) return true;
		else return false;
	};
	dfs(1, 0);
	while (m -- )
	{
		int k;
		cin >> k;
		vector<int> v(k);
		for (int i = 0; i < k; i ++ )
		{
			cin >> v[i];
			if (v[i] != 1) v[i] = fa[v[i]];
		}
		sort(v.begin(), v.end(), cmp);
		bool flag = true;
		for (int i = 1; i < k; i ++ )
		{
			if (!check(v[i - 1], v[i]))
			{
				flag = false;
				break;
			}
		}
		if (flag) cout << "YES\n";
		else cout << "NO\n";
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}