2019 年百度之星·程序设计大赛 - 复赛 wu-kan

最后十六秒绝杀过了 1002,捡了件衣服~

Diversity

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 9;
vector<vector<int>> g;
int t, n, a[N][2];
ll f[N][2];
void dp(int u, int fa)
{
	f[u][0] = f[u][1] = 0;
	for (auto to : g[u])
		if (to != fa)
		{
			dp(to, u);
			f[u][0] += max(abs(a[u][0] - a[to][0]) + f[to][0], abs(a[u][0] - a[to][1]) + f[to][1]);
			f[u][1] += max(abs(a[u][1] - a[to][0]) + f[to][0], abs(a[u][1] - a[to][1]) + f[to][1]);
		}
}
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%d", &n);
		g.assign(n, vector<int>());
		for (int i = 1, u, v; i < n; ++i)
		{
			scanf("%d%d", &u, &v);
			--u, --v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		for (int i = 0; i < n; ++i)
			scanf("%d%d", &a[i][0], &a[i][1]);
		dp(0, -1);
		printf("%lld\n", max(f[0][0], f[0][1]));
	}
}

Transformation

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sgn(ll a)
{
	return a < 0 ? -1 : a > 0 ? 1 : 0;
}
int main()
{
	ll t, a, b, c, d;
	for (scanf("%lld", &t); t--;)
	{
		scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
		if (a == c && b == d)
		{
			printf("Yes\n\n");
			continue;
		}
		if (a == b || c == d)
		{
			printf("No\n");
			continue;
		}
		if (a < b && c > d || a > b && c < d)
		{
			printf("No\n");
			continue;
		}
		ll x = abs(a - b), y = abs(c - d), o = 0;
		for (;; x <<= 1, ++o)
		{
			if (x > y)
				o = -1;
			if (x >= y)
				break;
		}
		if (o < 0)
		{
			printf("No\n");
			continue;
		}
		ll u = d - b, v = b - a;
		if (u % v)
		{
			printf("No\n");
			continue;
		}
		u /= v;
		string s;
		for (int i = 0; i < o; ++i)
			s += u % 2 ? 'A' : 'B', u /= 2;
		for (int i = 0; i < s.size(); ++i)
		{
			if (s[i] == 'A')
				b = 2 * b - a;
			else
				a = 2 * a - b;
		}
		if (a == c && b == d)
		{
			printf("Yes\n");
			cout << s << '\n';
		}
		else
			puts("No");
	}
}

Quasi Binary Search Tree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Mod
{
	const ll M, SM;
	Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
	ll qadd(ll &a, ll b) const { return a += b, a < M ? a : a - M; } //假如a和b都已经在同余系内,就不必取模了,取模运算耗时很高
	ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); }	//考虑a和b不在同余系内甚至为负数的情况
	ll mul(ll a, ll b) const { return add(a * b, M); }
	//ll mul(ll a, ll b) const { return add(a * b, -M * ll((long double)a / M * b)); }
	ll pow(ll a, ll b) const
	{
		ll r = 1;
		for (a = add(a, M); b; b >>= 1, a = mul(a, a))
			if (b & 1)
				r = mul(r, a);
		return r;
	}
	ll inv(ll a) const { return pow(a, M - 2); } //要求M为素数
	/*
	ll inv(ll a) const                             //模m下a的乘法逆元,不存在返回-1(m为素数时a不为0必有逆元)
	{
		ll x, y, d = gcd(a, M, x, y);
		return d == 1 ? add(x, M) : -1; //return pow(a, phi(M) - 1);
	}
	vector<ll> sol(ll a, ll b) const //解同余方程,返回ax=b(mod M)循环节内所有解
	{
		vector<ll> ans;
		ll x, y, d = gcd(a, M, x, y);
		if (b % d)
			return ans;
		ans.push_back(mul((b / d) % (M / d), x));
		for (ll i = 1; i < d; ++i)
			ans.push_back(add(ans.back(), M / d));
		return ans;
	}
	*/
	ll log(ll a, ll b) const
	{
		unordered_map<ll, ll> x;
		for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
			if (!x.count(e))
				x[e] = i;
		for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
			if (x.count(b))
				return i * SM + x[b];
		return -1;
	}
} M(1e9 + 7);
const int N = 1e5 + 9;
int t, n, l[N], r[N], fa[N], siz[N], mi[N], ans[N];
void dfs(int u)
{
	siz[u] = 1;
	mi[u] = u;
	if (l[u])
		dfs(l[u]), siz[u] += siz[l[u]], mi[u] = min(mi[u], mi[l[u]]);
	if (r[u])
		dfs(r[u]), siz[u] += siz[r[u]], mi[u] = min(mi[u], mi[r[u]]);
}
void dp(int u, int &cnt)
{
	if (!l[u])
	{
		if (!r[u])
		{
			ans[u] = ++cnt;
			return;
		}
		if (mi[r[u]] < u)
			dp(r[u], cnt), ans[u] = ++cnt;
		else
			ans[u] = ++cnt, dp(r[u], cnt);
		return;
	}
	if (!r[u])
	{
		if (mi[l[u]] < u)
			dp(l[u], cnt), ans[u] = ++cnt;
		else
			ans[u] = ++cnt, dp(l[u], cnt);
		return;
	}
	if (u < mi[l[u]] && u < mi[r[u]] && siz[l[u]] != siz[r[u]])
	{
		vector<int> v{siz[l[u]], siz[r[u]]};
		sort(v.begin(), v.end());
		for (int i = 0; i < 1; ++i)
		{
			if (v[i] == siz[l[u]])
				dp(l[u], cnt);
			else if (v[i] == siz[r[u]])
				dp(r[u], cnt);
		}
		ans[u] = ++cnt;
		for (int i = 1; i < 2; ++i)
		{
			if (v[i] == siz[l[u]])
				dp(l[u], cnt);
			else if (v[i] == siz[r[u]])
				dp(r[u], cnt);
		}
		return;
	}
	vector<int> v{mi[l[u]], mi[r[u]]};
	sort(v.begin(), v.end());
	for (int i = 0; i < 1; ++i)
	{
		if (v[i] == mi[l[u]])
			dp(l[u], cnt);
		else if (v[i] == mi[r[u]])
			dp(r[u], cnt);
	}
	ans[u] = ++cnt;
	for (int i = 1; i < 2; ++i)
	{
		if (v[i] == mi[l[u]])
			dp(l[u], cnt);
		else if (v[i] == mi[r[u]])
			dp(r[u], cnt);
	}
}
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%d", &n);
		fill(fa + 1, fa + n + 1, 0);
		fill(l + 1, l + n + 1, 0);
		fill(r + 1, r + n + 1, 0);
		fill(ans + 1, ans + n + 1, 0);
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d%d", &l[i], &r[i]);
			fa[l[i]] = fa[r[i]] = i;
		}
		for (int i = 1, cnt = 0; i <= n; ++i)
			if (!fa[i])
			{
				dfs(i);
				dp(i, cnt);
				break;
			}
		ll an = 0;
		for (int i = 1; i <= n; ++i)
			an = M.add(an, M.mul(ans[i] ^ i, M.pow(233, i)));
		printf("%lld\n", an);
	}
}