牛客月赛108

目录

        A. 小S按按钮

        C. 小T数星星

        E. 小M种树 

A. 小S按按钮

        （1） 二分答案的右边界一定要开大。若 x 等于 0，最多 2 * y 次

        （2）根据是要最小还是最多，调整 if ( check ( mid ) ) 里的是 l 还是 r

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5, INF = 1e18;
int t, n, x, y, ans;

bool check(int mid)
{
	if (mid % 2 == 0)
		ans = mid / 2 * (1 + x);
	else
		ans = (mid - 1) / 2 * (1 + x) + 1;
	return ans >= y;
}

signed main()
{
	cin >> t;
	while (t --)
	{
		cin >> x >> y;
		int l = -1, r = y * 2 + 1, mid;
		while (l + 1 < r)
		{
			mid = l + (r - l) / 2;
			if (check(mid))
				r = mid;
			else
				l = mid;
		}
		cout << r << '\n';
	}
	return 0;
}

C. 小T数星星

    （1）遍历 map 的时候用 it -> second 表示键对应的值

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, INF = 1e18;

int T, n, cnt, ans, a[N];
string s;
map<int, int> mp;

signed main()
{
	cin >> T;
	while (T --)
	{
		cin >> n;
		mp.clear();
		for (int i = 1; i <= n; i ++)
		{
			cin >> a[i];
			mp[a[i]] ++;
		}
		ans = mp.size();
		map<int, int> :: iterator it;
		for (it = mp.begin(); it != mp.end(); it ++)
		{
			if (it -> second % 2 == 0)
				ans ++;
		}
		cout << ans << '\n';
	}
	return 0;
}

E. 小M种树 

        （1）一个结点颜色的改变，会影响根结点到该结点链上所有的结点的平衡值

        （2）第一次 dfs 遍历树，存下每个结点为根结点的子树内红蓝色总数

        （3）第二次 dfs，存下从根结点到当前结点有多少结点符合：当前结点若为红，变成蓝，平衡值会减少，会增加。减少的数量减去增加的数量大于零则当前结点变色符合条件，设为 1。若为蓝亦然。相当于求了一个树上的前缀和

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5, INF = 1e18;

int T, n, cnt, ans[N], sr[N], sb[N];
string s;
vector<int> G[N];

void dfs1(int x, int fa)
{
	sr[x] = 0, sb[x] = 0;
	sr[x] = (s[x] == 'R');
	sb[x] = (s[x] == 'B');
	for (int i = 0; i < G[x].size(); i ++)
	{
		int v = G[x][i];
		if (v != fa)
		{
			dfs1(v, x);
			sr[x] += sr[v], sb[x] += sb[v];
		}
	}
}

void dfs2(int x, int fa, int a, int b, int c, int d)
{
	if (sr[x] - sb[x] >= 2) a ++;
	if (sr[x] - sb[x] <= 0) b ++;
	if (sb[x] - sr[x] >= 2) c ++;
	if (sb[x] - sr[x] <= 0) d ++;
	if (s[x] == 'R')
	{
		if (a - b > 0)
			ans[x] = 1;
		else
			ans[x] = 0;
	}
	if (s[x] == 'B')
	{
		if (c - d > 0)
			ans[x] = 1;
		else
			ans[x] = 0;
	}
	for (int i = 0; i < G[x].size(); i ++)
	{
		int v = G[x][i];
		if (v != fa)
			dfs2(v, x, a, b, c, d);
	}
}

signed main()
{
	cin >> T;
	while (T --)
	{
		cin >> n >> s;
		s = ' ' + s;
		for (int i = 1; i <= n; i ++)
			G[i].clear();
		for (int i = 1; i < n; i ++)
		{
			int u, v;
			cin >> u >> v;
			G[u].push_back(v), G[v].push_back(u);
		}
		dfs1(1, 1);
		dfs2(1, 1, 0, 0, 0, 0);
		for (int i = 1; i <= n; i ++)
			cout << ans[i];
		cout << '\n';
	}
	return 0;
}