solved 7 problems
A、B、E、H、J、K、L：dbywsc
前言
第一次做台湾赛区的题目，被雷到了，深刻怀疑出题人的水平和态度。
补题链接
官方题解
K.kick
题意
给定一个字符串 \(s\) ，求其中子串 "kick" 的数量。
思路
直接遍历一遍即可。
代码
void solve(void) {std::string s;std::cin >> s;int cnt = 0;for(int i = 0; i < s.size() - 3; i++) if(s[i] == 'k' && s[i + 1] == 'i' && s[i + 2] == 'c' && s[i + 3] == 'k') cnt++;std::cout << cnt;
}
J.Java Warriors
题意 && 思路
输出 \(n \times 4000\) 。
代码
void solve(void) {int n; std::cin >> n;std::cout << n * 4000;
}
A.Advance to Taoyuan Regional
题意
给定一个日期，判断当前日期和 \(2023\) 年 \(10\) 月 \(21\) 日之间是否至少相隔 \(35\) 天。
思路
直接判断当前日期是否在 \(2023-9-16\) 日之前即可。
代码
void solve(void) {std::string s; std::cin >> s;if(s > "2023-09-16") {std::cout << "TOO LATE";return;}std::cout << "GOOD";
}
L.Location, Location, Location
题意
给定二维平面上的 \(n\) 个点，要求找到一个点，使得这 \(n\) 个点到这个点的哈夫曼距离的总和最小。如果存在多个，取 \(x\) 最小的点。
思路
要想让哈夫曼距离的总和最小，应该讲 \(x\) 轴和 \(y\) 轴分开看，取 \(n\) 个点 \(x\) 坐标的中位数和 \(y\) 坐标的中位数构成一个点即可。
代码
void solve(void) {int n; std::cin >> n;std::vector<int> x(n + 1), y(n + 1);for(int i = 1; i <= n; i++)std::cin >> x[i] >> y[i];std::sort(x.begin() + 1, x.end());std::sort(y.begin() + 1, y.end());if(n % 2) {std::cout << x[(n + 1) / 2] << " " << y[(n + 1) / 2];}else std::cout << x[n / 2] << ' ' << y[n / 2];
}
B.Better Chance
题意
我个人认为这是本场中出的最烂的一个题，题意含糊不清，题目描述中没有给出任何关键信息，将有用的信息塞在冗杂的 Note 中，强行让人阅读理解。
其实就是给定了一个公式
分别给一个队伍在两场比赛总的 \(R\) 和 \(S\) ，问在哪一场中计算出的排名更高。
思路
位了避免精度问题，可以将式子变形：
将除法变成乘法。此时还需要考虑 \(S_T,S_J\) 是小数，由于题目上说它们乘以一百一定是整数，因此可以将它们统一乘上 \(100\) 。但是要注意本题卡了 \(C++\) 等语言小数舍入的规则，必须使用 std::round() 将小数舍入改为四舍五入的形式。
代码
void solve(void) {int a, b;double c, d;std::cin >> a >> b >> c >> d;i64 rk1 = (a - 1) * (i64)std::llround(d * 100.0);i64 rk2 = (b - 1) * (i64)std::llround(c * 100.0);if(rk1 == rk2) std::cout << "SAME";else std::cout << (rk1 < rk2 ? "TAOYUAN" : "JAKARTA");
}
E.Exponentiation
题意
给定 \(x + x^{-1} = \alpha\) ，求 \(x^{\beta} + x^{-\beta} \mod m\) 的值。
思路
这是一个比较经典的式子，设 \(T_n = x^{n} + x^{n}\) ，注意到：
\(T_0 = 2\)
\(T_1 = \alpha\)
\(T_n = \alpha \ T_{n - 1} - T_{n - 2}\)
因此可以构造出矩阵：
使用矩阵快速幂加速即可。
需要注意本题卡了 __uint128_t ，对C++非常不友好，所以用了Python代码。
代码
import sysdef mul(x, y, m):a = (x[0] * y[0] % m + x[1] * y[2] % m) % mb = (x[0] * y[1] % m + x[1] * y[3] % m) % mc = (x[2] * y[0] % m + x[3] * y[2] % m) % md = (x[2] * y[1] % m + x[3] * y[3] % m) % mreturn (a, b, c, d)def pow_mat(base, exp, m):res = (1, 0, 0, 1)while exp > 0:if exp % 2 == 1:res = mul(res, base, m)base = mul(base, base, m)exp >>= 1return resdef solve():input = sys.stdin.read().split()a = int(input[0])b = int(input[1])m = int(input[2])if b == 0:print(2 % m)returnif b == 1:print(a % m)returnM = (a, (m - 1) % m, 1, 0)P = pow_mat(M, b - 1, m)ans = (P[0] * a % m + P[1] * 2 % m) % mprint(ans)if __name__ == "__main__":solve()
H.Heap Structure
题意
给定一个大小为 \(n\) ，二叉树形式的，每个元素互不相同的最小堆，问第 \(k\) 小第元素最多可以放在几个不同的位置上。
思路
设第 \(k\) 小元素所在的子树大小为 \(s(i)\) ，在整个堆中，有 \(n - k\) 个元素大于当前元素，显然它的子树中的其他 \(s(i) - 1\) 个元素一定是由这 \(n - k\) 个元素组成的，也就是说我们需要满足 \(s(i) - 1 \leq n - k\) 。当某一层的节点满足这个要求时，它下面的节点一定也满足这个要求，因此可以二分。
代码
void solve(void) {u64 n, k; std::cin >> n >> k;auto check = [&](i64 x) -> bool {u64 left = x, right = x, cnt = 0;while(left <= n) {u64 r = (right < n ? right : n);cnt += r - left + 1;left <<= 1;right = (right << 1) | 1;}return cnt <= n - k + 1;};u64 ub = 0;if(k >= 64) {ub = n;} else {u64 t = 1ull << k;ub = std::min(n, t - 1);}u64 l = 1, r = ub, ans = ub + 1;while(l <= r) {u64 mid = (l + r) / 2;if(check(mid)) {r = mid - 1;ans = mid;} else l = mid + 1;}std::cout << (ans <= ub ? (ub - ans + 1) : 0);
}