One contestant of team004. Rank 1. Solved 7/12.
A. Tree Destruction
图论+组合数，待补充
B. Encore
计算几何，待补充
C. Konnakol
题意
无穷次重复斐波那契数列的前八项，构成一个序列。
给定整数 \(n, k\)，提取出前 \(n\) 个数，输出第 \(k\) 个数。
思路
首先，\(n\) 是没用的。
其次，取模即可。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
vector<int> p = {1, 1, 2, 3, 5, 8, 13, 21};
int sb, x;
cin >> sb >> x;
cout << p[(x - 1) % 8] << "/8\n";
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}骗人 \(\times 1\)
D. Data Mining and Big Data
题意
给定一个只包含 \(0\) 或 \(1\) 的字符串，长度为 \(2^k, k \in [0, 2]\)，定义一次操作为：将当前的字符串中的所有二进制数取反，并拼接到原字符串的后面。
按照如上操作进行若干次后，可得一个 \(1024GB\) 的数据，输出数据中 \(0\) 的个数。
思路
显然，最后 \(0\) 和 \(1\) 的个数是相等的，那么我们直接输出长度的一半即可。
不用敲样例，答案就是 \(1 << 32\)。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
string s;
cin >> s;
cout << (1ll << 32) << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}不会真有人敲错吧（
E. Function
题意
初始状态下，令方程 \(f(x) = 0\)。
给定 \(q\) 个询问，每个询问会给定操作序号，以及操作所需的参数：
给定两个整数 \(a, b\)，将 \(f(x)\) 更新为 \(f(x) + |x - a| + b\)；
输出让 \(f(x)\) 的值最小的 \(x\)，以及 \(f(x)\) 的最小值。
对于询问，执行对应的操作。
思路
我们把 \(|x - a|\) 和 \(b\) 分成两部分考虑。
首先很明显，无论 \(x\) 是什么，右边的值都不会受到影响，因此我们可以在更新的时候顺便记录右边的值的总和。
其次，在更新了 \(n\) 次后，左边的值的总和为 \(|x - a_1| + |x - a_2| + \ldots + |x - a_n|\)。
不难发现，要让这个值最小，\(x\) 就是 \(a_1, a_2, \ldots, a_n\) 的中位数。
因此，本题最后归结到，如何动态维护中位数。
对于这个，考虑到码量，我们会优先选择对顶堆，而非线段树。
何为对顶堆？小根堆维护前 \(\frac{n}{2}\) 大的数，剩余的数由大根堆维护。
那么，我们只要保持大小根堆的大小的差值不大于 \(1\)，即可保证大根堆的队头就是中位数。
在维护大小根堆的同时，我们根据元素的位置维护左半部分的和即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 1e7 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int q;
cin >> q;
priority_queue<int> g;
priority_queue<int, vector<int>, greater<>> l;
int sum1 = 0, sum2 = 0;
while(q --){
int op;
cin >> op;
if(op == 1){
int a, b;
cin >> a >> b;
sum2 += b;
if(!l.empty() && a > l.top()){
l.emplace(a), sum1 += a;
}else{
g.emplace(a), sum1 -= a;
}
if(g.size() > l.size() + 1){
l.emplace(g.top()), sum1 += g.top() * 2, g.pop();
}
if(l.size() > g.size()){
g.emplace(l.top()), sum1 -= l.top() * 2, l.pop();
}
}else{
cout << g.top() << ' ';
int ans = sum1 + sum2;
if(g.size() > l.size()) ans += g.top();
cout << ans << '\n';
}
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}妙捏
F. A * B Problem
题意
给定三个数 \(a, b, c\)，定义一次操作为：选择两个数，将某个数 \(+1\)，另一个数 \(-1\)。
输出最小的操作数，使得存在某两个数的乘积为第三个数。
思路
我们设最后得到的 \(a, b, c\) 满足 \(ab = c\)。
那么 \(a + b + ab = sum\)。
左右各加 \(1\)，化简得到 \((a + 1)(b + 1) = sum + 1\)。
也就是说，\(a + 1\) 是 \(sum + 1\) 的因子。
因此，如果这道题的数据量不大，那么解法就是线性筛+分解质因数+\(\mathtt{dfs}\)枚举因子。
wait，你可能会疑惑，为什么可以 \(\mathtt{dfs}\)。
事实上，\(1e18\) 的因子数量的数量级只有 \(1e5\) 左右，因此暴力是可行的。
好，看一下数据范围 \(1e18\)，寄。
这边需要用到 Pollard Rho 算法，用 \(O(n ^ {\frac{1}{4}})\) 的复杂度完成分解质因数。
因此，在得到因子后，我们将 \(a, b, c\) 进行排列，并与之前的 \(a, b, c\) 分别进行作差取绝对值后 求和除 \(2\)，最后取最小值即可。
时间复杂度：\(O(n ^ {\frac{1}{4}}p)\) ,p为因子个数
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
/* *************************************************
* Miller_Rabin 算法进行素数测试
* 速度快可以判断一个 < 2^63 的数是不是素数
*
**************************************************/
const int S = 8; //随机算法判定次数一般 8∼10 就够了
// 计算 ret = (a*b)%c a,b,c < 2^63
int mult_mod(int a, int b, int c) {
a %= c;
b %= c;
int ret = 0;
int tmp = a;
while (b) {
if (b & 1) {
ret += tmp;
if (ret > c)ret -= c;//直接取模慢很多
}
tmp <<= 1;
if (tmp > c)tmp -= c;
b >>= 1;
}
return ret;
}
// 计算 ret = (a^n)%mod
int pow_mod(int a, int n, int mod) {
int ret = 1;
int temp = a % mod;
while (n) {
if (n & 1)ret = mult_mod(ret, temp, mod);
temp = mult_mod(temp, temp, mod);
n >>= 1;
}
return ret;
}
// 通过 a^(n−1)=1(mod n)来判断 n 是不是素数
// n − 1 = x ∗ 2
// 中间使用二次判断
// 是合数返回 true, 不一定是合数返回 false
bool check(int a, int n, int x, int t) {
int ret = pow_mod(a, x, n);
int last = ret;
for (int i = 1; i <= t; i++) {
ret = mult_mod(ret, ret, n);
if (ret == 1 && last != 1 && last != n - 1)return true;//合数
last = ret;
}
if (ret != 1)return true;
else return false;
}
//**************************************************
// Miller_Rabin 算法
// 是素数返回 true,(可能是伪素数)
// 不是素数返回 false
//**************************************************
bool Miller_Rabin(int n) {
if (n < 2)return false;
if (n == 2)return true;
if ((n & 1) == 0)return false;//偶数
int x = n - 1;
int t = 0;
while ((x & 1) == 0) {
x >>= 1;
t++;
}
srand(time(NULL));
/* *************** */
for (int i = 0; i < S; i++) {
int a = rand() % (n - 1) + 1;
if (check(a, n, x, t))
return false;
}
return true;
}
//**********************************************
// pollard_rho 算法进行质因素分解
//*********************************************
int factor[1000005];//质因素分解结果（刚返回时时无序的）
int tol;//质因素的个数，编号 0∼tol-1
int gcd(int a, int b) {
int t;
while (b) {
t = a;
a = b;
b = t % b;
}
if (a >= 0)return a;
else return -a;
}
//找出一个因子
int pollard_rho(int x, int c) {
int i = 1, k = 2;
srand(time(NULL));
int x0 = rand() % (x - 1) + 1;
int y = x0;
while (1) {
i++;
x0 = (mult_mod(x0, x0, x) + c) % x;
int d = gcd(y - x0, x);
if (d != 1 && d != x)return d;
if (y == x0)return x;
if (i == k) {
y = x0;
k += k;
}
}
}
//对 n 进行素因子分解，存入 factor. k 设置为 107 左右即可
void findfac(int n, int k) {
if (n == 1)return;
if (Miller_Rabin(n)) {
factor[tol++] = n;
return;
}
int p = n;
int c = k;
while (p >= n)p = pollard_rho(p, c--);//值变化，防止死循环 k
findfac(p, k);
findfac(n / p, k);
}
//-------- ACM Template of kuangbin p. 30 ----------
const int inf = 0x3f3f3f3f3f3f3f3f;
vector<int> keys;
map<int, int> fact_map;
set<int> fact_set;
int qp(int a, int b) {
int res = 1;
while (b > 0) {
if (b & 1) res *= a;
a *= a;
b >>= 1;
}
return res;
}
void factorize(int x){
fact_map.clear();
keys.clear();
tol = 0;
findfac(x, 107);
for(int i=0;i<tol;i++) {
if(fact_map[factor[i]] == 0) keys.pb(factor[i]);
fact_map[factor[i]] ++;
}
}
void dfs(int x, int step){
if(step == fact_map.size()){
fact_set.emplace(x);
return;
}
for(int i=0;i<=fact_map[keys[step]];i++){
dfs(x * qp(keys[step], i), step + 1);
}
}
void solve() {
int a, b, c;
cin >> a >> b >> c;
int sum = a + b + c;
factorize(sum + 1);
fact_set.clear();
dfs(1, 0);
int ans = inf;
for(auto e : fact_set) {
if(e == 1) continue;
int aa = e - 1, bb = (sum + 1) / e - 1, cc = sum - aa - bb;
ans = min(ans, (abs(aa - a) + abs(bb - b) + abs(cc - c)) / 2);
ans = min(ans, (abs(aa - a) + abs(bb - c) + abs(cc - b)) / 2);
ans = min(ans, (abs(aa - b) + abs(bb - a) + abs(cc - c)) / 2);
ans = min(ans, (abs(aa - b) + abs(bb - c) + abs(cc - a)) / 2);
ans = min(ans, (abs(aa - c) + abs(bb - a) + abs(cc - b)) / 2);
ans = min(ans, (abs(aa - c) + abs(bb - b) + abs(cc - a)) / 2);
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}但凡数据量小就很签（（
G. CET-4
赛时的样例出错，\(\mathtt{OJ}\) 上的重现赛的题面已修正
题意
\(n\) 选 \(r\) 问题中答对 \(x\) 道题的概率。
思路
首先，因为如果某道题选错，可能会影响后续的正确选项的选择，所以简单的组合数是不对的。
我们不妨考虑广义容斥的做法，或者说，这就是一道广义容斥的模板题。
考虑到我比较若，这边把官方题解搬过来了，并略微做了点修改。
我们设 \(β(x)\) 为有 \(x\) 个条件的满足的方案数。
则恰好有 \(x\) 个方案满足的方案数为 \(\displaystyle{f(x)=\sum_{i=x}^{n}(-1)^{i-x}β(x) {i\choose x}}\)。
对应到本题，求解步骤即为：
\(β(x)\) 的意思是至少对 \(x\) 题，也就是先从 \(r\) 个空中选出 \(i\) 个是对的，然后对于剩下的 \(n-i\) 个选项，我们再选出 \(r-i\) 个填入剩下的空。 那么方案数为 \(\displaystyle{ {r \choose i} { {n-i} \choose {r-i} } (r-i)!}\) 。
代入公式，\(\displaystyle{f(x)=\sum_{i=x}^{r}{i \choose x}(-1)^{i-x}{r \choose i}{n-i\choose r-i }(r-i)!}\) 。
全部的方案数量为 \(\displaystyle{ {n \choose r} r! }\)，因此将 \(f(x)\) 和这个作除即可得到答案。
当然也可以用 dp 实现。
时间复杂度：看你怎么预处理
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e6 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
int fact[N], fact_inv[N];
int qp(int a, int b) {
int res = 1;
while (b > 0) {
if (b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
int inv(int x){
return qp(x, mod - 2);
}
void init(){
fact[0] = fact_inv[0] = 1;
for(int i=1;i<=2e6;i++){
fact[i] = fact[i - 1] * i % mod;
fact_inv[i] = inv(fact[i]); //当然这边还可以优化
}
}
int C(int n, int m){
return fact[n] * fact_inv[n - m] % mod * fact_inv[m] % mod;
}
void solve() {
int n, r, x;
cin >> n >> r >> x;
int p = 0;
for(int i=x;i<=r;i++){
int now = C(i, x) * C(r, i) % mod * C(n - i, r - i) % mod * fact[r - i] % mod;
if((i - x) % 2 == 0) p = (p + now) % mod;
else p = (p + mod - now) % mod;
}
cout << p * inv(C(n, r) * fact[r] % mod) % mod << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
init();
int t = 1;
cin >> t;
while(t --) solve();
}论我想了半天4选1对1题的概率为什么是1/6这件事
H. Group Theory
题意
定义一次操作为将整个序列向右移动一格，并将最后一个元素放到序列的开头。
给定一个字符序列，输出进行任意次操作后是否能将序列变为回文。
思路
数据量很小，所以是一道签到题。
与其模拟放置的过程，我们不妨直接在左边和右边分别复制一遍原序列，并遍历这个新序列，若出现了长度为 \(n\) 的回文序列，那么就是可行。
时间复杂度：\(O(\frac{3}{2}n^2)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
if(n == 0){
cout << "YES\n";
return;
}
vector<string> a(3 * n + 3);
for(int i=0;i<n;i++){
cin >> a[i];
a[n + i] = a[n * 2 + i] = a[i];
}
bool f = false;
for(int i=0;i<2*n;i++){
bool cur = true;
for(int j=0;j<n/2;j++){
if(a[i + j] != a[i + (n - j - 1)]){
cur = false;
break;
}
}
if(cur){
f = true;
break;
}
}
cout << (f ? "YES\n" : "NO\n");
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}签到签到
I. Balls
题意
给定 \(n\) 个盒子，每个盒子里最多有 \(3\) 个球。
定义操作为等概率选一个盒子（包括空的），并取出一个球。
给定每个盒子内的球数，输出将所有球取出的数学期望。
思路
首先，我们来考虑 \(4\) 维 dp，其中 \(dp[i][j][k][p]\) 代表还剩 \(0, 1, 2, 3\) 个球分别对应的盒子个数 \(i, j, k, p\) 该状态的数学期望。
该状态可由下面的子状态转移得到：
从一个包含 \(3\) 个球的盒子中取出一个球，对应期望为 \(\frac{p}{n}dp[i][j][k + 1][p - 1]\)；
从一个包含 \(2\) 个球的盒子中取出一个球，对应期望为 \(\frac{k}{n}dp[i][j + 1][k - 1][p]\)；
从一个包含 \(1\) 个球的盒子中取出一个球，对应期望为 \(\frac{j}{n}dp[i + 1][j - 1][k][p]\)；
从一个包含 \(0\) 个球的盒子中取出一个球，对应期望为 \(\frac{i}{n}dp[i][j][k][p]\)；
加上自己可作为单独的一个状态的期望 \(1\)，最后整理得到式子：
\(dp[i][j][k][p] = \frac{n}{j + k + p} + \frac{j}{j + k + p}dp[i + 1][j - 1][k][p] + \frac{k}{j + k + p}dp[i][j + 1][k - 1][p] + \frac{k}{j + k + p}dp[i][j][k + 1][p - 1]\)
有趣的是，\(i + j + k + p = n\)，因此我们可以拿掉一维。
最后得到状态转移方程：
\(dp[i][j][k] = \frac{n}{i + j + k} + \frac{i}{i + j + k}dp[i - 1][j][k] + \frac{j}{i + j + k}dp[i + 1][j - 1][k] + \frac{k}{i + j + k}dp[i][j + 1][k - 1]\)
时间复杂度：\(O(n ^ 3)\)
对应AC代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
double f[305][305][305];
int a[5], n;
signed main() {
cin >> n;
for(int i = 1, x; i <= n; i++) cin >> x, a[x]++;
for(int k = 0; k <= n; k++) {
for(int j = 0; j <= n; j++) {
for(int i = 0; i <= n; i++) {
if(i || j || k) {
if(i) f[i][j][k] += f[i - 1][j][k] * i / (i + j + k);
if(j) f[i][j][k] += f[i + 1][j - 1][k] * j / (i + j + k);
if(k) f[i][j][k] += f[i][j + 1][k - 1] * k / (i + j + k);
f[i][j][k] += 1.0 * n / (i + j + k);
}
}
}
}
cout << setprecision(10);
cout << fixed << (f[a[1]][a[2]][a[3]]);
return 0;
}自己写的dp状态重复了（也就是以一种递归的方式正推），十分头大于是找了一篇洛谷的题解研究了一波（（
J. Wish You Can Have Fun Today
题意
输出 "Wish We Can Have Fun Today."
思路
如题，别打错。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
cout << "Wish We Can Have Fun Today.\n";
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}有人在比赛的刚开始把这题交错位置了，我不说是谁（
K. Chessboard City
题意
给定一个由 \(n\) 个横向街道和 \(m\) 个纵向街道组成的矩形城市，定义一条横向或纵向的街道只能有一个标记，只能标记在十字路口上。
给定标记总数 \(k\)，输出方案数。
思路
排列组合的签到题。
先从 \(n\) 个横向街道里选择 \(k\) 个街道，不考虑顺序，再从 \(m\) 个纵向街道里选择 \(k\) 个街道，考虑顺序，最后取模即可。
也就是说，答案是 \(C^k_nA^k_m\)。
注意需要线性求逆元哦，估计就卡死在这里了吧。
时间复杂度：看你怎么预处理
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 1e7 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
int fact[N], inv[N], fact_inv[N];
int qp(int a, int b) {
int res = 1;
while (b > 0) {
if (b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
void init(){
fact[0] = inv[0] = fact_inv[0] = fact[1] = inv[1] = fact_inv[1] = 1;
for(int i=2;i<=1e7;i++) {
fact[i] = fact[i - 1] * i % mod;
inv[i] = inv[mod % i] % mod * (mod - mod / i) % mod;
fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
}
}
int C(int n, int m){
return fact[n] * fact_inv[n - m] % mod * fact_inv[m] % mod;
}
int A(int n, int m){
return fact[n] * fact_inv[n - m] % mod;
}
void solve() {
int n, m, k;
cin >> n >> m >> k;
cout << C(n, k) * A(m, k) % mod << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
init();
int t = 1;
cin >> t;
while(t --) solve();
}签到签到
L. Game
题意
给定 \(n\) 个商店，每个商店将会在 \(0.5, 1.5, 2.5, \ldots\) 时刻售出一份库存游戏。
给定家到每个商店需要的时间，以及每个商店的库存，输出买到游戏的最短时刻，以及对应的商店的编号（有多个满足条件输出全部）。
思路
首先，如果到达时间大于库存量，那么到的时候就卖光了。
其次，我们直接暴力枚举找出最小值以及对应的商店即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 1e7 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
int mn = inf;
set<int> ans;
for(int i=0;i<n;i++){
int a, b;
cin >> a >> b;
if(a > b) continue;
if(a < mn){
mn = a, ans.clear(), ans.emplace(i + 1);
}else if(a == mn) ans.emplace(i + 1);
}
if(mn == inf){
cout << -1 << '\n';
return;
}
cout << mn << '\n';
for(auto e: ans) cout << e << ' ';
cout << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}居然没看到反面有题哈哈哈哈（x