关于比赛
atcoder比赛是有价值的，比赛态度要端正，比赛以后要好好订正好好总结，写这篇博客的目的，一方面是为了引导你们去订正，一方面把比赛中暴露的问题和有价值的地方记录下来，终究是为了信奥取得好成绩，最后强调一下，但凡做题如果有了解题的思路不要急于敲代码，先问一下自己用了什么算法解这道题，时间空间复杂度心里估算一下。
AtCoder Beginner Contest 411
C350题意：N个方格一字排开，Q个Ai，Ai表示翻动方格的位置，每次翻动白变黑或黑变白，问每次翻动后，连续黑色方格带有几个
D425题意：N台PC和一台服务器，Q次操作三种命令，1 p用服务器字符串替换p号PC，2 p s表示在p号PC追加字符串s，3 p用p号PC字符串替换服务器，问最后服务器内的字符串是啥
E450题意：给N个6面骰子，每个骰子都给出6个数字，同时投骰子，问每次投出骰子后出现最大的数字的期望
F525题意：N个点M条边的图，Q次操作Xi，Xi表示给出边的编号，边两端的顶点缩点之间的连边消失，问每次操作后图中还剩几条边
G600题意：N个点M条边的图，没有自环，统计满足条件环的数量，要求环对应的边集是一个排列，数量为k，且边集中每条边链接的两个顶点编号必须满足，j，j%k+1且1<=j<=kAtCoder Beginner Contest 410
AtCoder Beginner Contest 409
AtCoder Beginner Contest 408
AtCoder Beginner Contest 407
AtCoder Beginner Contest 406
AtCoder Beginner Contest 405
C300题意：给出长度为N的数列，求任选2个数积的和
D400题意：给出H*W的二维网格，'.'表示路，'#'表示墙，'E'表示逃生出口，用^v<>表示上下左右绘制一张逃生地图，标出所有点的最佳逃生路径，可能存在多种解，输出其中的一个解即可
E475题意：ABCD分别表示苹果、橘子、香蕉、葡萄的数量方程一排，要求苹果放在香蕉的左面，苹果放在葡萄的左面，橘子放在葡萄的左面，问有多少种放法
F525题意：给出一个圆，周长上有2N个点，给出M对线段(Ai,Bi)表示圆上Ai点到Bi点连线，再给出Q对询问(Ci,Di)表示圆上Ci点到Di点连线与之前M对线段有几段相交
思路：我们把圆上的点看成一维的轴，那M给出的就是一段段区间，Q对询问就可以看成当前的线段和几段线段相交，大脑里面瞬间就能反映出来这不是和新网站689差不多吗，谈一下689的做法，用一个树状数组维护种下树的左区间bit1，用另一个树状数组维护种下树的右区间bit2，对于查询区间[lt,rt]来说，用rt去查询bit1的数量，然后减去lt-1从bit2中查询出来的数量即可，仔细看一下和689的区别就是把包含的线段数量去掉就是答案，会做689的你需要举一反三一下，即会搞定这道题目的
G625题意：给出一个长度为N的数列，给出Q个查询，一次查询包含L，R，X，表示取出数列第L到第R的元素，然后把大于等于X的都去掉，对剩下的做排列，问排列的方案数是多少AtCoder Beginner Contest 404
C300题意：给出N个顶点和M条边，问是否能构成一个环
D400题意：N个动物园，每个动物门票为Ci，M种动物，每种动物都给出一个Ki，表示在哪几个动物园能看到，问把M种动物都看到的且每个动物至少看两次的最小代价
E475题意：有N个碗编号从0到N-1，一开始0号碗的豆子数量为0，从1号碗到N-1号碗有Ci和Ai，Ai表示碗内的豆子数量，Ci表示从第i个碗中取出的豆子可以自由分配到第i-Ci个碗至第i-1个碗中的任何一个碗中，问所有豆子都移到0号碗的最少操作次数
F550题意；给出N，T，M，K，N表示有N个按钮，玩T轮，每轮Aoki先安排一个按钮为赢得，其他按钮都是输的，Takahashi每轮按M次，可以按不同得按钮，也可以按同一个按钮，按完后Aoki告诉Takahashi这轮得输赢情况，最后统计TakahashiT轮总共按对按钮的次数，如果大于等于K，Takahashi赢否则输，问Takahashi赢得概率是多少
G600题意：给出长度为M的三个数列L，R，S，求存在一个数列A，使得数列Li至Ri的和满足Si，如果存在多种满足的数列，输出数列和最小的那种数列，只要输出A数列的和AtCoder Beginner Contest 403
C300题意：N个用户M个比赛页面，Q个操作三种命令:1表示授权X用户能访问Y页面，2表示授权X能访问所有页面，3查询X用户能否访问Y页面
D425题意：给出长度为N的数列Ai，再给出一个D，问删除最少数量的元素使得数列中任意两个元素的绝对差值不等于D
E500题意：有两个multiset X和Y，意味里面元素能重复，Q个操作1表示把字符串放入X，2表示把字符串放入Y，每次操作后问Y中有多少个字符串的前缀没有在X中出现
F500题意：给出一个数字N，运算表达式只能由1, +, *, (, )这五种字符构成，问构成运算表达式的最小长度
思路：看数据规模常规的f[i]不好弄，看看N的规模2000，状态f[i]表示i这个数能构成的最少表达式长度，这个状态会有个小问题，f[6]=f[2]*f[3]，f[2]可能是由加法构成的，转移的时候就有问题，你不知道这个f[2]外面到底要不要加括号，这样我们需要辅助状态，设计2个状态:f[i]表示i这个数能构成的最少表达式长度，g[i]表示i这个数能构成的最少表达式且参与状态转移时这个表达式不会有任何歧义，大致转移方程思路如下：
f[i]加法时由f[]向它转移，f[i]乘法时g[]向它转移，g[i]思路类似，还有考虑清楚初值
G600题意：给出一个迭代公式Yi每次给出，Zi是上一次的结果构成，当前迭代会根据Yi和Zi生成，把这个值放入一个集合B，然后排序，把排在奇数位的数值拿出来相加构成了下一次迭代的Z值，问每次生成的z值AtCoder Beginner Contest 402
C300题意：有N种原料，M道菜，第i道菜有Ki种原料构成，Snuke不适应任何一种原料，然后Snuke列出一个计划，每天适应一种原料，如果某道菜中的原料都能被适应了，那么这道菜就能吃了，根据天数给出每天适应一种原料的数列，问第i天能有几道菜能吃
D400题意：一个圆在周长上等分N个点，顺时针编号，然后给出M对点对，点对构成一条直线，问两两相交的直线对数
E450题意：有N个问题，每个问题有Si,Ci,Pi，分别表示提交的得分，提交的花费，提交成功的概率，问给出一个花费的限额X，问不超过这个X能得到的最大期望得分是多少
F525题意：给出一个N*N的网格，每个网格中都已一个数字，范围从1到9，从(1,1)出发只能往右或往下走，一边走一边拼网格中的数字，最后走到(N,N)，拼成的数字对M取余，求拼成数字取余的最大值是多少
思路：看上去像左上递推到右下，但是因为拼数字还要取余的不确定性，必然是要把所有情况都保存下来，这样时空都要炸，那么我们各考虑做一半，用小数据举例子，N=5，左上走到右下一共9步，那么我们从左上往右下走4步，从右下往左上走4步，从左上往右下走4步逻辑上符合一棵4层的满二叉树，第4步的数据有8个，总共产生15个数据，数据N=20你算算时空都不会炸，接下来的问题就是如何构造数据结构，我们可以用bfs来生成每一步的数据，最后的一个问题就是第5步的数据怎么去找前4步和后4步的数据，这里我们练一个技巧，因为我们用bfs生成时记录每一步的二维坐标，然后我们把二维坐标变成一维的，这样我们对左上半区的第4步16个数据按照一维的编号排序，对右下半区的后4步数据做一样的处理，排序后的两个数列是一一对应的，然后找出对应的第5步处理一下贡献答案即可
G650题意：给出一个公式，T组数据，每次给出公式中N,M,A,B1,B2的值，求公式的值AtCoder Beginner Contest 401
C300题意：一个数列长度N+1，下标从0开始，前K项都为1，从第K个开始都是前K项和，问最后一项的值是多少
D400题意：给出一个长度为N的字符串和一个K，字符串由'.o?'三种字符组成，'?'可以变成'.'或'o'，问字符串能否有K个'o'且任意两个'o'不能相邻的方案，对于所有合法方案中如果当前位置能确定是'.'或'o'的就输出确定的字符，不能确定的输出'?'
E425题意：给出一个无向图N个顶点和M条边，通过删除若干个顶点得到一个连通子图，如果这个联通子图顶点数量为K，那这个联通子图中点的顶点正好是1，2，...到K，现在问得到1至N的联通子图分别要删除的顶点数量
F500题意：给出两棵树Tree1和Tree2，在两棵树中分别任选一点（i和j）然后建边，f(i,j)表示节点i和节点j建边后这棵树的直径，问所有组合f(i,j)的直径和
思路：根据第一个测试样例做如下计算，第一棵树三个节点(1,2,3)分别作为根的时候到叶子最长路径分别是(1,2,2)，第二棵树三个节点(1,2,3)分别作为根的时候到叶子最长路径分别是(1,2,2)，死枚举可以得到答案，我们换一种方式计算，下面尽可能把计算方式说的细一点
(1)第一棵树节点1连到第二棵树的任意节点计算结果为：3*(1+1)+(1+2+2)，1+1表示第一棵树连第二棵树时路径长度在原有基础上加1，因为第二棵树有3个节点，所以乘3，这样看第二棵树各个节点作为根得到的最长路径可以直接加起来
(2)用上面的方法可以得到第一棵树节点2和节点3连第二棵树的贡献，分别是3*(2+1)+(1+2+2)和3*(2+1)+(1+2+2)
(3)我们从上面的计算过程很容易再归纳，答案的计算变成3*(1+2+2+3*1)+3*(1+2+2),你应该会明白这些数字分别是怎么计算得来的
明白上面所说的，那这道题目就很简单了，用树的直径标程(要两次dfs需要换根)随便做了
特别注意：你还要考虑一下两个树连起来的时候，直径是由一棵树提供的情况，也就是T1和T2相连时，直径来自于T1或T2
G575题意：一个二维平面内有N个人和N个按钮，N个人同时移动，每秒最多只能移动一个单位，可以往任意方向移动，每个按钮只能被一个人按动，问按钮需要同时被按动的最小时间AtCoder Beginner Contest 400
C350题意：X=2^a×b^2，问N范围内这样的X有多少个
思路：看数据范围死枚举肯定时间超限，通过分析可知道a最多不超过60，那么通过枚举a可得到b，然后验一下b是不是平方数，b范围内的就是解，这里面有个问题b范围内的解有重复，把公式转换一下X=2^a×(2×c)^2，会发现重复主要来自于b范围内的偶数，而偶数中的2的幂都会被a枚举到，所以答案就来自于b范围内的奇数数量的和，这道题目还有个问题很有价值，b需要用double，因为double的取值范围很大所以精度有问题，sqrt(b)会有偏差，所以需要回验sqrt(b)的值
D400题意 题意：给定一个H×W的网格，'.'表示有路，'#'表示墙，有路的情况下可以上下左右移动，没路的时候可以通过front kick的操作使得某个方向上的一块墙或两块墙变成路，一次front kick的代价为1，问(A,B)到(C,D)的最小代价
思路：把联通的路可以看成一个联通块，主要问题是怎么处理联通块之间的最短路，分析完题目给出的条件，可以得出以下建图信息，如果当前是'.'，周围某个方向是'.'建一条边权为0的有向边，如果周围是'#'建一条边权为1的有向边和再跳一格建一条边权为1的有向边，如果当前是'#'，周围某个方向是'.'建一条边权为0的有向边，如果周围是'#'建一条边权为1的有向边和再跳一格建一条边权为1的有向边，把二维数组映射成一维的点建图，最后跑最短路即可
E425题意：数字N需要满足两个条件，一个是必须有两种素数构成，且素数的幂为偶数，现在有Q个查询每次给出一个A，问不大于A中最大的N为多少
思路：分析题意后N可看成N=t^2，实际上就是求t，t只要满足两个素数构成即可，那么可以利用埃氏筛来求出每个数字有几种素数构成，然后线性扫描一下，把满足2个素数构成的数字放进一个数组，最后在Q此查询时sqrt(A)查询满足条件的最大值即可
F550题意：此题就是涂色问题，一般的涂色问题就是给定连续个格子，涂成期望的颜色问代价问题，这道题目是把蛋糕做成期望的颜色，在a位置开始连续涂b个长度的颜色为c，代价就是b+col[c]，问涂成期望颜色的代价最小
思路：一看数据规模典型的区间DP，f[lt][rt]是常规状态，主要考虑清楚几个点：因为循环数组开两倍；f[i][i]初值问题；当col[lt]=col[rt]时还有一种转移方式；最难的一点就是f[lt][k]+f[k+1][rt]中c[lt]=c[k+1]时再优化的问题
G625题意：有N块蛋糕，每块蛋糕都是一个三元组(X,Y,Z)，任选一对蛋糕(a,b)的最大价值为max(Xa+Xb,Ya+Yb,Za+Zb),问选K对不相同的蛋糕使得K对的价值和最大
思路：Alien DPAtCoder Beginner Contest 399
C350题意：给出一个无向图N个顶点M条边，问删掉几条边把图变成森林
D400题意：有N对夫妇坐在一排，如果a对夫妇不相邻，且b对夫妇也不相邻，两队中各挑一人交换位置，使得a和b两队夫妇都相邻，同时保证a<b，问这样要的交换数量有多少，给出T组数据
E500题意：两个长度都为N的字符串S和T，都由小写字母构成，S中的同一种字母可以变换成任意的小写字母，问把S串变换成T串最少需要几次，如果无法完成输出-1
F550题意：给出一个长度为N的数列和K，求这个数列所有区间和的幂为K的和
G675题意：给出一个无向图N个顶点和M条边，没有自环但有重边，每条边都有一个权值ci表示颜色，共有C种颜色，给出一个长度为C的数列Ai，设区间[L,R]，1≤L≤R≤C，使得一棵生成树中，边的某种颜色x的数量最多不超过Ax，且Ax在[L,R]区间中，问满足这种条件的区间有多少个AtCoder Beginner Contest 398
C300题意：给出一个数列N,问没有重复出现过的数字中的最大值的下标
D425题意：二维平面原点有一堆篝火，给出一个字符串S，每个字符表示单位时间的风向，篝火生成的烟每个单位时间会随风向飘去，给出二维平面中的一个点(R,C)问每个单位时间这个点是否会有烟，有的话输出1否则输出0
E425题意：交互题可以理解为人机对战，给出一棵树N个节点，如果你选择先手或后手，先手输出"First"，然后选择输出一条边，如果后手输出"Second",等待电脑选边输出，选边的要求，这条边不是重边，另外不能构成奇环，当电脑没边可选会输出-1，程序结束
F500题意：给出一个字符串S，使得这个S成为回文串的前缀，且使得这个回文串尽可能短并输出
G600题意：给出一个简单图N个顶点和M条边，Takahashi和Aoki玩游戏，Aoki先手，选两个顶点建一条边，这条边不能是重边，且不能构成奇环，问谁会赢AtCoder Beginner Contest 397
C350题意：给出一个长度为N的数列，i作为分割数列的位置，1≤i≤N−1，把数列分成左右两个半区，求两个个半区各自去重后数字的数量的和，求最大值，问那几个i等于最大值，把这些i求和输出
D425题意：给出一个数字N，x^3-y^3=N，问有多少对(x,y)符合条件
E475题意：给出一棵树，节点数列NK，问是否能生成一个N*K的矩阵，矩阵中的元素有节点编号构成且不能重复，另外矩阵中每行相邻元素之间在树中要有边存在
F550题意：题面意思和C一样
G625题意：给出一个有向图N个顶点和M条边，初始所有边权都是0，选K条边边权变为1，使得1到N的最短路尽可能大AtCoder Beginner Contest 396
C300题意：给出N个黑球和M个白球，每个球都有对应的价值，选出的球中黑球数量不得少于白球，问怎么选使得价值最大
D400题意：给出一个简单无向图N个顶点M条边，求1到N的最短异或路
E450题意：给出三个长度为M的数列X,Y,Z，构造一个长度为N的数列Ai，数列满足A(Xi)+A(Yi)=Zi，如果有多个数列满足条件，选数列Ai和最小的输出
F500题意：给出一个数列N和M，数列中元素Ai+k对着M求余数产生一个新的数列Bi，求数列Bi的逆序对数，k从0变到M-1，问每一次Ai+k的逆序对数量
G600题意：给出一个H*W的网格，网格初始值0或1，每可以选中一行或一列，选中的行或列中的元素1变0、0变1，问如何选使得最后网格中所有的元素和最小并输出这个值AtCoder Beginner Contest 395
C300 题意：给出一个长度为N的数列，求最短子序列，子序列中必须有重复元素，pre的裸题
D350 题意：有N只鸽子编号从1到N，一开始编号为i的鸽子在鸽巢i中，Q个操作：1、移动编号为a的鸽子去鸽巢b，2、鸽巢a和鸽巢b中的鸽子对换，3、查询编号为a的鸽子在哪个鸽巢，这道题目实际上就是sa/rk的题目，关键把鸽巢做成sa/rk，rk[i]=j，第i个鸽巢的门牌为j，照这思路想就可以了
E425 题意：给一张有向图N个顶点M条边，问1到N的最短路，在求最短路的时候有两种操作，顺着原始边走每走一条边代价为1，或者整体反转所有边然后再走，反转一次的代价为X，走一条边的代价还是1，给个数据结构，瞬间能明白做法，dist[u][2]
F500 题意：给上下两排牙齿的高度，使得对位的牙齿上下长度和都一样，且相邻牙齿的绝对差值小于等于X，问最小代价
思路：首先贪心会想到，求一个最小值，这样可以把所有牙齿的上下长度和都磨成一样，但是第二个条件不一定满足，比如X=2，给出上排牙齿1，9和下排牙齿9，1，看一下数据规模很容易想到二分，然后贪心验合法性
G625 题意：给出一个N个顶点的完全无向图的邻接矩阵和K，Q个查询，每次给出s和t，问使得1到K以及s和t都联通的最小生成树的边权和AtCoder Beginner Contest 394
C300 题意：给出一个字符串S，要求把所有的WA替换成AC，需要考虑替换完又形成新的WA，类似WWA，利用栈的思想可线性处理
D400 题意：给出一个字符串S，只含有 (, ), [, ], <, >这些字符，问括号是否匹配，栈思想实现即可
E450 题意：给出一个N*N的邻接矩阵，有路的用字母表示，没路的用-表示，问所有点对之间是否用路且构成回文串，有的话输出最短回文串的长度，否则输出-1
思路：假设求x到y的最短回文串，考虑x出发有几条路，到达y的有几条路，看看是否有一样的，没有就结束，有的话继续双向搜索即可，用bfs很合理
F500 题意：给出一棵无根树，找一棵最大的子树，这棵子树节点的度要么为1要么为4，且必须有一个度为4的节点
思路：构造子树节点信息，f[u]表示u向父节点的贡献，注意f[u]在收集子树信息时需要分类探讨，另外根节点的处理有别于子树节点，感觉一把dfs能做完，也可以标准GESP七级做法
G600 题意：给出一个H*W的网格，网格中的元素表示一幢建筑的楼层，建筑内楼层可以上下，相邻建组同一楼层间有人行走廊，给出Q个询问，给出两幢建筑A和B及各自的楼层，问从A的楼层到B的楼层最小代价，上下楼层移动一层的代价为1，人行走廊的代价为0。AtCoder Beginner Contest 393
C300 题意：给N个顶点M条边，问至少去掉几条边，使得图不带自环和重边，看数据规模，自环手动处理一下，重边用map是最方便的
D425 题意：给出长度为N的01串，相邻两个元素可以交换，问最少交换几次使得所有的1都相邻，显然不能认为所有的1都向中间靠拢最优，那么我们设lt[i]表示第i个位置的1的左边向i靠拢的代价，rt[i]为右边靠拢的代价，枚举所有i取最小代价，lt[i]的做法类似前缀和后缀和容斥的做法
E475 题意：给定长度为N的数列和K，设数列中的元素为Ai，询问N次，每次询问要从数列中选中K个数且必须含有Ai，使得这些数的GCD最大并输出
思路：询问时间复杂度优化不了，那里面的做法就两种，结合题目给出的数据规模，打表和查询都可以控制在调和级数时间复杂度范围内，只要处理出每个数的约数及约数出现的数量即可
F500 题意：给定长度为N的数列，Q次查询，每次查询给出R和X，前R个数中最长不降子序列中的每个数都不能超过X，问最大长度
思路：此题需要会最长不降子序列的二分优化，先把Q个查询全部读入排序，然后一边二分优化处理到第i个的最长不降子序列，一边回答查询需要二分
G675 题意：给出一个N*N的矩阵及P和Q，可以改变矩阵中的任何元素，每次改变的量不能超过P/Q，改变后的矩阵每个元素相对原有矩阵的改变量的总和不能超过P/Q，问如何改变使得改变后的矩阵相邻元素差值之和最小，输出这个最小值及改变后的矩阵
思路：费用流，Primal-DualAtCoder Beginner Contest 392
C300 题意：第i个人身上号码为Qi盯着第Pi个人，按照Qi的序输出第i个人盯着的那个人身上的号码，此题主要检验英语阅读能力或是观察测试数据的能力
D400 题意：有N个骰子，第i个骰子有Ki个面，同时给出每个面的数字，问任取两个sai筛子掷出相同概率最高是多少
思路：看数据规模C(100,2)的时间复杂度是10^4，分母就是K相乘，分子就是一个骰子的数字出现次数乘上在另一个骰子中此数字出现的次数的和，把后面主要考虑查找的优化即可
E450 题意：给出N个顶点和M条边，问最少修改边的数量使得所有顶点相连，同时输出修改的边的编号及相连的顶点
思路：先找出联通块，再找出每个联通块的割边，修改非割边即可
F500 题意：有N个数字，然后按顺序给出每个数字插入数列的位置，输出最终的数列
思路：一看数据规模，再结合题目有查增，平衡树模板上去直接解决，但是500分的题目还是以思维为主，倒过来考虑，此题找到规律后变为查改的题目
G600 题意：给出一个数字集合，任取三个数A、B、C，满足A<B<C且B-A=C-B，问方案数
思路：转化成多项式展开+FFTAtCoder Beginner Contest 391
C300 题意：N只鸽子，一开始第i只鸽子在第i号鸽巢，Q次操作，1表示把第P只鸽子移动到第H号鸽巢，2询问鸽巢内鸽子数量超过1只的鸽巢有几个，小学生常规技巧
D400 题意：二维平面坐标系，给出N个方块，开始0秒，每秒执行两步操作，1：如果最底下方块满了，就移除掉最底下一样的所有方块，2：上面的方块顺势往下落，为了理解上没有歧义，所以询问t+0.5秒后，第i块方块是否存在
E450 题意：给3^N长度的二进制，三个分为一组，按照01数量谁多记为这组的值，以此循环往复N次，最后得到一个答案，如果答案为1(0)，问如果想让答案变为0(1)，原二进制位最少的改变次数
F500 题意：给出ABC三个队列，长度都为N，按照题目给出的公式，能生成N^3个数，问排第K大的数是几AtCoder Beginner Contest 390
C300 题意：给定一个网格，'#'、'.'、'?'分别表示、黑、白、未知，'?'可以变成黑色或白色，问能否使得所有的'#'构成一个实心的黑色矩形，做法上把黑色的上下左右四个边界找到，算一下范围的数量即可，注意要考虑特殊情况，就是网格没有'#'
D400 题意：有N个背包，每个背包中有若干个石子，可以进行任意次操作把一个背包中的石子放入另一个背包，最后把背包中的石子进行异或操作，问不同结果的方案数。看N的规模非常小，要么排列组合要么类似状压位运算，先用排列组合模拟一下，每个物品最多有12种的方法，那就是12^12的时间复杂度肯定要超，看看能不能收敛一下，发现这当中是有重复的，实际上第一个背包有N种操作，第二个背包有N-1种操作，算下来是12！，时间复杂度正好
E450 题意：有N个食品，每个食品有大小、维生素(只有三种)、卡路里三种属性，给定一个卡路里X，问在N个食品种任选，卡路里的总和不超过X，使得三种维生素摄入量（各自的总和）的最小值最大，输出摄入最少维生素的数值
思路：看题意和数据规模，类似于背包，但是转移的时候加减三种维生素的值不好处理，因为维生素只有三种，可以先分别做背包DP，再贪心一下即可
F525 题意：给定一个长度为N的数列Ai，函数f(l,r)计算区间的某种值，l和r对齐数列下标，l到r之间有几段连续的数字，f(l,r)就是几，数字未必有序，枚举所有区间求f的和
思路：看数据规模是不可能枚举做的，这道题是好题，设lt[i]为Ai对所有区间左端点的贡献，rt[i]为Ai对所有区间右端点的贡献。AtCoder Beginner Contest 389
C300 题意：给出Q次操作三种类型，1、给出蛇长度，进队，注意起始位置为0，2、队头的蛇出队，相应的队伍中的蛇都往前挪，3、查询队列中排第i条蛇的起始位置，实现上开个手动结构体队列，队列中的蛇不用移动，通过计算出队长度，维护一个相对的队头位置即可，注意数据类型
D400 题意：正方形网格为1，问给出一个半径R，能完全围住多少正方形，题目特地说明了一下，圆心设在某个正方形的中心能围住最多，题目主要考一下平面几何的感觉，从数据规模1000000可以估出，就是数学理解+一层枚举的做法，因为圆内正方形网格对称，所以算一下第一象限的情况就可以了，探讨第一象限从下往上一排排算能围住的正方形网格，设第一排高度y=0.5，用勾股定理算一下，能算出圆周上的某一点x，第一排第一个正方形右上角是0.5，第二个正方形右上角是1.5，以此类推，直到小于圆周上的x，找下规律就能O(1)得到第一排正方形的数量，时间复杂度N
E475 题意：给出N种商品，数量无限，第i种商品购买k个的花费为k*k*Pi，问不超过M最多能买多少个商品，这道题看数据规模很难背包，如果花费中没有k*k那就是贪心题，如果用优先队列模拟着做，会发现一个个购买的商品具有单调性，把k*k*Pi拆开看，可理解为第i种商品在购买第k个时的花费为(2*k-1)*Pi，选取商品和某种商品内部都呈现单调性，所以设x为最后一个购买的商品价格，这样我们用这个x可以计算出每种商品各买了几个，总价是多少，二分x，check总价即可，时间复杂度NlogM
F525 题意：类似地上放了Q个不同高度的积木，然后给出N次操作，每次操作[lt,rt]好比只要高度在这个范围内的积木再增加一块积木，问最后这Q个积木的最后高度为多少，看数据规模，只可能两种做法QlogN或者Q，想想这些积木的操作涉及改查，QlogN的做法很难，接下来继续看看题目的要求，发现如果一开始把积木升序排放，然后再执行N次操作，积木的高度还是会保持单调性，思考打表Q(1)查询做法。
具体做法：预处理X范围内的所有积木，先初始化arr[1]=1,arr[2]=2,arr[3]=3,...,因为N次操作为区间修改，所以把arr[i]做成差分数组，dif[1]=1,dif[2]=1,dif[3]=1,...,又因为N次操作不改变积木高度的单调性，积木高度arr[i]=∑dif[j]，每次[lt,rt]，利用二分查询第一个arr[i]>=lt的dif下标，再利用二分查询最后一个arr[i]<=rt的dif下标，然后区间修改即可，最后arr[i]的值就可以O(1)查询了，注意我们这里说的arr和dif都是逻辑上的数组，写代码是dif转化成树状数组，arr靠sum_bit维护，另外看似差分做，实则不需要差分树状数组，普通的树状数组即可，这道题是思维上的单调性差分维护区间修改二分维护区间定位，代码层面就是树状数组+二分。AtCoder Beginner Contest 388
C300 题意：给定一个数列，任选两个x和y，使得x≤y/2，问方案数，二分可解，时间复杂度NlogN
D400 题意：给定一个数列，执行i次，第i次时，1到i-1的每个数字减1（如果数字为0则不操作），增加到第i个数字上，找规律题目，时间复杂度N
E450 题意：和C类似，只是问同时选中多对数字，使得每队都满足x≤y/2，问最多选中几对，二分可解，时间复杂度NlogN
F550 题意：给定一个数列，给定若干区间，区间内不可访问，再给定一个[A,B]的移动范围，可以理解为可跳跃的步数，问从1能否跳到N，
思路：先处理一下输入，可以把不成立的先剔除，看一下数据规模，N没啥用，M表示需要跳M次障碍区，同时也把数据分成M+1段无障碍区，A和B的范围有说法，其实每段无障碍区内最多可以分成20类，那做法上和线性DP的思路差不多，注意跳的时候也可能会无解AtCoder Beginner Contest 361
D 题意：给定一个起始字符串，后面+“..”，任选两个相邻字符和“..”交换，问达到目标字符串的最少步骤，BFS可解
E 题意：给定一棵树及边权，问任选一点出发能达到的汉密尔顿路径的最小值
F 题意：查询N范围内的平方数数量AtCoder Beginner Contest 352
D 题意：给出一个排列，把这个排列看成sa数组，然后做一个rk数组，rk数组的值就是题目中的i，问rk数组连续区间为k的最大值和最小值差值最小，看懂题意后rmq可解AtCoder Beginner Contest 351
D 题意：给出一个H*W的网格，'#'表示磁铁，'.'表示空格，可以从任意一个空格出发，移动到和磁铁相邻的空格就不能再移动了，问选一个空格为起点，能移动到的最多空格数
看到这种题目要引起重视了，未来的出题风格可能都是这种，在原有的算法外面套了一层壳，需要有分析能力去处理掉这层壳，这道题目其实就是二维数组dfs或bfs遍历问题，但是他加了一层限制，那在读入数据的时候，把和'#'相邻的空格处理成另外一个字符，比如'*'，这样遍历的时候，碰到'.'可继续遍历，碰到'*'就返回但是数量也要算上，你能悟出点什么吗？这题目关键就是能看出来其实就是求一个外圈是*里面是.的最大面积，*是根据#处理出来的，所以不用反复递归。
E 题意：在二维坐标系中给出N个点，同时定义了点之间距离的计算方法dist，问∑∑dist(Pi,Pj)
F 题意：给出一个长度N的数列Ai，问∑∑max(Aj-Ai,0)
G 题意：给出一个有N个节点的有根树，根为1，每个节点都有一个值Ai，定义了一个函数f(i)来算节点的值，接下来给出Q次查询，在线询问，每次修改某个节点Ai值，问f(1)的值AtCoder Beginner Contest 350
AtCoder Beginner Contest 349
AtCoder Beginner Contest 348
B 题意：二维坐标系内给出N个互不相同的点，输出离第i个点直线距离最远的点的编号。看N的规模，两层循环枚举求最值即可
C 题意：有N颗豆，每颗豆子都有美味度Ai和颜色Ci，每种颜色的豆子都有一个美味度的最小值，问这些最小值中最大的值是多少
考试最快的做法是用STL，但是作为练手应该用离散化来做
D 题意：给出一个H*W的地图，'.'表示可走，'#'表示障碍，'S'表示起始位置，'T'表示结束位置，再给出N个三元组（Ri,Ci,Ei）,表示位置（Ri,Ci）出有一个体力能量包Ei，走到这个位置体力就会变成Ei（注意能量不累加），每次移动一格消耗一点能量，开始体力为0，问能否从起始位置走到结束位置。
一看二维数组，再结合题目肯定是dfs，需要设一个体力的数组，用来优化剪枝
E 题意：给出一个N个节点的树，同时给定N-1条边，再给出一个长度为N的正数序列Ci，d(a,b)表示a节点到b节点的距离，f(x)表示x到1~n各个定点i的距离乘上Ci的和，x可以是任意一个节点，问最小的f(x)是多少
F 题意：给出一个N*M的矩阵，把每行看成一个数列，任选两行，如果两个数列相同位置的数字一样的个数为奇数，称这两行为一个相似对，问这个矩阵的相似对数量
G 题意：有一个数量为N的二元组(Ai,Bi)集合，从这个集合中任选k个后得到一个集合s，使得s中元素Ai的和减去最大的Bi最大，问k从1~N时，最大值分别是多少AtCoder Beginner Contest 347
B 题意：计算子串的种类数
看数据规模，那就用最朴素的做法做，正好练练基本功，两层循环枚举子串，然后check子串是否存在，不存在就加到字符串数组，并且ans++
C 题意：给定A天(假日)+B天(工作日)，给出N天，问这些天能否都在假日，开始时间可以从任意一天开始
E
F
GAtCoder Beginner Contest 346
B 题意：给定一个字符串“wbwbwwbwbwbw”，可以无限拼接，问是否存在这样一个区间，这个区间中有W个‘w'和B个‘b’
一定要学会看数据规模，因为W和B最多100，而给出的串长度12，那把串复制100遍，构造一个长度1200的字符串，如果有解那就一定存在在这个字符串中，1200的长度只够两层枚举，那计算区间字符数量，就需要预处理前缀和数组，枚举区间的时候容斥
C
D 题意：给一个长度N的01串，下标对齐1开始，每个位置对应一个修改的价值Ci，可修改任意位置的字符，0变1或1变0，使得修改后的字符串中只能出现一对相邻字符一样的情况（可以是两个一样的1，也可以是0），其他位置都必须01交替出现,问最小代价是多少AtCoder Beginner Contest 345
B 题意：给出一个long long范围的数字，除以10后向上取整输出，看题目数据范围不超，但是long long转double精度会出问题，double精度只有16~17位左右，一旦除以10以后，小数点后面都是0，这里要用到long double，但是long double的输入输出用scanf和printf会很麻烦，有的编译器是%Lf,有的是%llf，所以这道题目的输入用cin，输出用cout
C 题意：给出一个字符串S，操作一次，任取两个位置i和j，保证i<j，交换S[i]和S[j]的字符，问能产生多少种不同的字符串
具体做法：
（1）n=strlen(S)，用cnt[]记录字符出现的数量，需要处理两个特殊情况：cnt[i]==n，直接输出1；cnt[i]>1，ans=1
（2）组合思想C(n,2)加到ans中去，表示交换的所有方案数，包含重复情况
（3）然后枚举cnt[i]，cnt[i]>1时，从ans中减去C(cnt[i],2)
D 题意：给了N块砖，给出一个H×W的网格，问是否能从N块砖中任选几块正好铺满网格，看数据规模N上限7，所有方案数=从n块里面任选1~7块的全排列，算一下枚举次数大约10000+，然后把每次的枚举出的砖的排列，铺在网格里面试试看，看上去在二维数组中不好弄，但是每次最多铺7块砖，大不了每次铺一块砖就枚举H×W的网格，尝试一次方案的时间复杂度也就256*100，考虑到剪枝优化的存在，这是练练暴搜不错的题目
E 题意：给N个球，每个球有颜色Ci和价值Vi，去掉K个球使得任意相邻两球颜色都不一样，且使得价值和最大并输出，如果无法达成输出-1
这题一看就是DP，先想朴素的状态f[i][j]，表示前i个球（第i个球必须选）去掉j个的最大方案数，考虑到状态转移，那需要三层循环来实现，画一张图看一看状态如何转移的，就能想清楚优化过程，这道题目值得上课好好说说，DP的主流题目
F 题意：给出N个顶点和M条边的简单图，每个顶点上有一盏灯，初始时都是灭的，选中一条边，可使得边连接的两盏灯改变状态，问任意操作（范围0~M次）能否让K盏灯亮，如果可以输出操作次数，并且把操作序列输出
G 题意：AtCoder Beginner Contest 344
B
C 题意：给出三个数列A、B、C，Q个查询，问给出的数ci是否满足ci=ai+bi+ciAtCoder Beginner Contest 343
B 题意：给出一个邻接矩阵，把第i个顶点的所有直连的顶点输出，题目很水，但需要懂图的存储结构
C 题意：找出不大于N的最大回文立方数
D 题意：N个玩家，T行数据，每行(Ai,Bi)表示第Ai玩家在第i秒得分Bi，玩家自己的得分进行累加，问每秒后玩家手中的分数的种类数
E 题意：在三维坐标系中放三个边长为7的正方体，不相交的体积和为V1,两两相交的体积和为V2，三个相交的体积和为V3，问给出V1、V2、V3，能否成立，能成立的话，给出三个立方体放置的x，y，z的起始坐标。
F 题意：给出一个数列，（1 p x）表示把第p个数改成x，（2 l r）询问在[l,r]区间第二大的数出现几次。
G 题意：给出N个字符串，问构造一个字符串使得给出的字符串都是这个串的子串，问构造的这个串最短长度是多少？AtCoder Beginner Contest 342
AtCoder Beginner Contest 341
AtCoder Beginner Contest 340
C 题意：给定一个数字N，分解成两个连续数（两个数字和为N），代价为分解的数字，如果数字不为1，继续用刚刚的方法把每个数字分解成两个数字，并统计所有的代价。数字的分解犹如一颗二叉树，看数据规模最多分解1000000层，如果枚举每个数字会超时，但是分解是有规律的，合并一下还是比较容易解决的。
D 题意：给了N个阶段，每个阶段i给出一个三元组（ai,bi,xi），ai表示到下一个阶段i+1的时间，bi表示到xi阶段的时间，求1到N阶段的最少时间，看数据规模，每个点最多建两条出边，那直接建个图，迪杰斯特拉跑一下最短路结束。
E 题意略，就是一个区间修改的题目，直接上线段树解决。
F 题意：二维平面给出一个点(x,y)，求一个点(a,b)，使得(x,y)(a,b)(0,0)三个点构成的面积为1，注意答案要求整数解，否则输出-1。这题目需要会叉乘求向量构成的三角形面积，然后转成线性不定方程，接着用扩欧求解。AtCoder Beginner Contest 339
B 题意：给定一个网格，每行首尾相连，每列首尾相连，从(1,1)出发，一开始面朝上，如果当前网格是‘.’，那么就变成‘#’,并且顺时针转90度，走到面向所指的下一格，如果当前网格是‘#’，那么就变成‘.’,并且逆时针转90度，走到面向所指的下一格，给定步数，问最后网格变成啥样子打印出来，模拟水题。
C 题意：给出N站的上下客人数，注意车辆在停靠每站后，车上的人数至少为0，不可能为负数，问最后车上有多少人。送温暖题
D 题意：地图里面两个人，可以往上下左右移动，但是必须保持同步，如果移动过程中遇到障碍或越界就停留在原地，问两个人走到同一个位置最少步数是多少。500分左右及以下的题目的做题技巧先考虑朴素的做法，然后再看看数据规模而定。这题如果往贪心方向想，显然能感觉出来不好处理，那就往暴搜想，这种题目一看就不是线性搜的题目，然后暴搜只剩下dfs和bfs，一看数据规模，就是bfs+最短路（注意不带边权的，又是二维数组保存的图不需要用sssp的算法）的做法，具体做法如下：
(1)保存地图，同时找到两个人的位置(c1,d1)和(c2,d2)
(2)dist[i][j][k][l]表示走到(i,j)和(k,l)这两个位置的最少步数，一开始dist[c1][d1][c2][d2]=0，同时构造一个node{c1,d1,c2,d2},扔到队列中
(3)队列不为空，队头就不断出队，往四个方向走，会产生四个方向的值，注意因为有障碍和越界的情况，所以有的点就会停留在原地，生成的值只有比dist小才更新，同时入队
(4)在出队的时候可以判一下队头node，如果c1=c2且d1=d2，那就是题目的答案，如果队列空了都没解，就输出-1
E 题意：求一个满足条件（相邻元素的差值不能大于给定的D）的最长子序列长度，这题目一看就是DP，裸方程f[i]=max{f[j]}+1,|a[j]-a[i]|≤D，1≤j<i，但是一看数据规模超时了，这道题目肯定是需要优化的，看数据规模必须用logN来优化，介绍一下线段树优化的做法（此题一定要研究给出的数据规模）
(1)逻辑上构造的线段树的叶子是对齐ai值的，叶子上面存的是ai为结尾能构成的最长子序列的长度，而整个线段树返区间最大值
(2)每次读到一个a[i],分别到线段树中的两个区间去查询，一个区间[max(1,a[i]-D),a[i]]，另一个区间[a[i],min(500000,a[i]+D)],查询到的最大值+1就是当前a[i]为结尾能构成的最长子序列长度，然后再更新线段树中叶子a[i]的值，返回时维护最大值
F 题意：给定一个长度为N的数列，问满足Ai×Aj=Ak的方案数，注意i,j,k可以为同一个数，看数字的规模貌似需要高精度，再一看长度，用高精度枚举的话肯定超时，因为条件用到的只有乘法，所以用双hash把数字的规模降到int范围内，用双hash保证数字唯一，推荐更高效的做法，两层循环来枚举i和j，用map来查询k，由于存在数字重复的可能，先去重统计，后面自然用到加乘原理，题目是2秒的限时，双has三层死枚举你们可以试试看AtCoder Beginner Contest 338
C 题意：n种食材，每种食材数量qi，做两种类型的菜肴，每种类型菜肴的分别消耗数量为ai和bi的食材（下标和食材下标对齐），问最多能生产多少数量的菜肴。300分题目的算法很简单，此题需要分析能力，具体做法如下：
(1)先枚举ai计算出生产第一种菜肴的上限cnta
(2)外循环枚举cnta到0，内循环计算能做出第二种菜肴的最大值cnta，然后更新全局最大值，另外注意考虑一些特殊情况（例如消耗量为0，消耗量超出给定的食材数）
D 题意：n个岛构成一个环，给定一个M长的游岛路线，问断某一条边时游岛路线所经过的边数最小值
首先来看朴素的做法（超时），外循环枚举断边，把路线相邻岛屿(a,b,且a<b)看成一个区间问题，内循环枚举区间，如果断边被[a,b)包含，那么就累加n-(b-a),否则就累加b-a，然后来更新ans
正解需要用到差分数组的思想，假设n=6,旅游路线2，4，整个数组记录(2,4)断边和不断边对所有区间的影响，如果[2,4]之间存在断边，那么dif[2]=4,dif[4]=-4,注意dif下标与边对齐,dif[2]表示2-3边断开，非[2,4]之间的断边表示为dif[4]=2,dif[1]=2,dif[2]=-2，最后求一下差分数组的前缀和，同时求最小值就是答案了。
E 题意：给2N个点，以顺时针顺序均有分布在一个环上，给N个弦，弦的两端(a,b)是环上的点，保证给出所有弦的端点都是唯一的，问是否有存在相交的弦，如果有输出“Yes”，否则输出“No”，具体做法如下：
(1)任意弦的两端|a-b|是偶数，那必然有相交
(2)如果|a-b|=1，f[a]=f[b]=1，表示这两个端点消掉，|a-b|≠1,pq.push({min(a,b),max(a,b),|a-b|})
(3)我们从最短的弦开始消，判断a+1和b-1是否消掉,或者判断a-1和b+1是否消掉，如果能消掉就继续消，如果都不成立，就说明一定存在相交的情况。
F 题意：给定一个有向带权图，并且保证不存在负权回路，问保证至少每个点都能访问到，求路径最小值。这道题目的做法基本上就是floyd+TSP（TSP是模板问题，类似状压的做法）
(1)先用floyd求出所有点对的最短路
(2)f[i][j]i用二进制表示访问过的点集，j表示访问过的点集最后的那个点，然后三层循环，第一层枚举i，第二层枚举j，第三层枚举k，f[i][j]的转移有两种写法，一种是向谁转移，还有一种是谁转移而来，看个人习惯，最后求一下f[(1<<n)-1][j]的最小值即可。AtCoder Beginner Contest 337
B 字符串规则校验问题，数据规模很小，所以可以随便做，但是如果用队列的思想会非常高效，和队尾一样就跳过，不一样要么非法要么加入队尾
C 以测试数据为例
6
4 1 -1 5 3 2 其实根据题意，1在4的右边，根据输入数据构造这样的二元组(4,1)(1,2)(0,3)(5,4)(3,5)(2,6)，然后构造一个数组即可，arr[4]=1,arr[1]=2...，我们从0开始索引，arr[0]=3,接着arr[3]=5,以此类推，很容易就得到答案了
D 题意:每次可以把一个'.'变成'o'，问最少的变换次数能得到一个连续的'o'长度为K(可以是行或是列上)，无解输出-1，一般到了第四题一定要看数据规模，此题的数据规模要么线性要么O(nlgn)，保存数据输入数据，先每行搜一遍，再每列搜一遍，做法上类似尺取法，接下来以某行数据来解释算法“.x..o...oox.”,K=6
起始位置对齐1，lt=1,rt=0，rt++，因为是'.'所以cnt++(是'o'就不用++，是'x'就要重置)，rt-lt+1<K，不用更新ans，接着rt++，发现'x',lt=rt+1=3，cnt=0，然后rt++，因为又是'.'所以cnt++，rt-lt+1<K，不用更新ans，以此类推，当rt=8的时候，lt=3,这个时候长度rt-lt+1=K，cnt=5更新ans，当再r++，rt-lt+1>K，我们让lt++，发现lt的位置是'.'，那么我们cnt=4，然后更新ans，这样就像一把长度为6的尺一段段量过去，而lt++好比出队，rt++好比入队，每个元素只进出一次队，所以时间复杂度O(n)
E noip出过这种交互题，所以一定要做做，免得考试的时候不习惯
题意：给N瓶果汁，其中有一瓶已经变质了，问你最少要找M个人来，喝一把就能确定哪瓶果汁变质了，要求你根据给出的N来确定M,并且如何分配这些人喝那几瓶果汁(数量，瓶子编号且升序)，然后它会回答你一个S，是一个01串，对齐人的编号，1表示哪个人喝坏了肚子（有可能有多个1），要求你确定哪瓶果汁是坏的，这是个结论题(考试临场来不及想)，具体做法如下
人数M=ceil(log2(N)),然后把人和瓶子的编号都对齐0开始，然后瓶子的编号看成二进制，二进制哪位有1就让对应编号的那个人喝，最后喝出有问题的人的编号对应到相应的二进制，转程十进制就是有问题的果汁编号(注意在偏移回1)
F 题意：给出N个球M个盒子K为每个盒子放球的数量限制，再给出每种球的颜色Ci且顺序排放，执行n次，每次完成以下两步后统计所有盒子球的数量输出
（1）把队头的球移动r次到队尾，r和N的对应关系（0~N-1）
（2）顺序遍历所有的球，队头的球做如下两种操作：如果存在一个盒子装有同种颜色的球且数量小于k，则放入此盒；如果不存在这样的盒子，若存在空盒则放入，不存在空盒就舍弃此球
这道题目是区间统计的问题，个人觉得以前考区间统计无非掌握splay或者莫队做法，但是现在的题目就是考逻辑思维，这道题目值得上课好好说说
GAtCoder Grand Contest 336
B 题意：二进制下从低位开始找连续0的数量，此题有O(1)做法
C 题意：只能用0,2,4,6,8来组数字，问第N个数是啥，把这五个数字看成五个符号，就当五进制来处理即可
D 题意：给定一个长度为N的数列，构造成最长的1,2,…,k−1,k,k−1,…,2,1类似金子塔的数列，可以选择数列中的任意元素减1，也可以删除队头或队尾。一看题目就有点像最长上升子序列，但是必须连续，且严格递增1或递减1，这显然是线性DP的题目，定义f[i][0/1],f[i][0]表示当前数字i为顶从左面能构造的最长长度，f[i][1]表示当前数字i为顶从右面能构造的最长长度，这种题目放六级考能笑出来，转移方程很容易想，注意考虑的周到一点。
E 题意：给定一个N，问数字能被数位和整除的数字有多少个，这题目一看数据规模，再一看简洁的题目而且给了10s的限时，那肯定是数位DP的题目，做法如下：（枚举+数位DP）
F 题意：给定一个H×W的网格，每次选定一个(H−1)×(W−1)大小区域做180度的选择，问20次内的操作是否能让网格内的数字以行优先顺序排列，如果能输出最少步骤，如果不能输出-1。看题目给出的选择区域大小，实际上每次操作只有四种选择，那逻辑上就是一颗四叉树，但是仔细分析以下，有一叉是上一步的逆步骤，所以实际上就是3叉树，那时间复杂度3^20超了，因为目标明确，那很自然的就想到双向bfs，时间复杂度2×(3^10)，这道题目还是偏裸题的，比E好做多了。AtCoder Beginner Contest 335
B 题意：给定一个N，打印所有x+y+z<=N的方案数，按照字典序，递归练手题
C 题意：二维坐标系，一条龙初始在(1,0)到(N,0)的位置，龙头在(1,0)位置，Q次操作，1 c（R, L, U, D）表示龙头往上下左右四个方向移动一格，自然的龙身的每一部分都移动到前一部分的位置，2 p询问龙p位置当前在哪个坐标。分析一下不难发现，龙头移动一次代表一帧，而龙身距离龙头的位置关系和每一帧存在对应关系，例如，龙头移动了5次后，询问龙身第4部分的最新坐标，因为4相对龙头间隔3个位置，龙头的第2帧位置就是龙身第4分部分的坐标，做法上用数组记录龙头的每一帧坐标，然后根据映射关系就能计算出坐标，还有要注意如果龙头移动帧数少，而龙身很长，这时候后要特殊探讨一下。
D 题意：给定一个网格N，T必须放在（(N+1)/2,(N+1)/2）的位置，其他格子用1到N^2-1填充，而且要求形成一条数链，数据规模很小，如果N是奇数的话，打印一个螺旋矩阵即可，如果是偶数，自己花一下，也是可以用螺旋矩阵打印的，不过出发点必须是右上角，所以给定一个数，直接从右上角开始打印一个螺旋矩阵，然后填充一个T即可。
E 题意：给定一个无向图，每个顶点有一个权值，找一条从1到N的简单路径的长度，要求路径上的点的权值必须非减，且点的权值种类数最多（相同权值算一种）。分析题目，最长路径不一定是最优解，而是要这条非减路径上的不同权值尽量多，这题的难点就在于怎么处理相同权值的点，具体做法如下：
(1)如果a[u]<a[v]，就从v到u建有向边，a[u]>a[v]同理，如果a[u]=a[v]就双向建边，并且把这些边都保存下来
(2)tarjan缩点建新图，同时记录一下1和n的新的编号new1和newn
(3)然后从newn开始dfs，类似记忆化搜索记录dist[],最后输出即可
注意我写了一下，但是大数据都超了200ms，很多地方直接copy模板，细节上的优化值得说说
F 题意：N个方块顺序排放，第i个方块对应Ai，第1块是黑色的，其他都是白色的，通过i+Ai×x可以把第i个方块染黑，问染成黑色（可以是部分方块为黑色）的方案数AtCoder Beginner Contest 334
AtCoder Beginner Contest 333
AtCoder Beginner Contest 332
AtCoder Beginner Contest 331
AtCoder Beginner Contest 330
AtCoder Beginner Contest 329
AtCoder Beginner Contest 328
AtCoder Beginner Contest 028
A
B
C
D
E
FAtCoder Beginner Contest 112
C金字塔中心CX,CY,其他坐标(X,Y)为x(H−|X−CX|−|Y−CY|,0)，Cx，Cy为0到100（包含）的整数，H是不小于1的整数。给出其他点的信息求中心坐标和高度。
D给出数字数量N和累积和M，求这些数字的最大公约数。AtCoder Regular Contest 103
E
FAtCoder Beginner Contest 111
C使一个数列只有2种数字，且距离间隔为2的数字都一样，问最少替换多少数字。
D给1000个二维平面上的点，坐标值域[-1e9,1e9]，构造一个机械臂，最多40条边，每条边有长度和方向，方向可以是上下左右，你需要确定边的个数和各个边的长度，再对于每一个题目给出的点，通过改变每条边的方向，使得每个点都可以通过机械臂和(0,0)连接，注意(0,0)和每个询问点分别是机械臂的两端端点AtCoder Beginner Contest 110
C
DAtCoder Grand Contest 027
A
B
C
D
E
FAtCoder Beginner Contest 109
C给出横坐标上n个点，从X出发，要求最大的D，可以+D也可以-D，保证每个点都能走到，距离X的距离的最大公约数
D给你一个n*m的矩阵，你可以让一个元素-1，然后选择一个和他相临（上下左右）的元素+1。每个元素只能减一次。问你进行任意次操作后，矩阵中偶数元素最多。AtCoder Regular Contest 102
E给n个k个面的骰子，询问i在2到2k-1，问n个筛子任意2个和不等于i的组合方式
F给出n长的排列，范围2≤i≤N−1，如果pi−1>pi>pi+1就反转，整个排列都可以输出yes，不然输出noAtCoder Beginner Contest 108
C给定一个N，造一个三角形三条边都不大与N，且任意两边之和能够除尽K，问这样的三角形有多少种
D给出一个L，构造一个N个顶点M条边的图，使得顶点1到顶点N的有L条路，且每条路长度从0到L-1AtCoder Regular Contest 101
E给出一个顶点数是偶数的树，把所有节点分成n/2对，在点对之间的最短路径覆盖彩带，保证每条边都被彩带覆盖，问有多少种方法
F在数轴上有n个机器人和m个出口， 可以把所有机器人同时向左或者向右移动一个单位，一个机器人碰到出口就会离开，问有多少种方案数把让所有机器人都从出口出去，两个方案不同当且仅当存在一个机器人从不同的出口出去，答案对1e9+7取模AtCoder Beginner Contest 107
Cx轴上有N个蜡烛，从原点出发问点燃k个蜡烛的最短距离
D给定一个数列，求出所有连续子序列的中位数，再在这些中位数中求中位数。AtCoder Beginner Contest 106
C由1-9构成的字符串，变换5*10^15天后，问第k个字符是什么
D给出一个区间1-n有m辆火车，每辆火车有自己的行驶区间，每次询问有一个l,r问l,r内有多少辆火车。树状数组，差分，利用STL、离散化来做。AtCoder Beginner Contest 105
C用-2进制表示任意的一个整数
D连续子序列和为偶数的个数AtCoder Beginner Contest 104
C有D种题目，分数分别为100，200，。。。，AC完一种题目都有一个奖励分，给出目标分问至少AC多少题目，二进制暴搜
D给出有ABC？构成的字符串，如果有有？可能有多个，所有的由ABC排列填入问号，问所有非连续子串ABC的数量AtCoder Beginner Contest 103
C给定一个数列，找到一个数，使得这个数除以这个数列中的每个数的余数和最大。考试可能考，普及组第一题
D从西向东各节点之间有一条路，给出M条信息，每条信息包含两个节点，问最少删掉几条路，使得M条信息中的节点都不连通。有概率会考AtCoder Grand Contest 026
A给出一个数列，相邻2个数一行会自动合并，问改变多少个数字使得任意2个相邻的数都不一样
B早上有A瓶果汁，每天买B瓶果汁，晚上如果小于等于C瓶果汁，第二天早上能增加D瓶果汁，给出T条数据，问每天能不能都买到B瓶果汁
C给出一个字符串，给每个字符涂色红或者兰，使得从左取红色字符组成的串和从右取出蓝色字符组成的串相同，问有多少种涂色方案。
D给出一个裁剪过的网格，给这些网格特色，使得有上下左右的四个网格中有两个红色和两个蓝色，问有多少中涂色方案。
E
FAtCoder Regular Contest 100
E2的N次方个数，存为Ai，令1≤K≤2的N次方−1，请你求出(i,j)，使Ai+Aj最大，并且0<=i< j<=2的N次方-1且(i or j)≤K。输出Ai+Aj的最大值。
F构造一个由1到k（都出现）长度为N的所有数列，给出长度为M的子数列A，问A在所有数列中出现次数的总和。AtCoder Beginner Contest 102
C给出公式abs(A1−(b+1))+abs(A2−(b+2))+…+abs(AN−(b+N))找出b使得公式的值最小
D把一个数列分成4段，每一段累积求和，使得最大值和最小值之间的绝对差值最小AtCoder Regular Contest 099
E无向图一分为二，要求每一个图中的任意两点之间都有路，问一条路的两端同属同一个图的路有几条，且在满足题意的条件下去最小，无解输出-1。
F给你一个字符串表示操作。+表示在指针对应位置上的值+1,-表示在指针对应位置上的值-1,>表示把指针右移1位,<表示把指针左移1位。假设按原串操作后序列为A。求有多少个子串使得操作后的序列B等于A。AtCoder Beginner Contest 101
C给出一个数列n，每次选中k个长度的连续子序列，把这个连续子序列变成这个子序列中的最小值，问最少操作次数。贪心归纳
Ds（x）代表数位和，m>n，且m/s(m)>=n/s(n),求前k个这样的数字AtCoder Beginner Contest 100
C给定一个数列，每一次操作可以对数列中的元素乘以3或者除以2，但是不允许都乘以3，且每次操作完都必须是整数，问最多操作多少次
D给定N种蛋糕，每种蛋糕有ABC三种值可以为0也可以为负，现在要买M中蛋糕，使得每种蛋糕所有A总和的绝对值+B总和的绝对值+C总和的绝对值最大。AtCoder Beginner Contest 099
A题目大意atcoder原来比赛命名规则ABC+数字，但是当比赛数量超过1000以后原来的命名规则不支持了，最后决定如果比赛是1000到1998范围内就用ABD开头，算法略
B题目大意有999座塔，塔与塔之间间隔1米，从西向东按题意递增，现在给出相邻两座塔未被积雪覆盖的高度，求积雪厚度，因为不管积雪怎么覆盖，相邻两座塔的差值不变，求出差值就能算出两座塔的高度，自然就能得到积雪的厚度
C题目一看就是动态规划，给出几种货币，问给定的面值用最少的货币凑出来，直接方程了f[i]=min(f[i],f[i-a[j]]+1)。f[i]表示i面值的货币数量，a[j]表示第j个货币的面值，这题需要按照题目范围构造出题目意思中的货币，构造完a[j]数组需要按面值排序，另外注意常规动态规划题目不值钱只有300分，算简单的题目了。
D题目大意给定一个N行N列的网格，网格中的每个格子(i,j)颜色用c(i,j)表示，就是输入数据中第二个矩阵的值，这个矩阵的大小肯定是N行N列，要求整个网格是个好网格，好网格满足任意两个格子的坐标和对3取余数如果一样颜色必须一样，坐标和对3取余数不一样，颜色也必须不一样，输入数据给出的第一个矩阵表示从某种颜色转到另一种颜色的代价值，矩阵的大小肯定是C行C列，要求把题目中给出的网格变成好网格付出的代价最小，题目看懂枚举一下即可AtCoder Grand Contest 025
A给定一个N，使得A+B=N，问A的数位和加上B的数位和的最小值。主流考题
B涂色N层的塔，给定A和B两种值，红色为A，绿色A+B，蓝色B，问涂层总值为K的方案数有多少种。
CAlice和Bob在玩一个游戏，初始时Bob在数轴原点，Alice手上有NN条线段，每次进行操作：Alice选择一条之前没有选择过的线段；Bob走到线段上任意一点；最后Bob回到数轴原点。令Bob走过的距离为KK，Alice想要KK尽量大，Bob想要KK尽量小，求最终KK是多少。
D二维平面中点的数值在给定范围0到2N之间，构造一个点集，使得点集中任意两点距离都不等于D1平方根和D2平方根，输出点集
E
FAtCoder Regular Contest 098
EQ次操作，每次操作任取K个长度的连续子序列，删除其中最小的元素，使得Q次操作中删除的最大数和最小数之差最小。
F无向图中每个顶点有Ai和Bi两个值，开始值为W，从一个Ai（<=W）出发会有两种花费产生，当前点花费Bi，走到相邻点会花费相邻点的A值，问遍历完所有点的最小初值W。有可能会考AtCoder Beginner Contest 098
A题目大意两个整数作加减乘运算，求三种运算后的最大值
B题目大意把一个字符串任意位置一切为二，求切开后两个子串中都含有的字母数最大数。这题看一下数据规模才100，枚举一下任意位置后求最大值即可。
C题目大意从西向东排着一队人，队伍中的每个人或是面向西或是面向东，从队伍中选一个领队出来，接下来队伍中所有的人都必须面向这个领队，求选一个领队使队伍中改变面相的人数最少，问有多少个人需要改变面向。弄两个前缀和数组一个记录西一个记录东，然后线性枚举利用两个前缀和数组求最小值即可。
D题目大意给定一个整数序列，从这个序列中找一个起始位置left，结束位置right（left<=right），使得从left到right中所有数字的异或和等于所有数字的和，问满足以上条件的left和right总共给有多少对。作这道题假设你们已经理解了前缀和的用法，接下来谈谈对异或的理解，如果有一个二进制1101，然后我们用两个二进制数1001和1000对这个1101进行异或，第一次异或下来的结果是0100，接着异或结果是1100，通常意义上我们把异或理解成对称加密，1101经过1001、1000两个密钥进行两次加密变成1100，如果1100和0100异或是什么结果，结果就是1000，也就是用两次加密的结果和一次加密的结果进行异或就能异或出第二次的密钥，因此这道题就非常的简单了，弄两个数组分别记录前缀和和前缀异或，然后两层循环外循环枚举left，内循环枚举right，结果是利用两个数组可以直接求出结果的。AtCoder Grand Contest 024
A一开始有3个数A,B,C， 每次操作A1=B+C,B1=A+C,C1=A+B，然后A=A1,B=B1,C=C1，问操作K次后A−B的值。
B给定一个排列，每次可以选择一个元素，将其移到序列最前面或最后面，求最少移动多少次能把排列按升序排好。
C长度为N的X队列初始都为0，给出一个长度为N的A队列，可以操作X队列中第i+1个元素的值等于第i个元素加1，问最少操作多少次X队列和A队列一样
D给出一个由n个点的组成的树，你可以加一些点形成一个更大的树。对于新树中的两个点i和j，如果以i为根的树与以j为根的树是同构的那么i和j颜色可以相同。问最少需要多少颜色，在颜色最少的情况下，最少需要多少叶子节点。可能考？
E
FAtCoder Regular Contest 097
E有2N个球排列，N个白球，N个黑球，乱序排放，可以相邻交换使得白球升序黑球升序，问最小的交换次数。高概率DP
F一棵树叶子或白或黑，一只猫在树上走一秒走一次相邻的节点，当前节点的颜色和要走的相邻节点的颜色都会反转，起始和结束可以任选位置，问最少多少秒使这棵树变黑。高概率DPAtCoder Beginner Contest 097
A略
B题目大意是求最接近给定X的完全幂数，由于X的值不大，可以枚举作也可以直接打表出结果
C题目大意是给定字符串中所有的子串（子串需要去重且不包含空串）按字典序排，求出第k个子串，算法上面先求出k个长度的子串，用一个变量minstr保存最小的k个长度子串，每次取k个长度子串时不断与minstr做比较，比minstr小更新minstr且拆分k个长度子串进set，如果不比minstr小就不处理，需要考虑边界条件，这道题用set类模板和string类会方便很多
D题目大意给定一个排列，再给m个位置对（位置里面的两个数字可以交换），m个位置对可以反复操作，求经过无数次操作后，每个数字换回到与自身数字一样的位置上的最大可能数有多少个，算法上把每个数字都看成图中的一个结点，位置对表示连接两个结点的一条边，然后来看整个图里面的强连通分量有几个，比如1位置上是数字5，就到图里面去看数字1和数字5是不是联通，如果联通说明数字1一定能交换回位置1，具体做法上面可以建联通图用dfs查询也可以用并查集dsu作，dsu作很方便AtCoder Beginner Contest 096
A题目大意是给定2018年中的某月某日，求之前月日相同的天数，枚举一下即可，推荐月中的天数直接全局变量事先做好
B题目大意是给定三个数，找出最大的数经行k次的double，最后求三个数的和
C题目大意是给定一个H行W列的画布，‘#’代表画黑色，‘.’代表画白色，每次画黑色的时候必须相邻的两块同时画黑色，如果相邻的两块中有黑色画完后还是黑色，问给出的图案是否能画出来，直接枚举图案中每个点，如果是黑色的点看看周围有没有黑点相邻，不相邻直接跳出返回No即可,常规枚举题。
D题目大意是求出N个质数，这N个质数必须满足以下条件：从N个质数中任意挑5个数出来求和必须是一个合数。如果纯粹枚举的话这道题目会超时，这道题是基于对数字特征的理解，因为任意挑5个数的和是合数，所以我们让选出来的质数只要除以5的余数都是1就可以了，枚举一下质数可以发觉1结尾的质数很多，显然这些质数都是满足除以5的余数是1，另外发现这些质数的间距通常在20到40之间，那么我们可以以11或31开头，每次增加20或30来枚举符合条件的质数AtCoder Grand Contest 023
A一个数列里面连续子序列和为0的子序列数量
B给出第一块板中的字母，找一对(A,B)把第一块板中单元格 (i+A,j+B) 中的字母放入第二块板中单元格 (i,j)中，使第二块板中的单元格（i，j）等于（j，i），问这样的A和B有多少对
C给出一排方格，长度为N，开始都是白色，设一个长度为N-1的排列P，用排列中的数字来涂色（涂i和i+1），所有颜色都涂成黑色时记录使用的排列数字的个数作为分数，统计所有排列的总分
D有在一条数轴上有N座公寓，第i座公寓坐落于上xi上，公司坐落于S，公司的每个员工都住在某个公寓里，第i个公寓里住了pi个人；每天下班的时候大家⼀起投票向前还是向后，每个都能知道大家的得票情况，并根据大家的投票情况来选择自己的投票情况，如果票数相同就固定向前走，但最重要的一点，每个⼈是自私的，希望自己尽早回家。 ，但不一定就会投自己方向（可以参考传送门的样例）每个人到家了就会下车，问大家做最优决策的情况下，最后⼀个回家的人多久就可以到家？
E
FAtCoder Regular Contest 096
E给N种浇头，不允许任意两碗拉面的浇头一样，同时满足所有的浇头都必须出现2次以上在不同的碗中，问满足以上条件需要多少碗拉面，结果对M取余
F用X面粉制造N个甜甜圈，后面的甜甜都是从1号甜甜圈直接或间接转变而来用pi记录，ci代表每种甜甜圈数量，要求满足cpi≤ci≤cpi+D，D为给定的数字，问最多甜甜圈数量。AtCoder Beginner Contest 095
A题目大意字符串三位分别代表是否要加煮蛋、肉片、绿洋葱，最后计算拉面的价钱，基本字符串操作
B题目大意是给N种甜甜圈，并且标明了每种甜甜圈要消耗的moto量，接下来再给出moto的总量，问每种甜甜圈至少做一个的情况下，最多能做出多少个甜甜圈，这题算是最简单的贪心题目了，先减去每种甜甜圈都做一个消耗的moto量，剩下的都做消耗moto量最少的那种甜甜圈
C题目大意是有三种匹萨，A匹萨，B匹萨，AB各一半的组合匹萨，三种匹萨对应的价格是A、B、C，现在需要X个A匹萨和Y个B匹萨，允许A匹萨和B匹萨可以通过买AB组合匹萨重新拼成，问最少花费多少钱可以买X个A匹萨和Y个B匹萨。这道题属于分类讨论，有可能单买划算也有可能买组合匹萨划算，题目不难，分类讨论的时候要求有清晰的条理性
D题目大意是给定一个周长为C的圆台，圆台上有N份寿司，每份寿司给出圆台边上的位置和摄入的能量，从位置0开始走，每走1米消耗1点能量，吃一份寿司获得能量，可以顺时针走也可以逆时针走，不需要吃完所有的寿司，问获得能量的最大值，这道题目对考试来说是有价值的，先顺时针计算每个位置能量值假设用数组a，再逆时针计算每个位置能量值假设用数组b，接下来需要处理一下a和b数组，a[i]=max(a[i-1],a[i]),只要考虑前一步和当前这一步，同理b数组反着处理一下，接下来重新考虑a数组、b数组、a[i]和b[i+1]的组合、b[i]和a[i-1]的组合是否有更优解AtCoder Regular Contest 095
E给定一个H*W的矩阵，矩阵里面的元素都是字符，任意两行交换或者任意两列交换，问是否能让矩阵对称a[i][j]=a[H+1-i][W+1-j]
F给你一个序列(p1,p2,…,pn)对于每一个结点(1,2,…,n)，两种操作：1.如果pi=1,无需任何操作；2.如果pi≠1，找出最大的j,满足pj<pi，则连接结点i和结点j。通过序列(p1,p2,…,pn)可以唯一的构造一棵树。题目给你n表示有n个结点，然后n-1条边构造一棵树。问是否可以输出一个(p1,p2,…,pn) 序列，通过这个序列构造的树和题目给出的树同构，可以的话，输出满足这个条件的最小字典序的序列。无解的话输出-1。AtCoder Beginner Contest 094
A做之前最好能归纳一下：满足X>=A且0<=X-A<=B
B这题目一般的做法就是比较0枚举到X和X枚举到N看谁小，比较好的做法在读入M个数据的时候直接和X比大小，用两个变量计数一下就可以了，最后把小的输出
C这道题和奇偶性挂钩，题目的大意为给定一个数列（数列数字编号1到N，且N为偶数），求分别拿走编号1到N个数字时，对应的第（N-1+1）/2个大的数字是几？比如拿掉第一个数字，剩下2到N个数字，这时有N-1个数字，按照题目要求算出（长度+1）/2个大的数字。算法上对数列排序，然后计算当前的数字与整个排序完后的中间数做比较，如果比中间数大结果就是中间数，如果比中间数小，结果就是中间数后面那个数字
D题目名字叫二项式系数，最近的题目都是偏数学的，题目的大意就是comb(n,r)，组合公式n里面选r个，问给定的一堆数字里面挑两个出来他们的组合数最大，如果存在多个答案，输出里面任意一对即可，这个题目先要证明一个问题，假设选出两个数comb(a,b),如果c>a，那么comb(c,b)>=comb(a,b),这个画一下杨辉三角就明白，所以选两个数字，首先选给定数列里面最大的那个数字，然后再选个数字（就是杨辉三角一行上面靠近中间的数字）就是结果了，题目叫二项式系数，顺便说下组合可以用在二项式定理,展开公式如下$$(x+y)^n=C(n,0)x^n+C(n,1)x^{n-1}y+C(n,2)x^{n-2}y^2+...+C(n,m)x^{n-m}y^m+...+C(n,n)y^n$$
AtCoder Regular Contest 094
E给定两个数列A和B，两个数列的和是相等的，每一轮在A中任意挑一个数字减1，在B中任意挑一个数字减1，每执行一轮就增加一个糖果，对A的操作使得糖果的数量尽可能多，对B的操作使得糖果的数量尽可能少，问在此策略下如果使得糖果数量最多，输出糖果数。
Fn≤200000的abc字符串，现能进行如下变换零次或若干次：选一个i<n且si≠si+1，把si和si+1替换成abc三个字母中除了这两个外的另一个。问s能变出多少字符串。AtCoder Beginner Contest 093
A下标对位，小学编程掌握的基本技巧之一
B用一般程序思维写只能说soso，这道题用数学的思维就是个容斥题目，自己悟一下，前k个+后k个如果大于数字的个数必有交集产生，当然还要思考一下如果前k个+后k个小于数字的个数如何处理，接着把边界情况处理干净就行了
C这道题目找下规律归纳一下，统计每个数字和最大数字相差几个1和几个2，然后相差1的个数除以2看看余数是否为0，不是0说明最大的数字还需要增加，在原有累积出来的步数上相应的多增加2步
D这种就和17年提高组的day1第一题差不多，严格来说可以属于小学范畴奥数题，题目大意给定Takahashi在两个比赛中的排名a和b，然后问有多少个选手使得x*y<a*b(x和y是其他某一选手的排名)，接下来举例说一下算法，比如给出2和5，2*5=10，10的算术平方根取整是3，这个3可以假设成x或y的取值范围，这里我们假设3作为x的取值范围，那么一定能选中一个y和x的乘积不会超过10，这个题目核心的地方就是能想到1≤x≤(int)sqrt(a*b)（万恶的结论题就是这样的）,必定能得到一对x*y<a*b,最后处理的时候需要注意两点，一个就是a*b的算术平方根如果正好是个正整数怎么处理，一个是上面的算法上乘2，因为x和y能对调一次，看不明白我说的你们数学堪忧了。AtCoder Grand Contest 022
A定义一个完美的字符串表示为：字符串中没有出现两个相同的字符。现在给出一个完美的字符串，求字典序比它大的最小的完美的字符串。若没有输出-1。贪心
B给出一个N，找出N个数按升序输出，这N个数满足：所有数的gcd=1；任意一个数和其他数字的和的gcd！=1
C给出一个初始数列A，一个目标数列，每次找一个k，使得数列中的每个数字要么不变，要么变成除以k的余数，变换一次的代价2^k,问最终变换到B数列的代价。
DYui希望逛街购物，每个商店有一个火车站，位于一条坐标轴上，坐标为xi，现在，Yui从原点出发，到每个火车站的商店购物，并最后回到家中。已知每个商店的购物时间分别为ti ,这个火车从头开到尾从尾开到头，周而复始，问Yui能逛完所有商店回到家的时间最小值。
E
FAtCoder Regular Contest 093
E给出一个N个点M条边无向连通图，现在需要给每条边染色（黑/白），染色完毕后，算出一颗至少包含一条黑边与一条白边的最小生成树，要求这个生成树的权值和为X，求染色的方案数。
F有2^N个选手参与一场比赛，相邻的两个人比赛一次，败者淘汰掉，胜者继续进行，直到只剩一个人为止。给出M个数字，比赛规则是：1.1号和其他人比，如果其他人数字在给出的M个数字中，其他人赢；2.1号和其他人比，如果其他人数字不在给出的M个数字中；1号赢，3.非1号的两个人比，谁数字小谁赢。问让1号赢的排列方案数。AtCoder Beginner Contest 092
A这道题特别是老学生，写不出min(a,b)+min(c,d)你们可以去面壁了
B没什么好说的，怎么高效怎么来，连数组都不需要
C这道题目就有价值了，看到这种输出，第一反应就是题目需要打表（打表就是为了降时间复杂度），既然是打表的题目那就需要在读入数据（假设读入到数组a，注意下标对位）的时候进行处理，这道题目算容易的，就做个累积求和（假设累积到变量S），最后在输出的时候S-(|a[i]-a[i-1]|+|a[i]-a[i+1]|)+|a[i-1]-a[i+1]|,注意一下边界的控制
D这种题目就是平时用来积累的，其实就是需要做过才能在考试的时候反应的出来，题目的意思就是假设给个2 3，要你构造一个不超过100*100的格子，白色联通块和黑色联通块的数量分别为2和3，'.'代表白色格子'#'代表黑色格子，测试数据是具有迷惑性的，做法就是构造100行100列的格子，前50行都是黑色，后50行都是白色，然后看题目给出的数据，就在黑色里面方白色格子，假设要求你建3个白色联通块，那就在第一行第一列和第三列改成白色即可，极端的话前50行每行间隔放25个白色，然后隔着一行再用此法，那前50行可以放25*25个白色，这是小于给出的数据上限，所以这种方法是可行的。AtCoder Regular Contest 092
E给出一个数列，如果选中的数字是数列的两端就删除，如果不是两端的把左右相邻的数字相加替换自身，反复操作直到最后留下的一个数字最大。
F给定一个有向图，每次将一条边方向反转，问这个操作是否改变了图中的强连通分量数，对于每条边输出改变输出diff，不改变输出sameAtCoder Beginner Contest 091
A略
B这道题体现出C++优势，用map作会非常的方便，对于这类数据其实需要用散列的思想（数据无序主要体现在增删改查的时候不太容易用线性的方式，所以会用到key-value的映射关系来存储），散列存储基本来说考试就用map了，现在也是必须具备的基本用法之一
C这道题算法属于贪心，贪心算法就是解题过程一直用采用最优的策略，等整个过程走完得到的结果就是基于局部的最优策略算来的，这道题把红点和蓝点放在一起对着x坐标作升序，然后开始从头开始检索这些点，读到红点时把红点放入一个队列中（注意队列的形式也可以是数组，怎么方便怎么来，看自己驾驭代码的能力），队列中以红点的y坐标作有序排列，读到蓝点时用蓝点的y坐标去红点的队列中查找，找出小于蓝点y坐标的所有红点y坐标当中那个最大的（这里就是贪心了，本题的核心地方）然后答案加1，这个被找到的红色点出列下次就不用比对了，如果找不到就什么都不做继续检索下一个点，最后答案就出来了。当然还有一种做法就是二分图，固定算法不用变形直接用就可以了。
D这种题目就是平时用来积累的，粗略一看算法很显然就是暴搜，再一看用暴搜数据范围肯定爆了。这道题目的算法需要把数据变成二进制来处理，而且要把数据分成两大块来处理，因为是第一行数据分别加第二行数据最后异或和，在相加的时候会产生进位，而在异或和的时候是不会产生进位的，所以这道题在算法上就分成处理进位的数据和不进位的数据，用具体的数据来解释一下（还是担心有人看不懂这种和数学有关联的题目，就是需要大脑不断的演算数据，越到后面越考验计算能力），以样例数据为例4(1+3),5(1+4),5(2+3) and 6(2+4)，最后把4、5、5、6作异或就是答案了。我们换种算法先统计第一行数据1和2在二进制下每一位1的个数，再统计数据3和4在二进制下每一位1的个数，假设a、b代表第一排统计出来第四位的0和1的个数，c、d代表第二排统计出来第四位的0和1的个数，((a*d)%2+(b*c)%2)%2就表示第四位上面1的个数对着2取余（想通这点很重要，1如果偶数个这位就是0），接着ans^=(((a*d)%2+(b*c)%2)%2)<<4。如果加法都没有产生进位这样做就好了，问题是做加法的时候会产生进位会影响到最后的结果，所以接下来还需要处理每一次加法对最后结果的影响，先用数组保存后k位的二进制，接下来用第一行的每个数据去计算每一位是否能产生进位，产生几次进位就需要用到前面的数组，在查询数组的时候用到了二分查找，如果理解了做法，请告诉我这道题目时间复杂度是多少。AtCoder Regular Contest 091
E给出数字1到N，构造一个数列满足最长上升子序列长度为A，同时最长下降子序列为B，如果构造不出输出-1。有概率
F给n堆石子，每堆有一开始有ai个和一个常数ki。两个人轮流操作，每个人每轮可以选一堆石子，然后在其中取走1到ai/ki颗。谁不能操作就算输，问先手必胜还是后手必胜。AtCoder Beginner Contest 090
C有一个n*m的矩阵，这n*m个格子里都有一张正面朝上的牌，现对每张牌进行一次操作，就是翻转这张牌，同时，他的上下左右以及对角线方向，即包围它的八个方向上的8张牌也跟着反转一次，问，对每张牌进行该操作后，还有多少张牌朝上。
D给出N，K，a%b>=K且a和b<=N,问这样的a和b有多少对AtCoder Beginner Contest 089
C给一堆人名，只能从里面选出三个人，首字母必须是 M, A, R, C or H，且首字母不能相同，问方案数。普及高概率
D给定一个矩形，矩形中每个行每列有一个数字，给出距离D，给去Q个查询，必须通过移动D个距离，使得L到达R，问L到达R需要走几步。考试有概率AtCoder Grand Contest 021
A给定一个N，求不大于N且数位和最大的那个数字的数位和
B给 N 个平面上的点，现在平面上任选一点放置一个机器人。这个机器人会走到离自己距离 (此距离指欧几里得距离) 最近的点，然后停下。问机器人到每个点停下的概率是多少？
C用1*2和2*1的砖铺N*M的网格，给定1*2和2*1的数量A和B，问不能重叠的情况下在指定的网格中能否铺满A和B数量的砖
D在改变原串最多K个字母的前提下,使得T和T的反串的LCS尽量长。最长回文子序列的长度
E
FAtCoder Beginner Contest 088
C给定一个3*3的矩阵C，矩阵的行对应一维数组A，列对应一维数组B，C[i][j]=A[i]+B[j]问是否存在A，B满足矩阵C
D给你个包含.#的地图，.代表白色方块，#代表黑色方块，在保证可以从左上角走到右下角情况下，求最多可以把多少白块变成黑块。DFS或BFSAtCoder Regular Contest 090
E一张无向图中给出两个点S和T，问同时从两个点出发分别到对方且途中不相遇的最短路径的方案数。
Ff(n)表示为数字n的位数个数，给出S要求满足f(l)+f(l+1)+...+f(r)=S，l至r区间内所有数字位数的和等于S，问这样的区间有多少个。AtCoder Beginner Contest 087
C一个2行N列的网格，每个格子里都有糖果，起始为坐上（1，1），终点为右下（2，N），只能向右或向下走，问能收集的最多糖果数。递推
Dx坐标轴上有N个人，同一个坐标上可能有多个人，现给出M条信息，包含R，L，D，分别表示第R个人到第L个人相聚D个单位距离，问是否存在满足M的可能性AtCoder Regular Contest 089
E给出一个d<x,y>矩阵，给出n个顶点，要求做一张有向图，包含边和权以及出发点S和终点T，权值可以有固定值，也可以用x和y表示，x和y的取值范围在d矩阵中且x和y的任意取值都满足S到T的最短距离满足d矩阵中的值。
F给出长度N的白色空格，给出长度为k的染色序列，只有红蓝，可以在长度n的任意区间进行染色，但是蓝色不能覆盖白色，问方格染色的方案数AtCoder Beginner Contest 086
C每次只能上下左右移动一格，给出n步的数据包括时间和位置，问是否能达成给出的计划。
D给定花纹的规模k，给出n格指定坐标的颜色，问满足条件的方案数。AtCoder Grand Contest 020
A给定长度为N的格子，给定A和B初始位置，每个人只能往左右的空格移动一次，如果不能移动就输，问谁能赢或是打平。博弈
B给出n轮小孩子抱圈的数量，抱圈可以有多组，与抱圈数量的小孩子离开，最后总是剩下2个小孩子，问开始时人数的上限和下限。
C给定一个数列，求所有子序列和在非降序序列中的中值
D给出A和B的数量组成字符串，取出相同字母的子串尽可能短，在满足以上条件下使组成的字符串在字典序下最小。
E
FAtCoder Beginner Contest 085
C给定3种货币面值数量无限，给定货币数量和金额问能否用这三种货币组成且各自的数量，组不成输出-1。三层枚举，二层优化
D给出怪兽的血量，给出n种武器，每种武器有两种伤害值：击打值和投掷值（投掷只能一次），问消灭怪兽至少攻击几次，贪心算法，普及强化。AtCoder Beginner Contest 077
D给定一个数k，使得k于任意数字相乘得到结果的数位和最小，输出这个数位和
