526互联

Codeforces Round 860 (Div. 2) - 题解

发布时间 2023-03-27 23:50:15作者: RB16B

https://codeforces.com/contest/1798/problems

A. Showstopper

考虑将 \(\max(a_i,b_i)\) 全都交换到 \(b_i\)，那么 \(a_i\) 就是 \(\min(a_i,b_i)\)。

只需要判定：

\[a'=[\min(a_1,b_1),\min(a_2,b_2),\dots,\min(a_n,b_n)] \]

\[b'=[\max(a_1,b_1),\max(a_2,b_2),\dots,\max(a_n,b_n)] \]

是否满足即可。

正确性显然。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
int _;
int a[105], b[105], n;
signed main () {
	scanf ("%d", &_);
	while (_ --) {
		scanf ("%d", &n);
		for (int i = 1;i <= n; ++ i) scanf ("%d", &a[i]);
		for (int i = 1;i <= n; ++ i) scanf ("%d", &b[i]);
		for (int i = 1;i <= n; ++ i) {
			if (a[i] <= b[i]) ;
			else swap (a[i], b[i]); 
		}
		int mxa = 0, mxb = 0;
		for (int i = 1;i <= n; ++ i) {
			mxa = max (mxa, a[i]);
			mxb = max (mxb, b[i]);
		}
		if (a[n] == mxa && b[n] == mxb) printf ("Yes\n");
		else printf ("No\n");
	}
	return 0;
}

B. Three Sevens

可以发现，第 \(i\) 天的 Winner 一定是没有在 \(i+1\sim m\) 天中的参赛者，所以只需要将 \(a_i\) 中在 \(a_{i+1},a_{i+2},\dots,a_m\) 中出现过的数去掉，如果为空就无解，不然就从操作过的 \(a_i\) 中随便选一个作为 \(p_i\)。

具体可以用一个桶维护每个数出现次数。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
int mp[50005], m, n[50005], winner[50005];
vector < int > seq[50005];
signed main () {
	int _;
	scanf ("%d", &_);
	while (_ --) {
		scanf ("%d", &m);
		for (int i = 1;i <= m; ++ i) {
			scanf ("%d", &n[i]);
			for (int j = 1;j <= n[i]; ++ j) {
				int u;
				scanf ("%d", &u);
				seq[i].push_back (u);
				mp[u] ++;
			}
		}
		int ok = 1;
		for (int i = 1;i <= m; ++ i) {
			winner[i] = -1;
			for (int j = 1;j <= n[i]; ++ j) mp[seq[i][j - 1]] --;
			for (int j = 1;j <= n[i]; ++ j) {
				if (!mp[seq[i][j - 1]]) {
					winner[i] = seq[i][j - 1];
					break;
				}
			}
			if (winner[i] == -1) ok = 0;
		}
		for (int i = 1;i <= m; ++ i) {
			for (int j = 1;j <= n[i]; ++ j) seq[i].pop_back ();
		}
		if (ok) {
			for (int i = 1;i <= m; ++ i) printf ("%d ", winner[i]);
			printf ("\n");
		}
		else printf ("-1\n");
	}
	return 0;
}

C. Candy Store

可以发现，\([L,R]\) 可以满足条件当且仅当 \(\displaystyle \gcd\limits_{i=L}^{R}(a_ib_i) \bmod \text{lcm}_{i=L}^{R}(b_i)=0\)。

静态查询 \(\gcd,\text{lcm}\) 可以使用 ST 表预处理。

注意这个 \(\text{lcm}\) 会爆 long long，记得对 \(10^{13}+1\) 进行取 min 操作，别爆了。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int gcd (int a, int b) {return b == 0 ? a : gcd (b, a % b);}
inline int lcm (int a, int b) {
	if (a > 1e13 || b > 1e13) return 1e13 + 1;
	int LHS = a / gcd (a, b);
	int RHS = 1e13 / b;
	if (LHS > RHS) return 1e13 + 1;
	int awa = LHS * b;
	if (awa > 1e13) awa = 1e13 + 1;
	return awa;
}
int lc[200005][21], gc[200005][21], lg[200005], f[200005], early[200005];
inline int lcm_b (int l, int r) {
	int k = lg[r - l + 1];
	return lcm (lc[l][k], lc[r - (1 << k) + 1][k]);
}
inline int gcd_ab (int l, int r) {
	int k = lg[r - l + 1];
	return gcd (gc[l][k], gc[r - (1 << k) + 1][k]);
}
int n, a[200005], b[200005];
signed main () {
	int _;
	scanf ("%lld", &_);
	while (_ --) {
		scanf ("%lld", &n);
		for (int i = 1;i <= n; ++ i) scanf ("%lld %lld", &a[i], &b[i]);
		lg[0] = -1;
		for (int i = 1;i <= n; ++ i) lg[i] = lg[i / 2] + 1;
		for (int i = 1;i <= n; ++ i) lc[i][0] = b[i], gc[i][0] = a[i] * b[i];
		for (int j = 1;j <= 19; ++ j) {
			for (int i = 1;i + (1 << j) - 1 <= n; ++ i) {
				lc[i][j] = lcm (lc[i][j - 1], lc[i + (1 << (j - 1))][j - 1]);
				gc[i][j] = gcd (gc[i][j - 1], gc[i + (1 << (j - 1))][j - 1]);
			}
		}
		for (int i = 1;i <= n; ++ i) {
			int L = 1, R = i;
			while (R - L > 1) {
				int mid = L + R >> 1;
				if (gcd_ab (mid, i) % lcm_b (mid, i) != 0) L = mid;
				else R = mid;
			}
			if (gcd_ab (L, i) % lcm_b (L, i) == 0) early[i] = L;
			else early[i] = R;
		}
		f[0] = 0;
		f[1] = 1;
		for (int i = 1;i <= n; ++ i) f[i] = f[early[i] - 1] + 1;
		printf ("%lld\n", f[n]);
	}
	return 0;
}

D. Shocking Arrangement

特别的，全为 \(0\) 的序列肯定无解（至于为什么自己算）。

对于剩下的序列，因为 \(\displaystyle \sum_{i=1}^{n}a_i=0\)，所以 \(\max\limits_{i=1}^{n}a_i>0,\min\limits_{i=1}^{n}a_i<0\)。

进一步推出：\(\max\limits_{i=1}^{n}a_i-\min\limits_{i=1}^{n}a_i>\max\limits_{i=1}^{n}|a_i|\)（因为有正有负，所以极差肯定是两个绝对值大于 \(0\) 的数的绝对值之和）。

所以我们只需要保证每个子序列的和的绝对值都不超过 \(a\) 中绝对值最大的数的绝对值。

考虑每次 push_back，如果当前和 \(\leq 0\)，就加上最大的正数，否则就加上最小的负数。（因为和为 \(0\) 所以肯定会有加的数）

这样做一定不会爆掉，前缀和一减也不会爆。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
int a[300005], n;
signed main () {
	int _;
	scanf ("%lld", &_);
	while (_ --) {
		scanf ("%lld", &n);
		int os = 0;
		for (int i = 1;i <= n; ++ i) scanf ("%lld", &a[i]), os += (a[i] == 0);
		sort (a + 1, a + 1 + n);
		if (os == n) {
			printf ("No\n");
			continue;
		}
		printf ("Yes\n");
		int L = 1, R = n, sum = 0, num = n;
		while (num --) {
			if (sum <= 0) {
				printf ("%lld ", a[R]);
				sum += a[R];
				R --;
			}
			else {
				printf ("%lld ", a[L]);
				sum += a[L];
				L ++;
			}
		}
		printf ("\n");
	}
	return 0;
}