bistuacm 2019新生训练赛第9场题解
2019-06-01 本文已影响0人
不知名小号
A. Mahmoud and Ehab and the MEX
题目链接：https://codeforces.com/problemset/problem/862/A
题意
对于一个集合，它的mex就是集合里所不包含的最小的非负整数
比如集合{1, 2, 3}的mex是0，集合{0, 1, 2, 4}的mex是3
给你一个集合s，和一个数x
现在可以有如下操作：
- 往集合里加一个数
- 往集合里删一个数
要求你操作最少的次数，使得集合s的mex是x。
思路
- 如果集合s里没有x，那么把集合里不存在的并且比x小的数都补进去，这样子比x小的数都存在了，那么x就是第一个集合里不存在非负整数。
- 如果集合s里有x，那么需要把集合里的x删掉，然后把集合里“不存在的并且小于x的数”都加到集合里，这样子集合里不存在的非负整数就是x了。
代码
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e6 + 7;
int main(int argc, char * argv[])
{
int n, x;
while (cin >> n >> x){
int a[maxn];
bool mark[maxn];
int cnt = 0;
memset(mark, 0, sizeof(mark));
for (int i = 1; i <= n; i++){
cin >> a[i];
mark[a[i]] = 1; // 因为数据比较小，就用一个同来存了
}
if (mark[x] == true){ // mark[x] == true代表x在集合里，它既然在集合里，那就把它去掉
cnt++;
}
for (int i = 0; i < x; i++){
if (mark[i] == false){ // mark[i] == false代表i不存在集合里
cnt++;
}
}
cout << cnt << endl;
}
return 0;
}
B.If at first you don't succeed...
题目链接
https://codeforces.com/problemset/problem/991/A
题意
一共有n个人，有a个人去过A餐厅，有b个人去过B餐厅，还有C个人两个餐厅都去过。问有多少个人没去过餐厅？
注：如果没有人没去过餐厅则输出-1（题目故事背景要求）
如果给出的数据是矛盾的造成局面不合法则输出-1。至于哪种不合法，思路里讲
思路
不合法的条件是啥呢？
比如说有3个人去了A餐厅，5个人去了B餐厅，然后告诉你有4个人两个餐厅都去过，这是相互矛盾的，因为只有3个人去了A餐厅，后面却说有4个人两个餐厅都去过。
如果局面是合法的，那么去了餐厅的人数就是a + b - c。不去餐厅的人数就是n - (a + b - c)。
代码
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e6 + 7;
int main(int argc, char * argv[])
{
int a, b, c, n;
while (cin >> a >> b >> c >> n){
if (a + b - c >= n || c > min(a, b)){
cout << -1 << endl;
}
else{
cout << n - (a + b - c) << endl;
}
}
return 0;
}
C.Urbanization
题目链接
https://codeforces.com/problemset/problem/735/B
题意
有n个居民，他们有不同数量的财产，现在要搬到两个城市city1和city2，其中有citiy1能容纳n1个居民，city2能容纳n2个居民，政府给居民发发出n1和n2个offer给居民分别到city1和city2。如果没有收到offer就不搬（可以忽略不计了）。政府想要新的城市city1的财产平均值和city2的财产平均值之和尽可能大，求这个平均值之和。
思路
我猜的结论hhh。把收入做个排序。假设n1和n2的最小值是a，最大值是b
然后让收入最高的前a人去住人数最少的那个城市，然后从a + 1到a + b个人（也就是出去前a个人之后的b个人）去住人数最多的那个城市。这样子就能达到平均收入值最高。
代码
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e6 + 7;
int main(int argc, char * argv[])
{
int n, n1, n2;
while (cin >> n >> n1 >> n2){
int a[maxn];
int x = min(n1, n2);
int y = n1 + n2 - x;
double ans = 0;
double sum1 = 0, sum2 = 0;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= x; i++){
sum1 += a[n - i + 1]; // 最大的x个
}
for (int i = x + 1; i <= x + y; i++){
sum2 += a[n - i + 1]; // 次大的y个
}
ans = sum1 / x + sum2 / y;
printf("%.8lf\n", ans);
}
return 0;
}
D. Proper Nutrition
链接
https://codeforces.com/gym/245430/problem/D
题意
给出x, y, n。问有没有非负整数a, b。使得a * x + b * y == n
思路
这题太简单了，我们不要n方枚举，n枚举，枚举x的倍数t = i * x(i >= 0)，然后看n - t对y是否整除。如果整除则i和(n - i * x) / y就是答案。
代码
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e6 + 7;
int main(int argc, char * argv[])
{
int n, a, b;
while (cin >> n >> a >> b){
bool flag = 0;
int ans1, ans2;
for (int i = 0; i * a <= n; i++){
if ((n - i * a) % b == 0){
ans1 = i;
ans2 = (n - i * a) / b;
flag = 1;
break;
}
}
if (!flag){
cout << "NO" << endl;
}
else{
cout << "YES" << endl;
cout << ans1 << " " << ans2 << endl;
}
}
return 0;
}
E.Developing Skill
题目链接
https://codeforces.com/problemset/problem/581/C
题意
有n个角色，第i个角色有技能点a[i]。然后总的攻击力是每个a[i] / 10向下取整的和。
现在有k次提升，每次提升可以让一个角色的i的技能点加1。加到100为止（每个角色的技能点不能超过100）。
思路
我写得比较挫。。
这题是个贪心，就是优先把那些个位数接近10的补到10（十位数进一的意思），补到10的话除以十向下取整就会多加1。如果把所有的都补到10之后，k还剩的话，那就把不满100的补到100。
开了一个只有一个整数的结构体，然后重载了这个结构体的比较函数cmp，让他们按照%10的结果从大到小排序，这样子就能优先补那些个位数距离10比较近的。
然后补完了如果k还剩的话，再来一个按照模10距离从小到大排序，这样子的话之前那些被补到正常的从大到小排序，如果当前角色的技能点小于100，就给补到100，如果k不够补到100了，那就把所有k都给它补了。
最后再记他们除10向下取整的和就好了。
代码
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e6 + 7;
struct role{
role(){}
role(int _x){
x = _x;
}
int x;
};
// 两个cmp函数
bool cmp(role a, role b){
// 一个是按照模10的结果从大到小排序
return (a.x % 10) > (b.x % 10);
}
bool cmp2(role a, role b){
// 一个是普通的排序
return (a.x) < (b.x);
}
int main(int argc, char * argv[])
{
int n, k;
while (cin >> n >> k){
std::vector<role> v;
int t;
long long ans = 0;
for (int i = 1; i <= n; i++){
cin >> t;
if (t < 100){ // 小于100才进v，进行下一步运算，等于100的话直接最终结果加10
v.push_back(role(t));
}
else{
ans += 10;
}
}
sort(v.begin(), v.end(), cmp);
for (int i = 0; i < v.size(); i++){
// cout << v[i].x << " ";
// 全都加到10的整数倍
if (k >= 10 - v[i].x % 10){
k -= 10 - v[i].x % 10;
v[i].x += 10 - v[i].x % 10;
}
}
sort(v.begin(), v.end(), cmp2);
for (int i = 0; i < v.size(); i++){
if (k >= 100 - v[i].x){
k -= 100 - v[i].x;
v[i].x = 100;
}
else{
v[i].x += k;
k = 0;
}
ans += v[i].x / 10;
}
/*
for (int i = 0; i < v.size(); i++){
cout << v[i].x << " ";
if (i == v.size() - 1){
cout << endl;
}
}*/
cout << ans << endl;
}
return 0;
}
F. Cyclic Components
题目链接
https://codeforces.com/problemset/problem/977/E
题意
给若干个点，和若干条边。然后问有多少个环？
注：这里的环是指一个联通分支组成一个且只一个环。
思路
一个很重要的结论：一个环上的所有点的度数都等于2.
我没想到这个结论，队友告诉我才把题补了。
判断一个联通分支里的节点的度数是不是都为2。如果是的话这个联通分支就是环。那么有两种方法判断联通分支，一种是dfs一种是并查集。
但并查集的时候要注意一下，如果两个元素已经连接了，就不需要再连了（这虽然说废话但我忘了写，就犯了一个小错误hhh）并查集加上路径压缩才能过！
代码
dfs版
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e6 + 7;
int pre[maxn];
int book[maxn];
int du[maxn];
int cnt = 0;
std::vector<int> G[maxn];
int n, m, p, q;
void dfs(int x){
// cout << "indfs:" << x << endl;
if (du[x] != 2){
cnt = 1;
}
for (int i = 0; i < G[x].size(); i++){
if (!book[G[x][i]]){
book[G[x][i]] = 1;
dfs(G[x][i]);
}
}
}
void add(int p, int q){
G[p].push_back(q);
}
int main(int argc, char * argv[])
{
while (cin >> n >> m){
int ans = 0;
for (int i = 1; i <= m; i++){
cin >> p >> q;
add(p, q);
add(q, p);
du[p]++;
du[q]++;
}
for (int i = 1; i <= n; i++){
if (!book[i]){
book[i] = 1;
cnt = 0; // 如果遇到度数不为2的边，那么cnt就会变为1，则下面的if不成立
dfs(i);
if (!cnt){
ans++;
}
}
}
/*
cout << "out" << endl;
for (int i = 1; i <= n; i++){
cout << i << " " << mark[i] << endl;
}
cout << endl;
*/
cout << ans << endl;
}
return 0;
}
并查集版
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e6 + 7;
int pre[maxn]; // 父节点的编号
int du[maxn]; // 度数
int sz[maxn]; // 子节点的个数
int cnt[maxn]; // 当前根的度数为2的子节点的个数
int n, m;
void init(){
for (int i = 1; i < maxn; i++){
pre[i] = i;
du[i] = 0;
sz[i] = 1;
cnt[i] = 0;
}
}
int root(int x){
while (x != pre[x]){
pre[x] = pre[pre[x]];
x = pre[x];
}
return x;
}
void uni(int p ,int q){
int root_p = root(p);
int root_q = root(q);
if (root_p == root_q){
return;
}
pre[root_p] = root_q;
sz[root_q] += sz[root_p];
}
void print(){
cout << "pre:" << endl;
for (int i = 1; i <= n; i++){
cout << pre[i] << " ";
}
cout << endl;
cout << "sz" << endl;
for (int i = 1; i <= n; i++){
cout << sz[i] << " ";
}
cout << endl;
}
int main(int argc, char * argv[])
{
while (cin >> n >> m){
init();
int ans = 0;
int p, q;
for (int i = 1; i <= m; i++){
cin >> p >> q;
du[p]++;
du[q]++;
uni(p, q);
}
// print();
for (int i = 1; i <= n; i++){
if (du[i] == 2){
cnt[root(i)]++; //cnt[i]这个联通分支的根i的有少个度数为2的子节点
}
}
for (int i = 1; i <= n; i++){
if (pre[i] == i && cnt[i] == sz[i]){
// 如果一个元素的父亲是它自己，那么它就是这个集合里的根，如果它的所有孩子都是的度数为1，则它是个环。
ans++;
}
}
cout << ans << endl;
}
return 0;
}
