LIS(最长上升子序列)
/*
以"导弹拦截"为例
第一问求最长单调不上升子序列
第二问求最长单调上升子序列
O(nlogn)实现
f[i]代表当最长单调子序列长度为i时最优的末尾元素
len为最长单调子序列的长度
以最长不上升子序列为例
①当a[i] <= f[len] 说明可以接在后面
②当a[i] > f[len] 在f中找到第一个小于a[i]的数 并替换为a[i]
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define FAST ios::sync_with_stdio(false); cin.tie(0);
//#define int long long
using namespace std;
const int MAXN = (int)1e5 + 5;
int n, a[MAXN], f[MAXN];
int Solve1() {
int len = 1;
f[1] = a[1];
for(int i = 2; i <= n; i++) {
if(a[i] <= f[len]) {
f[++len] = a[i];
} else {
f[upper_bound(f + 1, f + 1 + len, a[i], greater<int>() ) - f] = a[i];
}
}
return len;
}
int Solve2() {
int len = 1;
f[1] = a[1];
for(int i = 2; i <= n; i++) {
if(a[i] > f[len]) {
f[++len] = a[i];
} else {
f[lower_bound(f + 1, f + 1 + len, a[i]) - f] = a[i];
}
}
return len;
}
signed main()
{
n = 0;
while(cin >> a[++n]) ;
n--;
for(int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl;
printf("%d\n", Solve1());
printf("%d", Solve2());
return 0;
}
LCS(最长公共子序列)
/*
给定一个字符串 s 和一个字符串 t ，输出 s 和 t 的最长公共子序列。
通过LCS的dp方程( O(n^2) ) 暴力寻找路径 ( O(n^2) )
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define FAST ios::sync_with_stdio(false); cin.tie(0);
//#define int long long
using namespace std;
const int MAXN = 3005;
struct Node {
int x, y;
};
char S[MAXN], T[MAXN], ans[MAXN];
int sLen, tLen, dp[MAXN][MAXN];
Node pre[MAXN][MAXN];
signed main()
{
scanf("%s", S + 1);
scanf("%s", T + 1);
int sLen = strlen(S + 1);
int tLen = strlen(T + 1);
for(int i = 1; i <= sLen; i++) {
for(int j = 1; j <= tLen; j++) {
if(S[i] == T[j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
/*
for(int i = 1; i <= sLen; i++) {
for(int j = 1; j <= tLen; j++) {
printf("%d ", dp[i][j]);
}
printf("\n");
}
*/
int p = 0, px = sLen, py = tLen;
while(px != 0 && py != 0) {
if(dp[px][py] == dp[px][py - 1]) py--;
else if(dp[px][py] == dp[px - 1][py]) px--;
else if(dp[px][py] == dp[px - 1][py - 1] + 1) {
ans[++p] = S[px];
px--;
py--;
}
}
for(int i = p; i >= 1; i--) printf("%c", ans[i]);
return 0;
}
LCIS(最长公共上升子序列)
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define FAST ios::sync_with_stdio(false); cin.tie(0);
//#define int long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 3005;
int n, a[MAXN], b[MAXN], dp[MAXN][MAXN];
/*
dp[i][j]表示
a数组前i个元素和b数组前j个元素
以b[j]为结尾
的LCIS
*/
void LCIS() {
int curmax;
//O(n^2)做法
for(int i = 1; i <= n; i++) {
curmax = dp[i][0] + 1;
for(int j = 1; j <= n; j++) {
if(a[i] == b[j]) {
dp[i][j] = max(dp[i][j], curmax);
} else {
dp[i][j] = dp[i - 1][j];
}
if(b[j] < a[i]) //等价于朴素做法中b[k] < b[j] (b[j] == a[i])
curmax = max(curmax, dp[i - 1][j] + 1);
}
}
/*
//O(n^3)朴素做法 不采用
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(a[i] == b[j]) {
for(int k = 0; k < j; k++) {
if(b[k] < b[j]) {
dp[i][j] = max(dp[i][j], dp[i - 1][k] + 1);
}
}
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
*/
}
signed main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
LCIS();
int ans = 0;
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= n; j++) {
ans = max(ans, dp[i][j]);
}
}
printf("%d", ans);
return 0;
}
/*
input1:
4
2 2 1 3
2 1 2 3
output1:
2
input2:
10
1 5 3 6 3 2 7 3 6 2
9 6 2 3 1 5 3 3 6 1
output2:
3
*/
在数列的一维方向找到一个连续的子数列，使该子数列的和最大
/*
这种问题有两种解法:
1.分治+前缀和 O(nlogn)
2.DP O(n)
代码采用第二种方法
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define FAST ios::sync_with_stdio(false); cin.tie(0);
//#define int long long
using namespace std;
const int MAXN = (int)2e5 + 5;
const int INF = 0x7fffffff;
int n, a[MAXN], dp[MAXN];
signed main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) {
/*
dp[i]代表最大子段和的尾部元素
扫到i时 能转移过来的状态只有两种
一是另起炉灶 只留有a[i]
二是将a[i]接到a[i-1] 此时最大子段和就是dp[i-1] + a[i]
*/
dp[i] = max(dp[i - 1] + a[i], a[i]);
}
int ans = -INF;
for(int i = 1; i <= n; i++) ans = max(ans, dp[i]);
printf("%d", ans);
return 0;
}
//通用模板
dfs(数的最后若干位,各种限制条件,当前第几位)
if 最后一位
return 各种限制条件下的返回值
局部变量 curDigit=当前位的数字
局部变量 sum=0;
for i=0 to curDigit-1
sum+=当前位取i时一定无无限制的合法状态数
sum+=当前位取i时满足当前限制的合法状态数
根据curDigit更新限制条件 不再满足则return sum
return sum+dfs(当前位后的若干位,更新后的限制条件,下一位)
solve(当前数)
if(只有一位) return 对应的贡献
局部变量 maxDigit;
for maxDigit = 当前数可能最高位 to 1
if 当前位有数字 break
局部变量 curDigit=当前位数字
局部变量 sum=0
for i=1 to curDigit-1
sum+=当前位取i后合法情况任意取的贡献
for i=1 to maxDigit-1
for j=1 to 9
sum+=第i位取j后合法情况任意取的贡献
sum+=dfs(去掉第一位后的若干位,限制条件,第二位)
return sum
main
预处理当前位取i的各种条件各种限制的贡献
读入 L R
--L
输出 solve(R)-solve(L)
return 0
以[CQOI2016]手机号码为例
人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号码单独出售。为了便于前期规划，运营商希望开发一个工具来自动统计号段中满足特征的号码数量。
工具需要检测的号码特征有两个：号码中要出现至少 3 个相邻的相同数字；号码中不能同时出现 8 和 4。号码必须同时包含两个特征才满足条件。满足条件的号码例如：13000988721、23333333333、14444101000。而不满足条件的号码例如：1015400080、10010012022。
手机号码一定是 11 位数，前不含前导的 0。工具接收两个数 L 和 R，自动统计出 [L,R] 区间内所有满足条件的号码数量。L 和 R 也是 11 位的手机号码。
#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false); cin.tie(0);
#define int long long
using namespace std;
int dp[20][3][3][3][20][20][3], num[30], l, r;
int f(int len, bool three, bool exist8, bool exist4, int pre1, int pre2, int limit) {
//printf("%d %d %d %d %d %d %d\n", len, three, exist8, exist4, pre1, pre2, limit);
/*
three 是否存在3个相邻的相同数字
exist8 是否存在8
exist4 是否存在4
pre1 前推一位数位
pre2 前推两位数位
limit 有无数位限制(len位以后的数字可以随便取)
*/
if(exist4 && exist8) return 0;
if(len == 0) return three;
if(~dp[len][three][exist8][exist4][pre1][pre2][limit]) //记忆化
return dp[len][three][exist8][exist4][pre1][pre2][limit];
int res = 0;
int digit = limit == 0 ? 9 : num[len];
for(int i = 0; i <= digit; i++) {
//printf("%d %d %d %d %d %d %d\n", len - 1, i == pre1 && pre1 == pre2, exist8 || i == 8, exist4 || i == 4, i, pre1, limit && i == num[len]);
res += f(len - 1, three || ((i == pre1) && (pre1 == pre2)), exist8 || (i == 8), exist4 || (i == 4), i, pre1, limit && (i == num[len]));
}
return dp[len][three][exist8][exist4][pre1][pre2][limit] = res;
}
int Solve(int x) {
int len = 0;
memset(dp, -1, sizeof(dp));
while(x > 0) {
num[++len] = x % 10;
x /= 10;
}
if(len != 11) return 0;
int res = 0;
//for(int i = 1; i <= len; i++) cout << num[i] << " "; cout << endl;
for(int i = 1; i <= num[len]; i++) {
res += f(10, 0, i == 8, i == 4, i, 0, i == num[len]);
}
return res;
}
signed main()
{
FAST
cin >> l >> r;
cout << Solve(r) - Solve(l - 1);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
char S1[MAXN], S2[MAXN];
int l1, l2, pmt[MAXN]; //pmt数组(部分匹配表) 向右偏移一位为next数组 并让next[0] = -1
void KMP() {
pmt[0] = 0;
int p = 0;
for(int i = 2; i <= l2; i++) {
while(p && S2[p + 1] != S2[i]) p = pmt[p];
if(S2[p + 1] == S2[i]) p++;
pmt[i] = p;
}
p = 0;
for(int i = 1; i <= l1; i++) {
while(p && S2[p + 1] != S1[i]) p = pmt[p];
if(S2[p + 1] == S1[i]) p++;
if(p == l2) {
printf("%d\n", i - p + 1);
p = pmt[p];
}
}
}
int main()
{
cin >> S1 + 1;
cin >> S2 + 1;
l1 = strlen(S1 + 1);
l2 = strlen(S2 + 1);
KMP();
for(int i = 1; i <= l2; i++) printf("%d ", pmt[i]);
return 0;
}
/*
Manacher算法:
先在两个字符串中插入某个字符(‘$‘) 避免分别处理奇回文和偶回文的情况
设置两个指针maxR(前i个字符能回文扩展到的最右端) pos(前i个字符中哪个字符能回文扩展到最右端)
每次扫描到第i个字符时
①如果i<maxR,更新f[i] ②暴力拓展maxR(maxR从起点到终点且不会往回退) ③maxR增大时更新maxR和pos
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = (int)1.1e7 + 5;
char S[MAXN << 1], T[MAXN << 1];
int f[MAXN << 1], n;
void Manacher() {
//Prework
T[0] = ‘#‘;
T[1] = ‘$‘;
for(int i = 1; i <= n; i++) {
T[i * 2] = S[i];
T[i * 2 + 1] = ‘$‘;
}
n = n * 2 + 1;
for(int i = 0; i <= n; i++) S[i] = T[i];
//Manacher
int maxR = 0, pos = 0;
for(int i = 1; i <= n; i++) {
if(i < maxR) f[i] = min(f[pos * 2 - i], maxR - i);
while(S[i + f[i] + 1] == S[i - f[i] - 1] && i - f[i] - 1 > 0 && i + f[i] + 1 <= n) f[i]++;
if(i + f[i] > maxR) maxR = i + f[i], pos = i;
}
}
void PrintTest() {
for(int i = 1; i <= n; i++) cout << f[i] << " "; cout << endl;
}
int main()
{
//ios::sync_with_stdio(false);
scanf("%s", S + 1);
n = strlen(S + 1);
Manacher();
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = max(ans, f[i]);
}
printf("%d", ans);
return 0;
}
/*
可采用STL的deque实现 但常数过大 不推荐使用
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define FAST ios::sync_with_stdio(false); cin.tie(0);
//#define int long long
using namespace std;
const int MAXN = (int)1e6 + 5;
int n, k, a[MAXN];
int Index[MAXN], Value[MAXN]; //单调队列
void QueryMin() {
int head = 1, tail = 0;
for(int i = 1; i <= n; i++) {
while(head <= tail && Index[head] < i - k + 1) head++;
while(head <= tail && Value[tail] > a[i]) tail--; //保持单调队列始终升序
Index[++tail] = i;
Value[tail] = a[i];
if(i >= k) printf("%d ", Value[head]);
}
printf("\n");
}
void QueryMax() {
int head = 1, tail = 0;
for(int i = 1; i <= n; i++) {
while(head <= tail && Index[head] < i - k + 1) head++;
while(head <= tail && Value[tail] < a[i]) tail--; //保持单调队列始终降序
Index[++tail] = i;
Value[tail] = a[i];
if(i >= k) printf("%d ", Value[head]);
}
printf("\n");
}
signed main()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
QueryMin();
memset(Index, 0, sizeof(Index));
memset(Value, 0, sizeof(Value));
QueryMax();
return 0;
}
定义函数 \(f(i)\) 代表数列中第 i 个元素之后第一个大于\(a_i\)的元素的下标 求\(f(1...n)\) (f数组)
#include<bits/stdc++.h>
using namespace std;
const int MAXN = (int)3e6 + 5;
int n, a[MAXN], f[MAXN];
int Value[MAXN], Index[MAXN];
void Query() {
int top = 0;
for(int i = 1; i <= n; i++) {
while(top > 0 && Value[top] < a[i]) { //单调栈保持降序
f[Index[top]] = i;
top--;
}
Value[++top] = a[i];
Index[top] = i;
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
Query();
for(int i = 1; i <= n; i++) {
printf("%d ", f[i]);
}
return 0;
}
/*
input:
5
1 4 2 3 5
output:
2 5 4 5 0
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = (int)1e5 + 5;
int n, m, a[MAXN];
int st[MAXN << 1][45]; //注意st表第一维空间(n的数量)至少要开2倍
void Prework() {
for(int k = 1; (1 << k) <= n; k++) {
for(int i = 1; i <= n; i++) {
st[i][k] = max(st[i][k - 1], st[i + (1 << (k - 1) )][k - 1]);
}
}
/*
for(int i = 1; i <= n; i++) {
for(int j = 1; (1 << j) <= n; j++) {
cout << st[i][j] << " ";
}
cout << endl;
}
*/
}
inline int Query(int l, int r) {
int t = floor(log2(r - l + 1));
return max(st[l][t], st[r - (1 << t) + 1][t]);
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
st[i][0] = a[i];
}
Prework();
while(m--) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", Query(l, r));
}
}
/*
区间查询 单点更新
*/
#include<bits/stdc++.h>
#define MAXN (int)1e6 + 7
#define ll long long
using namespace std;
ll n, q, a[MAXN], c[MAXN];
ll lowbit(ll x) {
return x & (-x);
}
void Modify(int t, int x) {
while(t <= n) {
c[t] += x;
t += lowbit(t);
}
}
ll Query(int t) {
ll sum = 0;
while(t > 0) {
sum += c[t];
t -= lowbit(t);
}
return sum;
}
int main(){
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
Modify(i, a[i]);
}
while(q--) {
int opt, x, y;
scanf("%d%d%d", &opt, &x, &y);
if(opt == 1) {
Modify(x, y); //a[x]加上y
} else {
printf("%d\n", Query(y) - Query(x - 1)); //[x,y]的区间和
}
}
return 0;
}
将原数组化为差分数组 对于原数组的区间更新 单点查询 可化为对于差分数组的单点更新(两次) 区间查询(差分数组的前缀和)
树状数组求逆序对（有重复元素）：
逆序对的基本思想是对于每一个下标i，找下标在[1,i-1]中比a[i]大的数
排序之后按值从大到小，往树状数组相应下标处依次加入元素 每次先查询前面有多少个比当前元素大的元素
注意：当出现相同元素时 我们要按下标从大到小排序 这样查询的时候相同元素会按下标从后往前查询 这样就防止逆序对出现下标不同而值相同的情况
#include<bits/stdc++.h>
#define MAXN (int)1e6 + 7
#define int long long
using namespace std;
struct Node {
int val, num;
}a[MAXN];
int n, c[MAXN];
bool cmp(Node a, Node b) {
if(a.val == b.val) return a.num > b.num;
return a.val > b.val;
}
int lowbit(int x) {
return x & (-x);
}
void Modify(int t, int x) {
while(t <= n) {
c[t] += x;
t += lowbit(t);
}
}
int Query(int t) {
int sum = 0;
while(t > 0) {
sum += c[t];
t -= lowbit(t);
}
return sum;
}
signed main(){
scanf("%lld", &n);
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i].val);
a[i].num = i;
}
sort(a + 1, a + 1 + n, cmp);
int ans = 0;
for(int i = 1; i <= n; i++) {
Modify(a[i].num, 1);
ans += Query(a[i].num - 1);
}
printf("%lld", ans);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 5;
int n, m, isprime[maxn], prime[maxn], cnt;
bool ans[maxn];
void PreWork() {
cnt = 0;
isprime[1] = 1;
for(int i = 2; i <= n; i++) {
if(!isprime[i]) {
prime[++cnt] = i;
ans[i] = 1;
}
for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {
isprime[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
//for(int i = 1; i <= cnt; i++) cout << prime[i] << " "; cout << endl;
}
int main()
{
scanf("%d%d", &n, &m);
PreWork();
for(int i = 1; i <= m; i++) {
int now;
scanf("%d", &now);
if(ans[now]) printf("Yes");
else printf("No");
printf("\n");
}
return 0;
}
给出一个有理数 \(c=\frac{a}{b}\)，求 \(c\bmod 19260817\)的值。
#include <algorithm>
using namespace std;
int main() {
iterator begin, end; // 指代某种数据结构首尾迭代器
T i, x, a, b;
sort(begin, end, <cmp>); // 排序函数，默认从小到大
// 遇到需要特殊排序的需要编写cmp函数 or 重载内部运算符
next_permutation(begin, end); // 下一个排列
prev_permutation(begin, end); // 前一个排列
set_union(begin(a), end(a), begin(b), end(b), begin(c));
// 取两个有序序列a、b的并集，存放到c中
set_intersection(begin(a), end(a), begin(b), end(b), begin(c));
// 取两个有序序列a、b的交集，存放到c中
set_difference(begin(a), end(a), begin(b), end(b), begin(c));
// 取两个有序序列a、b的差集，存放到c中
unique(begin, end); // 有序数据去重
merge(begin(a), end(a), begin(b), end(b), begin(c), cmp);
// 合并两个有序序列a、b，存放到c中，cmp可定义新序列排列方式
lower_bound(begin, end, x); // 返回x的前驱迭代器
// 在普通的升序序列中，x的前驱指的是第一个大于等于x的值
upper_bound(begin, end, x); // 返回x的后继迭代器
// 在普通的升序序列中，x的后继指的是第一个大于x的值
// 上述两个函数时间复杂度为O(log2(n))，内部实现是二分
// 如果找不到这样的值，会返回end
find(begin, end, x); // O(n)查找x
binary_search(begin, end, x) // 二分查找x，返回bool
min(a, b); max(a, b); // 返回a、b中的最小/最大值
fill(begin, end, x); // 往容器的[begin, end)内填充x
swap(a, b); // 交换a、b的值
return 0;
}
#include <vector>
#include <list>
using namespace std;
int main() {
T i;
unsigned int n, x;
bool flag;
iterator it;
// 动态数组部分
// 注意vector的空间需要预留两倍大小
vector<T> v;
v.push_back(i); // 往数组尾添加一个元素i
v[x]; // 访问第x - 1个元素
v.begin(); // 返回头元素的迭代器
v.end(); // 返回末尾迭代器（尾元素的下一个）
n = v.size(); // 数组中元素数量
v.pop_back(); // 删除最后一个元素
v.erase(it); // 删除某个的元素
v.insert(x, i); // 在x位置插入元素i
// erase、insert时间复杂度为O(n)
v.clear(); // 清空数组，不释放空间
flag = v.empty(); // 判断数组是否为空（真值）
// 链表部分
list<T> li;
li.push_front(i); // 在链头添加一个元素i
li.push_back(i); // 在链尾添加一个元素i
li.pop_front(i); // 删除链表头元素
li.pop_back(i); // 删除链表尾元素
li.erase(it); // 删除某个的元素
li.insert(x, i); // 在x位置插入元素i O(n)
li.begin(); // 返回头元素的迭代器
li.end(); // 返回末尾迭代器（尾元素的下一个）
n = li.size(); // 链表中元素数量
li.remove(i); // 删除链表中所有值为i的元素
li.unique(); // 移除所有连续相同元素，留下一个
li.reverse(); // 反转链表
li.clear(); // 情况链表，不释放空间
return 0;
}
#include <queue> // 队列头文件
#include <deque> // 双端队列头文件
using namespace std;
int main() {
T i;
unsigned int n, x;
bool flag;
// 普通队列部分，注意queue没有迭代器
queue<T> q, tmp_q; // 定义普通队列
q.push(i); // 队尾插入元素i
q.pop(); // 弹出队首元素
i = q.front(); // 访问队首元素
i = q.back(); // 访问队尾元素
n = q,size(); // 队内元素数量
flag = q.empty(); // 判断队列是否为空（真值）
q.swap(tmp_q); // 交换两个队列元素
// 优先队列部分，注意其没有迭代器
priority_queue<T> pq; // 定义优先队列
pq.push(i); // 队尾插入元素i
pq.pop(); // 弹出队首元素
i = pq.top(); // 访问队首元素
n = q,size(); // 队内元素数量
flag = q.empty(); // 判断队列是否为空（真值）
q.swap(tmp_q); // 交换两个队列元素
// 注意优先队列内部是使用<运算符，默认大根堆
// 可以采用重载运算符或加入运算符类自定义排列方式
// 例：priority_queue<T, vector<T>, greater<T> > 小根堆
/*
struct node {
int x, y;
};
bool operator < (node a, node b) {
// 这里注意是<右边的元素会放在前面
if(a.x != b.x) return a.x < b.x;
else return a.y < b.y;
}
priority_queue<node>
*/
// 双端队列部分
// 注意deque用到了map来映射，时间复杂度上常数略大
deque<T> dq; // 定义双端队列
// 可以称为vector、list、queue的结合体
// 用法类似，这里只给代码不做注释
dq.push_back(i);
dq.push_front(i);
dq.front();
dq.back();
dq.pop_front();
dq.pop_back();
dq.begin();
dq.end();
dq[x];
n = dq.size();
flag = dq.empty();
dq.insert(x, i);
return 0;
}
#include <stack>
using namespace std;
int main() {
T i;
unsigned int n;
bool flag;
stack<T> st; // 注意stack没有迭代器
st.push(i); // 往栈顶加入一个元素
st.pop(); // 弹出栈顶元素
i = st.top(); // 获得栈顶元素的值
flag = st.empty(); // 判断是否为空（真值）
n = st.size(); // 获得栈内元素个数
return 0;
}
#include <set>
#include <pair>
using namespace std;
int main() {
T i;
T1 t1;
T2 t2;
iterator it;
unsigned int n;
bool flag;
// pair是将两种元素组成一对
pair<T1, T2> p;
p = make_pair(t1, t2); // 将t1、t2构造成一对
// pair支持比较，遵循字典序
p.first; // 访问第一个元素，这里是t1
p.second; // 访问第二个元素，这里是t2
// set内部是RB-tree维护
set<int> st; // 注意，set内元素不重复
st.insert(i); // 往set内插入一个元素i
// 时间复杂度O(log2(n)) 这里会返回一个<pair>迭代器
// first指向插入元素后所在的迭代器
// second指向是否插入成功（真值）
st.begin(); // 返回首迭代器
st.end(); // 范围尾迭代器
st.erase(it); st.erase(i);
// 删除某个元素
st.equal_range(i); // 返回几何中与i相等的上下限两个迭代器
flag = st.empty();
n = st.size();
st.clear();
// set内置了lower_bound和upeer_bound函数
// 用法和algorithm的一样
// 可重复元素set
multiset<int> mst;
// 用法与set大致相同
// 唯一不同只在删除函数上
mst.erase(i); // 会删除所有值为i的元素
return 0;
}
// 如果需要给set自定义排序顺序
struct CMP {
bool operator() (const int& a, const int& b) const {
return a > b; // 返回真值则代表左边的值优先级高
}
};
multiset<int, CMP> mst;
#include <map>
using namespace std;
int main() {
T1 t1;
T2 t2;
// map将两种元素做映射，一种指向另一种
// 内部也是RB-tree维护
map<T1, T2> mp;
mp[t1] = t2; // 直接让t1对应到t2
mp[t1]; // 访问t1对应的内容，时间复杂度O(log2(n))
// 如果t1没有指向任何内容，则会返回T2类型的初始值
return 0;
}
#include <bits/stdc++.h> // 标准库头文件
using namespace std;
int main() {
__int128 a; // 128位整数，最大值大概10^38次方
// C++11以上可用，无法用标准方法读入
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(false);
// 关闭cin、cout同步流，此举后不可混用scanf/printf
auto x; // 自动变量，可以是任意属性
// 举个例子
std::set<int> st;
std::for(auto i:st); // C++版for_each
// 其中i是auto变量，也可改成set<int>::iterator
// 所有的STL容器push/insert操作都可替换为emplcace
// 速度上减小常数（不用临时变量）
// 例：
int i;
std::set<int> st;
st.emplace(i);
std::vector<int> vc;
vc.emplace_back(i);
return 0;
}
#include <bits/stdc++.h>
#include <bits/extc++.h> // 扩展库头文件
/*
* 这里如果没有bits/extc++.h的话需要
* ext/pb_ds/tree_policy.hpp
* ext/pb_ds/assoc_container.hpp
* ext/pb_ds/priority_queue_policy.hpp
* ext/pb_ds/trie_policy.hpp
* ext/rope
* ...
*/
using namespace __gnu_pbds;
using namespace __gnu_cxx;
int main() {
// 哈希表部分，用法与map一样，效率在C++11以下效率高
// 注意，这部分在namespace __gnu_pbds下
cc_hash_table<string, int> mp1; // 拉链法
gp_hash_table<string, int> mp2; // 查探法(快一些)
// 优先队列部分，比STL中高级
priority_queue<int, std::greater<int>, TAG> pq;
/*
* 第一个参数是数据类型
* 第二个是排序方式
* 第三个是堆的类型
* 其中堆的类型有下面几种
* pairing_heap_tag
* thin_heap_tag
* binomial_heap_tag
* c_binomial_heap_tag
* binary_heap_tag
* 其中pairing_heap_tag最快
* 并且这个东西是带默认参数的，只需要定义一个int
*/
// 比STL中的优先队列多了join和迭代器
// 例子：
priority_queue<int> pq1, pq2;
pq1.join(pq2); // 会将pq2合并到pq1上
pq1.begin(); pq1.end(); // 可遍历
// 红黑树（平衡树）部分，与set相似，但更快
tree <
int,
null_type,
std::less<>,
rb_tree_tag,
tree_order_statistics_node_update
> t, tre;
/*
* int 关键字类型
* null_type 无映射（低版本g++为null_mapped_type）
* less<int> 从小到大排序
* rb_tree_tag 红黑树（splay_tree_tag splay）
* tree_order_statistics_node_update 结点更新
*/
int i, k;
t.insert(i); // 插入
t.erase(i); // 删除
t.order_of_key(i);
// 询问这个tree中有多少个比i小的元素
t.find_by_order(k);
// 找第k + 1小的元素的迭代器,如果order太大会返回end()
t.join(tre); // tre合并到t上
t.split(i, tre); // 小于等于i的保留，其余的属于tre
// 基本操作有size()/empty()/begin()/end()等
// 同样内置lower_bound/upper_bound
// 可持久化平衡树部分
// 注意，这部分在namespace __gun_cxx下
rope<char> str;
// 待我学习完后再更新
return 0;
}
@echo off
:loop
随机数据生成.exe
暴力.exe
正解.exe
fc 暴力.out 正解.out
if not errorlevel 1 goto loop
pause
:end
#pragma GCC optimize(2)
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //iostream特供
//不开longlong见祖宗 x年ACM一场空
#define int long long
...
signed main() {
...
}
原文：https://www.cnblogs.com/Orzjh/p/14744546.html