DONE:
2020OPEN BBBSSSGGGPPP
2020FEB BBBSSSGGGPPP
2020JAN BBBSSSGGGPPP
2019DEC BBBSSSGGGPPP
2019OPEN BBBSSSGGGPPP
2019FEB BBBSSSGGGPPP
2019JAN BBBSSSGGGPPP
2018DEC BBBSSSGGGPPP
2018OPEN BbbSSsGggppP
2018FEB BbbsssgggpPP
2018JAN bbbsssgggppp
2017DEC bbbsssgggppp
2017OPEN bbbsssgggppp
2017FEB bbbsssgggPPp
2017JAN bbbsssGggPpp
2016DEC bbbsssgggppp
2016OPEN bbbsssgggppp
2016FEB bbbsssgggppp
2016JAN bbbsssgggppp
2015DEC bbbsssGggPPP
TODO:
2020OPEN ____________
2020FEB ____________
2020JAN ____________
2019DEC ____________
2019OPEN ____________
2019FEB ____________
2019JAN ____________
2018DEC ____________
2018OPEN bb__s_gg_p
2018FEB bbsssgggp_
2018JAN _______g_ppp
2017DEC ___sssgggppp
2017OPEN bbbsssgggppp
2017FEB bbbsss_____p
2017JAN bbbsss_gg_pp
2016DEC bbb___gggp_p
2016OPEN bbbsssgg__pp
2016FEB bbbsssgggppp
2016JAN bbbsssgggppp
2015DEC bbs____g__
2015OPEN bbbsssggg
2015FEB bbbsssggg
2015JAN bbbsssggg
2014DEC bbbsssggg
图论
最短路（必须会堆或set
最小生成树（必须会并查集
LCA
数据结构
堆 priority_queue
并查集
树状数组
线段树
动态规划 Dynamic Programming
最长不下降子序列
最长公共子序列
背包
树形DP
区间DP
数学 （USACO几乎不考）
Silver
栈 Stack
单调栈 monotonic stack
队列 Queue / BFS
单调队列 monotonic queue
链表 Linked List
优先队列
C++ STL
递归 / DFS / BFS
Gold
数据结构
树状数组 Fenwick Tree
线段树 Segment Tree
并查集 Union Find Set
堆 Heap / 优先队列 PriorityQueue
平衡树 set / map
图论
最短路
Dijkstra
Floyd
最小生成树
Prim
Kruskal
最近公共祖先 LCA
倍增 Binary Lifting
动态规划
背包 knapsack problem
区间DP interval
树形DP tree DP
数学
筛法 sieve of Eratosthenes
gcd / lcm
快速幂 square and multiply
cross product
乘法逆元 取模
Platinum
插头DP
线段树分治
广义后缀自动机
高斯消元
矩阵乘法
行列式求值
其他
二分 binary search
Platinum
没出过 FFT 和多项式
sort(a, a + n);
sort(&a[0], &a[n])
USACO 2020 US Open Contest, Platinum
Problem 2. Exercise
1.
所有环的LCM是最终的步数
10 = 2 + 2 + 3 + 3
问有多少个排列，对应 2 2 3 3 这些环长
10! / 2 / 2 / 3 / 3 / 2! / 2!
除以所有环长，除以所有相同环长个数的阶乘
f[i][j]
到当前为止
总和是 i， LCM是 j
枚举加了l个k
f[i][j] -> f[i+l*k][lcm(j, k)] / pow(k, j) / l!
基本没有问题 j 的可能性会特别多
Problem 3. Circus
只有一个中心点
空了2个
((距离中心点 <= 1 的点的个数) - 2) 个点可以互换位置，答案要 除以 点数!
如果两个中心点距离是d （之间有d条边，d+1个点）
在空d+2个点时，这两个中心点会融为一体。
USACO 2020 February Contest, Platinum
Problem 3. Help Yourself
连通块 个数 k 次方
如果有 c 个连通块，那么贡献是 c ** k
改一下贡献，改成 C(c, k)
k=1 样例答案：8 c
k=2 样例答案：1 c*(c-1) / 2
(k=2的答案) * 2 + (k=1的答案) 就是最终需要的结果
c*(c-1) / 2 * 2 + c = c**2
P6202 [USACO07CHN]Summing Sums G
0: ai s
2:ai+(n-2)s (n(n-2)+1)s
4:ai+(n-2)s+(n-2)(n(n-2)+1)s (n(n-2)+1)(n(n-2)+1)*s
首项 s
公比 (n*(n-2)+1)
最后的和再 *(n-2)
P6218 [USACO06NOV] Round Numbers S
P4317 花神的数论题
数位DP
是否考虑前导0
P6208 [USACO06OCT] Cow Pie Treasures G
起点只有1个，其他起点应该设为 -inf
界外设为 -inf
P6205 [USACO06JAN]Dollar Dayz S
USACO 难得出一次高精度
P6193 [USACO07FEB]Cow Sorting G
首先整理出若干个环
每个环有2个选择
环长l，所有数字之和s，环上最小的数字mn
P6770 [USACO05MAR]Checking an Alibi 不在场的证明
简单的最短路
P6768 [USACO05MAR]Ombrophobic Bovines 发抖的牛
Floyd 多重匹配 最大流
P6771 [USACO05MAR]Space Elevator 太空电梯
把物品排序，做混合背包，记录哪些高度可以凑出来
2和4在mod7的意义下，互为乘法逆元
2 * 4 % 7 == 1
2 * x % 7 == 1
a % x % p == 1
如果存在解(0 < x < p)，那么x是唯一的
存在解的条件a和p互质
4相当于1/2
2和1/2互为倒数
12 / 2 % 7 = 12 * 4 % 7 = 6
12 / 4 % 7 = 12 * 2 % 7 = 3
12 / 2 % 6 = 0
6 / 2 % 6 = 3
p是质数
费马小定理
a**(p-1) % p == 1
a * a**(p-2) % p == 1
a**(p-2)%p 是 a 的逆元
p不是质数
(1) 扩展欧几里得
(2) 欧拉定理
int gcd(int a, int b)
{
if (b == 0)
{
return a;
}
else
{
return gcd(b, a % b);
}
}
已知a和b，求x和y使得
ax + by = gcd(a, b)
求出其中一组解，求|x|+|y|最小的一组解
只考虑a和b互质的情况
ax + by = 1
如果(x, y)是一组解
那么(x + b, y - a)也是一组解
void exgcd(int a, int b, int &x, int &y)
{
if (b == 0) // 1 * a + 0 * 0 = gcd(a, 0)
{
x = 1;
y = 0;
return;
}
int g = exgcd(b, a % b, y, x);
// b * y + (a % b) * x == 1
// b * y + (a - a / b * b) * x == 1
// (b * y - a / b * b * x) + a * x == 1
// b * (y - a / b * x) + a * x == 1
y -= a / b * x;
// y' = y - (a / b) * x
// x' = x
// b * y' + a * x' == 1
}
a * x + b * y == 1
a * x == 1 (mod b)
// y' = x - (a / b) * y // x' = y
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
(a ** b) % p = ((a % p) ** (b % p)) % p
输入a和b
求c
b * c == a (mod 19260817)
scanf("%d", &a);
读入优化
// cin >>
scanf
// fread()
getchar() 每次读入下一个字符
剩下的自己分析
aksjdh123
p <= 2147483647
如果a和b满足
0 <= a < p
0 <= b < p
那么a*b没有超过unsigned long long的范围
1! 2! .. n!
inv(n!) * n = inv((n-1)!)
..
inv(1!)
inv(i) = inv(i!) * (i-1)!
for(int i=n;i>=1;i--)
{
ans[i]=(last*c[i-1])%p; //last = inv(i!)
last=(last*i)%p;
}
(r3 * 70 + r5 * 21 + r7 * 15) % 3 = r3
(r3 * 70 + r5 * 21 + r7 * 15) % 5 = r5
(r3 * 70 + r5 * 21 + r7 * 15) % 7 = r7
r103 * ??
107
109
107 * 109
m = 103 * 107 * 109
r103 * ((m / 103) * pow(m / 103, 103 - 2, 103))) % m
using namespace std;
int n, a[10], b[10];
long long m = 1, z;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
m *= a[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < a[i]; j++) {
if (m / a[i] * j % a[i] == b[i]) {
z += m / a[i] * j;
}
}
}
cout << z % m << endl;
}
__builtin_parity 数1的个数
__builtin_popcount
3 2 1 4 5
1 2 3 4 5
1 2 3 4 5
3 2 1 4 5
其中一个是排列，另外一个不是，能不能做？
可以的
把是排列的，变成1到n，不是的跟着换
最后去最长上升子序列
两个序列，都是1到n每个数字出现2次，可以不可以做？
1 2 3 1 2 3
1 1 2 2 3 3
a b c a b c
a a b b c c
4 1 4 1 5 2 5 2 6 3 6 3 第一种理解方式
a:
(1, 1)
(1, 2)
(4, 1)
(4, 2)
b:
(2, 3)
(2, 4)
(5, 3)
(5, 4)
c:
(3, 5)
(3, 6)
(6, 5)
(6, 6)
在二维坐标中，求最长上升子序列
最长公共子序列，LCS，只能暴力O(n^2)
最长不下降子序列，LIS，可以O(n log n)
f[i] 表示以a[i]结束的最长不下降子序列的长度
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < i; j++)
{
if (a[j] <= a[i])
{
f[i] = max(f[i], f[j]);
}
}
f[i]++;
ans = max(ans, f[i]);
}
cout << ans << endl;
f[i] 表示，到当前为止，长度为i的不下降子序列，最后一位最小是多少。
如果不存在长度为i的不下降子序列，那么f[i] = inf;
f是单调增加的
初始化f数组为无穷大
f[0] = 0;
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
if (f[j - 1] <= a[i] && f[j] > a[i]) // 不下降
if (f[j - 1] < a[i] && f[j] >= a[i]) // 上升
{
f[j] = a[i];
ans = max(ans, j);
break;
}
}
}
可以用二分，得到f数组中第一个大于a[i]的位置
cout << ans << endl;
f[0] = 0;
int ans = 0;
for (int i = 1; i <= n; i++)
{
int pos = upper_bound(f + 1, f + n + 1, a[i]) - f;
f[pos] = a[i];
ans = max(ans, pos);
}
进一步化简
清无穷大
memset(f, 0x3f, sizeof f);
数组整体从0开始用。
int ans = 0;
for (int i = 1; i <= n; i++)
{
int pos = upper_bound(f, f + n, a[i]) - f;
// 如果是不下降，那么upper_bound
// 如果是上升，那么lower_bound
f[pos] = a[i];
// *upper_bound(f, f + n, a[i]) = a[i];
}
cout << (lower_bound(f, f + n, 0x3f3f3f3f) - f) << endl;
// 找到第一个inf
f[i]表示以值i结束的最长不下降子序列的长度
不仅可以存储最长的长度，还可以存储方案数
(长度, 方案数)
暴力O(n^2)
使用数据结构优化O(n log n)复杂度
数据结构:
为什么可以用后2个？因为
询问一定是前缀
修改一定越改越大
值域非常大怎么办？
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < a[i]; j++)
{
f[a[i]] = max(f[a[i]], f[j]);
}
f[a[i]]++;
ans = max(ans, f[a[i]]);
}
cout << ans << endl;
a[0] .. a[n-1]
for (int i = 0; i < n; i++)
{
l[lc++] = a[i];
}
sort(l, l + lc);
1 1 1 2 2 2
lc = unique(l, l + lc) - l;
for (int i = 0; i < n; i++)
{
a[i] = lower_bound(l, l + lc, a[i]);
}
1 4 第k小的
1001 第k大的
0110 第k小的
2 3 第k大的
如果A集合 < B集合
那么将A和B转为01序列，
一定是A的序列 > B的序列
USACO 2018 DEC P2
我们希望知道，以每个数字作为开始，最长不下降子序列 多长，多少个
a[1] a[2] a[3] ... a[n]
b[i] = a[i] - a[i-1]
a[i] = b[1] + b[2] + ... + b[i]
a[l] += x, a[l+1] += x, ..., a[r] += x
b[l] += x, b[r+1] -= x;
原数组a
树状数组c
c[i] = a[i - lowbit(i) + 1] + ... + a[i]
原数组a
a[1] = c[1] + c[2] + c[4] + c[8] + ...
a[2] = c[2] + c[4] + c[8] + ...
a[3] = c[3] + c[4] + c[8] + ..
a[4] = c[4] + c[8] + ..
void change(int x, int y) // a[1] += y, a[2] += y, .. a[x] += y
{
for (; x > 0; x -= x & -x)
{
c[x] += y;
}
}
修改操作，指定一个前缀a[1], a[2] .. a[x] 和 y
a[1] = max(a[1], y)
a[2] = max(a[2], y)
...
a[x] = max(a[x], y)
线段树
一共分成了2n - 1组
每个点在至多log n组中
所有组的大小之和是n log n
7 x x 1个
4 x x 3个
1 x x 6个
需要求第6个
在
1 x x
的6个中，找第2大的
1 8 x 1个
1 5 x 2个
1 2 x 3个
在
1 5 x
的2个中，找第1大的
1 5 9 1个
1 5 6 1个
4 x 4个
3 x 3个
2 x 2个
1 x 1个
需要求第6个
在
3 x
的2个中找第2大的
3 7 1个
3 6 1个
3 5 1个
1000
1001
1011
1010
1110
1111
1101
1100
0100
0101
0111
0110
0010
0011
0001
0000
101010101... 共n位，从2进制转成10进制输出即可
输入n
输出2**(n+1)/3
原码n 对应的格雷码是 n ^ (n >> 1)
1111 ^ (0111) = 1000
1010 ^ (0101) = 1111
原码是 101010101...
101010101 ^ 010101010 = 111111111
原码
0110 ^ (0011) = 0101
输入一些东西
问其中每个有多少个
98 99 98
98 100 99 98
98 99 100 98
98 99 99 98
m = 4
r = 2
f[10] = f[9] * 2 + f[9] - f[5] * 16
f[9] = f[8] + 2 * f[7] + 4 * f[6] + 8 * f[5]
f[8] = f[7] + 2 * f[6] + 4 * f[5] + 8 * f[4]
f[9] = f[8] * 2 + f[8] - f[4] * 16
f[i] 前i个的最优解
s[i] 前i个中，G比H多 多少个
从j转移到i （j+1 .. i划为1组）
f[i] = min(f[j] + (s[i] - s[j] >= 0)) (i - j <= k)
什么样的j最好？
f[j]越小越好
f[j]相同，s[j]越大越好
相当于对于每个i，询问i-k ... i-1区间中，(f[j], -s[j])最小值是多少
每一条树上选一个有向的路径 sz * (sz - 1)
f[i] 从i出发的最大收益
if (f[i] < (f[i - 1] + f[i + 1]) / 2)
{
f[i] = (f[i - 1] + f[i + 1]) / 2;
vector
queue
stack
deque
有向图 强连通分量
划分
http://usaco.org/current/current/current/current/current/data/sol_boards_gold_jan20.html
set
{
if (i % 2 == 1)
{
s.erase(i);
}
}
https://codeforces.com/contest/915/submission/34164031
https://www.luogu.com.cn/blog/qyrzr/solution-cf915d
f[i][j][k]
前i个数字，其中有j个0，第i个数字是k，最少修改次数。
k>0
f[i-1][j][k-1] -> f[i][j][k]
k==0
f[i-1][j-1][??] -> f[i][j][0]
f[i][j]
前i天，j次出逃，最少修改次数
f[i][j] = f[k][j - 1] + (k+1出逃到i修改代价)
双指针法
尺取法
区间最值 RMQ
线段树（支持修改）
修改log n
询问log n
Sparse Table
不支持修改
预处理O(n log n)
询问O(1)
如果询问的区间不包含
不存在[l1, r1] [l2, l2]
l1 < l2 && r2 < r1
可以用单调队列
时间复杂度O(n + q)
x y
if (a == x)
{
return y;
}
if (a == y)
{
return x;
}
return x + y - a;
x y z
if (a == x)
{
return (y, z);
}
if (a == y)
{
return (x, z);
}
if (a == z)
{
return (y, x);
}
0 0 0 0 <- rt[0]
1 0 0 0
1 0 1 0
1 0 1 1 <- rt[3]
1 1 1 1
(rt[3] - rt[0])
1 0 1 1
map<int, vector
询问区间内 <= 1的数字之和，s0
询问区间内 <= s0 + 1的数字之和，s1
询问区间内 <= s1 + 1的数字之和，s2
询问区间内 <= s2 + 1的数字之和，s3
...
si == s(i-1)
那么si + 1就表示不出来
1 2 3 5 8
<= 1 + 1 放一个恰好够不到的数字3
<= 3 + 1 放一个恰好够不到的数字5
<= 6 + 1 放一个恰好够不到的数字8
交集不为空
包含1的集合个数c[1]
包含2的集合个数c[2]
包含3的集合个数c[3]
交集不为空 = C(c[1], 2) + C(c[2], 2) + C(c[3], 3) - C(c[1, 2], 2) - C(c[1, 3], 2) - C(c[2, 3], 2) + C(c[1, 2, 3], 2)
1 2 3 4 +4
12 13 14 23 24 34 -6
123 124 134 234 +4
1234 -1
1 2 3 4 5 +5
大小为2的集合 -10
大小为3的集合 +10
大小为4的集合 -5
大小为5的集合 +1
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}
进制Hash：为了快速求一个字串的Hash
'abc' + 'd'
('a' * 1312 + 'b' * 131 + 'c') * 131 + 'd' - 'a' * 1313
d[i][j][k]
表示从起点走到(i, j)，步数%3==k
3
2
4
4
1
3
2
1
a
b
c
c
d
a
b
d
PPHPS
PPPPS
11012
11112
f[i][j][k]
前i个，改变了<=j次，最后一次出的是k，最多平局几次
34
6
23
0
5
99
2
d[x1][y1][x2][y2][dir1][dir2]
接收一串指令
如果初始向下，那么走到x1,y1，面相dir1
如果初始向右，那么走到x2,y2，面相dir2
问这段指令最短是多少
BFS
都是1的，直接队列
只有0和1，双端队列实现优先队列
值域比较大，直接优先队列，dijkstra
2147483648
9223372080854775
P1360
前缀和的用法
7 3
7
6
7
2
1
4
2
转成二进制，初始矩阵
1 1 1
0 1 1
1 1 1
0 1 0
1 0 0
0 0 1
0 1 0
对矩阵求前缀和，多一行
0 0 0
1 1 1
1 2 2
2 3 3
2 4 3
3 4 3
3 4 4
3 5 4
每一列都减去最后一列，少一列
0 0 0
0 0 1
-1 0 2
-1 0 3
-1 1 4
0 1 5
-1 0 6
-1 1 7
P1535
f[k][i][j]
经过k秒之后 从起点 到达(i, j)的方案数
if (s[i][j] != '*')
f[k][i][j] += f[k-1][i+1][j]
f[k][i][j] += f[k-1][i-1][j]
f[k][i][j] += f[k-1][i][j+1]
f[k][i][j] += f[k-1][i][j-1]
P1550 [USACO08OCT]Watering Hole G
最小生成树
P1561 [USACO12JAN]Mountain Climbing S
排序
最后模拟求答案
P1569 Generic Cow Protests
最长不下降子序列
必须选第一项和最后一项
P1607 [USACO09FEB]Fair Shuttle G
8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1
排序
1 5 2
4 6 1
5 8 3
8 14 2
9 12 1
12 15 2
13 14 1
14 15 1
P1842 [USACO05NOV]奶牛玩杂技
考虑相邻2个交换
i在j上
??? - s[i]
??? + w[i] - s[j]
j在i上
??? - s[j]
??? + w[j] - s[i]
如果 w[i] - s[j] < w[j] - s[i] 那么 i 在上
按 w[i] + s[i] 排序
P1848 [USACO12OPEN]Bookshelf G
有若干个 1e9，每个 1e9 拆成了若干个数字的和，复原出来怎么拆的，这是一个不可做题。
本题要求必须连续一段
f[i] 前 i 本书，分成若干层，总高度之和最小是多少
f[i] = min(f[j] + max(h[j+1], h[j+2], ..., h[i])) w[j+1] + w[j+2] + ... + w[i] <= L
只需要考虑2种j
w[j+1] + w[j+2] + ... + w[i] <= L
w[j] + w[j+1] + w[j+2] + ... + w[i] <= L
从 j+1 到 i 是 <= L, 但是如果多选w[j]，就 > L
h[j] > max(h[j+1], h[j+2] .. h[i])
如果本层多选了h[j]，那么本层的最大值将会更大
这个最优解可以表示为f[j] + m
暴力做 O(n^2)
5 3 4 1 2
5
5 3
5 4
5 4 1
5 4 2
一般人存
1 3 5
这份题解存
2 2
最后一个一定在栈中
最后一个下标 -2 一定在栈中
最后一个下标 -2-2 一定在栈中
int s[100000];
int *ss = s + 50000
ss[-1000];
s[50000 - 1000]
P1884 [USACO12FEB]Overplanting S
矩形面积并，n只有1000，可以离散化前缀和解决。
P1937 [USACO10MAR]Barn Allocation G
排序 multiset 贪心
P2971 [USACO10HOL]Cow Politics G
直径 LCA 求树上距离
P2975 [USACO10JAN]Taking Turns G
倒序 动态规划
P2977 [USACO10JAN]Cow Telephones G
树形DP
P3003 [USACO10DEC]Apple Delivery S
3个点 两两之间最短路
P4544 [USACO10NOV]Buying Feed G
f[i][j]
到点i，携带j饲料，最小花费
每个商店做一次多重背包
P2986 [USACO10MAR]Great Cow Gathering G
树上DP，两次DFS
P2982 [USACO10FEB]Slowing down G
DFS序列 树状数组
Stack / Queue / Two-pointer
Segment Tree
Lowest Common Ancester
DP
Math / Number Theory
Algorithm
No Parallel and distributed algorithms
No Approximate algorithms
The time of algorithm must greater than the size of input.
Read n integers, find the mode. (O(1) memory)
the mode(the number of occurences > n/2)