AtCoder Beginner Contest 142

前四道都是签到题，直接放代码

A. Odds of Oddness

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>  
#include <string>  
using namespace std;
 
int main()
{
	int x;
	cin >> x;
	if (x % 2 == 0)
		cout << 0.5000000000;
	else
		cout << ((double)(x + 1) / 2) / x;
 
	return 0;
}

B. Roller Coaster

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>  
#include <string>  
using namespace std;
 
int main()
{
	int n, k, tot = 0;
	cin >> n >> k;
	for(int i=1;i<=n;i++)
	{
		int tmp;
		cin >> tmp;
		if (tmp >= k)
			tot++;
	}
	cout << tot;
 
	return 0;
}

C. Go to School

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <cstring>
#include <string>
using namespace std;
 
map<int, int>a;
 
int main()
{
	int n, tmp;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> tmp;
		a.insert(pair<int, int>(tmp, i));
	}
 
	map<int, int>::iterator start = a.begin();
	for (; start != a.end(); start++)
		cout << start->second << ' ';
 
	return 0;
}

D. Disjoint Set of Common Divisors

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <cstring>
#include <string>
using namespace std;
 
long long  gcd(long long  x, long long y)
{
	if (y == 0)
		return x;
	if (x < y)
		return gcd(y, x);
	else
		return gcd(y, x%y);
}
 
int main()
{
	long long a, b, ans = 1;
 
	cin >> a >> b;
	long long c = gcd(a, b);
	long long d = c;
 
	for (long long i = 2; i <= sqrt(d); i++)
	{
		if (c%i == 0)
		{
			ans++;
			while (c%i == 0)
				c /= i;
		}
		else
			continue;
	}
 
	if (c != 1)
		ans++;
	cout << ans;
}

E. Get Everything

大意就是有n个盒子，m把钥匙，每把钥匙有一个cost，能开好几个不同的盒子，问打开全部盒子最少的花费。因为n的数量很小，所以正解应该是数位dp，我看有的神犇好像还用的是一阶dp，奈何本人对于dp这玩意儿一直是看得懂，做不出。最后用的是最短路的办法，点就是0~2ⁿ-1，边就是每个顶点按位或key值(就是把每个钥匙能开的盒子转成二进制表示)，最后跑个dijkstra。最先想出这个解法的人真是天才orz。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>
 
#define LL_MAX 0x7fffffffffffffff
 
using namespace std;
 
struct edge {
	int to;
	long long cost;
	edge(int t, long long c) : to(t), cost(c) {}
};
 
//dijkstra
vector<long long> dijkstra(vector<vector<edge>>& g, int start)
{
	vector<long long> res(g.size(), LL_MAX);
	res[start] = 0;
	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
		greater<pair<long long, long long>>> p;
 
	p.push({ 0, start });
 
	while (!p.empty())
	{
		long long dist = p.top().first, now = p.top().second;
		p.pop();
		if (res[now] < dist)
			continue;
		for (int i = 0; i < (int)g[now].size(); i++)
		{
			edge e = g[now][i];
			if (res[e.to] > res[now] + e.cost)
			{
				res[e.to] = res[now] + e.cost;
				p.push(make_pair(res[e.to], e.to));
			}
		}
	}
	return res;
}
 
int main()
{
	int n, m;
	cin >> n >> m;
 
	vector<int> cost(m);
	vector<int> key(m, 0);
 
	for (int i = 0; i < m; i++)
	{
		int num;
		cin >> cost[i] >> num;
		for (int j = 0; j < num; j++)
		{
			int tmp;
			cin >> tmp;
			key[i] += 1 << (tmp - 1);
		}
	}
 
	vector<vector<edge>> g((1 << n));
 
	for (int i = 0; i < (1 << n); i++)
		for (int j = 0; j < m; j++)
			g[i].push_back(edge(i | key[j], cost[j]));
 
	vector<long long> dis = dijkstra(g, 0);
 
	if (dis[(1 << n) - 1] == LL_MAX)
		cout << -1;
	else
		cout << dis[(1 << n) - 1];
 
	return 0;
}

F. Pure

WA了好几发，重新读了好几遍题加上看了别人的讨论才知道不只是随便找出一个环就好了，还要求是simple cycle(即不能环中套环)，为了偷懒直接暴力求最小环了。数据很弱，随便过。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>
 
#define M 1001
 
using namespace std;
 
int n, m, minl = 0x7fffffff;
bool mapp[M][M];
bool visit[M];
int ans[M];
int real[M];
 
void dfs(int x, int num)
{
	if (num > minl)
		return;
 
	if (visit[x] == true)
	{
		int p;
		for (int i = 1; i <= num; i++)
			if (ans[i] == x)
			{
				p = i;
				break;
			}
		minl = num - p;
		int tmp = 1;
		for (int i = p + 1; i <= num; i++)
			real[i - p] = ans[i];
 
		return;
	}
 
	visit[x] = true;
 
	for (int i = 1; i <= n; i++)
	{
		if (mapp[x][i] == true)
		{
			num++;
			ans[num] = i;
 
			dfs(i, num);
			num--;
		}
	}
 
	visit[x] = false;
	return;
}
 
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		mapp[x][y] = true;
	}
 
	for (int i = 1; i <= n; i++)
	{
		ans[1] = i;
		dfs(i, 1);
 
		memset(visit, 0, sizeof(visit));
	}
 
	if (minl == 0x7fffffff)
		cout << -1 << endl;
	else
	{
		cout << minl << endl;
		for (int i = 1; i <= minl; i++)
			cout << real[i] << endl;
	}
 
	return 0;
}