Codeforces Round #824 (Div. 2)A-D(思维+贪心+暴力枚举+组合数学)

发布于 2022-10-07  337 次阅读


比赛传送门:Dashboard - Codeforces Round #824 (Div. 2) - Codeforces

A. Working Week(数学)

给定一个数字N,选择三个点进行封锁,必须封锁最后一个点,不能封锁第一个点,且任意两个封锁的点不能连续(中间必须有没被封锁的点),于是这三个封锁的点会将整个序列划分为三块,每块都有一个长度(没被封锁的点的个数),求这三个长度的最小差值最大值

分析一下这道题,我们设这三个长度分别为\(x, y, z\),不妨设\(x \le y \le z\),现在的任务就是使得\(z - y和y - x\)最大。不难感性地发现,我们应该让x尽可能小,z尽可能大,而\(z - y和y - x\)尽可能相等,且满足\(x + y + z = N - 3\),x取最小的1,那么就有\(y + z = N - 4\)并且有\(z - y = y - 1\),解方程组得\(x = 1, y = (N - 3) / 3,z = N - 4 -x - y\),所以最终的答案是\((N - 3) / 3\)向下取整再减一(减去x)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;cin >> T;
	while(T --)
	{
		int N;cin >> N;
		cout << (N - 3) / 3 - 1 << '\n';
	}
	return 0;
}

B. Tea with Tangerines(贪心)

给N块橘子皮,每块橘子皮有一个长度ai(保证输入的a1 <= a2 <= ... <= an)现在可以进行一个操作将长度为x的橘子皮划分为长度为y和z的两块,且y + z = x。

现在要求任意两块橘子皮的长度x和y必须满足\(x < 2 * y且y < 2 * x\)。

分析一下,这道题只能将长度大的划分为小的,所以我们每次都选择最大的进行划分,并且尽可能的划分的合法且大

为了使得这个划分之后的长度合法,就需要知道最小的长度a[1],那么允许的长度就是[a1, 2 * a1 - 1],所以我们就将a[i]划分为k * (2 * a[i] - 1) + r(剩下的部分),剩下的部分可能小于a1,没关系,从前面的2 * a[1] - 1中分a[1]给这个部分就可以保证所有的都是合法的。

我们不能改变最小值因为这样必然使得划分次数增加。

我们可以算出\(k = a[i] / (2 * a[1] - 1)\),剩余部分\(r = a[i] mod (2 * a[i] - 1)\),最后k就是我们需要操作的次数,注意特判r == 0的情况,这种情况需要将k减去1,因为最后一个操作并不需要。

比如a[1] = 2,a[i] = 9,那么就可以分为3, 3, 3(两次操作),而不需要分为3, 3, 3, 0(三次操作)。

这题的数据确实有点小哦。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 110;
int a[maxn];


signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;cin >> T;
	while(T --)
	{
		int N, sum = 0;cin >> N;
		for(int i = 1;i <= N; ++ i)cin >> a[i];
		int ans = 0;
		for(int i = N;i >= 2; -- i)ans += a[i] / (2 * a[1] - 1) - (a[i] % (2 * a[1] - 1) == 0);
		cout << ans << '\n'; 	
	}
	return 0;
}

C. Phase Shift(并查集)

给了一个加密后的字符串,求加密前的字符串(要求字典序最小),加密方法是一个环形的长度为26的图。

其实可以看作将一个加密前的字符串进行加密,都一样啦,重点在求出“加密方法图”。

分析,我们可以将每个字符设置一个pre(前驱节点)和一个nex(后驱节点),由此连接成一个图。

对于每一个没有nex节点(初始为0)的字符,我们可以设一个ch,从‘a’开始找到‘z’(从小到大贪心),将第一个合法的连起来就可以,怎样是合法的呢?

首先要满足pre[ch] = 0,这样才能将nex[s[i]]设为ch。

齐次有两种情况,第一种是整个图中已连接的边条数小于25,就要求连接的这两个字符ch 和 s[i]不能是同一个集合里的,否则会产生一个长度小于26的环,这样的话只要不在一个集合里就直接连接。第二种是已连接的边的条数等于25,说明这时候这一条边ch-s[i]就是将整个图连接成环的最后一条边了。

