@TOC
Codeforces Round #805 (Div. 3) 题解
比赛地址： Codeforces Round #805 (Div. 3)
通过熬夜奋战写出了六道题，排名一千多，算是我打的cf中最好的成绩了，(回想起我半年前第一次打cf 八千多名）继续加油。
昨天总共参加了三场比赛，上午的力扣周赛，下午的河南萌新联赛，晚上的div3，打的特别累，而且上午和下午打的都不理想，备受打击，也没睡午觉，最后还是硬着头写的div3到凌晨，但成绩比较满意，嘿嘿。
A Round Down the Price
题目连接： Round Down the Price
题目大意
给你一个整数m(1<<m<<10^9)，问这个数最少减去多少可以使这个数变成10的整数次幂
思路： 构造
直接模拟枚举就行，先把10的整数次幂全部求出来，然后枚举一下，直到找到一个数能使
10^k <= m << 10^(k+1)即可
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll f[10];
void slove()
{
int n;
cin >> n;
for (int i = 1; i <= 10; i++)
{
if (n < f[i])
{
cout << n - f[i - 1] << endl;
return;
}
}
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
f[0] = 1;
for (int i = 1; i <= 10; i++)
f[i] = f[i - 1] * 10;
int t;
cin >> t;
while (t--)
{
slove();
}
return 0;
}B Polycarp Writes a String from Memory
题目连接： Polycarp Writes a String from Memory
题目大意
给你一个单词，每天最多只能写三种字母，最少要多少天才能写完这个单词
思路： 贪心
枚举即可，把这个单词从前往后遍历一遍，如果连续有四种不同的字母，那天数就要加一天，前面三个字母就清零，不在计算。用
set即可判断有多少个不同的字母
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
void slove()
{
string s;
cin >> s;
set<int> se;
int ans = 0;
for (int i = 0; i < s.size(); i++)
{
se.insert(s[i]);
if (se.size() > 3)
{
ans++;
se.clear();
se.insert(s[i]);
}
}
if (se.size())
ans++;
cout << ans << endl;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
{
slove();
}
return 0;
}C Train and Queries
题目连接： Train and Queries
题目大意
给你一个数组，数组中可能有相同的数，然后给你两个整数a和b，问在数组中是否有数字a的下标小于数字b的下标
思路： 贪心+数据结构
我们需要记录数组中每个数的位置在什么地方，有些数可能不止出现一次，我们难道要记录这个数的全部位置吗？其实不用，我们只需要这个数的最小的下标和最大的下标即可，我们求结果的时候一定是求能满足条件的，那么最值就能满足很多条件，而且最简便。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e6 + 10;
void slove()
{
int n, m;
cin >> n >> m;
map<int, PII> ma;
for (int i = 1; i <= n; i++)
{
int t;
cin >> t;
if (ma.count(t) == 0)
{
ma[t].x = i;
ma[t].y = i;
}
else
{
ma[t].y = i;
}
}
while (m--)
{
int a, b;
cin >> a >> b;
if (ma.count(a) == 0 || ma.count(b) == 0)
{
puts("NO");
continue;
}
a = ma[a].x;
b = ma[b].y;
if (a < b)
puts("YES");
else
puts("NO");
}
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
{
slove();
}
return 0;
}D Not a Cheap String
题目连接： Not a Cheap String
题目大意
给你一个由小写字母组成的字符串，每个字母都有其对应的26个字母其顺序的价值（a == 1, b==2... z == 26)，那么这个字符串的价值就是每个字母的价值的总和。然后你一个整数p，问最少去掉字符串中多少个字母能使这个字符串的价格小于等于p，并且输出去掉字母后的字符串。
思路： 贪心
为了使去掉的字母最少，那么就需要把字符串中价值最大的字母去掉，直到价值小于等于p，还需要记录去掉了哪些字母，最后还要输出处理过的字符串，我这里用了一个数组来记录每个字母有多少个，另一个数组用来记录删除了那些字母。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e6 + 10;
int a[30];
int b[30];
void slove()
{
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
string s;
int p;
cin >> s;
cin >> p;
int ans = 0;
for (int i = 0; i < s.size(); i++)
{
ans += s[i] - 'a' + 1;
a[s[i] - 'a']++;
}
for (int i = 0; i <= 25; i++)
b[i] = a[i];
for (int i = 25; i >= 0; i--)
{
if (ans <= p)
break;
while (a[i] > 0 && ans > p)
{
a[i]--;
ans -= i + 1;
}
}
string w = "";
for (int i = 0; i < s.size(); i++)
{
int e = s[i] - 'a';
// 不用删除的就保留
if (a[e] == b[e])
{
w += s[i];
}
else
{
a[e]++;
}
}
cout << w << "\n";
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
{
slove();
}
return 0;
}E Split Into Two Sets
题目连接： Split Into Two Sets
题目大意
给你n个集合，每个集合里有两个数字，问能否将这n个集合分成两组，并且每组内所有的集合里的数字组成一个集合后数字不能有重复
思路： 染色法判定二分图
一般要将一个集合分成两部分考查的都是二分图，这题算是二分图板子题，没有什么变化，只在于如何建边即可，为了让数字不能重复，那么一个数字所在的所有集合里都要连一条边，表示它俩不能在一个集合里，如果一个数所在的集合有三个，那么一定不能构成二分图，如果一个集合里两个数字相同，那么也一定不能构成二分图。建完图之后，就可以用染色法判定是否使二分图即可
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 2e5 + 10;
bool st[N];
int c[N];
vector<int> v[N]; // 存每个数字所在的集合
vector<int> ve[N]; // 邻接表存边
bool dfs(int u, int color) // 染色法判定二分图
{
c[u] = color;
for (int i = 0; i < ve[u].size(); i++)
{
int j = ve[u][i];
if (c[j] == color)
return false;
if (c[j] == 0 && !dfs(j, -1 * color))
return false;
}
return true;
}
void slove()
{
int n;
cin >> n;
int f = 1;
for (int i = 1; i <= n; i++)
{
c[i] = 0;
v[i].clear();
ve[i].clear();
}
for (int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
if (a == b)
{
f = 0;
}
v[a].push_back(i);
v[b].push_back(i);
if (v[a].size() > 2 || v[b].size() > 2)
f = 0;
}
if (f == 0)
{
puts("NO");
return;
}
for (int i = 1; i <= n; i++)
{
if (v[i].size() == 2)
{
ve[v[i][0]].push_back(v[i][1]);
ve[v[i][1]].push_back(v[i][0]);
}
}
for (int i = 1; i <= n; i++)
{
if (!c[i])
{
if (!dfs(i, 1))
{
f = 0;
break;
}
}
}
if (f)
puts("YES");
else
puts("NO");
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
{
slove();
}
return 0;
}F Equate Multisets
题目连接： Equate Multisets
题目大意
给你两个数组a和b，问是否能让b数组里的元素通过如下两种操作无限次，使b数组变成a数组，（只需要数组中的元素一样即可，不需要顺序一样）
- 将 x 变成 x * 2
- 将 x 变成 x / 2 (向下取整)
思路： 思维+贪心
这题贪心不是很好证明，可以自己推一下，只要正确就可以
如何将b数组变成a数组呢？我们来看各种情况
- a[i] == b[i] 那么可以直接跳过
- a[i] == b[i] 2 2 *.. 2 ,那么只需要将b[i] 一直使用操作1直到和a[i] 相同即可
- a[i] == b[i] / 2 / 2 / 2 那么一直执行操作2即可
我们先来看b数组里的元素无非最多就两种，偶数和奇数，偶数除于2最后一定可以得到一个奇数。那么b数组最后就变成了一个全是奇数的数组。那么我们也可以将a数组也这样做，为什么呢？举个例子
a[i] = 10, b[i] = 5, ==> b[i] * 2 ==> a[i] / 2 = b[i]
a[i] = 4, b[i] = 1, ==> b[i] 2 2 ==> a[i] / 2 / 2 = b[i]
这样只需要将a数组和b数组都这样转换成一个中间数组c后，就可以很快的判断了,是这样的一个定理：
A == C
B == C
==》 A == B
最后我们要来处理b数组了，我们现在只需要将b数组的数都执行操作2就行了，如果操作完之后在a数组里有对应的数，那么就可以转换，否则不能。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 2e5 + 10;
void slove()
{
int n;
cin >> n;
int f = 1;
map<int, int> ma;
for (int i = 1; i <= n; i++)
{
int a;
cin >> a;
while (a % 2 == 0)
a /= 2;
if (ma.count(a) == 0)
ma[a] = 1;
else
ma[a]++;
}
for (int i = 1; i <= n; i++)
{
int a;
cin >> a;
while (a % 2 == 0)
a /= 2;
while (a != 1 && ma[a] == 0)
a /= 2;
if (ma[a] > 0)
ma[a]--;
else
f = 0;
}
if (f)
puts("YES");
else
puts("NO");
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
{
slove();
}
return 0;
}G1和G2我还不会，这里就先放着了，以后在补上。
加油！
