鉴于我比较若,有小部分参考了网上的题解。

日常推销博客:https://floating-ocean.github.io/blog/a/fjnu_cpc_20

One contestant of team004. Rank 1. Solved 7/12.

A. Tree Destruction

图论+组合数,待补充

B. Encore

计算几何,待补充

C. Konnakol

题意

无穷次重复斐波那契数列的前八项,构成一个序列。

给定整数 n,kn, k,提取出前 nn 个数,输出第 kk 个数。

思路

首先,nn 是没用的。

其次,取模即可。

时间复杂度:O(1)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();
}

骗人 ×1\times 1

D. Data Mining and Big Data

题意

给定一个只包含 00 11 的字符串,长度为 2k,k[0,2]2^k, k \in [0, 2],定义一次操作为:将当前的字符串中的所有二进制数取反,并拼接到原字符串的后面。

按照如上操作进行若干次后,可得一个 1024GB1024GB 的数据,输出数据中 00 的个数。

思路

显然,最后 0011 的个数是相等的,那么我们直接输出长度的一半即可。

不用敲样例,答案就是 1<<321 << 32

时间复杂度:O(1)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)=0f(x) = 0

给定 qq 个询问,每个询问会给定操作序号,以及操作所需的参数:

  1. 给定两个整数 a,ba, b,将 f(x)f(x) 更新为 f(x)+xa+bf(x) + |x - a| + b
  2. 输出让 f(x)f(x) 的值最小的 xx,以及 f(x)f(x) 的最小值。

对于询问,执行对应的操作。

思路

我们把 xa|x - a|bb 分成两部分考虑。

首先很明显,无论 xx 是什么,右边的值都不会受到影响,因此我们可以在更新的时候顺便记录右边的值的总和。

其次,在更新了 nn 次后,左边的值的总和为 xa1+xa2++xan|x - a_1| + |x - a_2| + \ldots + |x - a_n|

不难发现,要让这个值最小,xx 就是 a1,a2,,ana_1, a_2, \ldots, a_n 的中位数。

因此,本题最后归结到,如何动态维护中位数。

对于这个,考虑到码量,我们会优先选择对顶堆,而非线段树。

何为对顶堆?小根堆维护前 n2\frac{n}{2} 大的数,剩余的数由大根堆维护。

那么,我们只要保持大小根堆的大小的差值不大于 11,即可保证大根堆的队头就是中位数。

在维护大小根堆的同时,我们根据元素的位置维护左半部分的和即可。

时间复杂度:O(nlogn)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,ca, b, c,定义一次操作为:选择两个数,将某个数 +1+1,另一个数 1-1

输出最小的操作数,使得存在某两个数的乘积为第三个数。

思路

我们设最后得到的 a,b,ca, b, c 满足 ab=cab = c

那么 a+b+ab=suma + b + ab = sum

左右各加 11,化简得到 (a+1)(b+1)=sum+1(a + 1)(b + 1) = sum + 1

也就是说,a+1a + 1sum+1sum + 1 的因子。

因此,如果这道题的数据量不大,那么解法就是线性筛+分解质因数+dfs\mathtt{dfs}枚举因子。

wait,你可能会疑惑,为什么可以 dfs\mathtt{dfs}

事实上,1e181e18 的因子数量的数量级只有 1e51e5 左右,因此暴力是可行的。

好,看一下数据范围 1e181e18,寄。

这边需要用到 Pollard Rho 算法,用 O(n14)O(n ^ {\frac{1}{4}}) 的复杂度完成分解质因数。

因此,在得到因子后,我们将 a,b,ca, b, c 进行排列,并与之前的 a,b,ca, b, c 分别进行作差取绝对值后 求和除 22,最后取最小值即可。

时间复杂度:O(n14p)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

赛时的样例出错,OJ\mathtt{OJ} 上的重现赛的题面已修正

题意

nnrr 问题中答对 xx 道题的概率。

思路

首先,因为如果某道题选错,可能会影响后续的正确选项的选择,所以简单的组合数是不对的。

