2019寒假成都摸鱼记

前言

还没放寒假的时候就知道要出去了,而且不用考生物,也是比较期待吧,于是肆意颓whk。这篇游记是Day7晚上在火车上写的,大多数印象比较清晰,知识点忘完了。

游记较长,大家可以跳着看

Day -inf

突然听说寒假要出去,还不用考生物,感觉很爽,也开始期待这场旅行(颓文化课)了。

Day -1

上午考完英语后,就往校门口跑。没到门口就看到我爹了,但没看到潘老师。打电话才知道去考场找我们去了,假,连我在桌子上留的纸条都没看见。总归是到校门口了,就往火车站走。
赶时间的情况下,还在火车站对面的铁酒吃了一顿不错的午餐,心真是大。不过也没有很赶啦,着急地去了候车室后发现还早,就玩起了手机。
候车的时候吃逼乎的安利下了这个神奇的计算器:Kalkyl(真叫这个,不是乱码)

居然可以画图像!虽然我严重怀疑这个${f(x)=x^x}$的图像画的有问题.

玩了会觉得没啥意思,然后就上车了。

在车上写了贪心的学习报告。本来准备写完后写线性DP的,但是鉴于贪心写了1000+(我太懒了),就没写了,开始颓CSGO

打了一下午死斗,全是机器人一点都不好玩。手机也没有信号,又回忆起在重庆旅游时手机有信号没电的痛了……

补了《Unnatural》的第一话,太好看了wocccccccccc!!可为什么硕鼠不能下载收费视频啊QAQ。

也没有全程颓啦,玩累了后把洛谷blog上的文章搬到了hexo上,顺便修改了一下补以前的锅

关于《巴黎圣母院》,我忘了

晚上没睡好QAQ,对面的小孩是真的吵。就晕晕地睡了大概四个小时。

这无所事事的一天就过去了。

Day 0

早上6:00到站,第一感觉就是,火车站怎么跟襄阳站一样破,才知道这是老城区。(去的照片搞丢了,这是回来的时候照的)

火车站

出站后,找了好久才看到龟缩在角落的KFC,吃的也不算是丰盛。

实在是太困了…于是去了锦里Starbucks,太早了人家都还没营业,好心的店主先把我们放进去了www。

待到了大概9:30的样子,回酒店了。感觉从酒店去锦里的时间比从锦里去酒店的时间要长的多。在酒店大堂看到了关老师(没上一节课的班主任)

领了听课证、课表和笔记本后,就去吃午饭了。没吃火锅.难受.jpg。下午也没干啥,在酒店打了一下午LOL

然后Day 0就结束了,依然无所事事。

Day 1

起的早,在食堂吃了早饭后,得知教室居然在食堂里面???不过还不错啦。

最开始是hcy老师讲搜索DFS我就没会过,讲了个框架,剩下大部分是讲例题。八皇后到是会,但八数码是啥啊……讲八数码,hcy就开始讲Hash,说到Hash,我就想到一个月前在机房用STL_SetA掉的字符串哈希,但是八数码好像并不能用Set做……一整节课,基本上强制在线。

搜索终于讲完了,接着讲的是贪心这个我会

国王游戏终于可以自己推了,高精依然不会(想)写。

贪心大概就是做题讲题做题讲题,知识性的东西并不多。

再然后就是分治与二分(没讲三分QAQ)。

思想还是清楚了,毕竟学过。然而在做题的时候发现自己打的好像是个假的二分板子:

1
2
3
4
5
while(l+1<r){
int mid=(l+r)>>1;
if(ans>=mid)mid=l;
else mid=r;
}

然后自己的DEBUG套路好像也行不通了(增减”=“号与+1或-1)

于是老老实实地就题论题打板子。

至于快速幂,讲的板子好像和我打的又不太一样还好我那个也能用

晚上把部分题写了写,剩下了一些(懒得)难以实现的。

回到酒店后颓了几集《Unnatural》。

Day 1就结束了。

Day 2

没吃早饭(真的吃不下)

早上去了没来什么人???(果然都吃早饭去了)

一整天都在讲数据结构

二叉堆?_priority_queue_就好了!

二叉搜索树?_set_就好了!

改革春风吹满地,_STL_真争气。

然后就讲起了并查集。

板子还是比较熟的,不过老师没讲按秩合并,只讲了路径压缩

这是按秩合并的板子:

1
2
3
4
5
6
7
8
int fa[maxn],size[maxn];
void init(int n){for(register int i=1;i<=n;i++){fa[i]=i;size[i]=1;}}
int find(int x){return fa[x]==x?x:find(fa[x]);}
void merge(int x,int y){
int xx=find(x),yy=find(y);
if(size[xx]>size[yy])swap(xx,yy);
fa[xx]=yy;size[yy]+=size[xx];
}

