C2上机题目总结

更新 1 a b：给定整数 $ a, b $，令 $ g(x) = f(x) + |x - a| + b $，然后把 $ f(x) $ 替换为 $ g(x) $。
例如：若当前 $ f(x) = 0 $，执行操作更新操作 1 2 1（即 $ a=2, b=1 $），则新的函数为 $ f(x) = |x-2| + 1 $；接着再执行操作 1 3 2（即 $ a=3, b=2 $），新的函数为
$ f(x) = |x-2| + 1 + |x-3| + 2 $。
查询 2：输出使 $ f(x) $ 最小的整数 $ x $ 以及最小值 $ f(x) $。如果有多个使得最小的 $ x $，选择最小的那个整数。

例如：当 $ f(x) = |x - 2| + 1 $ 时，$ x = 2 $ 使得 $ f(x) $ 最小为 1。

已知询问时输出的值总是整数，请以整数格式输出。

输入

第一行为一个整数 $ Q $（$ 1 \leq Q \leq 2 \times 10^{5} $），表示操作的总次数。接下来 $ Q $ 行，每行表示一次操作，格式如下：

1 a b 表示更新操作（$-10^{9} \leq a,b \leq 10^{9} $）；
2 表示查询操作。

保证第一个操作为更新操作。

输入样例

输出样例

1 4
2 14

解析

这道题相当于一条数轴上点的距离的问题，每次输入1加入一个新的点，输入2找到一个点，使这个点到所有点距离之和最小，并给出距离之和。

根据数学原理：奇数个点使总距离最小点的位置必然在中位数点那个位置上，而偶数个点为最中间两个点之间任何位置都可以（由于题目要求输出最小点，即数轴中间靠左的那个点的位置）。

所以用两个堆来维护：一个大顶堆，一个小顶堆。相当于把整个数轴（数组）按大小分为两个部分，偏大的部分存在小顶堆，偏小的部分存在大顶堆，则两个堆顶必然有一个为中位数/都为中位数（奇偶讨论）。每次输入维护两个堆，并且维持两个堆的平衡即可。

同时输出要求输入距离和，可以同时维护大顶堆的sum和小顶堆的sum，当中位数为 $m$ 时，$sum |x-a_i|$ 的值为：

(m \cdot |L| - \text{sumL}) + (\text{sumR} - m \cdot |R|)

其中 $L$ 是 $\le m$ 的那一半，$R$ 是 $> m$ 的那一半。

（另：c++自带大顶堆、小顶堆）：

priority_queue<int> da;
std::priority_queue<int, std::vector<int>, std::greater<int>> xiao;

代码

#include <bits/stdc++.h>
using namespace std;

int q;
long long sumb = 0, num = 0;

priority_queue<int> da;
std::priority_queue<int, std::vector<int>, std::greater<int>> xiao;

long long dasum = 0, xiaosum = 0;

int main(){
    cin >> q;
    while(q--){
        int op, a, b;
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d",&a,&b);
            sumb += b;
            num++;
            int datop =-1e9-9, xiaotop = 1e9+9;
            if(!da.empty()) datop = da.top();
            if(!xiao.empty()) xiaotop = xiao.top();
            if(a < datop){
                dasum -= datop;
                dasum += a;
                da.pop();
                da.push(a);
                a = datop;
            }
            if(a > xiaotop){
                xiaosum -= xiaotop;
                xiaosum += a;
                xiao.pop();
                xiao.push(a);
                a = xiaotop;
            }
            if(da.size()>xiao.size()){
                xiaosum += a;
                xiao.push(a);
            }else{
                dasum += a;
                da.push(a);
            }
        }else{
            int mid;
            mid = da.top();
            long long ans = sumb + mid * ( (long long)da.size() - (long long)xiao.size() )+ xiaosum - dasum;
            printf("%d %lld\n",mid,ans);
        }
    }
    return 0;
}

G ALyCE与堆

题目背景

ALyCE迷上了广告里的小游戏，但是广告中的主角每次都选择战力比他高的故意被打败，她再也忍受不了了，要帮主角找到最优的序列！

题目描述

给定 $ A, B $ 两个长度为 $ N $ 的序列，$ A, B $ 中各取一个值相加后可以得到 $ N^2 $ 个值，求这 $ N^2 $ 个值中最小的 $ N $ 个。

输入

第一行一个正整数 $ N $，满足 $ 0 \leq N \leq 10^5 $；

第二行 $ N $ 个正整数 $ a_1, a_2 \ldots, a_N $， $ 1 \leq a_i \leq 10^7 $；

