https://atcoder.jp/contests/abc254/submissions/32222821
大家可以想一想为什么这可能超时
https://atcoder.jp/contests/abc254/tasks/abc254_f
一个n行m列的数字，第行第j列是a[i]+b[j]
每次问一个矩形区域的GCD
求这个区域的gcd
a[2]+b[5] a[2]+b[6] a[2]+b[7] a[2]+b[8]
a[3]+b[5] a[3]+b[6] a[3]+b[7] a[3]+b[8]
a[4]+b[5] a[4]+b[6] a[4]+b[7] a[4]+b[8]
等价于
a[2]+b[5] b[6]-b[5] b[7]-b[6] b[8]-b[7]
a[3]+b[5] b[6]-b[5] b[7]-b[6] b[8]-b[7]
a[4]+b[5] b[6]-b[5] b[7]-b[6] b[8]-b[7]
等价于
a[2]+b[5] b[6]-b[5] b[7]-b[6] b[8]-b[7]
a[3]+b[5]
a[4]+b[5]
等价于
a[2]+b[5] b[6]-b[5] b[7]-b[6] b[8]-b[7]
a[3]-a[2]
a[4]-a[3]
如果输入的范围是h1 h2 w1 w2
a[h1]+b[w1] b[w1+1]-b[w1] ... b[w2]-b[w2-1]
a[h1+1]-a[h1]
...
a[h2]-a[h2-1]
分别求
a[h1]+b[w1]
gcd(b[w1+1]-b[w1] ... b[w2]-b[w2-1])
gcd(a[h1+1]-a[h1] ... a[h2]-a[h2-1])
https://atcoder.jp/contests/abc247/tasks/abc247_e
输入一个长度为n个数字，和最大值X，和最小是Y
问数组中有几个区间最大值是X且最小值是Y
所有数字分为>Y，==Y，<X，==X，X<..<Y五种情况
>Y和<X的位置一定不能选
选一个区间，包含至少一个==Y，包含至少一个==X，问有多少种方案
问以每个位置作为结尾，有多少个方案
对于每个位置，找自己之前的最近的X是多少，最近的Y是多少，至多选多少个数字没有>Y和<X的情况
https://atcoder.jp/contests/abc247/tasks/abc247_f
有n张牌，第i张牌正面是Pi，反面是Qi。保证Pi和Qi是1到n的排列
从所有的牌中选一个子集，使得从1到n的每个数字，都出现过（正面或反面）
把每张牌看做是连接Pi和Qi的一条边
因为Pi和Qi都是排列，所以整个图一定是由若干环组成的
对于每个环来说，选取一个子集，不能有连续的两条边不选
这是一个经典问题，答案是Lucas Number，是以2 1 3 4 7 ...开始的Fibonacci数列
不同环之间不会互相影响，把不同环的答案乘起来就可以了
https://atcoder.jp/contests/abc246/tasks/abc246_a
输入矩形的四个顶点中的三个，问最后一个顶点是什么？
https://atcoder.jp/contests/abc246/tasks/abc246_b
从点(0,0)向点(A,B)的方向走1的距离，问会到哪个点，输出小数
保证点(0,0)到点(A,B)之间的距离大于等于1
要找到两个数字(X,Y)
满足X*X+Y*Y=1且X/Y=A/B
https://atcoder.jp/contests/abc246/tasks/abc246_c
买n个商品，第i个商品价格是ai，有k个优惠券，每个优惠券可以优惠X元
优惠券可以在同一个商品上叠加，但是价格不能为负数
问最优情况下买这n个商品需要多少钱？
https://atcoder.jp/contests/abc246/tasks/abc246_d
输入N，找到一个数字X，使得X>=N且存在非负整数a和b使得X=a*a*a+a*a*b+a*b*b+b*b*b
问最小的X是多少？
双指针法
首先假设a=0求出b最小是多少（找到最小的b使得X>=N）
（直接cbrt相当于找到最大的b使得X<=N）
所以如果最优解就是a=0且b是cbrt(N)上取整，就会出错
while a <= b: if X >= N: b -= 1 else: a += 1
https://atcoder.jp/contests/abc246/tasks/abc246_e
国际象棋棋盘，有障碍物，问象从起点到终点最少需要几步？
先输入N，表示行数和列数
然后输入起点的坐标Ax和Ay
然后输入终点的坐标Bx和By
然后输入N行，表示棋盘的初始状态，其中.表示空，#表示障碍物
国际象棋的象，走斜线，任意多步
直接BFS会超时
BFS的时间复杂度是什么？
状态数*转移数
在这个题目中，状态数约为n*n/2，转移数（从一个位置可以走到多少个位置）大概2*n
所以直接BFS的时间复杂度是n*n*n是超时的
4
4 2
1 1
...#
...#
...#
...#
https://atcoder.jp/contests/abc246/submissions/30658548
if(m[ny][nx]=='*')continue;
这个方法没有问题，只会超时，不会WA
https://atcoder.jp/contests/abc246/submissions/30647486
else if(d[x][y]<=d[w.u][w.v]) break;
如果之前到这里的距离是d[x][y]
这次到这里的距离是d[w.u][w.v]+1
如果d[x][y]<d[w.u][w.v]+1
那么就没有必要继续沿着这个方向走下去了，因为从d[x][y]出发，即使再走一步，也和当前距离d[w.u][w.v]+1相等
边权只有0和1的BFS，用双端队列做
https://atcoder.jp/contests/abc246/tasks/abc246_f
有一个打字机，打字机有N行，第i行有Si这些字母（不同行可能有相同的字母）
打字的过程是选一行（之后不能在变了）只能用这行的字母，生成一个长度为L的字符串
问一共有多少种可能字符串（可能选不同行能生成同一个字符串，只算一次）
有A B C三行
答案是
+ A能打出的字符串
+ B能打出的字符串
+ C能打出的字符串
- A和B都能打出的字符串
- A和C都能打出的字符串
- B和C都能打出的字符串
+ A和B和C都能打出的字符串
https://atcoder.jp/contests/abc245/tasks/abc245_d
多项式除法
输入一个N次多项式A
输入一个N+M次多项式C
找到一个次数是M的多项式B
使得多项式A乘以多项式B等于多项式C
不需要取模，可能有负数，保证有解
2 1
12 14 8 2
6 4 2
----------
12 14 8 2
12 6
8 8 2
8 4
4 2
4 2
https://atcoder.jp/contests/abc245/tasks/abc245_e
n个巧克力，第i个巧克力宽A[i]长B[i]
m个盒子，第i个盒子宽C[i]长D[i]
每个盒子至多装1个巧克力
如果A[i]<=C[j]&&B[i]<=D[j]那么第i个巧克力可以被装进第j个盒子中
问能不能把所有巧克力都装进盒子
把巧克力和盒子一起按宽从大到小排序
如果盒子和巧克力宽一样，盒子在前
依次扫描所有的盒子和巧克力
如果这是一个盒子，multiset中加入这个盒子的长度
如果这是一个巧克力，在multiset中找最小能包含这个巧克力的长度的盒子
（因为multiset中的盒子都是在之前加入的，所以盒子的宽度一定大于等于当前巧克力的宽度）
这个题只问了能不能全找到，如果找不到直接就无解了
其实也可以问最多几个巧克力可以被放进盒子里
输入字符串，输出最后一个字符
https://atcoder.jp/contests/abc244/tasks/abc244_c
输入一个数字N，你和对方轮流说出一个1到2*N+1的数字
说过的数字不能再说
谁没有数字说，谁就输了
对方输入0，说明你赢了
fflush(stdout)
如果使用 cout 换行用endl还是'\n'无所谓，也不需要 flush
https://atcoder.jp/contests/abc244/submissions/30425407
https://atcoder.jp/contests/abc244/submissions/30425434
如果使用 printf 必须fflush(stdout)
https://atcoder.jp/contests/abc244/submissions/30425627
如果不fflush(stdout)会TLE
https://atcoder.jp/contests/abc244/submissions/30425609
输出数字之后一定要换行，不换行出错的例子：
https://atcoder.jp/contests/abc244/submissions/30280009
是否TLE与是否加 ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 无关
输入 A 和 B
输出实数 (A-B)/3+B
输入输出
输入 4 个字符串，问是不是 H 2B 3B HR 每个都出现且只出现一次
排序
输入字符串 S ，问 chokudai 作为子序列在不同的位置出现几次？
简单DP
输入一个无向图，边权都是1
问 1 到 n 最短路的条数
直接BFS
输入一个N * N的地图
从中选取一个四连通大小为K的区域
问有多少种选法
set vector 爆搜
abc211_f
输入 N 个多边形
Q个询问，询问一个格子被覆盖了多少次
离线树状数组
n个非负整数，初始互不相同
双方轮流操作
每次把最大的数字改成一个较小且没有出现过的数字
谁无法操作谁就输了，问先手赢还是后手赢？
如果 最大的两个数字，前面有相同个数的偶数个空位 先手必败
否则 先手必胜
要证明2个事情
第一个事情：
如果 最大的两个数字，前面有相同个数的偶数个空位
操作一次之后
最大的两个数字，前面有相同个数的偶数个空位 一定不成立
第二个事情：
对于任何一个不满足
最大的两个数字，前面有相同个数的偶数个空位
条件的局面
操作一次之后一定就满足了！