bistuacm 2019新生训练赛第9场题解

作者: 不知名小号 | 来源:发表于2019-06-01 00:36 被阅读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;
}

bistuacm 2019新生训练赛第9场题解

A. Mahmoud and Ehab and the MEX

题目链接：https://codeforces.com/problemset/problem/862/A

题意

思路

代码

B.If at first you don't succeed...

题目链接

题意

思路

代码

C.Urbanization

题目链接

题意

思路

代码

D. Proper Nutrition

链接

题意

思路

代码

E.Developing Skill

题目链接

题意

思路

代码

F. Cyclic Components

题目链接

题意

思路

代码

dfs版

并查集版

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读