ABC333(A-F)
A - Three Threes¶
题目大意
给你一个整数 \(N(1 \le N \le 9)\)，将 \(N\) 重复打印 \(N\) 次。
参考代码
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
cout << n;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int i = 0; i < n; i++)
System.out.print(n);
in.close();
}
}
B - Pentagon¶
题目大意
解题思路
根据对称性可以对线的端点进行同时移动，将两条线的一端都移动到点 \(A\)，然后判断另一端是否相同或者对称即可。
参考代码
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
char s[5];
int line[2][2];
for (int i = 0; i < 2; i++)
{
cin >> s;
line[i][0] = s[0] - 'A';
line[i][1] = s[1] - 'A';
while (line[i][0])
{
line[i][0] = (line[i][0] + 1) % 5;
line[i][1] = (line[i][1] + 1) % 5;
}
}
if (line[0][1] == line[1][1] || line[0][1] + line[1][1] == 5)
puts("Yes");
else
puts("No");
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[][] line = new int[2][2];
for (int i = 0; i < 2; i++) {
String s = in.next();
line[i][0] = s.charAt(0) - 'A';
line[i][1] = s.charAt(1) - 'A';
while (line[i][0] > 0) {
line[i][0] = (line[i][0] + 1) % 5;
line[i][1] = (line[i][1] + 1) % 5;
}
}
if (line[0][1] == line[1][1] || line[0][1] + line[1][1] == 5)
System.out.println("Yes");
else
System.out.println("No");
in.close();
}
}
C - Repunit Trio¶
题目大意
我们称 \(1, 11, 111, 1111, \cdots\) 为 repunit数列，选择三个 repunit 数列的数（允许重复选择），将三个数字相加得到的数称为 3-repunit 数。给你一个整数 \(N(1 \le N \le 333)\)，问，第 \(N\) 小的 3-repunit 数是多少？
解题思路
样例中给出了 \(N = 333\) 的时候答案是 \(112222222233\)，这样在 dfs 搜索的时候，每一个数字最大不会超过 \(111111111111\) （\(12\) 个 \(1\)），枚举量不会超过 \(12 ^3\)。进一步的，给出一种线性时间复杂度的枚举方法，在 dfs 枚举的时候，可以对下一层的数字的上界进行限制，例如：
1 1 1 3
11 1 1 13
11 11 1 23
11 11 11 33
111 1 1 113
111 11 1 123
111 11 11 133
111 111 11 233
111 111 111 333
1111 1 1 1113
按照这种顺序进行枚举，得到的数字一定也是按顺序的。设三个数字为 \(x,y,z\)，当 \(x\) 确定后，其 \(x+y+z\) 的上界为 \(3x\)，当 \(x\) 和 \(y\) 确定后，有 \(x+y+z\) 的上界为 \(x + 2y\)。而 \(x\) 的扩大是从 \(x\) 变成 \(10x+1\)，显然有 \(10x+1 > 3x\)，因此，应该首先让 \(x\) 变大，并作为上界对后面的数字进行限制。
这种方式枚举的时间复杂度为 \(O(n)\)，并且这个规律还可以进一步扩展，即跳过枚举的过程，直接枚举出第 \(N\) 个数字所需要的 \(x, y, z\)。
参考代码
#include <iostream>
using namespace std;
typedef long long LL;
int cnt, n;
void dfs(int cur, LL sum, LL last)
{
if(cur == 3)
{
if(++cnt == n)
cout << sum << endl;
return;
}
for(LL x = 1; x <= last && cnt < n; x = 10 * x + 1)
dfs(cur+1, sum+x, x);
}
int main()
{
cin >> n;
dfs(0, 0, 111111111111);
return 0;
}
import java.util.Scanner;
public class Main {
private static int cnt, n;
private static void dfs(int cur, long sum, long last) {
if (cur == 3) {
if (++cnt == n)
System.out.println(sum);
return;
}
for (long x = 1; x <= last && cnt < n; x = 10 * x + 1)
dfs(cur + 1, sum + x, x);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
dfs(0, 0, 111111111111l);
in.close();
}
}
D - Erase Leaves¶
题目大意
给你一棵 \(N\) 个节点的树，你可以执行一种操作：删除一个树中度数为 \(1\) 的节点以及这个点的连边。问：最少执行多少次操作才能将点 \(1\) 删除？
解题思路
以点 \(1\) 为根节点 dfs 一次，统计每个点的子树大小。最后枚举点 \(1\) 所有的孩子，留下最大的那颗子树，其余的就是需要删除的点。
参考代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 3E5 + 10;
const int maxm = 2 * maxn;
int n;
int head[maxn], edge[maxm], ne[maxm], idx = 1;
void add(int u, int v)
{
edge[idx] = v;
ne[idx] = head[u];
head[u] = idx++;
}
int son[maxn];
void dfs(int u, int f)
{
son[u] = 1;
for(int i = head[u]; i; i = ne[i])
{
int v = edge[i];
if(v == f)
continue;
dfs(v, u);
son[u] += son[v];
}
}
int main()
{
cin >> n;
for(int i = 1; i < n; i++)
{
int u, v;
scanf("%d %d", &u, &v);
add(u, v);
add(v, u);
}
dfs(1, 0);
vector<int> d;
for(int i = head[1]; i; i = ne[i])
{
int v = edge[i];
d.push_back(son[v]);
}
sort(d.begin(), d.end());
cout << son[1] - d.back();
return 0;
}
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
private static int[] head, edge, ne;
private static int idx = 1;
private static int[] son;
private static void graph_init(int n, int m) {
head = new int[n];
edge = new int[m];
ne = new int[m];
}
private static void add(int u, int v) {
edge[idx] = v;
ne[idx] = head[u];
head[u] = idx++;
}
private static void dfs(int u, int f) {
son[u] = 1;
for (int i = head[u]; i > 0; i = ne[i]) {
int v = edge[i];
if (v == f)
continue;
dfs(v, u);
son[u] += son[v];
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
graph_init(n + 1, 2 * n);
son = new int[n + 1];
for (int i = 1; i < n; i++) {
int u, v;
u = in.nextInt();
v = in.nextInt();
add(u, v);
add(v, u);
}
dfs(1, 0);
ArrayList<Integer> d = new ArrayList<>();
for (int i = head[1]; i > 0; i = ne[i]) {
int v = edge[i];
d.add(son[v]);
}
d.sort(null);
System.out.println(son[1] - d.get(d.size() - 1));
in.close();
}
}
E - Takahashi Quest¶
题目大意
你正在进行一场冒险，在这个冒险中有 \(N\) 个事件，事件有两种，1 x 表示你遇到了一瓶类型为 \(x\) 魔法药水，你可以选择拾取这个药水，这会占用你背包的 \(1\) 单位体积。2 x 表示你遇到了一直怪物，需要使用一瓶类型为 \(x\) 魔法药水才能战胜它。一瓶魔法药水瓶只能用一次，用过之后可以丢弃，不再占用背包的体积。同种类型的魔法药水可以拾取多瓶。问：为了战胜所有的怪物，最少需要多大容量的背包？如果无法战胜所有的怪物，输出 \(-1\)。如果可以战胜所有的怪物，第一行输出最小的背包容量，第二行输出遇到每个药水的时候是否拾取（1 表示拾取，0 表示不拾取）。
解题思路
之前做过一道 Expedition - POJ 2431，本题采用类似的思路。将遇到的药水存储起来（而不是立即捡起），在后面需要的时候再取出来使用。存储药水的时候可以开多个栈，每个栈存储同种类型的数组，需要用药水的时候从栈中弹出，这意味着取出的一定是最靠右的药水，可以证明这样做一定能让背包的容量最小。取出药水之后，在使用它之前都一直占用体积，用差分数组来实现区间加。最后还原出每个时间点的背包容量就是答案。总时间复杂度 \(O(n)\)。
参考代码
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
const int maxn = 2E5 + 10;
int n, b[maxn], t[maxn], x[maxn];
stack<int> st[maxn];
bool take[maxn];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
scanf("%d %d", &t[i], &x[i]);
for (int i = 1; i <= n; i++)
{
if (t[i] == 1)
st[x[i]].push(i);
else
{
if (st[x[i]].empty())
{
puts("-1");
return 0;
}
int p = st[x[i]].top();
st[x[i]].pop();
take[p] = 1;
b[p]++;
b[i]--;
}
}
int M = -1;
for (int i = 1; i <= n; i++)
{
b[i] += b[i - 1];
M = max(M, b[i]);
}
cout << M << endl;
for (int i = 1; i <= n; i++)
if(t[i] == 1)
printf("%d ", (int)take[i]);
return 0;
}
import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] b = new int[n + 1];
int[] t = new int[n + 1];
int[] x = new int[n + 1];
boolean[] take = new boolean[n + 1];
HashMap<Integer, Stack<Integer>> st = new HashMap<>();
for (int i = 1; i <= n; i++) {
t[i] = in.nextInt();
x[i] = in.nextInt();
}
for (int i = 1; i <= n; i++) {
if (t[i] == 1) {
if (!st.containsKey(x[i]))
st.put(x[i], new Stack<>());
st.get(x[i]).add(i);
} else {
if (!st.containsKey(x[i])) {
System.out.println(-1);
return;
}
int p = st.get(x[i]).pop();
if (st.get(x[i]).isEmpty())
st.remove(x[i]);
take[p] = true;
b[p]++;
b[i]--;
}
}
int M = -1;
for (int i = 1; i <= n; i++) {
b[i] += b[i - 1];
M = Math.max(M, b[i]);
}
System.out.println(M);
for (int i = 1; i <= n; i++)
if (t[i] == 1)
System.out.printf("%d ", take[i] ? 1 : 0);
in.close();
}
}
F - Bomb Game 2¶
题目大意
有 \(N(1 \le N \le 3000)\) 个人排成一个队列玩游戏，重复一种操作：队首的人有 \(\frac{1}{2}\) 的概率出局，或者有 \(\frac{1}{2}\) 的概率从队首移动到队尾。剩一个人时游戏结束，最后一个人获胜。求出每个人获胜的数学期望，答案对 \(998244353\) 取模。
解题思路
先看看样例的 \(N = 2\) 是怎么算的，不妨设 A 和 B 留下的概率是 \(x\) 和 \(y\)，考虑第一次操作的结果，如果第一次操作是 A 出局，则 B 获胜，这个事件的概率是 \(\frac{1}{2}\)。如果第一次 A 没有出局，则队伍变成乙在队头，甲在队尾。这是一种类似的情形，只不过位置替换，借助递归的定义，可以列出方程：
接下来考虑用 dp 解决这个问题，定义 \(dp[i][j]\)：\(i\) 个人的游戏中，第 \(j\) 个人能获胜的概率。
只需要考虑第一次操作的结果是否出局，可得：
这个转移式有个问题，算出 \(dp[i][1]\) 需要引用 \(dp[i][i]\)，而算出 \(dp[i][2]\) 需要引用 \(dp[i][1]\)，\(\cdots \cdots\) ，这是一种循环引用的关系，不能直接递推。
仿照解方程的方法，设 \(dp[i][1], dp[i][2], \cdots, dp[i][i]\) 为 \(x_1, x_2, \cdots, x_i\)，根据转移式，有 \(i\) 个方程，\(i\) 个变量，解方程的话是肯定可以解出来的。但是使用高斯消元解方程的复杂度达到 \(O(n^3)\)，必定超时。
注意到这里的方程是很简单的形式，所以可以优化。
观察 dp转移式，当 \(j > 1\) 时，\(\frac{1}{2} * dp[i-1][j-1]\) 的部分实际是一个常数，上一层就已经算出来了。而 \(\frac{1}{2}dp[i][j-1]\) 是上一个变量的线性倍，即：\(x_i = ax_{i-1} + b\)，这就可以通过一种简便的方法来解方程。
例如 \(N = 3\) 的时候：
又因为：
最终解得：
然后回代即可得到 \(x_2\) 和 \(x_3\)。
这个方法的核心就是因为 \(x_i = ax_{i-1} + b\) 的形式，所以我们可以只维护 \(a\) 和 \(b\) 的系数值，然后解出 \(x_1\)，这是非常容易的，显然，无论是求解 \(x_1\) 还是回代的过程都是 \(O(n)\) 的，这样总的复杂度就是 \(O(n^2)\)。
参考代码
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int maxn = 3000 + 10;
const LL mod = 998244353;
void exgcd(LL a, LL b, LL &x, LL &y)
{
if(!b)
{
x = 1, y = 0;
return;
}
exgcd(b, a%b, y, x);
y -= a / b * x;
}
LL inv(LL a)
{
LL x, y;
exgcd(a, mod, x, y);
if(x < 0)
x += mod;
return x;
}
LL mul(LL a, LL b)
{
a *= b;
a %= mod;
return a;
}
int n;
LL dp[maxn][maxn];
// dp[i][j] = 1/2 * dp[i][j-1] + 1/2 * dp[i-1][j-1]
// dp[i][1] = 1/2 * dp[i][i]
int main()
{
cin >> n;
LL p = inv(2);
dp[1][1] = 1;
for(int i = 2; i <= n; i++)
{
LL a = 1, b = 0;
for(int j = 2; j <= i; j++)
{
b += dp[i-1][j-1];
b %= mod;
a = mul(a, p);
b = mul(b, p);
}
a = mul(a, p);
b = mul(b, p);
dp[i][1] = mul(b, inv((1 - a + mod) % mod));
for(int j = 2; j <= i; j++)
dp[i][j] = mul(p, dp[i][j-1]+dp[i-1][j-1]);
}
for(int i = 1; i <= n; i++)
printf("%lld ", dp[n][i]);
return 0;
}
import java.util.Scanner;
public class Main {
final private static long mod = 998244353;
private static long[] exgcd(long a, long b) {
if (b == 0)
return new long[] { 1, 0 };
long[] xy = exgcd(b, a % b);
long x2 = xy[0], y2 = xy[1];
xy[0] = y2;
xy[1] = x2 - a / b * y2;
return xy;
}
private static long inv(long a) {
long x = exgcd(a, mod)[0];
if (x < 0)
x += mod;
return x;
}
private static long mul(long a, long b) {
a *= b;
a %= mod;
return a;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long[][] dp = new long[n + 1][n + 1];
long p = inv(2);
dp[1][1] = 1;
for (int i = 2; i <= n; i++) {
long a = 1, b = 0;
for (int j = 2; j <= i; j++) {
b += dp[i - 1][j - 1];
b %= mod;
a = mul(a, p);
b = mul(b, p);
}
a = mul(a, p);
b = mul(b, p);
dp[i][1] = mul(b, inv((1 - a + mod) % mod));
for (int j = 2; j <= i; j++)
dp[i][j] = mul(p, dp[i][j - 1] + dp[i - 1][j - 1]);
}
for (int i = 1; i <= n; i++)
System.out.println(dp[n][i]);
in.close();
}
}
G - Nearest Fraction¶
题目大意
给你一个实数 \(r(0 < r < 1)\) 和一个整数 \(N(1 \le 10^{10})\)，构造一个最接近的 \(r\) 的最简分数 \(\frac{p}{q}\)，其中 \(0 \le p \le q \le N\) 。换言之，构造一个 \(|r - \frac{p}{q}|\) 最小的 \(\frac{p}{q}\)，输出 \(p\) 和 \(q\) 的值，如果有多个答案，输出 \(\frac{p}{q}\) 较小的那个。
ps：不会做，改天补一下这道题......
创建日期: 2024-03-01