Codeforces Round #805 (Div. 3)
A.Round Down the Price
题目大意
输入一个数$n$,输出$n-10^k$,$k$等于$n$的位数减一。
解题思路
签到题,模拟即可。
具体代码
#include <bits/stdc++.h>
using namespace std;
int realdigit(string s)
{
int res = 0;
for (int i = 0; s[i]; i++)
res = res * 10 + s[i] - '0';
return res;
}
int main()
{
int T;
cin >> T;
while (T--)
{
string n;
cin >> n;
string tmp = "1";
for (int i = 1; i < n.length(); i++)
tmp += '0';
cout << realdigit(n) - realdigit(tmp) << '\n';
}
return 0;
}
B.Polycarp Writes a String from Memory
题目大意
一个人记单词很健忘。每天最多记三种字母。例如这个人现在要记单词$stringology$,那么他总共要记四天,第一天记$str$,第二天记$ing$,第三天记$olog$,第四天记$y$。输入一个单词,输出这个人要几天才能记住。保证题中字母都是小写。
解题思路
模拟。遍历字符串,因为每天只能记三种字母,如果记到第四种字母就说明需要新的一天,把之前的单词从记忆里清空,同时天数加一。
具体代码
#include <bits/stdc++.h>
using namespace std;
map<char, int> S;
int main()
{
int T;
cin >> T;
while (T--)
{
string str;
cin >> str;
int ans = 0;
for (int i = 0; i < str.length(); i++)
{
S[str[i]] = 1;
if (S.size() > 3)
{
S.clear();
S[str[i]] = 1;
ans++;
}
}
S.clear();
cout << ans + 1 << '\n';
}
return 0;
}
C.Train and Queries
题目大意
火车会单向地经过$u_1$,$u_2$,……,$u_n$这些站点。每次询问输入$a$,$b$,问火车能否从站点$a$到达站点$b$。
解题思路
$l$数组存站点第一次出现的位置,$r$数组存站点第二次出现的位置。如果询问的两个站点都是火车会经过的站点,且$l[a]<r[b]$,说明$a$能到达$b$。
具体代码
#include <bits/stdc++.h>
using namespace std;
map<int, int> l, r; //站点范围最大在10^9,所以要么离散化要么用map
int n, m;
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n >> m;
l.clear();
r.clear();
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
if (l[x] == 0)
{
l[x] = i;
r[x] = i;
}
else
r[x] = i;
}
while (m--)
{
int x, y;
cin >> x >> y;
if (l[x] && r[y] && l[x] < r[y])
puts("YES");
else
puts("NO");
}
}
return 0;
}
D.Not a Cheap String
题目大意
定义每个字母的价值是在字母表的排名,每个单词的价值是其中字母价值之和。例如单词$abca$的价值是$1+2+3+1=7$。现给出单词和$p$,要求删除最少的字母,使得单词的价值$\leq p$。如果有多解随意输出一种,有$specialjudge$。
解题思路
非常非常显然的贪心题,尽量删价值大的字母直到价值$\leq p$即可。
具体代码
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int f[N]; //记录各字母出现次数
int main()
{
int T;
cin >> T;
while (T--)
{
string str, ans;
int p;
cin >> str >> p;
int sum = 0;
memset(f, 0, sizeof f);
for (int i = 0; i < str.length(); i++)
{
sum += str[i] - 'a' + 1;
f[str[i] - 'a']++;
}
for (int i = 25; i >= 0; i--) //贪心,试着按zyxwvu……cba这样的顺序删
{
while (sum > p && f[i] > 0)
{
f[i]--;
sum -= i + 1;
}
}
for (auto x : str)
{
if (f[x - 'a'] > 0)
{
ans += x;
f[x - 'a']--;
}
}
cout << ans << '\n';
}
return 0;
}
E.Split Into Two Sets
题目大意
一个人收到了$n$个多米诺骨牌(保证$n$是偶数),每个多米诺骨牌都有正反面,正反面上各是一个$1$到$n$的整数。现在问能否将这些多米诺骨牌分成两份,使得每一份中都没有重复的数字。
解题思路
题干有一个很重要的隐藏信息:分好的两份里各有$n$个数,这些数的范围都是$1$到$n$,且各不相同,说明从$1$到$n$每个数都恰出现一次。
另外当以下两种情况发生时,显然不能分成合法的两份:
$1.$存在一张多米诺骨牌正反面是一样的数。
$2.$一个数在这些骨牌中出现了$3$次及以上。
接下来用并查集即可,对于每一张多米诺骨牌,就将正面与反面的数合并,这表示我们取了正面的数就一定会取反面的数。最后如果存在一个连通块中的点数是奇数,说明至少有一个数被重复选取了。想不通的话可以想想逆否命题,如果没有数被重复选取,那么任意一个连通块中的点数都是偶数。
另外此题还有二分图染色和建图dfs找奇数环的做法,感兴趣的可以去$codeforces$学习。(此题如果正常建图,每个合法连通块都必是偶数环,可以细细思考。)
具体代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
int p[N], s[N], f[N];
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= n; i++)
{
p[i] = i;
s[i] = 1; //连通块中点的数目
}
memset(f, 0, sizeof f); //每个数的出现次数
bool flag = false;
for (int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
f[a]++, f[b]++;
if (a == b)
flag = true;
if (find(a) != find(b))
{
s[find(b)] += s[find(a)];
p[find(a)] = find(b);
}
}
for (int i = 1; i <= n; i++)
{
if (flag || s[find(i)] % 2 == 1 || f[i] > 2)
{
flag = true;
break;
}
}
if (flag)
cout << "NO" << '\n';
else
cout << "YES" << '\n';
}
return 0;
}