ECNU 2020 XCPC Winter Training \#1

B. Number Circle

 

题意：环形排列给定的数列，使得每个数小于 它相邻的两个数之和。

先安排好最大的数，只有在它两边放第二，第三大的数才可能满足。接着把整个数列剩下的数从大到小放就好了，由于每个数一定与某个比它大的数相邻，所以一定满足条件。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n;
int a[maxn];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)scanf("%d", &a[i]);
	sort(a, a + n);
	swap(a[n-1], a[n-2]);
	for (int i = 0; i < n; i++) {
		if (a[i] + a[(i + 2) % n] <= a[(i + 1) % n]) {
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	for (int i = 0; i < n; i++)printf("%d%s", a[i], (i == n - 1 ? "\n": " "));
	return 0;
}

 

D. Add on a Tree

 

题意：给定一棵树，每次操作可以选两个叶子，把他们的路径上所有边加x，问是否能通过不断操作，使得所有边呈任意值。

如果有一个点的度为2，他所连的两条边的值不管怎样一定相同，这时就不能为任意值。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
int n;
int d[maxn];
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		d[u]++; d[v]++;
	}
	for (int i = 1; i <= n; i++) {
		if (d[i] == 2) {
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}

 

E. Add on a Tree: Revolution

 

题意：上一题的加强版，给定每条边的边权，要求给出操作，使得最终形成这种情况。保证边的值一定为偶数。

其实看到保证为偶数就应该想到把边权除2。

首先判断是否能做到，由上一题，度为2的点连的两条边值必须相等，否则不行。

以下可以假设一条全是度为2的点的链缩为一条边，则所有点要么是叶子，要么度大于等于3。枚举每一条边，两个端点一定还各自连着另外两个叶子设为Lx,Ly;Rx,Ry.则从Lx到Rx，再从Ly到Ry路径加边权/2，再从Lx到Ly，从Rx到Ry路径减边权/2，就只有这条边的值改变，其它边不受影响，可以对每条边这样处理。

再考虑度为2的链，对链上某一个边处理，就把其他边都处理到了，所以一条链上最多只能处理一条边，所以每次处理完向两端拓展，保证链上都标记完。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1010;
int n;
vector<int>G[maxn];
vector<pii>edges;
int w[maxn][maxn], vis[maxn], used[maxn][maxn];
int dfs(int u, int _fa) {
	vis[u] = 1;
	if ((int)G[u].size() == 1)return u;
	for (int v : G[u]) {
		if (v == _fa || vis[v])continue;
		return dfs(v, u);
	}
}
void pre(int u, int _fa) {
	used[u][_fa] = 1;
	if ((int)G[u].size() != 2)return;
	for (int v : G[u]) {
		if (u == _fa)continue;
		pre(v, u);
	}
}
struct X
{
	int u, v, w;
};
vector<X>ans;
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v, ww;
		scanf("%d%d%d", &u, &v, &ww);
		w[u][v] = w[v][u] = ww;
		G[u].push_back(v);
		G[v].push_back(u);
		edges.push_back(pii(u, v));
	}
	for (int i = 1; i <= n; i++) {
		if ((int)G[i].size() == 2 && w[i][G[i][0]] != w[i][G[i][1]]) {
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	for (pii e : edges) {
		int u = e.first, v = e.second;
		if (used[u][v])continue;
		fill(vis + 1, vis + n + 1, 0);
		int Lx = dfs(u, v); int Ly = dfs(u, v);
		int Rx = dfs(v, u); int Ry = dfs(v, u);
		ans.push_back(X{ Lx,Rx,w[u][v] / 2 });
		ans.push_back(X{ Ly,Ry,w[u][v] / 2 });
		if (Lx != Ly)ans.push_back(X{ Lx,Ly,-w[u][v] / 2 });
		if (Rx != Ry)ans.push_back(X{ Rx,Ry,-w[u][v] / 2 });
		pre(u, v); pre(v, u);
	}
	printf("%d\n", (int)ans.size());
	for (X p : ans)printf("%d %d %d\n", p.u, p.v, p.w);
	return 0;
}

 

F. Count Pairs

 

题意：给定一列数和质数 $p$，求满足 $(a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p$ 的数对个数。

左边这个式子明明去年还在初中题里见过。。

主要是要把 $i$ 和 $j$ 分开来。

两边乘以 $a_i-a_j$，化简，$(a_i^4-ka_i)-(a_j^4-ka_j)\equiv 0\bmod p$，则 $(a_i^4-ka_i)\bmod p=(a_j^4-ka_j)\bmod p$

算出每个模，放进map里，最后算即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
int n;
ll p, k;
map<ll, int>mp;
ll ans;
int main() {
	scanf("%d%lld%lld", &n, &p, &k);
	for (int i = 1; i <= n; i++) {
		ll u;
		scanf("%lld", &u);
		ll x = u;
		for (int j = 0; j < 3; j++)x = x * u%p;
		ll tmp = x - k * u%p;
		while (tmp < 0)tmp += p;
		tmp = tmp % p;
		mp[tmp]++;
	}
	for (auto it : mp) {
		ans += it.second*(it.second - 1) / 2;
	}
	cout << ans << endl;
	return 0;
}

 

G. Array Beauty

 

题意：定义数组的beauty为差值最小的两个数的差值 $\min\limits_{1 \leq i < j \leq n} |a_i - a_j|$。求给定数组的所有长度为 $k$ 的子序列的beauty之和。

显然不能直接算，还是要枚举每个beauty值的贡献。

问题就是求 $\sum_{beauty=1}^{MAXI}beauty\cdot numOfBeauty$，可以发现还能变为 $\sum_{beauty=1}^{MAXI}f[beauty]$，其中 $f[beauty]$ 为长度为 $k$ ，beauty 大于等于 $i$ 的子序列个数。

接下来dp求 $f[beauty]$。

由于是求差值，所以其实与顺序无关，所以先排个序。

$dp[i][j]$ 表示子序列最后一个数为第 $i$ 个数，序列长度为 $j$ 的序列数。

则 $dp[i][j]=\sum_{a_i-a_k\geq beauty}dp[k][j-1]$。

对于每一个长度 $j$ ，每一次算 $dp[i][j]$ 都是算第 $j-1$ 层的一个前缀的和。所以可以外层循环 $j$，这样每一层都可以通过一次遍历处理完所有的 $i$。

还有另一种dp方法是 $dp[i][j]$ 只是表示处理到第 $i$ 个数，长度为 $j$ ，并不一定选第 $i$ 个数，所以要分取/不取考虑，并且取的话也只要加上 $dp[k][j]$ 其中 $k$ 为最后一个满足 $a[i]-a[k]\geq beauty$ 的数。即 $dp[i][j]=dp[i-1][j]+dp[k][j-1]$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const int mod = 998244353;
int n, k;
int a[maxn];
int MAX;
ll ans;
ll dp[1010][1010];
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]), MAX = max(MAX, a[i]);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++)dp[i][1] = 1;
	for (int x = 1; x <= MAX / (k - 1); x++) {
		for (int j = 2; j <= k; j++) {
			ll sum = 0; int now = 1;
			for (int i = 2; i <= n; i++) {
				while (now < i&&a[i] - a[now] >= x) {
					sum = (sum + dp[now][j - 1]) % mod;
					now++;
				}
				dp[i][j] = sum;
			}
		}
		for (int i = 1; i <= n; i++)ans = (ans + dp[i][k]) % mod;
	}
	cout << ans << endl;
	return 0;
}

 

M. Consecutive Subsequence

 

题意：给定一个数列，求满足递增，且每次递增1的最长子序列。

直接dp数值，$dp[i]$ 表示末尾数值为 $i$ 的子序列最长长度，然后从前向后在原数组里找这一串数，用map存dp数组。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
int n;
int a[maxn];
map<int, int>mp;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		if (!mp.count(a[i]-1))mp[a[i]] = 1;
		else mp[a[i]] = mp[a[i] - 1] + 1;
	}
	int mx = -1, mxid = -1;
	for (auto p : mp) {
		if (mx < p.second) {
			mx = p.second;
			mxid = p.first;
		}
	}
	int st = mxid - mx + 1;
	printf("%d\n", mx);
	for (int i = 1; i <= n; i++) {
		if (a[i] == st)printf("%d%s", i, a[i] == mxid ? "\n" : " "), st++;
	}
	return 0;
}