讲起了线段树

我果然还是不会有灵魂(Lazy Tag )的线段树QAQ。懂是懂了,但是怎么实现啊

在luogu找了题解学习,大概明白怎么实现了。

讲完lazy tag,又讲了一大堆玄学

那一刻,仿佛所有题都能套线段树A掉。线段树太棒了

树状数组离线了……学不来
晚上写了一写题目,很多堆部分的练习以前都写过。

期望的RMQ和LCA都没有讲。

Day 2结束了。

Day 3

考试日。

上午在讲数论,并没有慌得一批。

gcd有一个更加简短的实现了:

1
int gcd(int a,int b){return b?gcd(b,a%b):a;}

lcm相对简单:

1
int lcm(int a,int b){return a*b/gcd(a,b);}

关于扩展欧几里得,以前打乘法逆元的板子时了解过,一直不会推,现在也会了。这里只给出代码:

1
2
3
4
5
6
7
8
9
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1;y=0;
return a;
}
int g=exgcd(b,a%b,y,x);
y-=a/b*x;
return g;
}

然后是筛法的预备知识:质数判定:

只需要枚举到${\sqrt n}$就行了,但需要注意从2枚举。

1
2
3
4
5
6
7
bool check(int n){
if(n==1||n==0) return 0;
for(register int i=2;i<=sqrt(n);i++){
if(!(n%i)) return 0;//一定要注意位运算符优先于算数运算符
}
return 1;
}

然后是埃氏筛(好久没打写挂了好几次)

1
2
3
4
5
6
7
8
for(register int i=1;i<=maxn;i++){
if(check(i)&&!vis[i]){
is[i]=1;
for(register int j=i;j<=maxn;j+=i){
vis[i]=1;
}
}
}

质因数分解:不放在这了。

最后就是逆元了:

可以运用费马小定理

${a^{p-1}}$ ≡ 1 (mod p),p为质数,a与p互质 (注意p为质数,不过noip如果要求逆元,p肯定是质数)

由此可得: a*${a^{p-2}}$ ≡ 1 (mod p)
所以,当模数为质数p时,a的逆元等于${a^{p-2}}$‘

当然也可以运用扩展欧几里得,这里不再赘述。

知识点就这些,也没写到什么题。下午就开始考试了。

这是题目:

T1随便写(虽然考场上没写优化挂了60分)

T2在考场上想了一个用set维护的骚操作,复杂度带log,应该能过,可惜最大值维护错了。

这是改后的代码:

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<set>
#define max(a,b) a>b?a:b
#define maxn 100010
using namespace std;
set<int>a;
set<int>::iterator it;
int main(){
freopen("guinness.in","r",stdin);
freopen("guinness.out","w",stdout);
int m,x,n,t,cnt=1,ans,maxx=0;
scanf("%d",&m);
for(register int i=1;i<=m;i++){
scanf("%d",&x);
a.insert(x);
}
scanf("%d",&t);
for(register int i=1;i<=t;i++){
it=a.begin();ans=1;
scanf("%d",&n);cnt=0;int tmp[n+1];
for(register int j=1;j<=n;j++){
scanf("%d",&x);
tmp[++cnt]=x; bool getans = 0;
for(it,ans;it!=a.end();it++,ans++){
if(x<*it){
printf("%d ",ans);
getans=1;
break;
}
}
if (!getans) printf("%d ",a.size()+1);
}
printf("\n");
while(cnt) a.insert(tmp[cnt]),cnt--;
}
fclose(stdin);fclose(stdout);
return 0;
}

T3可以爆搜,但是没时间(懒得写)了,就没写,直接交上去了。

所以成绩并不是很好。

Expected:140 Score:40

Day 4

换老师了。

今天讲的是图论。

先讲了一大堆图的概念,学过了,所以在下面复习Dijkstra+Heap

然后开始讲图的存储方式,前向星听了一下,剩下的学过,继续颓Dijkstra+Heap

终于开始讲最短路了:
果然开始就讲Dijkstra…没有堆优化太咸了!!!

于是继续颓Dijkstra+Heap

讲完后开始讲可爱的SPFA了,标准版的最短路果然还是构造数据卡了SPFA。

挂个SPFA的工作图:

关于Bellman Ford,只是提了一下和SPFA很像,丢了一个blog链接,并没有细讲。

讲完单源,自然开始讲多源

多源自然讲了可爱的$O(n^3)$的Floyd

五行代码真是太好了:

1
2
3
4
5
for(register int k=1;k<=n;k++)
for(register int i=1;i<=n;i++)
for(register int j=1;j<=n;j++)
if(map[i][k]+map[k][j]<map[i][j])
map[i][j]=map[i][k]+map[k][j];

在做题的过程中学了一些奇巧淫技

比如:

  1. 多源一汇最短路径?存个反图跑SPFA:

  2. 死掉的SPFA也可以判负环:(代码摘自这里

    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
    bool spfa(int n) {
        int u, v;
        while (!q.empty()) q.pop();
        memset(vis, false, sizeof(vis));
        memset(in, 0, sizeof(in));
        fill(d, d + n, oo);
        d[0] = 0; vis[0] = true;
        q.push(0);
        while (!q.empty()) {
            u = q.front();
            vis[u] = false;
            for (int i = prev[u]; i != -1; i = edge[i].next) {
                v = edge[i].v;
                if (d[u] + edge[i].t < d[v]) {
                    d[v] = d[u] + edge[i].t;
                    if (!vis[v]) {
                        in[v] ++;
                        if (in[v] > n) return true;
                        vis[v] = true;
                        q.push(v);
                    }
                }
            }
            vis[u] = false;
            q.pop();
        }
        return false;
    }

最短路讲完后是最小生成树,一样只是提了一下Prim,重点是Kruskal
使用了并查集,也非常好理解:
直接给出代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int find(int x){return fa[x]==x?x:find(fa[x]);}
bool merge(int x,int y){
int xx=find(x);int yy=find(y);
if(xx!=yy){
fa[xx]=yy;
return 1;
}
return 0;
}
for(register int i=1;i<=m;i++){
if(merge(s[i].x,s[i].y)){
sum+=s[i].w;cnt++;
if(cnt==n-1) break;
}
}

非常好理解,于是讲的很快。

然后是TopSort(拓扑排序):
相当于是寻找InDegree=0的点,push,然后删除。

也很好理解。代码实现:(行吧这是课件上的代码我没看懂)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool TopologicalSort(DirectGraph &g,vector<int>&in_degree){
queue<int>qu;
int cnt=0;
for(auto ite=in_degree.begin();ite !=in_degree.end();++ite){
if(*ite==0){
qu.push(*ite);
}
}
while(!qu.empty()){
int v=qu.front();
qu.pop();
printf("%d ",v);
cnt++;
for(const int &i:g.adj.at(v)){
if(0==--in_degree[i]){
qu.push(i);
}
}
}
return cnt>=v;
}

最后讲了树上倍增求LCA(该来的总是会来)

知识听懂了,但是实现过程看的稀里糊涂的,几乎强制在线

就像中国RMB一样,每次都尝试最大的${2^i \leq n}$,总能凑出LCA位置,毕竟${2^0 =1}$嘛。

晚上写了个Dijkstra+Heap的A+B Problem(我太咸了)

回酒店依然补剧…

Day 5

讲DP,本来满怀期待的,后来发现好多题以前都写过…

唯一值得一提的是01背包的原理又理解了一遍,比以前掌握的好多了。

Day 5没啥好写的。

Day 6

又是考试日。也换老师了。

上午讲的STL,也没啥好写的,会的以前都会,不会的比如全排列,无非感叹很有用,然后会用了,也没什么好说,(所以这玩意真方便)

下午的考试:

解压后看T1,看了看数据范围,觉得60pts打表能出,很稳,就开了Excel,写T1 Expected 60

5分钟写了暴力挂在那打表,开始看T2。

T2感觉没啥思路,打暴力的时候把dfs忘了(果然我还是不会dfs)写了${O(n^3)}$的存图,然后T1还没跑完,很慌,关了exe,把源程序的20改成了10打表,打开一看:

……

直接撸快速幂,100到手。

表变成了这个

那个tip还是我手画了一棵树后验证的

实在想不出来,一脑抽,就把T1交了……

然后看到群里的:

然后….

……

不得不滚回去打T2了。

暴力写挂了……

T3依然不知道在讲什么。

所以考试算是半凉凉吧……

Expected 160 Score=100

莫名rk3。

Day 7

上午讲了历年的一些题。

听懂了xkdyh的玄学解法,也会了货币系统老凯的疑惑

心心念念的天天爱跑步没讲

直到Day 7我才知道原来课表里面没有KMP

然后就结束了。

突然想到要滚回去上whk了,对这个地方还是有点不舍。

挂几张照片吧。

Day inf

卧在学校里,终于补了这篇游记的锅,虽然干货不多,但是知识点会慢慢写总结。

做该做的,才对的起自己。

# 游记
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×