为了方便我就没有节省空间,直接开了300的数组。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9, inf = 8e18;
char s[maxn];
int dsupre[300], pre[300], nex[300];//dsupre是并查集的前驱 

int root(int x)
{
	return dsupre[x] = (dsupre[x] == x ? x : root(dsupre[x]));
}

void Merge(int x,int y)
{
	dsupre[root(x)] = root(y);
}

bool iscon(int x,int y)
{
	return root(x) == root(y);
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;cin >> T;
	while(T --)
	{
		int N;cin >> N;
		cin >> s + 1;
		memset(pre, 0, sizeof pre);
		memset(nex, 0, sizeof nex);
		int cnt = 0;//表示边的条数 
		for(char i = 'a';i <= 'z'; ++ i)dsupre[i] = i;
		for(int i = 1;i <= N; ++ i)
		{
			if(!nex[s[i]])
			{
				for(char ch = 'a';ch <= 'z'; ++ ch)
				{
					if(ch == s[i])continue;
					
					bool tag = iscon(ch, s[i]) && cnt == 25 && !pre[ch];
					tag = tag || (!iscon(ch, s[i]) && !pre[ch]);
					
					if(tag)
					{
						nex[s[i]] = ch, pre[ch] = s[i];
						Merge(ch, s[i]);
						cnt ++;
						break;
					}
				}
			}
			
			cout << (char)nex[s[i]];
		}
		cout << '\n';
	}
	return 0;
}

D. Meta-set(暴力 + Hash)

现在有N张牌,每张牌有K个特征,对于某一个特征,如果有三张牌的该特征分别为x, y, z且满足\((x + y+ z) mod 3 = 0\),那么我们就说这个特征是一个good特征,如果这三张牌的所有特征都是good特征,那么这三张牌就组成了一个集合set。

一个meta-set是一个五张牌的集合且其中有大于一个的set。

分析不难发现,只要两个set且有一张牌重复就可以组成一个meta-set,其中可能有2个或3或4个set不用管。

于是我们可以处理出对于每一张牌,它参与在多少个set中,我们称之为这张牌的set个数。

题目保证了牌是独特的,也就是每一个set都不重复。

我们可以用一个hash来表示一张牌,对于一个set,我们可以知二推一,所以我们枚举所有的两张牌组合(i < j避免重复),求到第三张牌的hash然后将第三张牌的set个数+1

比如现在有三张牌x y z组成了一个集合,当我们枚举x, y时可以将z的set个数+1,枚举x, z时就可以将y的set个数+1,枚举到y, z的时候就可以将z的set个数+1,所以这样可以求出所有牌的set个数。

最后对于这N张牌的每一张牌,将其设置为“重复牌”,只要找它的任意两个set就可以组成一个meta-set,所以方案是\(C_{cnt}^{2}\),cnt是这张牌set个数。

这里用到了黑科技_gnu__pbds中的gp_hash_table,比map快了一倍多,用法和map一样。

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9, inf = 8e18, base = 13331;
typedef unsigned long long ULL;
int card[maxn][30], cnt[maxn];
ULL h[maxn];//保存N张牌的hash 
__gnu_pbds::gp_hash_table<ULL, int> mp;

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N, K;cin >> N >> K;
	for(int i = 1;i <= N; ++ i)
	{
		for(int j = 1;j <= K; ++ j)cin >> card[i][j];
		for(int j = 1;j <= K; ++ j)h[i] = h[i] * base + card[i][j] + 17;//求hash 
	}
	for(int i = 1;i <= N; ++ i)
	{
		for(int j = i + 1;j <= N; ++ j)
		{
			ULL sum = 0;
			for(int k = 1;k <= K; ++ k)sum = sum * base + (6 - card[i][k] - card[j][k]) % 3 + 17;
			mp[sum] ++;//将第三张牌的set个数++
		}
	}
	int ans = 0;
	for(int i = 1;i <= N; ++ i)//i作为重复牌,有meta-set 
	{
		int k = mp[h[i]];
		ans += k * (k - 1) / 2;
	}
	cout << ans << '\n';
	return 0;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-10-07