2020年10月13日随笔
现在是下午四点半,由于眼镜框坏掉(被我不小心压了然后掰坏的),我翘了离散数学的课,现在在宿舍码这一篇博客。
这篇博客是留给我自己的。
pb_ds简介
pb_ds简介
pb_ds 库全称 Policy-Based Data Structures,又称平板电视。
pb_ds 库封装了很多数据结构,比如哈希(Hash)表,平衡二叉树,字典树(Trie 树),堆(优先队列)等。
就像 vector 、 set 、 map 一样,其组件均符合 STL 的相关接口规范。部分(如优先队列)包含 STL 内对应组件的所有功能,但比 STL 功能更多。
pb_ds 只在使用 libstdc++ 为标准库的编译器下可以用。
堆
使用方法
123456789101112#include <ext/pb_ds/priority_queue.hpp>#include <bits/stdc++.h>// 注意<ext/pb_ds/priority_queue.hpp>不在<bits/stdc++.h>内using namespace __gnu_pbds;//注意pb_ds和std的类名称里有重复的地方//如果仅写这句话且不写using namespace std; ,则定义priority_queue&l ...
codeforces蓝名了!
蓝名了耶,finally!
昨天下午打完一场Education Round,虽然只切了四道,但是按照以往的经验,我的积分应该还是会上涨的。果不其然,今早看结果的时候直接升到蓝名了。芜湖~
说来也惭愧,接触OI也这么久了,还是人生第一次蓝名QAQ
从上次的CCPC网络赛失利开始,每一场cf的#div2比赛我都不会放过,才一点一点地打了上来,这期间大概上涨了200分,希望以后也再接再厉吧!
听vying说,他花了半年地时间从紫到橙。而已确定的一次校赛就在明年三月,距离现在也是差不多半年时间,希望我也能在校赛之前橙名。
加油!
Bitset小记
简介
std::bitset标准库中的一个存储0/1的大小不可变容器。严格来讲,它并不属于 STL。
由于内存地址是按字节即byte寻址,而非比特bit,一个bool类型的变量,虽然只能表示0/1, 但是也占了1 byte的内存。
bitset就是通过固定的优化,使得一个字节的八个比特能分别储存 8 位的0/1。
对于一个 4 字节的 int 变量,在只存0/1的意义下,bitset占用空间只是其132\frac{1}{32}321,计算一些信息时,所需时间也是其132\frac{1}{32}321。
在某些情况下通过bitset可以优化程序的运行效率。至于其优化的是复杂度还是常数,要看计算复杂度的角度。一般bitset的复杂度记为:(设原复杂度为O(n)O(n)O(n))
O(nw)O(\frac{n}{w})O(wn),其中w=32w=32w=32,这种记法较为普遍接受
O(nlogw)O(\frac{n}{logw})O(logwn),其中wvwvwv为计算机一个整型变量的大小
构造函数
用字符串构造时,字符串只能包含 ‘0’ 或 ‘1’ ,否则会抛出异常。
构造 ...
STL的简单应用
迭代器
指向某个STL容器container中的元素的迭代器的类型一般为container::iterator
迭代器可以用来遍历容器
注意auto可以起到同样的效果
123456789101112131415vector<int> data(10);// 使用下标访问元素for (int i = 0; i < data.size(); i++) cout << data[i] << endl; // 使用迭代器访问元素for (vector<int>::iterator iter = data.begin(); iter != data.end(); iter++) cout << *iter << endl; for (auto iter = data.begin(); iter != data.end(); iter++) cout << *iter << endl; for (auto x : data) cout << x << endl ...
数论杂项
类欧几里得算法
时间复杂度O(logn)O(logn)O(logn) 求f(a,b,c,n)=∑i=0n⌊ai+bc⌋g(a,b,c,n)=∑i=0ni⌊ai+bc⌋h(a,b,c,n)=∑i=0n⌊ai+bc⌋2f(a,b,c,n)=\sum_{i=0}^{n} \lfloor \frac{ai+b}{c} \rfloor \quad g(a,b,c,n)=\sum_{i=0}^{n} i\lfloor \frac{ai+b}{c} \rfloor \quad h(a,b,c,n)=\sum_{i=0}^{n} \lfloor \frac{ai+b}{c} \rfloor^2f(a,b,c,n)=∑i=0n⌊cai+b⌋g(a,b,c,n)=∑i=0ni⌊cai+b⌋h(a,b,c,n)=∑i=0n⌊cai+b⌋2 这三个函数的值
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include <bits/stdc++.h> ...
鸽巢原理
简介
雀巢原理:如果把n+1个个物体放进n个盒子,那么至少有一个盒子包含两个或者更多个物体
加强版1:设q1,q2,…,qnq_1,q_2,\ldots,q_nq1,q2,…,qn是正整数。若将q1+q2+⋯+qn−n+1q_1+q_2+\cdots+q_n-n+1q1+q2+⋯+qn−n+1个物体放入n个盒子中,那么或者第一个盒子至少含有q1q_1q1个物体,或者第二个盒子至少含有q2q_2q2个物体,…或者第n个盒子至少含有qnq_nqn个物体
加强版2:设n和r都是正整数。如果把n(r−1)+1n(r-1)+1n(r−1)+1个物体分配到n个盒子中,那么至少有一个盒子含有r个或更多的物体。
应用1
在13个人中存在两个人,他们的生日在同一个月份里。
应用2:
设有n对情侣,至少要从这2n个人中选出n+1个人才能保证能够选出一对情侣。
应用3:
给定m个整数a1,a2,a3,…,ama_1,a_2,a_3,\ldots,a_ma1,a2,a3,…,am,存在满足0≤i<j≤m0\le i<j\le m0≤i<j≤m的整数i和j ...
筛法
欧拉(Euler)筛法求素数
时间复杂度为O(n)
1234567891011121314151617181920void init(){ phi[1]=1; for(int i=2;i<MAXN;i++){ if(!vis[i]){ phi[i]=i-1; pri[cnt++]=i;//cnt为素数的总数 } for(int j=0;j<cnt;j++){ if(1LL*i*pri[j]>=MAXN)break; vis[i*pri[j]]=1; if(i%pri[j]){ phi[i*pri[j]]=phi[i]*(pri[j]-1); } else { phi[i*pri[j]]=phi[i]*pri[j]; ...
2020_09_23随笔
回顾
大二上开学快两周了,一切都似乎重回正轨。暑假的落败带来的惋惜与沮丧,却仍旧萦绕在心头挥之不去。
上周周末的CCPC网络赛,我争取到了一个临时队的名额。可整整一个下午,我们队就只完成了四道签到题,而且比赛过程中,脑子一团浆糊,还需要大一的队友来纠正我的错误。最后,我们就连另一个临时队都没打过。比赛结束后排名2000+ ————在3000个队伍之中。
菜!!!
像是当头一棒,我霎时间感觉自己的梦想和坚持是如此的可笑。
“我行吗???” ————我这几天来一直问着自己。
高中OI生涯的戛然而止,校队选拔的落榜…我在同一条河流跌倒了两次。
迷茫与抉择
说实话,有生以来,我从来没有像现在这样自卑过。
从前,我总觉得自己出类拔萃,能不能人群中脱颖而出,只是取决于我有没有这样的想法。
慢慢的,我才发现,我就是一个自以为是且执行力极差的懦夫。
这种念头在高中时就已有,但现在已经占据了我的脑海。我像是在暴风雨的大海中夜航船的渔夫,在焦虑与自我否定的漩涡巨浪中苦苦挣扎。
从前,我的梦想是做一个科研工作者,在求知的道路中无忧无虑地生活。可现在,我才发现,这似乎与我很遥远。
说实话,家里虽然没啥经济 ...
大一 · 下
2020_4月-6月
糟糕的处境
虽然受到疫情影响,但我们学校还是早早地在五月就开学了
六月底的期末考试周就快到了,说实话,复习备考的那段时间,我是真的身心俱疲…因为这次考试的成绩会和上学期成绩的在一起算平均分,然后决定专业分流的方向。对于死读cs的我来说,如果均分不够就gg了QAQ
万幸,我校作为cs不是那么突出的学校,要进计算机专业的话,卷得还是没那么严重,所以,录取分数线也不算很高。
很好,我上学期就是这样想的,然后水了一学期我就是那种最后一个月都敢翘高数课的憨憨
所以…不出意料,结果一塌糊涂,大一上的均分才76,整个大类里垫底的水平。不幸中的万幸,还好没有挂科,在这里感谢思修老师高抬贵手hh
备考
当我意识到问题的严重性的时候,已经是4月底了。
在和学长交流过后,发现就算按照去年的分数线,我这学期也只有均分90以上才能稳进cs。欸,还能咋办,急也没用,只有埋头苦学了呗。不过由于大一下刚开始一个多月一直在划水,东西欠的太多,而且平时课业也比较重,补的时候是真的令人窒息,在这里放张我当时的日程表吧:
说实话,我这段时间过得有高三内味了T_T 特别是到了考试周, ...