AtCoder Beginner Contest 142 题解

AtCoder Beginner Contest 142 题解

A.Odds of Oddness

◇题目传送门◆

题目大意

给定一个数$N$，求从$1$到$N$中的数中抽出一个奇数的概率是多少。

分析

水题。

参考程序

#include <cstdio>
#include <algorithm>
using namespace std;int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint N;scanf("%d" ,&N);int tmp = 0;for(int i = 1; i <= N; i++)if(i % 2) tmp++;printf("%f", 1.0 * tmp / N);return 0;
}

B.Roller Coaster

◇题目传送门◆

题目大意

找出比一个序列中比$K$大的的数的个数

分析

水题，扫一遍就够了。

参考程序

#include <cstdio>
#include <algorithm>
using namespace std;int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint N, t, cnt = 0;scanf("%d %d", &N, &t);for(int i = 1; i <= N; i++) {
    int x;scanf("%d", &x);if(x >= t) cnt++;}printf("%d\n", cnt);return 0;
}

C.Go to School

◇题目传送门◆

题目大意

给定一个学校里学生来的时间点，求将每个学生按时间顺序排序后输出编号。

分析

将每个数的编号记下来后排序输出即可。

参考程序

#include <cstdio>
#include <algorithm>
using namespace std;const int Maxn = 1e5;struct Node {
    int val, id;bool operator < (const Node &rhs) const {
    return val < rhs.val;}
};int N;
Node A[Maxn + 5];int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d", &N);for(int i = 1; i <= N; i++)scanf("%d", &A[i].val), A[i].id = i;sort(A + 1, A + N + 1);for(int i = 1; i <= N; i++)printf("%d ", A[i].id);return 0;
}

D.Disjoint Set of Common Divisors

◇题目传送门◆

题目大意

给定两个数$A,B$，要求选出$\gcd (A,B)$中的任意的因数，使得这些因数互素。求最多可以选多少个因数。

分析

简单分析一下就可以发现，我们要选的数就是$\gcd (A,B)$中的不同的质因数个数+1即可（1也可以算在里面）。

参考程序

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;typedef long long ll;
const int Maxn = 1e6;ll GCD(ll x, ll y) {
    if(y == 0) return x;return GCD(y, x % y);
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifll x, y;scanf("%lld %lld", &x, &y);int cnt = 1;ll g = GCD(x, y);for(ll i = 2; i * i <= g; i++) {
    if(g % i == 0)cnt++;while(g % i == 0) g /= i;}if(g > 1) cnt++;printf("%d\n", cnt);return 0;
}

E.Get Everything

◇题目传送门◆

题目大意

有$M$把钥匙和$N$个箱子，使用第$i$把钥匙需要$A_i$的代价，但能打开$B_i$个箱子（箱子的编号给定），求出打开所有的箱子需要的代价。

分析

考虑到$N$极其小，所以我们可以考虑状压。

定义状态$f(i,S)$为用前$i$把钥匙，打开在集合$S$中的箱子所用的最小代价。

转移显然，看程序就是了。

参考程序

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int Maxn = 12;
const int Maxm = 1000;
const int INF = 0x3f3f3f3f;int N, M;
struct Node {
    int A, C;
};
Node A[100000 + 5];int f[Maxm + 5][(1 << Maxn) + 5];int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d %d" ,&N, &M);for(int i = 1; i <= M; i++) {
    int x;scanf("%d %d", &A[i].A, &x);int t = 0;for(int j = 1; j <= x; j++) {
    int tmp;scanf("%d", &tmp);t |= (1 << (tmp - 1));}A[i].C = t;}memset(f, 0x3f, sizeof f);f[0][0] = 0;for(int i = 1; i <= M; i++) {
    for(int s = 0; s < (1 << N); s++) {
    int s1 = s | A[i].C;f[i][s1] = min(f[i][s1], f[i - 1][s] + A[i].A);f[i][s] = min(f[i][s], f[i - 1][s]);}}if(f[M][(1 << N) - 1] != INF)printf("%d\n", f[M][(1 << N) - 1]);else puts("-1");return 0;
}

F.Pure

◇题目传送门◆

题目大意

给定一个有向图图，要求从里面选出一个子图，使得这个子图中所有的点的出度和入度都是1。

分析

分析一下会发现当图中不存在环时是无解的。

那么问题就变成了在图上找到一个环。

具体还是见代码吧。。。

参考程序

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;const int Maxn = 1000;
const int Maxm = 2000;vector<int> G[Maxn + 5];int N, M;
bool vis[Maxn + 5];
int dep[Maxn + 5], ed;
vector<int> ans;bool DFS(int u) {
    vector<int> tmp;int t = -1;for(int i = 0; i < (int)G[u].size(); i++) {
    int v = G[u][i];if(dep[v] != -1) {
    if(t == -1) t = v;else if(dep[v] > dep[t]) t = v;}if(!vis[v]) tmp.push_back(v);vis[v] = true;}if(t == -1) {
    for(int i = 0; i < (int)tmp.size(); i++) {
    int v = tmp[i];dep[v] = dep[u] + 1;if(DFS(v)) {
    if(dep[u] >= dep[ed])ans.push_back(u);return true;}dep[v] = -1;}for(int i = 0; i < (int)tmp.size(); i++)vis[tmp[i]] = false;return false;} else {
    ed = t;ans.push_back(u);return true;}
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d %d", &N, &M);for(int i = 1; i <= M; i++) {
    int u, v;scanf("%d %d", &u, &v);G[u].push_back(v);}memset(dep, -1, sizeof dep);for(int i = 1; i <= N; i++) {
    memset(vis, false, sizeof vis);vis[i] = true, dep[i] = 0;if(DFS(i)) {
    printf("%d\n", ans.size());for(int i = (int)ans.size() - 1; i >= 0; i--)printf("%d\n", ans[i]);return 0;}dep[i] = -1;}puts("-1");return 0;
}