AtCoder Beginner Contest 292（A~F）

A - CAPS LOCK

题意：小写变大写

翻译：水

#include<bits/stdc++.h>
using namespace std;
int main()
{
	string str;cin >> str;
	int end = str.size();
	for(int i = 0;i < end;i++)
		cout << (char)(str[i] - 32);
}

B - Yellow and Red Card

题意：红牌下场，两张黄牌也下场，每次询问该球员是否在场

思路：水

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 101;
pair<int,int> pa[MAXN];
int main()
{
	int n,q;cin >> n >> q;
	for(int i = 1;i <= q;i++){
		int op,x;cin >> op >> x;
		if(op == 1){
			pa[x].first++;
		}else if(op == 2){
			pa[x].second++;
		}else{
			if(pa[x].first <= 1 && pa[x].second == 0)
				cout << "No" << endl;
			else
				cout << "Yes" << endl;
		}
	}
}

C - Four Variables

题意：找$AB+CD=N$的数量，$2\le N\le 2\ast 10^5$

思路：预处理$2\ast 10^5$内所有数分解为AB形式的数量，将这个N分成AB和CD，枚举AB的值，用N-AB得出CD的值，用两个可能性相乘，优化就枚举一半。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2e5 + 10;
ll dp[MAXN];
int main()
{
	int n;cin >> n;
	int ma = 2e5;
	int sq = sqrt(ma);
	for(int i = 1;i <= sq;i++){
		for(int j = i;j*i <= ma;j++)
			if(i != j)
				dp[i*j]+=2;
			else
				dp[i*j]++;
	}
	ll ans = 0;
	for(int i = 1;i <= n/2;i++){
		int j = n - i;
		if(i == j)
			ans += dp[i]*dp[j];
		else
			ans += 2*dp[i]*dp[j];
	}
	cout << ans << endl;
}

D - Unicyclic Components

题意：所有连通块的点的数量和边的数量相同

思路：并查集找连通块，枚举所有点和边，最后判断数量是否完全相同

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int nump[MAXN],numd[MAXN];
pair<int,int> ed[MAXN];
int a[MAXN];
int find(int x){
	if(a[x] == x) return x;
	return a[x] = find(a[x]);
}
void pre(int n){
	for(int i = 1;i <= n;i++)
		a[i] = i;
}

int main()
{
	int n,m;cin >> n >> m;
	pre(n);
	for(int i = 1;i <= m;i++){
		int u,v;cin >> u >> v;
		a[find(u)] = find(v);
		ed[i] = {u,v};
	}
	for(int i = 1;i <= n;i++)
		nump[find(i)]++;
	for(int i = 1;i <= m;i++)
		nump[find(ed[i].first)]--;
	bool f = 1;
	for(int i = 1;i <= n;i++)
		if(nump[i] != 0)
			f = 0;
	if(f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

E - Transitivity

题意：如果A连B，B连C，那么必须要有一条边使得A连C，问至少多连接几条边

思路：对于所有A能到达的点来说，A必须直接连接所有的点，那么用DFS找所有能到达的点的数量即可知道对于这个点来说必须要加入的边，枚举所有点再减去所有原有的边即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2e3 + 10;
vector<int> ed[MAXN];
ll ans = 0;
bool use[MAXN];
int num = 0;
void dfs(int u){
	for(auto v:ed[u]){
		if(use[v])
			continue;
		num++;
		use[v] = 1;
		dfs(v);
	}
}
int main()
{
	int n,m;cin >> n >> m;
	for(int i = 1;i <= m;i++){
		int u,v;cin >> u >> v;
		ed[u].push_back(v);
	}
	ans = -m;
	for(int i = 1;i <= n;i++){
		num = 0;
		for(int j = 1;j <= n;j++)
			use[j] = 0;
		use[i] = 1;	
		dfs(i);
		ans += num;	
	}
	cout << ans;
}

F - Regular Triangle Inside a Rectangle

题意：往一个长方形中塞一个最大的正三角形

思路：两种情况，一种为直接贴着最大边放，让顶点接触另一条最大边，另一种情况为无法贴着放使得接触到另一条最大边，这时我们就要以一个顶点为轴，旋转正三角形直到它的另外两个顶点都接触到边，用二分即可，注意π的精确度

#include<bits/stdc++.h>
using namespace std;
#define pi 3.1415926535897932
int main()
{
	int a,b;cin >> a >> b;
	double ma = max(a,b),mi = min(a,b);
	double sq_3 = sqrt(3);
	if(ma > (mi/sq_3)*2)
		printf("%.12lf",(mi/sq_3)*2);
	else
	{
		double l = 0,r = pi/12;
		while(ma/cos(r) - ma/cos(l) > 1e-11){
			double mid = (l+r) / 2;
			double other = pi/6 - mid;
			if(mi*cos(mid) > ma*cos(other))
				l = mid;
			else
				r = mid;
		}
		printf("%.12lf",ma/cos((l+r)/2));
	}
}