第三行 $ N $ 个正整数 $ b_1, b_2 \ldots, b_N $，有 $ 1 \leq b_i \leq 10^7 $。

输出

一行，$ N $ 个正整数，表示最小的 $ N $ 个和。

输入样例

2
3 5
4 6

输出样例

7 9

解析

这道题题目明显暗示用堆。

可是主播开始时想到可以对于数组$a_n$和$b_n$分别维护一个小顶堆，取出来堆顶相加必然是最小和。但是取出一个最小和之后无法继续维护这个最小堆了，产生了分支：a的第一小+b的第二小 or a的第二小+b的第一小那个小？堆在整个算法没啥用处，所以显然这个方法不对。

正确方法是：先对第一个数组和第二个数组分别排序（$O(nlg(n))$），取第一个数组第一个元素$a_0$，分别与第二个数组每个数相加，n个得数创建一个小顶堆。

循环n次（每次得出一个最小数并输出）：取出小顶堆的堆顶最小值，同时添加一个新的元素进入堆。比如堆顶是$a_i+b_j$，那么新加的元素时$a_{i+1}+b_j$，那么保证了上面主播开始的方法里两个分支结果都在堆里（此处要求存小顶堆时也要存上是哪两个位置相加得到的结果，不能只存和）。

代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;

struct dui{
    unsigned long long ans;
    int i,j;
};

int n;
int a[10000007], b[10000007];
int sizeh;
struct dui h[10000007];

void swap(int a, int b){
    struct dui tmp = h[a];
    h[a] = h[b];
    h[b] = tmp;
    return;
}

void down(int u){
    int t = u;
    if(u*2<=sizeh && h[u*2].ans<h[t].ans) t = u*2;
    if(u*2+1<=sizeh && h[u*2+1].ans<h[t].ans) t = u*2+1;
    if(u!=t){
        swap(u,t);
        down(t);
    }
}

void up(int u){
    while(u/2 && h[u/2].ans > h[u].ans){
        swap(u/2,u);
        u >>= 1;
    }
}

int main(){
    cin >> n;
    sizeh = 0;
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    for(int i = 0; i < n; i++){
        scanf("%d", &b[i]);
    }
    sort(a,a+n-1);
    sort(b,b+n);
    // for(int i = 0; i < n; i++){
    //     printf("%d ", a[i]);
    // }
    // for(int i = 0; i < n; i++){
    //     printf("%d ", b[i]);
    // }
    for(int i = 0; i < n; i++){
        struct dui aa;
        aa.ans = (unsigned long long)a[i] + b[0];
        //printf("%llu",aa.ans);
        aa.i = i;
        aa.j = 0;
        h[++sizeh] = aa;
        up(sizeh);
    }
    for(int i = 0; i < n; i++){
        printf("%llu ",h[1].ans);
        h[1].ans = a[h[1].i] + b[h[1].j+1];
        //printf("%llu",h[1].ans);
        h[1].j ++;
        down(1);
    }
    return 0;
}

H 苹果众数

题目背景

天才 Y 因为发明了安卓众数而名扬天下，这一次她又发明了苹果众数……

言归正传，最近天才 Y 非常喜欢研究数列，有一天，她为数列赋予了魔力……

题目描述

给定一个数列 $a_n$，一个长度为 $L$ 的区间 $a_t, a_{t+1}, \ldots, a_{t+L-1}$ 的平均值被称为一个 $L$ 阶魔力值，如果一个 $L$ 阶魔力值在所有 $L$ 阶魔力值中出现了至少 $\lceil \frac{k}{3} \rceil$ 次（其中 $k$ 表示 $L$ 阶魔力值的数量）则称该魔力值的是优美的。现给定长度为 $n$ 的数列 $a_n$，求哪些阶数存在优美的魔力值。

输入

输入一共两行。第一行一个正整数 $n$ （$4 \leq n \leq 5 \times 10^{3}$）表示数列的长度。第二行包含 $n$ 个整数表示数列 $a_1, a_2, \ldots, a_n$ （$\forall 1 \leq i \leq n, 0 \leq a_i \leq 10^9$）。

输出

输出一行若干个整数，每个整数之间使用一个空格分割。整数必须升序排列，表示这些阶存在优美魔力值。

输入样例

6
3 4 5 6 3 1

输出样例

1 2 4 5 6

样例解释

1 阶魔力值依次为 3, 4, 5, 6, 3, 1，故 $\lceil \frac{k}{3} \rceil = 2$，而 3 正好出现 2 次。

2 阶魔力值依次为 3.5, 4.5, 5.5, 4.5, 2，故 $\lceil \frac{k}{3} \rceil = 2$，而 4.5 正好出现 2 次。

