Codeforces Round #723 (Div. 2) 个人题解

2024-03-13 21:16:09

上1400辣！

A. Mean Inequality

题意

给一个长度为偶数的数组，你需要重排这个数组，使得任意一个数不等于他前后两个数的平均值。

分析

只需保证数组元素为小 - 大 - 小 - 大，则两个小的平均值一定不为大，两个大的平均值一定不为小。这个条件的构造方法很多，可以排序后奇偶位互换，也可以排序后分成前半和后半，然后轮流输出。

代码

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
 
signed main()
{
    IOS;
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        int a[n];
        n *= 2;
        for(int i = 0; i < n; ++i){
        	cin >> a[i];
		}
		sort(a, a + n);
		for(int i = 0; i < n / 2; ++i){
			cout << a[i] << ' ';
			cout << a[i + n / 2] << ' ';
		}
		cout << endl;
    }
    return 0;
}

B. I Hate 1111

实际上这是昨天被卡的最惨的题……

题意

给定一个数，问其是否可以表示为
k 1 × 11 + k 2 × 111 + k 3 × 1111 + k 4 × 11111 + . . . , k i ∈ N k_1×11+k_2×111+k_3×1111+k_4×11111+...,k_i∈N k1×11+k2×111+k3×1111+k4×11111+...,ki∈N
数据规模1e9.

分析

三种做法

打表

通过bfs打表获得所有10000以下能被表示出来的数，观察发现差不多到1000多的时候，数据就开始连续出现了，也就是说，至少从2000开始，所有的数都能表示出来。
代码

