201910清北学习总结

该文章Markdown版本

这次国庆,参加了清北的提高刷题班(在文化课炸掉的情况下,怎么补还是个问题),有一些收获(讲实话大部分听不懂),应老师的要求和个人的感想,想写一篇学习总结。

因为参加的是提高刷题班,所以考了许多试,总共六次。

几次考试中,逐渐发现了自己的几处不足。

所以这篇总结,我们先从考试开始!

考试

经验总结

成绩并不是很稳定,上下变化幅度大。

原因有这样几个:紧张?[×]、不会[√]、会打暴力[×]、会打正解[×××]、题难[√/×]。

从其中也得到了一些考试的经验。

  1. 做题先不要想正解!!!

    因为难题的正解几乎是无法想出来的,甚至要靠直觉和运气,所以一定要先拿到暴力分!!!(钟长者:你先拿到暴力再去写正解嘛~~,毕竟暴力分是能拿一等的,先拿了一等再去干别的。

    而且可以为后面的调试、对拍打下基础。

    而且暴力分是真的多啊(被某神仙嘲讽连暴力都打不出来了,QWQ)

  2. 不要死抠同一道题。

    为什么????????????
    当你一道题连暴力都打不出来时,那这道题基本没救了,除非你可以像神仙WYF\mathtt{WYF}一样可以用正解拍暴力,否则去做下一道题吧

    但是如果暴力打出来了(可以证明其正确性),而且想想一想正解的活,(完全没有任何想法的情况下)千万不要浪费太多的时间,毕竟正解是很难想的。

  3. 同一道题的两份程序一定要对拍!

    这是一个可以让你保证程序正确性的一个技巧!

    有关ZHX\mathtt{ZHX}长者的对拍程序(切克儿.cpp),请从这里查看。

  4. 考试始终开启文件读入读出

    调试时直接查看文件,有许多好处(最重要的是可以避免忘记打换行之类的蠢货错误)。

    ex:

    1
    2
    3
    4
    #include<cstdio>

    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
  5. 不要浪费时间!!!

    不用多说,对不?

  6. 分析好程序的时间复杂度。

    尽量拿更多的分。。

  7. 思路尽量灵活。

    有些题的代码长度并不是很多,但是却需要很强的思维技巧。能想就一定要想。
    有些题甚至可以:大胆猜想,无需证明

  8. 心态、多练习……都是经常会说的了,就不再多提。


考试题解

待有时间继续上传。


知识总结

模板类

数论

附上林学姐的数论整理

有些东西是真的不懂,还需要时间去理解(以我的数学水平,唉

欧几里得算法与拓展欧几里得算法

这个算法窝曾经在blog中讨论过,具体请看这里

所以在这里,窝只给出代码(虽然EXgcd\mathtt{EXgcd}的证明始终记不住)。

gcd
1
2
3
4
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
exgcd
1
2
3
4
5
6
7
8
9
10
11
12
int Exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = Exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - (a / b) * y;
return d;
}

素数及其筛法

有关素数的知识可以看窝之前的blog

这里依然只放出isprime()和Euler 筛法的代码。

isprime()
1
2
3
4
5
6
bool isPrime(a) {
if (a < 2) return 0;
for (int i = 2; i * i <= a; ++i)
if (a % i) return 0;
return 1;
}
Euler 筛法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>

const int maxn=1e7+10;

int n,m,PR[maxn],cnt;
bool pr[maxn];

int main(){
scanf("%d%d",&n,&m);
pr[0]=pr[1]=true;
for(register int i=2;i<=n;i++){
if(!pr[i]) PR[++cnt]=i;
for(int j=1;j<=cnt&&i*PR[j]<=n;j++){
pr[i*PR[j]]=true;
if(!i%PR[j]) break;
}
}
for(register int i=1;i<=m;i++){
register int x;
scanf("%d",&x);
printf("%s\n",!pr[x]?"Yes":"No");
}
return 0;
}

欧拉函数

正好补窝之前的博客

欧拉函数(Eulers  totient  function\mathtt{Euler's \; totient \; function}),即 φ(n)\varphi(n) ,表示的是小于等于 nnnn 互质的数的个数。

最简单的例子:φ(1)=1\varphi(1)=1

互质是公约数只有1的两个整数,叫做互质整数。公约数只有1的两个自然数,叫做互质自然数,后者是前者的特殊情形。

nn为质数时,很明显φ(n)=n1\varphi(n)=n-1

唯一分解定理与欧拉函数

利用唯一分解定理,我们可以把一个整数唯一地分解为质数幂次的乘积,

n=p1k1p2k2psksn = p_1^{k_1}p_2^{k_2} \cdots p_s^{k_s} ,其中 pip_i 是质数,那么定义 φ(n)=n×i=1spi1pi\varphi(n) = n \times \prod_{i = 1}^s{\frac{p_i - 1}{p_i}}

欧拉函数的性质
  1. 欧拉函数是积性函数。

    什么是积性函数?
    积性是什么意思呢?如果有 gcd(a,b)=1\gcd(a, b) = 1 ,那么 φ(a×b)=φ(a)×φ(b)\varphi(a \times b) = \varphi(a) \times \varphi(b) 。特别地,当 nn 是奇数时 φ(2n)=φ(n)\varphi(2n) = \varphi(n)

  2. n=dnφ(d)n = \sum_{d | n}{\varphi(d)}(不会用,待学习)
  3. n=pkn = p^k ,其中 pp 是质数,那么 φ(n)=pkpk1\varphi(n) = p^k - p^{k - 1} 。 (根据定义可知)
求欧拉函数
1
2
3
4
5
6
7
8
9
10
11
int euler_phi(int n) {
int m = int(sqrt(n + 0.5));
int ans = n;
for (int i = 2; i <= m; i++)
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
线性筛法求欧拉函数

来自OI-WIKI

注意到在线性筛中,每一个合数都是被最小的质因子筛掉。比如设 p1p_1nn 的最小质因子, n=np1n' = \frac{n}{p_1} ,那么线性筛的过程中 nn 通过 n×p1n' \times p_1 筛掉。

观察线性筛的过程,我们还需要处理两个部分,下面对 nmodp1n' \bmod p_1 分情况讨论。

如果 nmodp1=0n' \bmod p_1 = 0 ,那么 nn' 包含了 nn 的所有质因子。

φ(n)=n×i=1spi1pi=p1×n×i=1spi1pi=p1×φ(n)\begin{aligned} \varphi(n) & = n \times \prod_{i = 1}^s{\frac{p_i - 1}{p_i}} \\ & = p_1 \times n' \times \prod_{i = 1}^s{\frac{p_i - 1}{p_i}} \\ & = p_1 \times \varphi(n') \end{aligned}

那如果 nmodp10n' \bmod p_1 \neq 0 呢,这时 nn'nn 是互质的,根据欧拉函数性质,我们有:

φ(n)=φ(p1)×φ(n)=(p11)×φ(n)\begin{aligned} \varphi(n) & = \varphi(p_1) \times \varphi(n') \\ & = (p_1 - 1) \times \varphi(n') \end{aligned}

1
2
3
4
5
6
7
8
9
10
void phi_table(int n, int* phi) {
for (int i = 2; i <= n; i++) phi[i] = 0;
phi[1] = 1;
for (int i = 2; i <= n; i++)
if (!phi[i])
for (int j = i; j <= n; j += i) {
if (!phi[j]) phi[j] = j;
phi[j] = phi[j] / i * (i - 1);
}
}
欧拉定理

额,这个东东不会用。但可以理解。

欧拉定理:
gcd(a,m)=1\gcd(a, m) = 1 ,则 aφ(m)1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}

证明[1]
r1,r2,,rφ(m)r_1, r_2, \cdots, r_{\varphi(m)} 为模 mm 意义下的一个简化剩余系,则 ar1,ar2,,arφ(m)ar_1, ar_2, \cdots, ar_{\varphi(m)} 也为模 mm 意义下的一个简化剩余系。所以 r1r2rφ(m)ar1ar2arφ(m)aφ(m)r1r2rφ(m)(modm)r_1r_2 \cdots r_{\varphi(m)} \equiv ar_1 \cdot ar_2 \cdots ar_{\varphi(m)} \equiv a^{\varphi(m)}r_1r_2 \cdots r_{\varphi(m)} \pmod{m} ,可约去 r1r2rφ(m)r_1r_2 \cdots r_{\varphi(m)} ,即得 aφ(m)1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}

mm 为素数时,由于 φ(m)=m1\varphi(m) = m - 1 ,代入欧拉定理可立即得到费马小定理。

拓展欧拉定理

拓展欧拉定理


费马小定理

pp 为素数, gcd(a,p)=1\gcd(a, p) = 1 ,则 ap11(modp)a^{p - 1} \equiv 1 \pmod{p}

另一个形式:对于任意整数 aa ,有 apa(modp)a^p \equiv a \pmod{p}


裴蜀定理

a,ba,b 是不全为零的整数,则存在整数 x,yx,y , 使得 ax+by=gcd(a,b)ax+by=\gcd(a,b)


逆元

如果一个线性同余方程 ax1(modb)ax \equiv 1 \pmod b ,则 xx 称为 amodba \mod b 的逆元,记作 a1a^{-1}

求逆元
1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>
#define N 3000001
int n,p;
long long a[N];
int main()
{
scanf("%d%d",&n,&p);
a[1]=1;
for(int i=2;i<=n;i++) a[i]=(p-(p/i))*a[p%i]%p;
for(int i=1;i<=n;i++) printf("%lld\n",a[i]);
return 0;
}

其他

  1. 中国剩余定理。
  2. BSGS。
  3. 卢卡斯定理。
  4. 。。。

图论

2-SAT

比较容易理解,但是由题建图很难。

就是给你nn个变量aia_i,每个变量能且只能取0/10/1的值。

同时给出若干条件,形式诸如(not)ai  opt  (not)aj=0/1(not)a_i \; opt \; (not) a_j=0/1,其中optopt表示and(&),or(),xor()and(\&),or(|),xor(\wedge)中的一种。

求解2-SAT的解就是求出满足所有限制的一组aa

建图方式正如opt之意。


DP等等老生常谈的东西

DP

DP也有许多套路,需要多做题整理总结(大胆猜想,无需求证)

例如:[2]
DP1

故不再多做总结。


逆序对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<algorithm>

#define int long long
const int maxn=5e5+10;

int n,tree[maxn],r[maxn],ans;

struct type{
int num,x;
}a[maxn];

inline bool cmp(int x,int y){
if(a[x].num==a[y].num) return a[x].x>a[y].x;
return a[x].num>a[y].num;
}

inline int lowbi(int x){return x&(-x);}

inline void update(int x){
while(x<=n){
tree[x]+=1;
x+=lowbi(x);
}
return ;
}

inline int query(int x){
int sum=0;
while(x>=1){
sum+=tree[x];
x-=lowbi(x);
}
return sum;
}

inline int read(){
char ch=getchar();int x=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return f*x;
}

signed main(){
n=read();
for(register int i=1;i<=n;i++) a[i].num=read(),a[i].x=i,r[i]=i;
std::sort(r+1,r+1+n,cmp);
for(register int i=1;i<=n;i++){
update(r[i]);
ans+=query(r[i]-1);
}
printf("%lld",ans);
return 0;
}

快速幂(ksm.cpp)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<cstdio>
#include<iostream>
using namespace std;

unsigned long long b,p,k,ans;

int quick_power(unsigned long long a,unsigned long long b);

int main(){
scanf("%lld%lld%lld",&b,&p,&k);
cout<<b<<'^'<<p<<' '<<"mod "<<k<<'='<<quick_power(b,p)%k;
return 0;
}

int quick_power(unsigned long long a,unsigned long long b){
unsigned long long r=1,base=a;
while(b!=0){
if(b%2){
r=r*base%k;
}
base=base*base%k;
b/=2;
}
return r;
}

KMP和AC自动机

KMP

写过博客,不再多说,只放出代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<cstring>

const int maxn=1e6+10;

char c[maxn],p[maxn];
int next[maxn];

void find(int lc,int lp);void getfail(int lp);

int main(){
scanf("%s",c);scanf("%s",p);
int lc=strlen(c),lp=strlen(p);
find(lc,lp);
for(int i=1;i<=lp;i++) printf("%d ",next[i]);
return 0;
}

void find(int lc,int lp){
getfail(lp);
int j=0;
for(int i=0;i<lc;i++){
while(j&&p[j]!=c[i]) j=next[j];
if(p[j]==c[i]) j++;
if(j==lp) printf("%d\n",i-lp+2);
}
return ;
}

void getfail(int lp){
next[0]=0;
int j=0;
for(int i=1;i<lp;i++){
while(j&&p[i]!=p[j]) j=next[j];
next[i+1]=p[i]==p[j]?++j:0;
}
return ;
}
AC自动机

基于Trie和KMP。

Trie
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//并未通过编译,大体就这样
//假设我们所存储的单词只用26个小写英文字母组成
//字母个数 tot
const int sigma_size=26;//26个小写英文字母
const int maxn=tot*tot+10;


struct Trie{
int ch[maxn][sigma_size];//ch[i][j]表示节点i的子节点j
int val[maxn];//表示节点i的附加信息
int sz;//节点总数

Trie(){//初始节点为0
sz=1;//初始节点的下一个节点的编号
memset(ch[0],0,sizeof(ch[0]));
}

int idx(char c){return c-'a';}//返回字母编号

void insert(char *s,int v){//向其中插入s,附加信息为v
int u=0,n=strlen(s);
for(int i=0;i<n;i++){
int c=idx(s[i]);
if(!ch[u][c]){//节点不存在
memset(ch[sz],0,sizeof(ch[sz]));//初始化新节点
val[sz]=0;//中间节点的附加信息为0
ch[u][c]=sz++; //新建节点
}
u=ch[u][c];//顺着向下走
}
val[u]=v;//将最终的单词节点的附加信息更新
}

//查询待update
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
struct Tree//字典树
{
int fail;//失配指针
int vis[26];//子节点的位置
int end;//标记以这个节点结尾的单词编号
}AC[100000];//Trie树
int cnt=0;//Trie的指针
struct Result
{
int num;
int pos;
}Ans[100000];//所有单词的出现次数
bool operator <(Result a,Result b)
{
if(a.num!=b.num)
return a.num>b.num;
else
return a.pos<b.pos;
}
string s[100000];
inline void Clean(int x)
{
memset(AC[x].vis,0,sizeof(AC[x].vis));
AC[x].fail=0;
AC[x].end=0;
}
inline void Build(string s,int Num)
{
int l=s.length();
int now=0;//字典树的当前指针
for(int i=0;i<l;++i)//构造Trie树
{
if(AC[now].vis[s[i]-'a']==0)//Trie树没有这个子节点
{
AC[now].vis[s[i]-'a']=++cnt;//构造出来
Clean(cnt);
}
now=AC[now].vis[s[i]-'a'];//向下构造
}
AC[now].end=Num;//标记单词结尾
}
void Get_fail()//构造fail指针
{
queue<int> Q;//队列
for(int i=0;i<26;++i)//第二层的fail指针提前处理一下
{
if(AC[0].vis[i]!=0)
{
AC[AC[0].vis[i]].fail=0;//指向根节点
Q.push(AC[0].vis[i]);//压入队列
}
}
while(!Q.empty())//BFS求fail指针
{
int u=Q.front();
Q.pop();
for(int i=0;i<26;++i)//枚举所有子节点
{
if(AC[u].vis[i]!=0)//存在这个子节点
{
AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
//子节点的fail指针指向当前节点的
//fail指针所指向的节点的相同子节点
Q.push(AC[u].vis[i]);//压入队列
}
else//不存在这个子节点
AC[u].vis[i]=AC[AC[u].fail].vis[i];
//当前节点的这个子节点指向当
//前节点fail指针的这个子节点
}
}
}
int AC_Query(string s)//AC自动机匹配
{
int l=s.length();
int now=0,ans=0;
for(int i=0;i<l;++i)
{
now=AC[now].vis[s[i]-'a'];//向下一层
for(int t=now;t;t=AC[t].fail)//循环求解
Ans[AC[t].end].num++;
}
return ans;
}
int main()
{
int n;
while(233)
{
cin>>n;
if(n==0)break;
cnt=0;
Clean(0);
for(int i=1;i<=n;++i)
{
cin>>s[i];
Ans[i].num=0;
Ans[i].pos=i;
Build(s[i],i);
}
AC[0].fail=0;//结束标志
Get_fail();//求出失配指针
cin>>s[0];//文本串
AC_Query(s[0]);
sort(&Ans[1],&Ans[n+1]);
cout<<Ans[1].num<<endl;
cout<<s[Ans[1].pos]<<endl;
for(int i=2;i<=n;++i)
{
if(Ans[i].num==Ans[i-1].num)
cout<<s[Ans[i].pos]<<endl;
else
break;
}
}
return 0;
}

矩阵快速幂加快递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
const int maxn=1000000;
const int mod=10000;
#define me(a) memset(a,0,sizeof(a))
#define ll long long
using namespace std;
struct node{
int a[2][2];
node(){memset(a,0,sizeof(a));}
};
node jx(node a,node b)
{
node s;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
s.a[i][k]=(s.a[i][k]+a.a[i][j]*b.a[j][k])%mod;
return s;
}
node qsort(node a,int n)
{
node s;
for(int i=0;i<2;i++) s.a[i][i]=1;
while(n)
{
if(n&1) s=jx(s,a);
a=jx(a,a);
n>>=1;
}
return s;
}
int main()
{
node a;
int n;
a.a[0][0]=a.a[1][0]=a.a[0][1]=1;
while(cin>>n&&n!=-1)
{
node s=qsort(a,n);
cout<<s.a[1][0]<<endl;
}
return 0;
}

主席树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid (l+r)/2
using namespace std;
const int N = 200010;
int n, q, m, cnt = 0;
int a[N], b[N], T[N];
int sum[N<<5], L[N<<5], R[N<<5];
inline int build(int l, int r)
{
int rt = ++ cnt;
sum[rt] = 0;
if (l < r){
L[rt] = build(l, mid);
R[rt] = build(mid+1, r);
}
return rt;
}
inline int update(int pre, int l, int r, int x)
{
int rt = ++ cnt;
L[rt] = L[pre]; R[rt] = R[pre]; sum[rt] = sum[pre]+1;
if (l < r){
if (x <= mid) L[rt] = update(L[pre], l, mid, x);
else R[rt] = update(R[pre], mid+1, r, x);
}
return rt;
}
inline int query(int u, int v, int l, int r, int k)
{
if (l >= r) return l;
int x = sum[L[v]] - sum[L[u]];
if (x >= k) return query(L[u], L[v], l, mid, k);
else return query(R[u], R[v], mid+1, r, k-x);
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i ++){
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b+1, b+1+n);
m = unique(b+1, b+1+n)-b-1;
T[0] = build(1, m);
for (int i = 1; i <= n; i ++){
int t = lower_bound(b+1, b+1+m, a[i])-b;
T[i] = update(T[i-1], 1, m, t);
}
while (q --){
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
int t = query(T[x-1], T[y], 1, m, z);
printf("%d\n", b[t]);
}
return 0;
}

题目解析

有时间再写,先看看课件吧

数论.pptx
基础算法.pdf
模拟贪心.pdf
历年真题选讲.pptx
数据结构考点总结.pdf
g17.pptx
dp11.pptx
搜索和基础算法课件过大无法上传,若需要请点击这里练习Lla

友人

zzx qbxt学习总结.pdf

sjy国庆外出学习总结.pdf

wyf

更多资料

ACM模板

线性代数课件(完整版)同济大学过大无法上传,若需要请点击这里练习Lla

六次模拟赛数据过大无法上传,若需要请点击这里练习Lla

OI-wiki

VJ

udebug

黄学长

讲解超详细(大概)的big_news的博客

插曲

下载链接


  1. 来自OI-WIKI ↩︎

  2. 来自WYF的博客 ↩︎

文章作者: Langlangago
文章链接: https://langlangago.xyz/2019/10/05/201910清北学习总结/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Langlangago's blog

评论