写在前面
05/10/19
今天心情很糟糕，没学新东西，复习没复习，作业没写完，下午要网课，明天要月考，脑子里就像是被一团棉花塞住了。静静的思考了半个小时，把自己手头上的事情排了个序，所以决定先把游记写个一半。刚刚把耳机捂热了，却不放任何的歌曲——我可以静一静了。
再见，那些知识点
暨·两年后填坑清单【不完整
加粗为截至05/10/19尚未掌握的知识点
基本上每个知识点都会附上代码或者是例题，或许还会有一些当时学习的心得？
基础算法
贪心
分治
- 外星密码//这道题在luogu中打了分治的标签，分解括号确实是的（很多时候我都没察觉到考分治），乍一看这题很简单，但是调代码似乎要有点久……
高精度
- 高精度的加法与减法//此外应该还有乘法除法等其他的运算模板，等待以后的lsq去搜集了
递归与递推
BFS && 双向BFS
- 马的遍历//现在怎么也想不起来当初的代码是怎么WA了的，对比了一下似乎也没什么区别鸭……
DFS && 回溯
- 八皇后//回溯必备
前缀和
- 前缀和和差分//总是会很有用的优化技巧
离散化
- 离散化//应该是吧抄老师的代码的emmm这里还有手写删除函数等待挑战
倍增（QMI、RMQ、LCA、ST算法……）
二分、实数域上的二分和三分//注意左右取舍间的开闭情况
//**单调递增序列中** //x或x的后继 while(l<r){ int mid=(l+r)>>1; if(a[mid]>=x) r=mid; else l=mid+1; } return a[l]; //x或x的前驱 while(l<r){ int mid=(l+r)>>1; if(a[mid]<=x) l=mid; else r=mid-1; } return a[l];模拟
- 瑞士轮//至今都还没调对的模拟
STL
//关于STL的博客，就不在这里一一列了
- vector
- set
- map && multimap
- stack
- queue && priority_queue
- bitset
数据结构
- 树
- 图
- 拓扑排序（AOV、AOE）
- 单调栈
a[n+1]=p=0;
for(int i=1;i<=n+1;++i){
if(a[i]>s[p]){
s[++p]=a[i];
w[p]=1;
}
else{
int width=0;
while(s[p]>a[i]){
width+=w[p];
ans=max(ans,(long long)width*s[p]);
p--;
}
s[++p]=a[i];
w[p]=width+1;
}
}
int l=1;r=1;
q[1]=0;
for(int i=1;i<=n;++i){
while(l<=r&&q[l]<i-m) l++;
ans=max(ans,sum[i]-sum[q[l]]);
while(l<=r&&sum[q[r]]>=sum[i]) r--;
q[++r]=i;
}
字符串处理
图论
//我会永远记得奇怪的电梯的！
- 最小生成树
- 最短路
- Floyd版奇怪的电梯//枚举中间点、起点、终点
- Bellman-Ford//xqy之前说这是辣鸡算法（还好啦），就不分配它内存了（？？？）
- SPFA
- Dijkstra && Dijkstra优化版
- 热浪//没优化版本
- 单源最短路经（标准版）//优化版本
- 网络流//考省队的知识……就干脆没去理解了（我好懒）
- 最大流与最小割
- 割点和桥
- 二分图
- 二分图的最大匹配/匈牙利算法（chao de）代码
- 染色法判定二分图
- 强连通分量
- Tarjan//我看懂了……然后代码还没自己敲过，现在又忘了，可惜。
数论
谁能想到我现在学的里面最全的居然是数论……
请参考寒假的博客请麻烦压一下定理的棺材板啦
- 质数与约数
- 线性筛/欧拉筛法
- 辗转相除法
- 扩展欧几里德
- 快速幂
- 欧拉函数
- 威尔逊定理
- 卢卡斯定理
- 费马小定理
- 矩阵
- 高斯消元
- 容斥原理
- 博弈论//关于NIM
- 组合数
- 中国剩余定理
动态规划
一些零碎/未曾遇见的知识点
- 对拍//有用小技能
- 命令行//有用小技能*2
- 计算几何
- 莫队
- 位运算
- 打表//打表出奇迹！
- 随机化
再见，那些题与时刻
再见，那些代码
2018.7码风
#include<bits/stdc++.h>
using namespace std;
int pay[13];
int money[13];
int save[13];
int y[13];
int x[13];
int cannot;
int total;
double finalget;
int main(){
money[1]=0;
for(int a=1;a<=12;a++)
{
cin>>pay[a];
}
for(int i=1;i<=12;i++)
{
x[i]=money[i-1]+300-pay[i];
money[i]=x[i]%100;
if(x[i]<0)
{
cannot=-i;break;
}
else
{
y[i]=(money[i-1]+300-pay[i])/100;
save[i]=y[i]*100;
total+=save[i];
}
}
{
if(cannot==0)
{
finalget=total*1.2+money[12];
cout<<finalget<<endl;
}
else
{
cout<<cannot<<endl;
}
}
return 0;
}
2019.1码风
#include<bits/stdc++.h>
using namespace std;
long long n,m,d=1,num,a=1,b,c;
long long gcd(long long x,long long y)
{
if(y>x)
{
int tmp;
tmp=x;
x=y;
y=tmp;
}
if(x%y==0)
{
return y;
}
else gcd(y,x%y);
}
long long fun(long long x1,long long y1,long long x2,long long y2){
if(y2==n+1) return m;
m=x1*y2+x2*y1;
return fun(m,y1*y2,1,y2+1);
}
int main(){
cin>>n;
if(n==2) m=3;
else m=fun(1,1,1,2);
for(int i=1;i<=n;i++)
{
d=d*(i/gcd(m,i));
m=m/gcd(m,i);
}
m=m*n/gcd(d,n);
d=d/gcd(d,n);
if(m>d)
{
num=m/d;
m=m-d*num;
}
if(m==0) cout<<num;
else
{
a=num;
while(a>0)
{
b++;
a/=10;
}
a=d;
while(a>0)
{
c++;
a/=10;
}
for(int i=1;i<=b;i++) printf(" ");
printf("%lld\n%lld",m,num);
for(int i=1;i<=c;i++) printf("-");
printf("\n");
for(int i=1;i<=b;i++) printf(" ");
printf("%lld\n",d);
}
return 0;
}
2019.8码风
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int T,n,cnt,t[N],c[N],f[N];
inline void sakura(){
for(int i=1;i<=n;++i){
int a,b,s;
scanf("%d%d%d",&a,&b,&s);
if(s==0) s=9999999;
for(int k=1;k<=s;k<<=1){
s-=k;
c[++cnt]=a*k;
t[cnt]=b*k;
}
if(s>0){
c[++cnt]=a*s;
t[cnt]=b*s;
}
}
}
inline int time(){
int t1,t2,t3,t4;
scanf("%d:%d %d:%d",&t1,&t2,&t3,&t4);
t2+=t1*60,t4+=t3*60;
return t4-t2;
}
int main(){
T=time();
scanf("%d",&n);
sakura();
for(int i=1;i<=cnt;++i)
for(int j=T;j>=c[i];--j)
f[j]=max(f[j],f[j-c[i]]+t[i]);
printf("%d",f[T]);
return 0;
}
再见，那些OJ/网站
- 学校里的OJ：DYZXOJ
- 洛谷（初学者的乐园，于是我在这里出不去了）：洛谷
- yxc的AcWing：AcWing
- 杭电大的OJ，和xqy打了一场爆零的比赛：杭州电子科技大学OJ
- 听hkn学长介绍的POJ：北大的OJ
- 万能博客库CSDN：CSDN
再见，那些人与事
此篇不作公开（像是有人会看一样），单独私发。