/**
  * @file    :vsDebug2.cpp
  * @brief   :CF Round 723
  * @date    :2021-05-28
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 10000;
int u[] = {11, 111, 1111};
map<int, int> mp;
void chart()
{
	queue<int> q;
	q.push(0);
	while(!q.empty())
	{
		int now = q.front();
		q.pop();
		for(int i = 0; i < 3; ++i){
			if(!mp.count(now + u[i]) && now + u[i] <= maxn){
				mp[now + u[i]] = 1;
				q.push(now + u[i]);
			}
		}
	}
}
signed main()
{
    IOS;
    int t;
   cin >> t;
	// t = 1;
	chart();
    while(t--)
    {
    	int n;
    	cin >> n;
    	if(n <= 10000){
    		if(mp[n]) cout << "YES" << endl;
    		else cout << "NO" << endl;
		}
		else cout << "YES" << endl;
    }
    return 0;
}

塞瓦韦斯特定理

把这些11,111,1111数字拿出来看看，发现 1111 = 11 ∗ 100 + 11 , 11111 = 111 ∗ 100 + 11 ， 111111 = 111 ∗ 100 + 111 , . . . 1111=11*100+11,11111=111*100+11，111111=111*100+111,... 1111=11∗100+11,11111=111∗100+11，111111=111∗100+111,...
于是可以得出结论：只有11和111是我们必需的，其他的都可以不要。

于是问题转化成：

方程 11 x + 111 y = b 11x+111y=b 11x+111y=b是否有解 ( x , y ) (x,y) (x,y).

又看到 g c d ( 11 , 111 ) = 1 gcd(11,111)=1 gcd(11,111)=1，这里很容易想到扩展欧几里得定理。另外，还有一个更简洁的塞瓦韦斯特定理，类似的题目见2017NOIP提高组《小凯的疑惑》这题，大佬的题解传送门（含定理证明）：https://www.cnblogs.com/xxzh/p/9178564.html

即已知a,b为大于1的正整数， g c d ( a , b ) = 1 gcd(a,b)=1 gcd(a,b)=1,则使不定方程 a x + b y = C ax+by=C ax+by=C无负整数解的最大整数为 C = a b − a − b C=ab−a−b C=ab−a−b.

代码
（见下方纯暴力的代码，暴力部分是一模一样的，只是判断一下，大于 11 ∗ 111 − 11 − 111 11*111-11-111 11∗111−11−111的数都输出 Y E S YES YES即可）

暴力

由于测试数据不够强，可以直接用11,111这两个数纯暴力过掉

由于数字只用11,111就可以表示了，因此可以枚举111的倍数，减掉后看能否整除11即可，由于1e9的范围，最多枚举约9e6次即可。然而题目给的 t t t是1e4，暴力法也只用了62ms，说明没有刻意造大数据，很奇怪……

代码

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
signed main()
{
//    IOS;
    int t;
   cin >> t;
    while(t--)
    {
    	int n;
		cin >> n;
		int p = 0;
		bool flag = 0;
		while(p * 111 <= n){
			n -= p * 111;
			if(n % 11 == 0){
				flag = 1;
				break;
			}
			n += p * 111;
			p++;
		}
		cout << (flag ? "YES" : "NO") << endl;
    }
    return 0;
}

C1. Potions(Easy Version)

题意

有 n n n个瓶子，你拥有一个初始生命值0，然后你按照从左往右的顺序，决定每一个瓶子喝与不喝。每个瓶子有一个权值 a i a_i ai，喝掉，则生命值加上 a i a_i ai. 注意 a i a_i ai可以为负数。你需要保证任何时候生命值均不大于0.问最多可以喝几瓶水？瓶子数≤2000.

分析

由于是Easy Version，这里给一个自己yy的 O ( n 2 ) O(n^2) O(n2)的dp做法。（想要 O ( n l o g n ) O(nlogn) O(nlogn)做法直接看Hard Version

设 d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i瓶，包括第 i i i瓶，喝了 j j j瓶的最大生命值。

转移方法稍微复杂：

首先 d p [ i ] [ j ] dp[i][j] dp[i][j]的子状态为 d p [ i − 1 ] [ j − 1 ] dp[i-1][j-1] dp[i−1][j−1]和 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j].即要么我们喝掉第 i i i瓶，要么不喝第 i i i瓶，而直接从前面选 j j j瓶.
且只有子状态不为负数时，我们才能转移，因为要保证时时刻刻生命值大于0嘛。

所以 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j − 1 ] + 1 , d p [ i − 1 ] [ j ] ) dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j]) dp[i][j]=max(dp[i−1][j−1]+1,dp[i−1][j])
仅当两个子状态都为非负才有这个方程，否则只选其中非负的那一个。如果都负，那么 d p [ i ] [ j ] dp[i][j] dp[i][j]是不可达到的，直接赋值负无穷。

代码

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2005;
int a[maxn];
int dp[maxn][maxn];
signed main()
{
//    IOS;
    int t;
//    cin >> t;
	t = 1;
    while(t--)
    {
    	int n;
    	cin >> n;
    	fors(i, 1, n) cin >> a[i];
    	if(n == 1){
    		if(a[1] >= 0){
    			cout << 1 << endl;
			}
			else cout << 0 << endl;
			continue;
		}
    	mem(dp);
    	int ans = 0;
    	dp[1][1] = a[1];
    	for(int i = 2; i <= n; ++i){
    		for(int j = 1; j < i; ++j){
    			if(dp[i - 1][j] < 0 && dp[i - 1][j - 1] < 0){
    				dp[i][j] = -1000000000LL;
				}
				else if(dp[i - 1][j] < 0){
					dp[i][j] = dp[i - 1][j - 1] + a[i];
				}
				else if(dp[i - 1][j - 1] < 0){
					dp[i][j] = dp[i - 1][j];
				}
				else{
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + a[i]);
				}
				if(dp[i][j] >= 0){
					ans = max(ans, j);
				}
			}
			if(dp[i - 1][i - 1] >= 0)
				dp[i][i] = dp[i - 1][i - 1] + a[i];
			else dp[i][i] = -1000000000LL;
			if(dp[i][i] >= 0) ans = max(ans, i);
		}
		cout << ans << endl;
    }
    return 0;
}

C2. Potions(Hard Version)

和C1题意一致，但数据规模从2000扩大到200000.

分析

这规模一扩大， O ( n 2 ) O(n^2) O(n2)不仅会爆时间，也会爆空间。因此原来的 d p dp dp不管用了。考虑贪心。
（昨天比赛的时候yy了很久 d p dp dp的优化，二分，预处理，前缀和都想过，最后都无果……突然想到用单调队列能不能行，最后搞出来个优先队列，惊喜地发现和官方题解做法几乎一样）

我们可以维护一个小顶的优先队列，然后遍历所有水瓶，每次将水瓶加入队列，然后维护当前队列中所有水瓶的生命值和。如果这个和小于0了，我们只需要让队列中最小的数不断出队（也就是堆顶）直到和值非负即可。最后的答案即为队列的长度。

代码

By Ekennis, contest: Codeforces Round #723 (Div. 2), problem: (C2) Potions (Hard Version), Accepted, #, Copy
/**
  * @file    :vsDebug2.cpp
  * @brief   :CF Round 723
  * @date    :2021-05-28
  * @Motto   :Love Sakurai Yamauchi Forever
  */
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
//int dp[maxn][maxn];
signed main()
{
//    IOS;
    int t;
//    cin >> t;
	t = 1;
    while(t--)
    {
    	int n;
    	cin >> n;
    	fors(i, 1, n) cin >> a[i];
    	// 维护一个单调队列.
    	int ans = 0;
    	priority_queue<int, vector<int>, greater<int>> q;
    	int cnt = 0, now = 0;
    	fors(i, 1, n){
    		q.push(a[i]);
    		now += a[i];
    		while(now < 0){
    			now -= q.top();
    			q.pop();
			}
			ans = max(ans, (int)q.size());
		}
		cout << ans << endl;
    }
    return 0;
}

码农公寓