hdu 多校赛 第七场

slove  0/11

rank  

补题   2/11

---------------------------------------------------

6655 Just Repeat

博弈，两个人每人一些牌，你不能出别人出过的数字，问谁先不能出牌

两人共有的牌，按照这个牌的两个人的总个数排序，从大到小贪心取就可以。

#include <bits/stdc++.h>
#include <unordered_map>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
unsigned long long k1, k2;
unsigned long long rng() 
{
	unsigned long long k3 = k1, k4 = k2;
	k1 = k4;
	k3 ^= k3 << 23;
	k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
	return k2 + k4;
}
ll a[500005], b[500005];
ll t[1000005];
struct node
{
	int first;
	int second;
}c[1000005];
int main()
{
	//freopen("1010.in", "r", stdin);
	//freopen("ans.txt", "w", stdout);
	int T;
	sc("%d", &T);
	while (T--)
	{
		int n, m, q;
		sc("%d%d%d", &n, &m, &q);
		int cnt = 0;
		if (q == 1)
		{
			for (int i = 0; i < n; ++i)
			{
				sc("%lld", &a[i]);
				t[cnt++] = a[i];
			}
			for (int i = 0; i < m; ++i)
			{
				sc("%lld", &b[i]);
				t[cnt++] = b[i];
			}
		}
		else
		{
			ll mod;
			sc("%lld%lld%lld", &k1, &k2, &mod);
			for (int i = 0; i < n; ++i)
			{
				a[i] = rng() % mod;
				t[cnt++] = a[i];
			}
			sc("%lld%lld%lld", &k1, &k2, &mod);
			for (int i = 0; i < m; ++i)
			{
				b[i] = rng() % mod;
				t[cnt++] = b[i];
			}
		}
		sort(t, t + cnt);
		int qq = unique(t, t + cnt) - t;
		for (int i = 0; i < qq; i++)
			c[i].first = c[i].second = 0;
		for (int i = 0; i < n; i++)
		{
			a[i] = lower_bound(t, t + qq, a[i]) - t;
			c[a[i]].first++;
		}
		for (int i = 0; i < m; i++)
		{
			b[i] = lower_bound(t, t + qq, b[i]) - t;
			c[b[i]].second++;
		}
		sort(c, c + qq, [](node q, node w) {
			return q.first + q.second > w.first + w.second;
			});
		int op = 1;
		int numa = 0, numb = 0;
		for (int i = 0; i < qq; i++)
		{
			if (c[i].first && c[i].second)
			{
				if (op & 1)
					numa += c[i].first;
				else
					numb += c[i].second;
				op ^= 1;
			}
			else if (c[i].first)
			{
				numa += c[i].first;
			}
			else if (c[i].second)
			{
				numb += c[i].second;
			}
		}
		puts(numa > numb ? "Cuber QQ" : "Quber CC");
	}
}

6656 Kejin Player

假设当前是  级，你需要支付  的代价，有  的概率变成  级，其他时候会变成  级（保证 ），多组询问，问从  级变成  级期望的花费。

1、首先确定，假设到了 i 级，到 i+1 级的代价与之前如何到 i 级是无关的。

2、考虑如何从第 i 级升到 i+1 级，假设dp[i] 为从1 级升到 i 级的期望花费，那么dp[i+1]等于失败1次，2次， 次的概率*花费的和

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const ll mod = 1e9 + 7;
ll dp[500000];
ll r, s, x, a;
ll power(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		int n, q;
		sc("%d%d", &n, &q);
		dp[1] = 0;
		for (int i = 1; i <= n; i++)
		{
			sc("%lld%lld%lld%lld", &r, &s, &x, &a);
			dp[i + 1] = dp[i] + a * s % mod * power(r, mod - 2) % mod + (s - r) * power(r, mod - 2) % mod * (dp[i] - dp[x] + mod) % mod;
			dp[i + 1] %= mod;
		}
		while (q--)
		{
			int a, b;
			sc("%d%d", &a, &b);
			pr("%lld\n", (dp[b] - dp[a] + mod) % mod);
		}
	}
}