ABC333 A-F

Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333） - AtCoder

A - Three Threes

题意：

打印n个n

题解：

void solve()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		printf("%d", n);
}

B - Pentagon

题意：

给出如图所示的正五边形

问线段s1s2的长度是否与t1t2相等

题解：

线段长度一共就两种，特判一下长度属于哪种就行了

void solve()
{
	char a = getchar(), b = getchar();
	getchar();
	char c = getchar(), d = getchar();
	int d1, d2;
	if (abs((int)a - b) == 1 || abs((int)a - b) == 4)
		d1 = 1;
	else
		d1 = 2;
	if (abs((int)c - d) == 1 || abs((int)c - d) == 4)
		d2 = 1;
	else
		d2 = 2;
	if (d1 == d2)printf("Yes\n");
	else printf("No\n");
}

C - Repunit Trio

题意：

给出一堆由1构成的数 1,11,111,1111,... 问由恰好以上的三个数相加得出的所有数的集合中第k大的数的大小

题解：

k范围只给打333，看样例3也知道数最大不超过long long范围，直接暴力求出所有long long范围内的所有数然后数到第k个数输出即可

set<LL>st;
void solve()
{
	int n;
	scanf("%d", &n);
	for (LL i = 1; i <= 1e18; i = i * 10 + 1)
	{
		for (LL j = i; j <= 1e18; j = j * 10 + 1)
		{
			for (LL k = j; k <= 1e18; k = k * 10 + 1)
				st.insert(i + j + k);
		}
	}
	for (auto i : st)
	{
		if (!--n)
		{
			printf("%lld\n", i);
			return;
		}
	}
}

D - Erase Leaves

题意：

给出一颗n节点的树，你每次可以从树中删除一个叶节点及与改叶节点相连的边，问最少进行多少次操作能够删除节点1

题解：

建一个以1为根的树，要删除1节点需要先把节点1的所有子树删到只有一颗（这样1就是叶节点了），那我们只需要保留最大的一颗子树不删然后把别的都删了即可，计算子树大小用树形dp

vector<int>e[N];
int s[N];
void dfs(int u, int f)
{
	s[u] = 1;
	for (auto v : e[u])if (v != f)
	{
		dfs(v, u);
		s[u] += s[v];
	}
}
void solve()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i < n; ++i)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0);
	int ans = 0;
	for (auto v : e[1])
		ans = max(ans, s[v]);
	printf("%d\n", n - ans);
}

E - Takahashi Quest

题意：

进行一场冒险，你会依次遇到以下两种的事件：1、遇到一瓶类型为x的药水，你可以选择拿或不拿。2、遇到一个类型为x的敌人，你可以使用一瓶类型为x的药水击败它，否则你将会失败。

你需要制定一个拾取药水的方案使得你所需要的背包容量（最多携带药水的数量）最小，并输出你的拾取方案：当遇到药水是拾取则输出1，不拾取输出0

题解：

贪心。要使得同时携带的药水最少，就要尽量让每瓶药水在捡到之后就尽快用掉。显然你无法选择用掉药水的时机，你只能选择拾取药水的时间，使得每瓶药的拾取时间更晚即可。

具体做法是开n个栈将你遇到每种药的时间都存入对应的栈中，然后从后往前枚举所有的怪物（若从前往后枚举怪物要存set），然后时间在遇到怪物时间最前最近的那瓶药水，然后选择拾取，若在这之前已经没有对应种类的药水，则你失败了。计算最小背包容量用差分数组然后前缀和一下就行了。

int f[N], op[N], x[N], d[N];
vector<int>v[N];
void solve()
{
	int n, ans = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d%d", &op[i], &x[i]);
		if (op[i] == 1)
			v[x[i]].push_back(i);
	}
	for (int i = n; i >= 1; --i)
	{
		if (op[i] == 2)
		{
			while (v[x[i]].size() && v[x[i]].back() > i)
				v[x[i]].pop_back();
			if (v[x[i]].empty())
			{
				printf("-1\n");
				return;
			}
			++d[v[x[i]].back()], --d[i];
			f[v[x[i]].back()] = 1;
			v[x[i]].pop_back();
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		d[i] += d[i - 1];
		ans = max(ans, d[i]);
	}
	printf("%d\n", ans);
	for (int i = 1; i <= n; ++i)
	{
		if (op[i] == 1)
			printf("%d ", f[i]);
	}
}

F - Bomb Game 2

题意：

有个n人的双端队列，你需要进行以下操作直至队列中只剩一个人：1、1/2的概率将第一个人踢出队列，2、1/2的概率将第一个人丢到队列的末尾。问每个人存活到最后的概率(MOD998244353)

题解：

dp[i][j]表示一共有i个人的情况下第j个人存活的概率。

若 j != 1，当前局面为场上存活i人，对于第j个人来说第一个人被踢出队列的，则他变成了存活i - 1人中的第j - 1人，第一个人被丢到队尾，则他变成了存活i人中的第j - 1人，故dp[i][j]的转移为dp[i][j] = 1/2 * dp[i - 1][j - 1] + 1/2 * dp[i][j - 1]

先不考虑dp[i][1]的情况下，我们可以递推出所有的dp[i][j]。

现在我们的问题是如何求出dp[i][1]，我的做法是设dp[i][1] = x，然后求出所有的dp[i][j]之后解方程求出x即可，然后我们手玩一下这个柿子就得到了以下代码（）

LL dp[N][N];
LL qpow(LL x, LL y)
{
	x %= MOD;
	if (y == 0)return 1;
	if (y & 1)
		return qpow(x * x, y >> 1) * x % MOD;
	return qpow(x * x, y >> 1) % MOD;
}
LL inv(LL x)
{
	return qpow(x, MOD - 2);
}
void solve()
{
	LL n, inv2 = inv(2);
	scanf("%lld", &n);
	dp[1][1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		LL sum = 0, t = 0;
		for (int j = 1; j < i; ++j)
		{
			t = inv2 * (t + dp[i - 1][j]) % MOD;
			sum = (sum + t) % MOD;
		}
		dp[i][1] = (1 - sum + MOD) * inv(2 - qpow(inv2, i - 1) + MOD) % MOD;
		for (int j = 2; j <= i; ++j)
			dp[i][j] = inv2 * (dp[i - 1][j - 1] + dp[i][j - 1]) % MOD;
	}
	for (int i = 1; i <= n; ++i)
		printf("%lld ", dp[n][i]);
}