3 阶魔力值依次为 4, 5, $\frac{14}{3}$, $\frac{10}{3}$，故 $\lceil \frac{k}{3} \rceil = 2$，但是没有值出现至少 2 次。

4 阶，5 阶，6 阶魔力值个数不超过 3 个，所以 $\lceil \frac{k}{3} \rceil = 1$，因此必然有优美魔力值。

题解

这道题初始想用哈希表来做。首先先计算整个数组的前缀和，循环每个不同的阶数的时候，先用前缀和计算某一段数组内的和，再拿一个哈希表来记录每个数字出现了几次，当某次添加后次数超过 $\lceil \frac{k}{3} \rceil$ 之后就输出答案。但是这种做法会TLE，原因是这道题会卡常。我也特意搜了一下什么叫卡常。

在OJ竞赛（Online Judge竞赛）中，“卡常”是“卡常数时间”或“卡常数复杂度”的简称，通常指的是在代码中通过一些技巧或者优化手段，使得程序在实际运行中更加高效，减少常数时间开销，从而在时间限制较严的情况下能通过测试。
具体来说，“卡常”并不是改变算法的时间复杂度的阶，比如从O(n²)变成O(n log n)，而是在同一复杂度下，通过各种方法减少运行时的常数因子，提高代码的执行速度。例如：
使用更快的I/O方法（如C++的ios::sync_with_stdio(false); cin.tie(nullptr);或者使用更高效的输入输出流）。
减少不必要的计算和函数调用。
优化数据结构的使用，减少重复访问或复制。
利用位运算替代部分算术操作。
合理运用内存局部性，提高缓存命中率。

就是来说C++内置的哈希表效率太低了，在 $O(1)$ 的查询效率下可能没表示出来的常数很大，导致超时。

这道题使用了一个多路投票算法。

给定数列 $a_1, a_2, \ldots, a_n$，求数列中出现次数超过一半的主元素 $a_x$，称为主元素问题。解决该问题的算法称为多数投票算法或摩尔投票算法。
算法思路：
通过一次遍历找到可能的主元素 $a_x$。
再次遍历确认该值是否为主元素。
关键思想：两两抵消
主元素出现次数超过 $\lceil \frac{n}{2} \rceil$。
在不断消除一个主元素和一个不同元素后，最后剩的就是主元素。
设计在线算法用两个变量：
cand：当前主元素候选
cnt：当前候选计数
初始 cnt = 0，遍历数列：
若 cnt == 0，将当前元素设为主元素候选 cand。
如果当前元素等于 cand，cnt 加 1。
否则，cnt 减 1。
遍历完成后，cand 即为主元素候选，再次遍历确认其出现次数是否超过一半。
此算法时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

而推广到出现次数大于等于 $\lceil \frac{k}{3} \rceil$ 的元素时，需要多添加一个主元素候选，同时运算时满足如下规则：

设变量：cand1, cand2为当前两个主元素候选，cnt1, cnt2对应候选的计数，初始化为0取出数列中元素，进行如下操作：
若 cnt1 不为0且 cand1 等于当前元素，cnt1++；
否则，若 cnt2 不为0且 cand2 等于当前元素，cnt2++；
否则，若 cnt1 为0，将当前元素设为 cand1，cnt1 = 1；
否则，若 cnt2 为0，将当前元素设为 cand2，cnt2 = 1；
否则，cnt1--，cnt2--。
（以上思路摘自C2同学题解）

找完之后再遍历一遍，看看两个主元素是否出现次数超过1/3，超过即可得出最终的答案。

在学习这个题解思路的时候，我曾遇到过两个问题（对于$\lceil \frac{n}{2} \rceil$的算法）：

若总元素个数为奇数，那么最后一个元素肯定会进候选里面，且cnt不等于0，怎么办？
当时没有想到再遍历一遍确认，如果再遍历一遍确认出现次数，那么肯定不会出错了。
若总元素个数为偶数，而且主元素正好出现$\lceil \frac{n}{2} \rceil$次，那么最后不正好被消掉了吗？
还是因为当时没有想到再遍历确认一遍，虽然最后消没之后cnt可能为0，但是cand没有变化，还保存的是之前的元素，所以对于cand从头确认一下总次数，就能发现其出现次数超过一半了。

代码

#include <bits/stdc++.h>
using namespace std;

int n;

int a[5009];
long long q[5009];

