TKKC round＃3

1. subject :http://xujcoj.org/Home/Problems/status/pro_id/1590

reflection :1. Solving equations -> Bisection approach

         2. Pay attention to the judgment of accuracy printf(".1lf",l) Keep one decimal place f:float lf:double .n Retain n Decimal place  

         3. Encountered a precision problem , Change unity to double, Except to the power

         4. It's about mathematics , Equation simplification is generally used

AC Code :

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long  ll;
int a, c;
double _exp = 1e-2;
double qp(double x, int y)
{
	double ans = 1;
	while (y)
	{
		if (y & 1) { ans = ans * x; }
		y >>= 1;
		x = x * x;
	}
	return ans;
}
bool check(double b)
{
	double res = 1 - (1.0 / (a + 1));
	double q = 1.0 / (b + 1);
	res += (q  - qp(q, a+1))/ (1 - q);
	return res >= c;
}
int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		cin >> a >> c;
		double l = 0, r = 1e9;
		while (r - l > _exp)// Within a certain error range 
		{
			double mid = (r + l) / 2;
			check(mid) ? l = mid : r = mid;// If you are big, look to the right 
		}
		printf("%.1fl\n", l);// Keep one significant digit 

	}
}

2. subject :http://xujcoj.org/Home/Problems/status/pro_id/1591/

reflection :

1. And look up the correct way of writing :

ll get(ll x)
{
return x==f[x]?x:f[x]=get(f[x]) 
}
// If our ancestors are not equal to ourselves   Just keep searching 
void merge(ll x,ll y)
{
f[get(y)]=get(x);
}
//x Ancestors are equal to y Our ancestors, our ancestors   To build a relationship 

2.vector When opening an array Set as a global variable

3. Pay attention to determine whether there are duplicate numbers

4.stack flow reason :1. Array too large 2. Dynamic allocation instead , Pile up 3. Recursion into dead loop

AC Code :

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long  ll;
const int N = 1e5;
ll f[N + 1];
vector<ll>v1[N + 1];
bool cmp(char x, char y)
{
	return x < y;
}
ll get(ll x)
{
	return x == f[x] ? x : f[x] = get(f[x]);
}
int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		for (int i = 0; i <= N; i++)
		{
			v1[i].clear();
		}
		for (int i = 0; i <= N; i++)
		{
			f[i] = i;
		}
		queue<int>ans;
		set<ll>s;
		vector<ll>v;
		int n, m;
		cin >> n >> m;
		for (int i = 1; i <= m; i++)
		{
			ll a, b;
			scanf("%lld%lld", &a, &b);
			f[get(b)] = get(a);
		}
		for (int j = 1; j <= n; j++)
		{
			bool flag = false;
			ll x;
			scanf("%lld", &x);
			int fx = get(x);
			if (s.count(fx) == 0)
			{
				ans.push(fx);
				s.insert(fx);
			}
			v1[fx].push_back(x);
		}
		bool first = 1;
		while (!ans.empty())
		{
			int t = ans.front();
			ans.pop();
			for (int i = 0; i < v1[t].size(); i++)
			{
				if (first)
				{
					printf("%lld", v1[t][i]);
					first = 0;
				}
				else
				{
					printf(" %lld", v1[t][i]);
				}
			}
		}
		puts("");
	}
}