6月11日 AtCoder Beginner Contest 099 题目链接：https://abc099.contest.atcoder.jp/
过水，不多说
思路： 一开始分析了下复杂度，以为迭代加深DFS可做。结果大样例跑了一万年QWQ。。
后面就想到了背包，完全背包直接从前向后扫一遍，就OK了。
代码:
1 |
|
思路： 开始想到暴力$n^2*c^3$，后面发现可以通过预处理将复杂度降为$n^2*c+c^3$，然后就可以过了。
代码：
1 |
|
6月11日 Educational Codeforces Round 45 题目链接：http://codeforces.com/contest/990
过水，不多说。
思路： 类似于模拟吧，不过思路一定要清晰（我弄错了很多次QWQ）。
可以用一个map记录有多少序列有x个左（右）括号未匹配，然后答案就可以通过这个计算得到。
代码：
1 |
|
思路： 是一道结论题吧。可以考虑当n>3时如果a,b均不等于1，则该情况不存在。当n=1或n=2并且a=b=1时同样无解。
其余情况都是有解的，然后就考虑输出方案。这时a或b有一个为1，如果b为1就直接构造，否则构造后输出它的反图。
代码：
1 |
|
思路： 也是一个比较简单的模拟+贪心。每一次放灯时尽量放右边，并且灯之间全要覆盖。要判一下能否符合要求，如果整个序列都符合要求，就更新一下答案。
代码：
1 |
|
大意就是：给你一个长度为n(n<=10000)的序列，再給你m(m<=20000)个询问，问你在给定区间[l,r]中的众数。（题目强制要求在线）
第一行n, m 第二行给你序列（序列元素小于10^9） 接下来m行每行两个数l, r。
m行，每行输出第m个询问的答案。
由于众数是不方便进行区间合并的，因此不能够使用线段树或树状数组等数据结构。在这种情况下，分块是一种可能的选择。
分块时，我们考虑一个区间的众数只可能是：包含在区间中所有完整块的众数或者是包含在不完整的块中的数。这样，对于任意一个区间我们把范围缩小到了$2*size$($size$为块的大小)个数。
我们可以预处理出第i个完整块到第j个完整块中的众数，储存为f[i][j]。然后我们就考虑如何计算这些数在区间中的出现次数。我们可以用vector储存下标，然后用二分查找找出区间内的元素个数，这个即是该数在区间内的出现次数。
分析一下复杂度，设一个完整块的大小为size。处理询问的复杂度是$m*size*log(n)$，预处理的复杂度是$n*n/size$，这样size在大约200差不多就不会TLE了。
1 |
|
有一个1-n的序列，你只知道在每一位之前有多少个数字比它小，请你求出这个序列。
第一行n， 接下来n-1行，第i行表示在第i个数之前有多少个数比它小。
输出这个序列
不难想到，这个序列我们可以从后往前推。我们设num[i]为第i个数之前有多少个数比它小。
因为最后一个数有num[n]个比它小，那它一定是num[n]+1。然后继续递推倒数第n-1个数，它就是除了num[n]+1中的第num[n-1]+1个数。依次类推，我们这样可以求出整个序列。
这道题有两种实现，一种是树状数组+二分，另一种是权值线段树，详细内容可以看代码。
树状数组+二分
1 |
|
线段树
1 |
|
6月3日 AtCoder Grand Contest 025 题目链接：https://agc025.contest.atcoder.jp/assignments
直接枚举就好了，不多说。
思路： 思路比较巧妙。我们可以将题意进行转化，你可以在n层中选取任意a层涂红，再从n层中选取任意b层涂蓝（如果一层既涂成红，又涂成蓝，那就相当与原题中的涂成绿）。
这样就把原来三种颜色变成两种。于是只要枚举a, b,答案就是
之和，其中满足A*a+B*b=K。
代码：
1 |
|
思路： 这是一个贪心，每次Aoki一定会选择让Takahashi行走距离最长的区间，而Takahashi一定会走到区间上最靠近自己的端点（如果Takahashi在区间中，则不动）。
因此，Aoki会选择左端点最右或右端点最左的区间，他轮流选择 左区间和右区间，这样使得Takahashi走的最长。
长度就比较好计算（细节见代码），但要注意由于起点和终点在原点，所以要把[0,0]这个区间加入进去。
代码：
1 |
|
思路： 这其实是一个二分图染色，假设一个点为白色，那么我们可以将与它相距$\sqrt{D}$的点染成黑色，那么这样永远不会有两种颜色相同的点距离为$\sqrt{D}$（由于是二分图，染色是不会冲突）。二分图的证明可以看原题题解，证明了一大堆
于是我们可以依据D1和D2，将这个图进行两次染色。我们可以根据我们染的颜色，确定出n^2个点。原题题解也证明了保证有n^2个点符合要求。 代码：
1 |
|