当输入数据 >= 10^5 时，用 scanf，printf
注意边界情况特判！！！！比如为空之类的！
向上取整：(n + m - 1) / m;
bfs()搜索时，在加入队列时，就需要标记已经被搜过
如果向让数字逆序，则在加入容器时加负号即可
strcmp(od, "Pop") == 0
long double 精度比 double 高
long double res = 123.45554;
printf("%.2Lf\n", res);
vector的erase函数：
ets.erase(ets.begin() + k, ets.end());
vector可以初始指定大小或者 v.resize(k) 大小
二维 vector 初始化
vector<vector<int>> res(r, vector<int>(c));
匿名函数使用
sort(top_k, top_k + k, [](int x, int y){
if(cnt[x] != cnt[y]) return cnt[x] > cnt[y];
return x < y;
});
数字转字符串函数
int x = 123;
string s = to_string(x);
字符串转数字 整数: stoi(), 小数: stof();
stof的使用
try{
size_t k;
x = stof(a, &k);
}catch(...){}
字符串可以直接和char类型的字符直接相加！
cout 可以直接输出字符数组
char str[10] = "abc";
cout << str << endl;
C++ string类型可以直接比较字典序大小！
如果时间以标准字符串格式读入: “hh:mm:ss”，则可以直接用字典序比较时间大小！
如果需要时间计算的话，可以如下读：
scanf("%02d:%02d:%02d", &hh, &mm, &ss);
string 类型判空：
string s;
if(s.empty()){}
读取一行字符串(记得getchar)：
string s;
getline(cin, s);
字符大小写转换函数：
char c = 'A';
c = tolower(c);
c = toupper(c);
也可以手写to_lower函数：
char to_lower(char c){
if('A' <= c && c <= 'Z') return c + 32;
return c;
}
字符串用%s输出：
string s = "123";
printf("%s", s.c_str());
double 类型变量也可以进行判0操作
double a = 0;
if(!a){}; if(a){};
C++ 中字符数组可以自动转换为字符串：
string s; char cs[25] = "123";
s = cs;
给字符串进行格式化的函数：
sscanf:
getline(cin, line);
sscanf(line.c_str(), "%d:%d:%d", &h1, &m1, &s1);
sprintf:
char format_str[25]; int a=1, b=2, c=3;
sprintf(format_str, "%02d:%02d:%02d", a, b, c);
string s = format_str;
区间问题可以考虑用前缀和优化
结构体sort排序需要重载 “<” （小于号），优先队列中要重载大于号 “>”（大于号）：
bool operator < (const Person & t) const{ // sort 排序
if(start_time != t.start_time) return start_time < t.start_time;
return arrive_time < t.arrive_time;
}
bool operator > (const Person & t) const{ // 优先队列中比较大小
return arrive_time > t.arrive_time;
}
round/ceil/floor 函数在 cmath库
多项式相加：对应指数的系数相加
多项式相乘：c[i+j] += a[i]*b[j]
vector可以进行比较
vector<int> a, b; ...
if(a == b){}
将 vector a 中的元素反转
1. vector<int> b(a.rbegin(), a.rend());
2. reverse(a.begin(), a.end());
vector传参时，尽量用引用，减少赋值！
增强遍历vector/map/unordered_map/set/unordered_set时，尽量用引用
秦九韶算法：
string s = "1010";
for(auto c:s) res = res * radix + (c-'0');
10进制转其他进制时，循环对进制取模后整除进制
while(x) s = get(x % base) + s, x /= base;
如果一个进制转成其他进制时为两位数，则：
int a = get(x / base), b = get(x % base);
从字符串中读取数据：
#include<sstream>
getline(cin, line);
stringstream ssin(line);
int x; ssin >> x;
string ws, res;
while(ssin >> ws) res += ws;
如果有字符串的映射的话，可以考虑 unordered_map
在有序列表中找某个数，可以考虑二分优化！！！
二分优化某题时，先要看是否在区间上满足二分的性质！！
引用相当于两个变量指向同一位置的内存：
auto &v = mp[name];
如果一个节点信息比较多可以用结构体存储！
结构体的构造方法与成员方法
struct Student{
string id;
int grade[K];
int cnt; // 满分数量
int pass_cnt; // 通过编译数
int total_score; // 总分数
Student(){
}
Student(string uid){
id = uid;
for(int i = 0; i <= k; i++) grade[i] = -2;
}
void calc(){
cnt = 0;
total_score = 0;
pass_cnt = 0;
for(int i = 1; i <= k; i++){
if(g[i] == grade[i]) cnt++;
if(grade[i] >= 0) pass_cnt++;
if(grade[i] == -1) grade[i] = 0;
total_score += max(0, grade[i]);
}
}
bool operator < (const Student &t) const{
if(total_score != t.total_score) return total_score > t.total_score;
if(cnt != t.cnt) return cnt > t.cnt;
return id < t.id;
}
};
// 使用
if(!sts.count(u_id)) sts[u_id] = Student(u_id);
// 使用默认构造
struct Node{
int id, x, y;
Node(): x(0),y(0),id(0){}
};
插入排序：前面已经排序好（非递减顺序），而后面没变
void down(int t, int n){
int u = t;
if(t * 2 <= n && q[u] < q[t * 2]) u = 2 * t;
if(t * 2 + 1 <= n && q[u] < q[t * 2 + 1]) u = 2 * t + 1;
if(t != u){
swap(q[u], q[t]);
down(u, n);
}
}
————————————————
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i]; // 原数组
for(int i = 1; i <= n; i++) cin >> q[i]; // 排序中的数组
// 插入排序：前面已经排序好（非递减顺序），而后面没变
int k = 2;
while(k <= n && q[k] >= q[k - 1]) k++;
int m = k;
while(k <= n && a[k] == q[k]) k++;
if(k == n + 1){ // 插入排序
puts("Insertion Sort");
//while(m > 1 && q[m] < q[m - 1]) swap(q[m], q[m - 1]), m--;
sort(q + 1, q + m + 1);
}else{ // 堆排序：排序好的那些元素一定大于等于堆顶元素
puts("Heap Sort");
m = n;
while(m >= 1 && q[m] >= q[1]) m--;
swap(q[1], q[m]);
down(1, m - 1);
}
归并排序：len = 2, 4, 8, 16…
void print(int a[]){
cout << a[0];
for(int i = 1; i < n; i++) cout << ' ' << a[i];
cout << endl;
}
bool check(){
for(int i = 0; i < n; i++)
if(a[i] != b[i])
return false;
return true;
}
---------------
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++) cin >> b[i];
int k = 1;
while(k < n && b[k] >= b[k-1]) k++;
int m = k;
while(k < n && b[k] == a[k]) k++;
if(k == n){
puts("Insertion Sort");
sort(b, b + m + 1);
print(b);
}else{
puts("Merge Sort");
int k = 1;
// 归并排序：len = 2, 4, 8, 16...
while(true){
int len = 1 << k;
bool flag = check();
for(int i = 0; i < n; i += len) sort(a + i, a + min(n, i + len));
if(flag) break;
k++;
}
print(a);
}
高精度加法：
vector<int> add(vector<int>& a, vector<int>& b){
vector<int> c;
int t = 0;
for(int i = 0; i < a.size() || i < b.size() || t; i++){
if(i < a.size()) t += a[i];
if(i < b.size()) t += b[i];
c.push_back(t % 10);
t /= 10;
}
return c;
}
一个二叉树，树中每个节点的权值互不相同,进行建树：
unordered_map<int, int> l, r, pos;
int postorder[N], inorder[N];
int n, q[N];
int build(int il, int ir, int pl, int pr){
int root = postorder[pr];
int k = pos[root];
if(il < k){
l[root] = build(il, k - 1, pl, pl + (k - 1 - il));
}
if(ir > k){
r[root] = build(k + 1, ir, pl + (k - 1 - il) + 1, pr - 1);
}
return root;
}
for(int i = 0; i < n; i++) cin >> postorder[i];
for(int i = 0; i < n; i++) {
cin >> inorder[i];
pos[inorder[i]] = i;
}
给定中序遍历和（前序/后序）遍历中的任意一个，在建树(build)过程中就可以求得(后序/前序)遍历的结果，
而如果要求层序遍历的结果，则需要将树重建出来再bfs()
（二叉搜索树的中序遍历的结果一定是有序的！！！）
判断二叉搜索树（判断给定的前序遍历的序列是否是二叉搜索树或者其镜像的遍历结果）：
// 二叉搜索树的中序遍历的结果一定是有序的！！！
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, cnt;
int preorder[N], inorder[N], postorder[N];
bool build(int il, int ir, int pl, int pr, int type){
if(il > ir) return true;
int root = preorder[pl];
int k;
// 正常
if(type == 0){
for(k = il; k <= ir; k++)
if(inorder[k] == root)
break;
if(k > ir) return false;
}else{ // 镜像（镜像后右边是严格小于，左边是大于等于）
for(k = ir; k >= il; k--)
if(inorder[k] == root)
break;
if(k < il) return false;
}
bool res = true;
if(!build(il, k - 1, pl + 1, pl + 1 + (k - 1 - il), type)) res = false;
if(!build(k + 1, ir, pr - (ir - k - 1), pr, type)) res = false;
postorder[cnt++] = root; // 建树过程中确定后续遍历
return res;
}
int main(){
cin >> n;
for(int i = 0; i < n; i++){
cin >> preorder[i];
inorder[i] = preorder[i];
}
sort(inorder, inorder + n);
if(build(0, n - 1, 0, n - 1, 0)){
puts("YES");
cout << postorder[0];
for(int i = 1; i < n; i++) cout << ' ' << postorder[i];
}else{
reverse(inorder, inorder + n);
cnt = 0;
if(build(0, n - 1, 0, n - 1, 1)){
puts("YES");
cout << postorder[0];
for(int i = 1; i < n; i++) cout << ' ' << postorder[i];
}else{
puts("NO");
}
}
return 0;
}
完全二叉搜索树（给定完全二叉搜索树的前/后序遍历结果，求层序遍历的结果）：
void dfs(int u){
if(u * 2 <= n) dfs(u * 2);
tr[u] = a[idx++];
if(u * 2 + 1 <= n) dfs(u * 2 + 1);
}
for(int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
dfs(1);
给定一组前序遍历和后序遍历，请你输出对应二叉树的中序遍历
int dfs(int l1, int r1, int l2, int r2, string& s){
if(l1 > r1) return 1;
if(pre[l1] != post[r2]) return 0;
int cnt = 0;
// 枚举前序遍历左子树右端点
for(int i = l1; i <= r1; i++){
string ls, rs;
int lcnt = dfs(l1 + 1, i, l2, l2 + i - l1 - 1, ls);
int rcnt = dfs(i + 1, r1, l2 + i - l1 - 1 + 1, r2 - 1, rs);
if(lcnt && rcnt){
s = ls + to_string(pre[l1]) + ' ' + rs;
cnt += lcnt * rcnt;
if(cnt > 1) break;
}
}
return cnt;
}
Z 字形遍历二叉树
while(hh <= tt){
int head = hh, tail = tt;
while(hh <= tail){
int u = q[hh++];
if(l.count(u)) q[++tt] = l[u];
if(r.count(u)) q[++tt] = r[u];
}
if(++step % 2) reverse(q + head, q + tail + 1);
}
AVL树
#include<iostream>
using namespace std;
const int N = 30;
int n;
int l[N], r[N], v[N], h[N], idx;
void update(int u){
h[u] = max(h[l[u]], h[r[u]]) + 1;
}
int get_balance(int u){
return h[l[u]] - h[r[u]];
}
void L(int &u){
int t = r[u];
r[u] = l[t], l[t] = u;
update(u), update(t); // 旋转完记得更新高度
u = t;
}
void R(int &u){
int t = l[u];
l[u] = r[t], r[t] = u;
update(u), update(t);
u = t;
}
void insert(int &u, int w){
if(!u){
u = ++idx;
v[u] = w;
}else if(w < v[u]){
insert(l[u], w);
if(get_balance(u) == 2){
if(get_balance(l[u]) == 1) R(u);
else L(l[u]), R(u);
}
}else{
insert(r[u], w);
if(get_balance(u) == -2){
if(get_balance(r[u]) == -1) L(u);
else R(r[u]), L(u);
}
}
update(u);
}
int main(){
cin >> n;
int root = 0;
int x;
for(int i = 0; i < n; i++) cin >> x, insert(root, x);
cout << v[root];
return 0;
}
bfs的另一种写法(一次搜一层)
int l = 1;
q[1].push_back(1);
while(q[l].size()){
for(auto u: q[l]){
for(int i = 1; i <= n; i++)
if(g[u][i])
q[l + 1].push_back(i);
}
l++;
}
----
queue<int> q;
q.push(u);
st[u] = true;
int res = 0;
for(int i = 0; i < l; i++){
int m = q.size();
res += m;
for(int j = 0; j < m; j++){
int t = q.front();
q.pop();
for(int k = h[t]; ~k; k = ne[k])
if(!st[e[k]]) q.push(e[k]), st[e[k]] = true;
}
}
---
while(hh <= tt){
int head = hh, tail = tt;
while(hh <= tail){
int u = q[hh++];
if(l.count(u)) q[++tt] = l[u];
if(r.count(u)) q[++tt] = r[u];
}
if(++step % 2) reverse(q + head, q + tail + 1);
}
dijkstra拓展
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 510;
int n, m, S, T;
int g[N][N], w[N][N];
int dist[N], cost[N];
int pre[N];
bool st[N];
void dijkstra(){
memset(dist, 0x3f, sizeof dist);
memset(cost, 0x3f, sizeof cost);
dist[S] = 0, cost[S] = 0;
for(int i = 0; i < n; i++){
int t = -1;
for(int j = 0; j < n; j++)
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
st[t] = true;
if(t == T) break;
for(int j = 0; j < n; j++)
if(dist[t] + g[t][j] < dist[j]){
dist[j] = dist[t] + g[t][j];
cost[j] = cost[t] + w[t][j];
pre[j] = t;
}else if(dist[t] + g[t][j] == dist[j] && cost[t] + w[t][j] < cost[j]){
cost[j] = cost[t] + w[t][j];
pre[j] = t;
}
}
}
int main(){
memset(g, 0x3f, sizeof g);
memset(w, 0x3f, sizeof w);
cin >> n >> m >> S >> T;
while(m--){
int a, b, c, d;
cin >> a >> b >> c >> d;
// 让路径和花费对应
if(c < g[a][b]){
g[a][b] = g[b][a] = c;
w[a][b] = w[b][a] = d;
}else if(c == g[a][b] && d > w[a][b]){
w[a][b] = w[b][a] = d;
}
}
dijkstra();
vector<int> res;
for(int i = T; i != S; i = pre[i]) res.push_back(i);
cout << S;
for(int i = res.size() - 1; i >= 0; i--) cout << ' ' << res[i];
cout << ' ' << dist[T] << ' ' << cost[T];
return 0;
}
-------------
#include<iostream>
#include<cstring>
#include<vector>
#include<unordered_map>
using namespace std;
const int N = 210;
int n, k;
string S, T;
unordered_map<string, int> mp;
string city[N];
int v[N], g[N][N];
// 起点的距离,幸福感最大,路径上经过的点,路径数, 上一个节点
int dist[N], cost[N], cnt[N], pcnt[N], pre[N];
bool st[N];
void djikstra(int s, int end){
memset(dist, 0x3f, sizeof dist);
dist[s] = 0, cost[s] = 0, cnt[s] = 0, pcnt[s] = 1;
for(int i = 0; i < n; i++){
int t = -1;
for(int j = 0; j < n; j++)
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
st[t] = true;
if(t == end) break;
for(int j = 0; j < n; j++)
if(dist[j] > dist[t] + g[t][j]){
dist[j] = dist[t] + g[t][j];
cost[j] = cost[t] + v[j];
cnt[j] = cnt[t] + 1;
pcnt[j] = pcnt[t];
pre[j] = t;
}else if(dist[j] == dist[t] + g[t][j]){
pcnt[j] += pcnt[t];
if(cost[j] < cost[t] + v[j]){
cost[j] = cost[t] + v[j];
cnt[j] = cnt[t] + 1;
pre[j] = t;
}else if(cost[j] == cost[t] + v[j] && cnt[j] > cnt[t] + 1){
cnt[j] = cnt[t] + 1;
pre[j] = t;
}
}
}
}
int main(){
memset(g, 0x3f, sizeof g);
cin >> n >> k >> S;
T = "ROM";
mp[S] = 0;
city[0] = S;
for(int i = 1; i < n; i++){
string s;
cin >> s >> v[i];
city[i] = s;
mp[s] = i;
}
while(k--){
int w;
string x, y;
cin >> x >> y >> w;
int a = mp[x], b = mp[y];
g[a][b] = g[b][a] = min(g[a][b], w);
}
int s = mp[S], t = mp[T];
djikstra(s, t);
cout << pcnt[t] << ' ' << dist[t] << ' ' << cost[t] << ' ' << cost[t] / cnt[t] << endl;
cout << S;
vector<int> res;
for(int i = t; i != s; i = pre[i]) res.push_back(i);
for(int i = res.size() - 1; i >= 0; i--)
cout << "->" << city[res[i]];
return 0;
}
----------
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 510, M = N * N;
int n, m, S, T;
int h[N], e[M], ne[M], w1[M], w2[M], idx;
int dist1[N], dist2[N], pre[N];
bool st[N];
void add(int a, int b, int c, int d){
e[idx] = b, w1[idx] = c, w2[idx] = d, ne[idx] = h[a], h[a] = idx++;
}
pair<int, vector<int>> dijkstra(int w1[], int w2[], int type){
memset(dist1, 0x3f, sizeof dist1);
memset(dist2, 0x3f, sizeof dist2);
memset(st, 0, sizeof st);
dist1[S] = dist2[S] = 0;
for(int i = 0; i < n; i++){
int t = -1;
for(int j = 0; j < n; j++)
if(!st[j] && (t == -1 || dist1[j] < dist1[t]))
t = j;
st[t] = true;
for(int u = h[t]; ~u; u = ne[u]){
int j = e[u];
int w;
if(type) w = 1;
else w = w2[u];
if(dist1[j] > dist1[t] + w1[u]){
dist1[j] = dist1[t] + w1[u];
dist2[j] = dist2[t] + w;
pre[j] = t;
}else if(dist1[j] == dist1[t] + w1[u] && dist2[j] > dist2[t] + w){
dist2[j] = dist2[t] + w;
pre[j] = t;
}
}
}
vector<int> vs;
for(int i = T; i != S; i = pre[i]) vs.push_back(i);
return {dist1[T], vs};
}
int main(){
memset(h, -1, sizeof h);
cin >> n >> m;
while(m--){
int a, b, c, d, type;
cin >> a >> b >> type >> c >> d;
add(a, b, c, d);
if(!type) add(b, a, c, d);
}
cin >> S >> T;
pair<int, vector<int>> pa, pb;
pa = dijkstra(w1, w2, 0);
pb = dijkstra(w2, w1, 1);
vector<int> res;
if(pa.second == pb.second){
printf("Distance = %d; Time = %d: ", pa.first, pb.first);
res = pa.second;
cout << S;
for(int i = res.size() - 1; i >= 0; i--) cout << " -> " << res[i];
}else{
printf("Distance = %d: ", pa.first);
res = pa.second;
cout << S;
for(int i = res.size() - 1; i >= 0; i--) cout << " -> " << res[i];
printf("\nTime = %d: ", pb.first);
res = pb.second;
cout << S;
for(int i = res.size() - 1; i >= 0; i--) cout << " -> " << res[i];
}
return 0;
}
地铁地图
// 1. 在一条地铁线的任意两个站点之间建边
// 2. 换线最少就转换成经过的点最少的问题
// 3. 此题在建边时注意是否是环
// 4. 此题由于点数多，所以只能用邻接表 + 堆优化版dijkstra
#include<iostream>
#include<cstring>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 10010, M = 1000010;
int n, m;
int h[N], e[M], ne[M], w[M], line[M], idx;
int dist[N], cnt[N], pre[N];
string info[N];
bool st[N];
void add(int a, int b, int c, int d){
e[idx] = b, w[idx] = c, line[idx] = d, ne[idx] = h[a], h[a] = idx++;
}
string get_number(int x){
char number[20];
sprintf(number, "%04d", x);
return number;
}
void dijkstra(int start, int end){
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, start});
dist[start] = cnt[start] = 0;
while(heap.size()){
auto t = heap.top();
heap.pop();
int cur = t.y;
if(st[cur]) continue;
st[cur] = true;
if(end == cur) break;
for(int i = h[cur]; ~i; i = ne[i]){
int j = e[i];
if(dist[j] > dist[cur] + w[i]){
dist[j] = dist[cur] + w[i];
pre[j] = cur;
cnt[j] = cnt[cur] + 1;
info[j] = "Take Line#" + to_string(line[i])
+ " from " + get_number(cur) + " to " + get_number(j) + ".";
heap.push({dist[j], j});
}else if(dist[j] == dist[cur] + w[i] && cnt[j] > cnt[cur] + 1){
pre[j] = cur;
cnt[j] = cnt[cur] + 1;
info[j] = "Take Line#" + to_string(line[i])
+ " from " + get_number(cur) + " to " + get_number(j) + ".";
}
}
}
cout << dist[end] << endl;
vector<string> res;
for(int i = end; i != start; i = pre[i]) res.push_back(info[i]);
for(int i = res.size() - 1; i >= 0; i--)
cout << res[i] << endl;
}
int main(){
memset(h, -1, sizeof h);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> m;
vector<int> s;
int x;
for(int j = 0; j < m; j++) cin >> x, s.push_back(x);
for(int j = 0; j < m; j++)
for(int k = 0; k < j; k++){
int c;
if(s[0] == s[m - 1]) c = min(j - k, m - 1 - j + k);
else c = j - k;
add(s[j], s[k], c, i), add(s[k], s[j], c, i);
}
}
int k;
cin >> k;
while(k--){
int start, end;
cin >> start >> end;
dijkstra(start, end);
}
return 0;
}
去重
sort(boys.begin(), boys.end());
boys.erase(unique(boys.begin(), boys.end()), boys.end());
在拓扑图中，如果A指向B，则在拓扑序列中，A一定在B的前面（即A的下标小于B的下标）
简单回路：访问每个点一次且仅一次的回路
计数类DP: (1的个数)
/*
求 x 在每一位出现的次数相加即可
abcdefg
假如当前位是d, 且 x > 0
左边取
0~abc-1时, 右边可以取 0 ~ 999 ==》 abc * 1000种
左边取
abc时
x > d => 0
x == d 右边可以取 0 ～ efg ==》efg + 1 种
x < d 右边可以取 0 ～ 999 ==》1000 种
x == 0 时 只能从左边第二位为x开始统计，因为最高位不为0，并且前面必须从 001 ~ abc
*/
#include<iostream>
#include<vector>
using namespace std;
int get_number(vector<int> &nums, int r, int l){
int res = 0;
for(int i = r; i >= l; i--) res = res * 10 + nums[i];
return res;
}
int power10(int k){
int res = 1;
while(k--) res *= 10;
return res;
}
int count(int n, int x){
vector<int> nums;
while(n) nums.push_back(n % 10), n /= 10;
n = nums.size();
int sum = 0;
for(int i = n - 1 - !x; i >= 0; i--){
int left = get_number(nums, n - 1, i + 1);
int right = get_number(nums, i - 1, 0);
int res = left * power10(i);
int d = nums[i];
if(x == d) res += right + 1;
else if(x < d) res += power10(i);
if(!x) res -= power10(i);
sum += res;
}
return sum;
}
int main(){
int n;
cin >> n;
cout << count(n, 1);
return 0;
}
所有子区间中所有数字的总和
#include<iostream>
using namespace std;
int main(){
long double res = 0, x;
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> x;
res += x * i * (n - i + 1);
}
printf("%.2Lf\n", res);
return 0;
}
连续因子
vector<int> res;
int max_len = 0;
for(int i = 2; i <= n / i; i++){
if(n % i == 0){
int k = i, x = n;
while(x % k == 0) x /= k, k++;
if(k - i > max_len){
max_len = k - i;
res.clear();
for(int j = i; j < k; j++) res.push_back(j);
}
}
}
if(res.empty()) res.push_back(n);
cout << res.size() << endl;
cout << res[0];
for(int i = 1; i < res.size(); i++) cout << "*" << res[i];
整数分解（dfs+剪枝）：
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int n, k, p;
int v[25];
vector<int> ans, path;
int max_sum = -1;
void dfs(int n, int cnt, int sum, int m){
if(cnt == k){
if(n == 0 && sum > max_sum){
max_sum = sum;
ans = path;
}
return;
}
for(int i = m; i >= 1; i--){
if(n - v[i] >= 0 && cnt + 1 <= k) {
path[cnt] = i;
dfs(n - v[i], cnt + 1, sum + i, i);
}
}
}
int main(){
cin >> n >> k >> p;
path.resize(k);
int x, i;
for(i = 1; x <= n && i <= 23; i++){
x = pow(i, p);
v[i] = x;
}
dfs(n, 0, 0, i - 1);
if(max_sum == -1) puts("Impossible");
else{
cout << n << " = ";
printf("%d^%d", ans[0], p);
for(int i = 1; i < ans.size(); i++)
printf(" + %d^%d", ans[i], p);
}
return 0;
}
|a v b| = |a| + |b| - |a ^ b|
PAT 计数：
解法一：找规律
#include<iostream>
using namespace std;
const int mod = 1000000007;
int main(){
string str;
cin >> str;
int a = 0, b = 0, res = 0;
for(auto c: str)
if(c == 'P') a++;
else if(c == 'A') b += a;
else res = (res + b) % mod;
cout << res % mod << endl;
return 0;
}
解法二：DP（状态机）
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010, mod = 1000000007;
int f[N][5];
string s = " PAT";
char str[N];
int main(){
scanf("%s", str + 1);
int n = strlen(str + 1);
f[0][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= 3; j++){
f[i][j] = f[i - 1][j] % mod;
if(str[i] == s[j]) f[i][j] = (f[i][j] + f[i-1][j-1]) % mod;
}
}
cout << f[n][3] % mod << endl;
return 0;
}
哈希（正增量的二次探测法）：
#include<iostream>
using namespace std;
const int N = 10050;
int sz, n, m;
int h[N];
bool is_prime(int x){
if(x < 2) return false;
for(int i = 2; i <= x / i; i++)
if(x % i == 0)
return false;
return true;
}
int find(int x, int &cnt){
int st = x % sz;
cnt = 1;
for(int i = 0; i < sz; i++){
int p = (st + i * i) % sz;
if(!h[p] || h[p] == x)
return p;
cnt++;
}
return -1;
}
int main(){
cin >> sz >> n >> m;
while(!is_prime(sz)) sz++;
int x, cnt;
for(int i = 0; i < n; i++){
cin >> x;
int p = find(x, cnt);
if(p == -1) printf("%d cannot be inserted.\n", x);
else h[p] = x;
}
int sum = 0;
for(int i = 0; i < m; i++){
int x;
cin >> x;
find(x, cnt);
sum += cnt;
}
printf("%.1lf", sum * 1.0 / m);
return 0;
}
最佳彩色带：
#include<iostream>
using namespace std;
const int N = 210, M = 10010;
int n, m, l;
int f[N][M];
int a[N], b[M];
int main(){
cin >> n;
cin >> m;
for(int i = 1; i <= m; i++) cin >> a[i];
cin >> l;
for(int i = 1; i <= l; i++) cin >> b[i];
for(int i = 1; i <= m; i++){
for(int j = 1; j <= l; j++){
f[i][j] = max(f[i-1][j], f[i][j-1]);
if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i][j-1] + 1);
}
}
cout << f[m][l] << endl;
return 0;
}
最大子序列和：
解法一（枚举）
#include<iostream>
using namespace std;
const int N = 10010;
int a[N];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
int sum = 0, l, r, start = 0, max_sum = -1;
for(int i = 0; i < n; i++){
sum += a[i];
if(sum > max_sum) max_sum = sum, l = start, r = i;
if(sum < 0) sum = 0, start = i + 1;
}
if(max_sum == -1) cout << 0 << ' ' << a[0] << ' ' << a[n-1];
else cout << max_sum << ' ' << a[l] << ' ' << a[r];
return 0;
}
解法二（DP）
dp1
#include<iostream>
using namespace std;
const int N = 10010;
int a[N], f[N];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
f[0] = -1e9;
int max_sum = -1, start = 1, l, r;
for(int i = 1; i <= n; i++){
f[i] = max(f[i-1] + a[i], a[i]);
if(f[i] < 0) start = i + 1;
if(max_sum < f[i]) max_sum = f[i], r = i, l = start;
}
if(max_sum == -1) max_sum = 0, l = 1, r = n;
cout << max_sum << ' ' << a[l] << ' ' << a[r];
return 0;
}
dp2
#include<iostream>
using namespace std;
const int N = 10010;
int a[N], f[N];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
f[0] = -1e9;
for(int i = 1; i <= n; i++)
f[i] = max(f[i-1] + a[i], a[i]);
int max_sum = -1, end = -1, start = -1;
for(int i = 1; i <= n; i++)
if(max_sum < f[i])
max_sum = f[i], end = i;
for(int i = end; i >= 0; i--)
if(f[i] < 0){
start = i + 1;
break;
}
if(max_sum == -1) cout << 0 << ' ' << a[1] << ' ' << a[n];
else cout << max_sum << ' ' << a[start] << ' ' << a[end];
return 0;
}
并查集合并时，合并一次连通分量减一！
并查集题一般可以先将边存下来，后面再合并！！
并查集：家产
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 10010;
struct Edge{
int a, b;
}e[N];
struct Family{
int id;
int ha, hc, cnt;
bool operator < (const Family &W) const{
if(ha * W.cnt != cnt * W.ha)
return ha * W.cnt > cnt * W.ha;
return id < W.id;
}
};
int n;
int p[N], c[N], hc[N], ha[N];
bool st[N];
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void init(){
for(int i = 0; i < N; i++) p[i] = i, c[i] = 1;
}
int main(){
cin >> n;
init();
int k = 0;
for(int i = 0; i < n; i++){
int id, fa, mr;
cin >> id >> fa >> mr;
st[id] = true;
if(fa != -1) e[k++] = {fa, id};
if(mr != -1) e[k++] = {mr, id};
int cnt;
cin >> cnt;
for(int i = 0; i < cnt; i++){
int child;
cin >> child;
e[k++] = {child, id};
}
cin >> hc[id] >> ha[id];
}
for(int i = 0; i < k; i++){
int a = e[i].a, b = e[i].b;
st[a] = st[b] = true;
int pa = find(a), pb = find(b);
if(pa != pb){
if(pa < pb) swap(pa, pb);
c[pb] += c[pa];
ha[pb] += ha[pa];
hc[pb] += hc[pa];
p[pa] = pb;
}
}
vector<Family> res;
for(int i = 0; i < N; i++){
if(st[i] && find(i) == i){
Family f = {i, ha[i], hc[i], c[i]};
res.push_back(f);
}
}
sort(res.begin(), res.end());
cout << res.size() << endl;
for(auto &t: res)
printf("%04d %d %.3lf %.3lf\n", t.id, t.cnt, t.hc*1.0/t.cnt, t.ha*1.0/t.cnt);
return 0;
}
树型DP（记忆化搜索）
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 100010;
int n;
double P, R;
int f[N], p[N];
int dfs(int x){
if(f[x] != -1) return f[x];
if(p[x] == -1) return f[x] = 0;
return f[x] = dfs(p[x]) + 1;
}
int main(){
memset(f, -1, sizeof f);
memset(p, -1, sizeof p);
scanf("%d%lf%lf", &n, &P, &R);
double res = 0;
for(int i = 0; i < n; i++){
int k;
scanf("%d", &k);
for(int j = 0; j < k; j++){
int son;
scanf("%d", &son);
p[son] = i;
}
if(k == 0){
int cnt;
scanf("%d", &cnt);
res += cnt * P * pow((1 + R*0.01), dfs(i));
}
}
printf("%.1lf", res);
return 0;
}
最低公共祖先：
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N = 10010;
int n, m;
unordered_map<int, int> pos;
int seq[N];
int pre[N], in[N];
int p[N], d[N];
int build(int il, int ir, int pl, int pr, int depth){
int root = pre[pl];
int k = root;
if(il < k) p[build(il, k - 1, pl + 1, pl + 1 + k - 1 - il, depth + 1)] = root;
if(ir > k) p[build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr, depth + 1)] = root;
d[root] = depth;
return root;
}
int main(){
cin >> m >> n;
for(int i = 0; i < n; i++){
cin >> pre[i];
in[i] = pre[i];
}
sort(in, in + n);
for(int i = 0; i < n; i++){
pos[in[i]] = i;
seq[i] = in[i];
in[i] = i;
}
for(int i = 0; i < n; i++) pre[i] = pos[pre[i]];
build(0, n - 1, 0, n - 1, 1);
while(m--){
int a, b, x, y;
cin >> a >> b;
if(pos.count(a) && pos.count(b)){
a = pos[a], b = pos[b];
x = a, y = b;
while(a != b){
if(d[a] > d[b]) a = p[a];
else b = p[b];
}
if(a != x && a != y) printf("LCA of %d and %d is %d.\n", seq[x], seq[y], seq[a]);
else if(a == x) printf("%d is an ancestor of %d.\n", seq[x], seq[y]);
else printf("%d is an ancestor of %d.\n", seq[y], seq[x]);
}else if(pos.count(a) == 0 && pos.count(b) == 0){
printf("ERROR: %d and %d are not found.\n", a, b);
}else if(pos.count(a) == 0){
printf("ERROR: %d is not found.\n", a);
}else{
printf("ERROR: %d is not found.\n", b);
}
}
return 0;
}
（公共自行车管理）dijkstra + dfs：
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int C, n, S, m;
int c[N];
int g[N][N];
int dist[N];
bool st[N];
vector<int> path, ans;
int send = INF, bring = INF;
void dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[S] = 0;
for(int i = 0; i < n; i++){
int t = -1;
for(int j = 0; j <= n; j++)
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
st[t] = true;
for(int j = 0; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
void dfs(int u, int s, int mins){
if(u){
s -= (C + 1) / 2 - c[u];
mins = min(mins, s);
}
if(u == S){
int sd = abs(min(mins, 0));
int bg = s + sd;
if(sd < send) ans = path, send = sd, bring = bg;
else if(sd == send && bg < bring) ans = path, bring = bg;
return;
}
for(int i = 1; i <= n; i++)
if(dist[u] == g[u][i] + dist[i]){
path.push_back(i);
dfs(i, s, mins);
path.pop_back();
}
}
int main(){
cin >> C >> n >> S >> m;
for(int i = 1; i <= n; i++) cin >> c[i];
memset(g, 0x3f, sizeof g);
for(int i = 0; i < m; i++){
int x, y, z;
cin >> x >> y >> z;
g[x][y] = g[y][x] = min(g[x][y], z);
}
dijkstra();
path.push_back(0);
dfs(0, 0, 0);
cout << send << ' ' << 0;
for(int i = 1; i < ans.size(); i++)
cout << "->" << ans[i];
cout << " " << bring << endl;
return 0;
}
判断一个很大的数是否是素数（可以进行试除法判定，但是需要将因子从1~sqrt(n)换为(1-sqrt(x)之间的素数),减少多余判断）
bool check(int n){
for(int i = 0; primes[i] <= n / primes[i]; i++)
if(n % primes[i] == 0)
return false;
return true;
}
对顶堆（动态维护中位数）
#include<iostream>
#include<stack>
#include<cstring>
#include<set>
using namespace std;
int n;
// 较大元素，较小元素
multiset<int> up, down;
stack<int> stk;
void adjust(){
if(up.size() > down.size()){
auto t = up.begin();
int x = *t;
up.erase(t);
down.insert(x);
}
if(down.size() - up.size() > 1){
auto t = down.end();
t--;
int x = *t;
down.erase(t);
up.insert(x);
}
}
int main(){
scanf("%d", &n);
while(n--){
char od[20];
scanf("%s", od);
if(strcmp(od, "Pop") == 0){
if(stk.empty()) puts("Invalid");
else{
int x = stk.top();
stk.pop();
printf("%d\n", x);
if(up.empty() || x < *up.begin()) down.erase(down.find(x));
else up.erase(up.find(x));
adjust();
}
}else if(strcmp(od, "PeekMedian") == 0){
if(down.empty()) puts("Invalid");
else {
auto it = down.end();
it--;
printf("%d\n", *it);
}
}else{
int x;
scanf("%d", &x);
stk.push(x);
if(up.empty() || x < *up.begin()) down.insert(x);
else up.insert(x);
adjust();
}
}
return 0;
}
螺旋矩阵
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
for(int i = 0, x = 0, y = 0, d = 1; i < n; i++){
res[x][y] = w[i];
int a = x + dx[d], b = y + dy[d];
if(a < 0 || a >= r || b < 0 || b >= c || res[a][b]){
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
x = a, y = b;
}
