刷题过程中的一些心得
慢读题，将讲到的限制条件列出来，对于编程题的话，根据这些限制条件进行猜测数据点，保证简单题的正确率，一次提交就能过！
从蓝桥杯分值入手，先做简单题，再做难题。 暴力先手，再是优化。 全排列12个数范围里面的都是可以在一秒内搞完的。 对于数据的题，要算的，不要凭空想象。 取点不一定要选择格子，也可以选择格子旁边的线，不要把自己的思路封闭了。
学会理解题意抽象出我们要的东西，不能被题意背景迷惑了，考的就是思维, 有了思维写下来， 一步一步优化思路， 把一些重复的， 没有多大用的步骤省略掉。
对于看起来需要排序的题目要注意了，明白他要排序的目的，如果只是计数并且数据范围没有超过索引最大范围的话，那便不用排序，比如说三元组，这个题，看起来需要排序，用sort + 二分, 但是他排序只是为了计数找出有多少个的话，可以用数组计数，前缀和便可以解决问题了， 所以思路要转变， 用某个算法的话，先要明白他要干什么， 能不能找到更方便的办法， 一步一步循序渐进， 当然咯，最主要的就是把题目意思了解清楚了。
看到最小、最大、最优类字眼，就要往贪心、动态规划方向想了，首先要从暴力入手，再慢慢优化。
近些年来，比较难的题目都考到了分类讨论，遇到两种变量的时候要定一变一，利用分类讨论的思想去想出简单的办法。
学会使用excel 。 学会暴力枚举， 保证不重不漏。 递归 从题意抽象出他要考的知识点。
对于代码填空题目，先要理解他要干什么，在编译器中看看运行效果， 然后进行猜测代码，根据运行出来的结果进行调试，直到调试出正确答案。
范围判断考点
n
≤
30
⟹
指
数
级
别
,
d
f
s
+
剪
枝
n \leq 30 \Longrightarrow 指数级别, dfs+剪枝
n≤30⟹指数级别,dfs+剪枝
n
≤
100
⟹
O
(
n
3
)
动
态
规
划
n≤100 \Longrightarrow O(n^3) 动态规划
n≤100⟹O(n3)动态规划
n
≤
1000
⟹
O
(
n
2
)
，
O
(
n
l
o
g
n
)
d
p
，
二
分
n≤1000 \Longrightarrow O(n^2)，O(nlogn) dp，二分
n≤1000⟹O(n2)，O(nlogn)dp，二分
n
≤
100000
⟹
O
(
n
l
o
g
n
)
=
>
s
o
r
t
，
线
段
树
、
树
状
数
组
、
s
e
t
/
m
a
p
、
h
e
a
p
、
二
分
n≤100000 \Longrightarrow O(nlogn) => sort，线段树、树状数组、set/map、heap、二分
n≤100000⟹O(nlogn)=>sort，线段树、树状数组、set/map、heap、二分
n
≤
1000000
⟹
O
(
n
)
h
a
s
h
、
并
查
集
∣
∣
常
数
比
较
小
的
O
(
n
l
o
g
n
)
的
做
法
：
s
o
r
t
、
树
状
数
组
、
h
e
a
p
n≤1000000 \Longrightarrow O(n) hash、并查集 || 常数比较小的O(nlogn) 的做法：sort、树状数组、heap
n≤1000000⟹O(n)hash、并查集∣∣常数比较小的O(nlogn)的做法：sort、树状数组、heap
n
≤
10000000
⟹
O
(
n
)
线
性
筛
素
数
n≤10000000 \Longrightarrow O(n) 线性筛素数
n≤10000000⟹O(n)线性筛素数
n
≤
1
0
9
⟹
O
(
n
)
判
断
质
数
n≤10^9 \Longrightarrow O(\sqrt{n}) 判断质数
n≤109⟹O(n
)判断质数
n
≤
1
0
18
⟹
O
(
l
o
g
n
)
，
最
大
公
约
数
，
快
速
幂
n≤10^{18} \Longrightarrow O(logn)，最大公约数，快速幂
n≤1018⟹O(logn)，最大公约数，快速幂
代码模板
快速幂
#include<iostream>
using namespace std
;
int qmi(int a
, int b
, int p
) {
int ans
= 1;
while (b
) {
if (b
& 1) ans
= ans
* a
% p
;
a
= a
* a
% p
;
b
>>= 1;
}
return ans
% p
;
}
int main() {
int a
, b
, p
;
scanf("%d%d%d", &a
, &b
, &p
);
printf("%d\n", qmi(a
, b
, p
));
return 0;
}
并查集
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std
;
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
const int N
= 100010;
int n
, m
, p
[N
];
int find(int x
) {
if (p
[x
] != x
) p
[x
] = find(p
[x
]);
return p
[x
];
}
int main() {
scanf("%d%d", &n
, &m
);
_rep(i
, 1, n
) p
[i
] = i
;
while (m
--) {
char op
[3];
int a
, b
;
scanf("%s%d%d", op
, &a
, &b
);
if (*op
== 'M') p
[find(b
)] = find(a
);
else {
if (find(a
) != find(b
)) printf("No\n");
else printf("Yes\n");
}
}
return 0;
}
hash 模板
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std
;
typedef unsigned long long ULL
;
const int N
= 100010, P
= 131;
char str
[N
];
ULL h
[N
], p
[N
];
ULL
get_hash(int l
, int r
) {
return h
[r
] - h
[l
- 1] * p
[r
- l
+ 1];
}
int main() {
int n
, m
;
scanf("%d%d%s", &n
, &m
, str
);
p
[0] = 1;
for (int i
= 0; i
< n
; ++i
) {
h
[i
+ 1] = h
[i
] * P
+ str
[i
] - 'a';
p
[i
+ 1] = p
[i
] * P
;
}
while (m
--) {
int l1
, r1
, l2
, r2
;
scanf("%d%d%d%d", &l1
, &r1
, &l2
, &r2
);
if (get_hash(l1
, r1
) == get_hash(l2
, r2
)) puts("Yes");
else puts("No");
}
return 0;
}
求最大公约数模板
#include<iostream>
using namespace std
;
int gcd(int a
, int b
) {
return b
? gcd(b
, a
% b
) : a
;
}
int main() {
int a
, b
;
scanf("%d%d", &a
, &b
);
printf("%d\n", gcd(a
, b
));
return 0;
}
求最大公倍数模板
#include<iostream>
using namespace std
;
int gcd(int a
, int b
) {
return b
? gcd(b
, a
% b
) : a
;
}
int lcm(int a
, int b
) {
return a
* b
/ gcd(a
, b
);
}
int main() {
int a
, b
;
scanf("%d%d", &a
, &b
);
printf("%d\n", lcm(a
, b
));
return 0;
}
线性筛法求质数模板
#include<iostream>
#include<cstdio>
using namespace std
;
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
const int N
= 1000010;
int primes
[N
], cnt
;
bool st
[N
];
inline void get_primes(int n
) {
for (int i
= 2; i
<= n
; ++i
) {
if (!st
[i
]) primes
[cnt
++] = i
;
for (int j
= 0; i
* primes
[j
] <= n
; ++j
) {
st
[i
* primes
[j
]] = true;
if (i
% primes
[j
] == 0) break;
}
}
}
int main() {
int n
;
scanf("%d", &n
);
get_primes(n
);
_for(i
, 0, cnt
) printf("%d ", primes
[i
]);
printf("\n");
return 0;
}
高精度模板
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std
;
#define FOR(i, a) for (int i = (a); ~i; --i)
typedef vector
<int> VI
;
VI
add(VI
& a
, VI
& b
) {
VI c
;
for (int i
= 0, t
= 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
;
}
bool cmp(VI
& a
, VI
& b
) {
if (a
.size() != b
.size()) return a
.size() > b
.size();
FOR(i
, a
.size() - 1) if (a
[i
] != b
[i
]) return a
[i
] > b
[i
];
return true;
}
VI
sub(VI a
, VI b
) {
VI c
;
int t
= 0;
FOR(i
, a
.size() - 1) {
t
+= a
[i
];
if (i
< b
.size()) t
-= b
[i
];
c
.push_back((t
+ 10) % 10);
if (t
< 0) t
= -1;
else t
= 0;
}
reverse(c
.begin(), c
.end());
while (c
.size() > 1 && !c
.back()) c
.pop_back();
return c
;
}
VI
mul(VI
& a
, int b
) {
VI c
;
for (int i
= 0, t
= 0; i
< a
.size() || t
; ++i
) {
if (i
< a
.size()) t
+= a
[i
] * b
;
c
.push_back(t
% 10);
t
/= 10;
}
return c
;
}
VI
div(VI
& a
, int& b
, int& r
) {
VI c
;
FOR(i
, a
.size() - 1) {
r
= r
* 10 + a
[i
];
c
.push_back(r
/ b
);
r
%= b
;
}
reverse(c
.begin(), c
.end());
while (c
.size() > 1 && !c
.back()) c
.pop_back();
return c
;
}
void input(VI
& c
) {
FOR(i
, c
.size() - 1) cout
<< c
[i
];
cout
<< endl
;
}
int main() {
VI a
, b
, c
;
string s
, ss
;
int d
, r
= 0;
cin
>> s
>> ss
>> d
;
FOR(i
, s
.size() - 1) a
.push_back(s
[i
] - '0');
FOR(i
, ss
.size() - 1) b
.push_back(ss
[i
] - '0');
c
= add(a
, b
);
cout
<< "a + b = ";
input(c
);
if (cmp(a
, b
)) {
cout
<< "a - b = ";
c
= sub(a
, b
);
}
else {
cout
<< "a - b = -";
c
= sub(b
, a
);
}
input(c
);
c
= mul(a
, d
);
cout
<< "a * d = ";
input(c
);
c
= div(a
, d
, r
);
cout
<< "a / d = ";
input(c
);
cout
<< "余数为：" << r
<< endl
;
return 0;
}
树状数组模板
模板题目
#include<iostream>
#include<cstdio>
using namespace std
;
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
typedef long long LL
;
const int N
= 500010;
LL c
[N
], n
, m
;
void add(int x
, LL k
) {
for (; x
<= n
; x
+= x
& -x
) c
[x
] += k
;
}
LL
ask(int x
) {
LL ans
= 0;
for (; x
; x
-= x
& -x
) ans
+= c
[x
];
return ans
;
}
int main() {
scanf("%lld%lld", &n
, &m
);
_rep(i
, 1, n
) {
LL x
;
scanf("%lld", &x
);
add(i
, x
);
}
while (m
--) {
LL x
, y
;
int op
;
scanf("%d%lld%lld", &op
, &x
, &y
);
if (op
== 1) add(x
, y
);
else printf("%lld\n", ask(y
) - ask(x
- 1));
}
return 0;
}
线段树模板
模板题目
#include<iostream>
#include<cstdio>
using namespace std
;
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
typedef long long LL
;
const int N
= 100010;
int n
, m
;
LL w
[N
];
struct Node
{
int l
, r
;
LL v
, lz
;
}tr
[N
<< 2];
inline void push_up(int u
) {
tr
[u
].v
= tr
[u
<< 1].v
+ tr
[u
<< 1 | 1].v
;
}
inline void eval(Node
& t
, LL k
) {
t
.v
+= ((LL
)t
.r
- t
.l
+ 1) * k
;
t
.lz
+= k
;
}
inline void push_down(int u
) {
LL
& lz
= tr
[u
].lz
;
eval(tr
[u
<< 1], lz
);
eval(tr
[u
<< 1 | 1], lz
);
lz
= 0;
}
void build(int u
, int l
, int r
) {
tr
[u
] = { l
, r
, 0, 0 };
if (l
== r
) tr
[u
].v
= w
[l
];
else {
int mid
= l
+ r
>> 1;
build(u
<< 1, l
, mid
), build(u
<< 1 | 1, mid
+ 1, r
);
push_up(u
);
}
}
void modify(int u
, int l
, int r
, LL k
) {
Node
& t
= tr
[u
];
if (t
.l
>= l
&& t
.r
<= r
) eval(t
, k
);
else {
push_down(u
);
int mid
= t
.l
+t
.r
>> 1;
if (l
<= mid
) modify(u
<< 1, l
, r
, k
);
if (r
> mid
) modify(u
<< 1 | 1, l
, r
, k
);
push_up(u
);
}
}
LL
query(int u
, int l
, int r
) {
Node
& t
= tr
[u
];
if (t
.l
>= l
&& t
.r
<= r
) return t
.v
;
else {
push_down(u
);
LL ans
= 0;
int mid
= t
.l
+ t
.r
>> 1;
if (l
<= mid
) ans
+= query(u
<< 1, l
, r
);
if (r
> mid
) ans
+= query(u
<< 1 | 1,l
, r
);
return ans
;
}
}
int main() {
scanf("%d%d", &n
, &m
);
_rep(i
, 1, n
) scanf("%lld", &w
[i
]);
build(1, 1, n
);
while (m
--) {
int op
, x
, y
;
LL k
;
scanf("%d%d%d", &op
, &x
, &y
);
if (op
== 1) {
scanf("%lld", &k
);
modify(1, x
, y
, k
);
}
else printf("%lld\n", query(1, x
, y
));
}
return 0;
}
