离散化 为什么要离散化处理？ 数据过于多时难以表示数组下标 离散化是什么？ 可以类比哈希表离散化就像哈希一样，只不过是由大映射到小。 比如你有一个长度为1e9数列，其中大部分值都为0，而你要寻找某一区间和，1e9的长度开数组肯定会爆栈，所以我们需要把有效区间缩小至小区间内表示。离散化例题 ac代码：#include <bits/stdc++.h> using ll = long long; const int N = 3e5 + 9; std::vector<int> X; ll a[N]; // 操作和询问 struct Q { ll a, b; } add[N], que[N]; int getindex(ll x) { return std::lower_bound(X.begin(), X.end(), x) - X.begin() + 1; } void vol() { int n, q; std::cin >> n >> q; // 离线处理 for (int i = 1; i <= n; i++) { ll x, w; std::cin >> x >> w; X.push_back(x); add[i] = {x, w}; } for (int i = 1; i <= q; i++) { ll l, r; std::cin >> l >> r; X.push_back(l), X.push_back(r); que[i] = {l, r}; } // 排序去重 std::sort(X.begin(), X.end()); X.erase(std::unique(X.begin(), X.end()), X.end()); for (int i = 1; i <= n; i++) { // 由大到小 int x = getindex(add[i].a); ll w = add[i].b; a[x] += w; } // 前缀和 for (int i = 1; i <= X.size(); i++) { a[i] += a[i - 1]; } for (int i = 1; i <= q; i++) { int l = getindex(que[i].a); int r = getindex(que[i].b); std::cout << a[r] - a[l - 1] << "\n"; } } int main() { std::ios::sync_with_stdio(0), std::cout.tie(0), std::cin.tie(0); int t; t = 1; //std::cin >> t; while (t--) { vol(); } return 0; }

超详细xcpc滚榜教程 首先需要导出比赛的表格1.处理表格最终效果如下图自行添加的列有id，judged，solved，penalty，timeid列按1234顺序problem列使用 ctrl + f 替换成相应题号result列使用 ctrl + f 替换成相应结果小技巧：在第二行使用公式后鼠标移至小格的右下角让鼠标变成黑色十字，按住往下拉即可judged列使用公式=LOWER(IF(A2>10,"true","true"))solved列使用公式=IF(D2="AC","true","false")penalty列使用公式=IF(OR(D2="WA",D2="RE",D2="TLE"),"true","false")time列使用公式=ROUND((E3-(DATE(年,月,日)+TIME(时,分,秒)))*86400,0)注:输入比赛时的年月日，比赛开始时的时分秒2.到网站转换格式成XML点击进入格式转换网站选择Excel下载：点击下载3.将导出文件中的<run>部分粘贴至解压好的文件夹内的mellowsky.xml对应部分,并根据注释按需修改最后需要把全部带#的注释行删除，不然运行报错4.最后在\Cust-Resolver-master文件夹使用命令快乐滚榜resolver.bat mellowsky.xml # 或者 ./resolver.bat mellowsky.xml运行时可能遇到的问题Warning: Contest not finalized Warning: Contest has no freeze time, will use default把注释或者超出部分删除即可不知道在哪里输入命令？按win健后搜索Cust-Resolver-master进入文件夹右键鼠标，选择“在终端中打开”，然后复制粘贴命令，Enter键确定

快速幂 快速幂 用于快速求a^b的算法 思想:拆分 例:求2^13 等价于求 2^1 2^4 2^8 其中13二进制表示(1101).对应十进制的位权为8，4，1. 因此对于求幂，我们可以将指数的二进制表示数每位所对应的十进制的位权作为拆分后的指数. 复杂度不难看出是O(logn).#include <iostream> int main () { int a, b; std::cin >> a >> b; long long ans = 1; while(b) { if(b & 1) { ans *= a; } a *= a; b >>= 1; } std::cout << ans; return 0; }