int main(){
    scanf("%d",&n);
    q[0] = 0;
    for(int i = 1; i<=n; i++){
        scanf("%d",&a[i]);
        q[i] = q[i-1] + a[i];
    }
    for(int t = 1; t<=n; t++){
        long long ans1 = -1, ans2 = -1;
        int ans1num = 0, ans2num = 0;
        for(int i = 1; i <= (n-t+1); i++){
            long long now = q[i+t-1] - q[i-1];
            if(ans1num != 0 && ans1 == now){
                ans1num++;
            }else if(ans2num!=0 && ans2 == now){
                ans2num ++;
            }else if(ans1num==0){
                ans1num++;
                ans1 = now;
            }else if(ans2num==0){
                ans2num++;
                ans2 = now;
            }else{
                ans1num--;ans2num--;
            }
        }
        ans1num = 0, ans2num = 0;
        for(int i = 1; i <= (n-t+1); i++){
            long long now = q[i+t-1] - q[i-1];
            if(now == ans1) ans1num++;
            if(now == ans2) ans2num++;
        }
        int lmt = (n-t+1)/3;
        if((n-t+1)%3!=0) lmt++;
        if(ans1num >= lmt || ans2num >= lmt) printf("%d ",t);
    }
    return 0;
}

I 2jogger1与 Miller-Rabin

题目描述

2jogger1又遇到了难题，他想要知道一堆数到底是不是质数，于是他写下来这样一个函数：

bool is_prime(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

但很快他就发现了问题：所给的数太大了，用上述函数会用掉亿点点时间。但好在他认识两位好朋友：Miller和Rabin，他们提出了一个更高效的算法判断 $n$ 是不是一个质数，其流程如下：

步骤1：预处理分解

将 $n - 1$ 分解成 $2^s \cdot d$ 的形式，其中 $d$ 是奇数。

步骤2：循环测试

接下来循环测试若干轮，每轮测试包含以下步骤：

2.1 随机选择底数

在区间 $[2, n-2]$ 中随机选择一个整数 $a_0$。

2.2 计算初始值

计算 $x_0 = a^d \mod n$。

2.3 初始条件检查

如果 $x_0 \equiv 1 \pmod{n}$ 或 $x_0 \equiv n-1 \pmod{n}$，那么这一轮测试通过，进入下一轮测试。
如果上述条件不满足，则进入平方序列检验。

2.4 平方序列检验

对于 $r = 1, 2, \ldots, s-1$，依次执行：

计算 $x_r = x_{r-1}^2 \mod n$。
检查 $x_r$ 的值：
- 若 $x_r \equiv n-1 \pmod{n}$，则本轮测试通过，跳出当前循环。
- 若 $x_r \equiv 1 \pmod{n}$，则本轮测试失败，判定为合数。
- 否则继续计算下一个 $x_r$。

2.5 最终判定

如果完成全部 $s-1$ 次平方运算后：

仍未出现 $x_r \equiv n - 1 \pmod{n}$ 的情况，且
$x_r \not\equiv 1 \pmod{n}$

则判定该数为合数。

步骤3：最终结论

如果所有测试轮次都通过，那么该数可能是质数。

可以证明，一个合数通过一轮检测的概率不大于 $\frac{1}{4}$，对于小于 $2^{64}$ 的整数，如果使用 $\{2, 325, 9375, 28178, 450775, 9780504, 1795265022\}$ 这组基数，一定不会出现错误。

注意：如果要使用这组基数需要注意：

所有的数都要取一遍，不能只选小于 $n$ 的。
需要把基数 $a$ 换成其模 $n$ 的值。
如果 $a \equiv 0, 1, -1 \pmod{n}$，可以直接通过这轮测试。

现在2jogger1希望你实现这一算法，帮他来判断素数。

输入

第一行输入一个整数 $T$，表示要判断的正整数的个数，保证 $1 \leq T \leq 10^5$。

第二行 $T$ 个正整数 $n_i$，保证 $2 \leq n_i \leq 10^{18}$。

输出

输出 $T$ 行，第 $i$ 行表示 $n_i$ 是不是素数，如果是输出 prime，否则输出 Not prime。

输入样例

3
2 998244353 114514

输出样例

prime
prime
Not prime

Hint

如果你不知道同余的概念，可以看这里：设 $m$ 是一个正整数，$a$ 和 $b$ 是整数，如果 $m$ 整除 $a - b$，那么我们称 $a$ 与 $b$ 模 $m$ 同余，记作：$a \equiv b \pmod{m}$。

你可能需要一个快速求整数幂的算法，参考资料：快速幂。

注意运算过程中如果使用 long long 可能会溢出，可以使用 __int128 这一数据类型。

解析

这题说啥做啥就行，早知道先做这个题力。

快速幂（求 $a^b \text{ }mod \text{ } p$ ）：

long long binpow(long long a, long long b, long long p) {
  if (b == 0) return 1;
  long long res = binpow(a, b / 2, p);
  if (b % 2)
    return res * res % p * a % p;
  else
    return res * res % p;
}

代码

#include <bits/stdc++.h>
using namespace std;
int t;
unsigned long long n, n_1;
unsigned long long base[8] = {0,2,325,9375,28178,450775,9780504,1795265022};


__int128 binpow(__int128 a, __int128 b, __int128 p) {
  if (b == 0) return 1;
  __int128 res = binpow(a, b / 2, p);
  if (b % 2)
    return res * res % p * a % p;
  else
    return res * res % p;
}

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%llu", &n);
        n_1 = n - 1;
        long long s = 0;
        unsigned long long d = 0;
        int ans = 0;
        while(n_1%2==0){
            n_1/=2;
            s++;
        }
        d = n_1;
        for(int i = 1;i <= 7; i++){
            unsigned long long a = base[i];
            if(a>=n) a = a%n;
            if(a==0||a==1||a==n-1) continue;
            __int128 x0 = binpow((__int128)a, (__int128)d, (__int128)n);
            if(x0==(__int128)1 || x0 == (__int128)(n-1)) continue;
            for(long long r=1; r<=s-1; r++){
                
                __int128 x1 = (x0*x0)%(__int128)n;
                if(x1==(__int128)(n-1)) goto nxt;
                if(x1==(__int128)1){
                    ans = 1;
                    goto daan;
                }
                x0 = x1;
            }
            ans = 1;
            goto daan;
            nxt:{}
        }
        daan: 
        if(ans==1) printf("Not prime\n");
        else printf("prime\n");
    }
    return 0;
}