我们不妨考虑广义容斥的做法,或者说,这就是一道广义容斥的模板题。

考虑到我比较若,这边把官方题解搬过来了,并略微做了点修改。

我们设 β(x)β(x) 为有 xx 个条件的满足的方案数。

则恰好有 xx 个方案满足的方案数为 $\displaystyle{f(x)=\sum_{i=x}^{n}(-1)^{i-x}β(x) {i\choose x}}$。

对应到本题,求解步骤即为:

  1. β(x)β(x) 的意思是至少对 xx 题,也就是先从 rr 个空中选出 ii 个是对的,然后对于剩下的 nin-i 个选项,我们再选出 rir-i 个填入剩下的空。那么方案数为 $\displaystyle{ {r \choose i} { {n-i} \choose {r-i} } (r-i)!}$ 。
  2. 代入公式,$\displaystyle{f(x)=\sum_{i=x}^{r}{i \choose x}(-1)^{i-x}{r \choose i}{n-i\choose r-i }(r-i)!}$ 。
  3. 全部的方案数量为 (nr)r!\displaystyle{ {n \choose r} r! },因此将 f(x)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

题意

定义一次操作为将整个序列向右移动一格,并将最后一个元素放到序列的开头。

给定一个字符序列,输出进行任意次操作后是否能将序列变为回文。

思路

数据量很小,所以是一道签到题。

与其模拟放置的过程,我们不妨直接在左边和右边分别复制一遍原序列,并遍历这个新序列,若出现了长度为 nn 的回文序列,那么就是可行。

时间复杂度:O(32n2)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

题意

给定 nn 个盒子,每个盒子里最多有 33 个球。

定义操作为等概率选一个盒子(包括空的),并取出一个球。

给定每个盒子内的球数,输出将所有球取出的数学期望。

思路

首先,我们来考虑 44 维 dp,其中 dp[i][j][k][p]dp[i][j][k][p] 代表还剩 0,1,2,30, 1, 2, 3 个球分别对应的盒子个数 i,j,k,pi, j, k, p 该状态的数学期望。

该状态可由下面的子状态转移得到:

  1. 从一个包含 33 个球的盒子中取出一个球,对应期望为 pndp[i][j][k+1][p1]\frac{p}{n}dp[i][j][k + 1][p - 1]
  2. 从一个包含 22 个球的盒子中取出一个球,对应期望为 kndp[i][j+1][k1][p]\frac{k}{n}dp[i][j + 1][k - 1][p]
  3. 从一个包含 11 个球的盒子中取出一个球,对应期望为 jndp[i+1][j1][k][p]\frac{j}{n}dp[i + 1][j - 1][k][p]
  4. 从一个包含 00 个球的盒子中取出一个球,对应期望为 indp[i][j][k][p]\frac{i}{n}dp[i][j][k][p]

加上自己可作为单独的一个状态的期望 11,最后整理得到式子:

$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=ni + 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(n3)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)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

题意

给定一个由 nn 个横向街道和 mm 个纵向街道组成的矩形城市,定义一条横向或纵向的街道只能有一个标记,只能标记在十字路口上。

给定标记总数 kk,输出方案数。

思路

排列组合的签到题。

先从 nn 个横向街道里选择 kk 个街道,不考虑顺序,再从 mm 个纵向街道里选择 kk 个街道,考虑顺序,最后取模即可。

也就是说,答案是 CnkAmkC^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

题意

给定 nn 个商店,每个商店将会在 0.5,1.5,2.5,0.5, 1.5, 2.5, \ldots 时刻售出一份库存游戏。

给定家到每个商店需要的时间,以及每个商店的库存,输出买到游戏的最短时刻,以及对应的商店的编号(有多个满足条件输出全部)。

思路

首先,如果到达时间大于库存量,那么到的时候就卖光了。

其次,我们直接暴力枚举找出最小值以及对应的商店即可。

时间复杂度:O(n)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

0 comments

No comments so far...