高精度运算(加减乘除) 在程序中高精度加法和高精度减法的运算本质是模拟我们在小学就学过的运算规则，也是我们平时用的运算规则：相加大于10就进1，相减小于就向高位借.高精度加法//高精度加法 #include <iostream> #include <string> #include <vector> #include <algorithm> //a,b字符串用于存入两个大数 std::string a, b; //m,n分别逆序存入a,b std::vector <int> m, n, p; //la,lb用于记录a,b的位数 int la, lb; void highPrecisionAddition() { int sum = 0; for (int i = 0; i < la || i < lb; i++) { if (i < la) { sum += m[i]; } if (i < lb) { sum += n[i]; } p.push_back(sum % 10); sum /= 10; } if (sum) { p.push_back(sum); } } int main() { //以字符串形式存放 std::cin >> a; std::cin >> b; la = a.size(); lb = b.size(); //将字符串按位逆序存入数组m, n for (int i = la - 1; i >= 0; i--) { m.push_back(a[i] - '0'); } for (int i = lb - 1; i >= 0; i--) { n.push_back(b[i] - '0'); } highPrecisionAddition(); reverse(p.begin(), p.end()); for (auto i : p) { std::cout << i; } return 0; }高精度减法//高精度减法 #include <iostream> #include <string> #include <vector> #include <algorithm> std::string a, b; std::vector <int> m, n, p; int la, lb; bool cmp() { if (la != lb) { return la > lb; } for (int i = la - 1; i >= 0; i--) { if (m[i] != n[i]) { return m[i] > n[i]; } } return true; } void highPrecisionSubtraction(std::vector <int> &m, std::vector <int> &n) { int sub = 0; for (int i = 0; i < la || i < lb; i++) { sub = m[i]; if (i < lb) { sub -= n[i]; } if (sub < 0) { m[i + 1]--; sub += 10; } p.push_back(sub); } //去除前面多余的零，保证输出时前面不出现零 while (p.size() > 1 && !p.back()) { p.pop_back(); } } int main () { std::cin >> a; std::cin >> b; la = a.size(); lb = b.size(); for (int i = la - 1; i >= 0; i--) { m.push_back(a[i] - '0'); } for (int i = lb - 1; i >= 0; i--) { n.push_back(b[i] - '0'); } //如果输入是小减大则需要输出负号 if (!cmp()) { //保证highPrecisionSubtraction里是大减小 std::swap(m, n); std::cout << "-"; } highPrecisionSubtraction(m, n); reverse(p.begin(), p.end()); for (auto i : p) { std::cout << i; } return 0; }高精度乘法 在程序中的高精度乘法也与我们平时的运算差不多，略有不同. //高精度乘法 #include <iostream> #include <string> #include <vector> #include <algorithm> std::string a, b; std::vector <int> m, n; int la, lb; void highPrecisionMultiplication(std::vector <int>& p) { for (int i = 0; i < la; i++) { for (int j = 0; j < lb; j++) { p[i + j] += m[i] * n[j]; p[i + j + 1] += p[i + j] / 10; p[i + j] %= 10; } } while (p.size() > 1 && !p.back()) { p.pop_back(); } } int main() { std::cin >> a; std::cin >> b; la = a.size(); lb = b.size(); std::vector <int> p(la + lb); for (int i = la - 1; i >= 0; i--) { m.push_back(a[i] - '0'); } for (int i = lb - 1; i >= 0; i--) { n.push_back(b[i] - '0'); } highPrecisionMultiplication(p); std::reverse(p.begin(), p.end()); for (auto i : p) { std::cout << i; } return 0; } 高精度除法 高精度除法的被除数为大数，而除数相对较小在整型范围内运算规则同平时在纸上所列的计算方法#include <iostream> #include <string> #include <vector> std::string a; int n; std::vector <int> m, p; int la, lb; void highPrecisionDivision() { long long r = 0; for (int i = la - 1; i >= 0; i--) { r = r * 10 + m[i]; p.push_back(r / n); r %= n; } while (p.size() > 1 && !p.back()) { p.pop_back(); } } int main () { std::cin >> a; std::cin >> n; la = a.size(); for (int i = la - 1; i >= 0; i--) { m.push_back(a[i] - '0'); } highPrecisionDivision(); for (auto i : p) { std::cout << i; } return 0; }

素数筛法(埃氏筛法、线性筛法) 素数筛法:用于筛选出素数核心思想:用一个数筛选其余的数普通筛法:时间复杂度为O(nlogn)#include <iostream> #define N 100 bool vis[N] = { false };// 0到N-1的元素都没有被标记 int primes[N]; // 存放素数 int tot; //普通筛法 int main() { vis[0] = vis[1] = true; // 0和1不是素数 for (int i = 2; i < N; i++) { if (!vis[i]) { primes[++tot] = i; // 找到一个素数，存放到primes中 } for (int j = 2 * i; j < N; j += i) { vis[j] = true; // 将i的倍数都标记为已被筛掉 } } for (int i = 1; i < tot; i++) { std::cout << primes[i] << " "; } std::cout << std::endl; return 0; }继续优化的话可以 只用质数去筛 ，这也就是埃氏筛法:时间复杂度为:O(nloglogn)int main() { vis[0] = vis[1] = true; // 0和1不是素数 for (int i = 2; i < N; i++) { if (!vis[i]) { primes[++tot] = i; // 找到一个素数，存放到primes中 for (int j = i * i; j < N; j += i) { vis[j] = true; // 将i的倍数都标记为已被筛掉 } } } for (int i = 1; i < tot; i++) { std::cout << primes[i] << " "; } std::cout << std::endl; return 0; }继续优化 线性筛 : 每个数都被其最小的质因数筛掉 时间复杂度为O(n)int main() { vis[0] = vis[1] = true; for (int i = 2; i <= N; i++) { if (!vis[i]) { primes[++tot] = i; } for (int j = 1; i * primes[j] < N; j++) { vis[i * primes[j]] = true; if (i % primes[j] == 0) { break; } } } for (int i = 1; i < tot; i++) { std::cout << primes[i]<< " "; } std::cout << std::endl; return 0; }