比赛传送门：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;
}
文章评论