J Toby 想要穿裙子

题目描述

「Toby」想要穿裙子！

AndroidNeko 告诉她：「如果你能答对以下若干个问题，我就给你买裙子。」

请你帮帮可爱的「Toby」！

具体来说，AndroidNeko 有 $n$ 根应援棒，应援棒有两个属性：颜色和长度。AndroidNeko 想知道，能否用三根颜色互不相同的应援棒组成一个非退化三角形。

设三角形的三边长度为 $a \leq b \leq c$，该三角形是非退化三角形当且仅当 $a + b > c$。

输入格式

第一行一个正整数 $n$ （$1 \leq n \leq 2 \times 10^5$），表示应援棒的数量。

接下来 $n$ 行，第 $i$ （$1 \leq i \leq n$）行两个正整数 $c_i, l_i$ （$1 \leq c_i, l_i \leq 10^9$），表示编号为 $i$ 的应援棒的颜色和长度。

输出格式

若存在三根颜色互不相同的应援棒可以组成一个非退化三角形，输出一行三个互不相同的正整数 $i, j, k$ （$1 \leq i, j, k \leq n$），表示三根应援棒的编号。如果有多种可能的答案，你可以输出任意一种。

否则，输出 I would like to see Toby wear a skirt every day！。

输入样例 1

输出样例 1

2 3 5

输入样例 2

输出样例 2

I would like to see Toby wear a skirt every day！

解析

读不懂题目背景何意味

先按照$l_i$按从小到大排序，可以证明如果有符合条件的三项，则排序后一定存在紧邻的三项满足条件。所以对于$l_i$遍历，且维护“颜色各不相同、且$l$前三大的”三个应援棒，每一次循环根据以下规则更新即可：

若 $c_i$ 与目前维护的 $best$ 中没有冲突颜色

若 $l_{best_1} + l_{best_2} > l_i$ ，即为答案，输出即可；
否则，根据当前应援棒，更新 $best$；

若 $c_i$ 与目前维护中的 $best$ 的一项拥有冲突颜色

若剩余未冲突两项长度之和 $> l_i$ ；
否则，根据当前应援棒，更新 $best$。

（以上思路来自于C2同学的题解）

懒得写这题代码了，主要是到周末了...

Alex Li的学习笔记

不想学习…

F wiki数星星

解析

代码

G ALyCE与堆

解析

代码

H 苹果众数

题解

代码

I 2jogger1与 Miller-Rabin

解析

代码

J Toby 想要穿裙子

解析

1 条评论

添加新评论

C2上机 题目总结

F wiki数星星

解析

代码

G ALyCE与堆

解析

代码

H 苹果众数

题解

代码

I 2jogger1与 Miller-Rabin

解析

代码

J Toby 想要穿裙子

解析

1 条评论

添加新评论

C2上机题目总结