AtCoder Beginner Contest 142 题解
A.Odds of Oddness
◇题目传送门◆
题目大意
给定一个数
N
N
N，求从
1
1
1到
N
N
N中的数中抽出一个奇数的概率是多少。
分析
水题。
参考程序
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
#ifdef LOACL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int 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
K
K大的的数的个数
分析
水题，扫一遍就够了。
参考程序
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
#ifdef LOACL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int 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 LOACL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%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
A,B
A,B，要求选出
gcd
(
A
,
B
)
\gcd(A,B)
gcd(A,B)中的任意的因数，使得这些因数互素。求最多可以选多少个因数。
分析
简单分析一下就可以发现，我们要选的数就是
gcd
(
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 LOACL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ll 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
M
M把钥匙和
N
N
N个箱子，使用第
i
i
i把钥匙需要
A
i
A_i
Ai的代价，但能打开
B
i
B_i
Bi个箱子（箱子的编号给定），求出打开所有的箱子需要的代价。
分析
考虑到
N
N
N极其小，所以我们可以考虑状压。
定义状态
f
(
i
,
S
)
f(i,S)
f(i,S)为用前
i
i
i把钥匙，打开在集合
S
S
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 LOACL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%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 LOACL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%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;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
