P1082 [NOIP2012 提高组] 同余方程
题中$$ax \equiv 1\pmod{b}$$这个式子，根据同余的定义， $$ax \mod b=1 \mod b$$ $1$模任何数都余$1$，所以$$ax \mod b=1$$ 根据模运算的性质得 $$ax-by=1$$ 于是这个方程就转化成了一个漂亮的不定方程，可以用exgcd求解。
2021-01-19 27 0
阅读全文
2020，我的OI
OI生活重启（一月到二月） 初一上的时候，我因为不适应初中生活，文化课爆炸，停了一个学期的OI。放假了，我满心欢喜重启竞赛生活的时候，我却发现，我学过的东西忘的差不多了。 于是我从搜索和01背包开始学，再到快速幂、最短路、最小生成树……虽然学得还是很慢…
2021-01-06 23 0
阅读全文
物理简答题整理
听录音机放出自己的录音，会觉得不像自己的声音。这是为什么呢？ 自己说话或唱歌时，通过骨传导听到声音，而播放自己的录音时，声音通过空气传播。传声介质不同，传播过程中声音音色发生了改变。 向暖瓶中倒水，水越多声音越尖细，为什么？ 向暖瓶中倒水，瓶…
2021-01-03 23 0
阅读全文
洛谷 P2014 [CTSC1997]选课 树形DP
#include<bits/stdc++.h> #define N 305 using namespace std; int n,m; vector<int> G[N]; int w[N]; int dp[N][N];//dp[i][j] : 从i往下选j门课得到的最大学分 void dfs(int u,int d){//选到第u门课，还剩d门课可以选 if(d==0)retu…
2020-12-30 21 0
阅读全文
差分约束系统 笔记
每个约束条件$X_i-X_j≤c_k$可以变形为$X_i≤X_j+c_k$，可以把每个变量$X_i$看做有向图中的一个点，对于每个约束条件$X_i-X_j≤c_k$，从节点j到节点y连一条长度为$c_k$的有向边。再把$0$号节点和每个节点连一条长度为$0$的边。然后以0为源点求单源最短路径。则$X_i$就是d[…
2020-12-29 25 0
阅读全文
最短路计数问题
定义cnt[i]表示源点到i点的最短路条数。 通过v点松弛源点r到u的距离时，若成功松弛（d[v]+val[i]<d[u]），r→v的最短路条数取代了r→u的最短路条数（cnt[u]=cnt[v];），因为最短路不是同一个长度了，所以之前记录的作废。 若新路径和目前最短路长度一样（d[v]+v…
2020-12-25 33 0
阅读全文
OI学习路线
ver. 1.0.1 假设你已经熟练掌握C++语言和OI有关的部分。 贪心和DP并没有被加入其中，原因是我觉得贪心和动态规划是一种思想，需要长期练习，不能被简单地归入某个学习阶段。 Part 1 算法基础 排序栈、队列、链表二分查找和二分答案前缀和和差分dfs和bfs （…
2020-12-24 53 0
阅读全文