第一次打Codeforces的比赛。作为好公民的我填不了验证码，那天晚上在贺神犇的帮助下终于成功注册了帐号QAQ 凌晨2点爬起来。本担心爆零，但是Div 2果然有良心的水题。当时只完成了前3道，+60 rating。到今天把6道题做完了，写一写题解。
A - Petr and a calendar
给出月份和该月第一天的星期，不考虑闰年，问日历有多少列。
#include <cstdio>
using namespace std;
const int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main()
{
int m, d, c = 0;
scanf("%d %d", &m, &d);
int r = day[m];
if (d != 1) {
++c;
r -= 8-d;
}
c += (r+6)/7;
printf("%d\n", c);
return 0;
}B - Frodo and pillows
n张床，m个枕头，要求每张床上至少一个枕头，相邻两张床枕头数目之差的绝对值不超过1，最大化第k张床上的枕头数。（1≤n≤m≤10^9, 1≤k≤n）
这道题花了好一会儿。
这个数据范围DP不现实，考虑贪心，可能要二分。
先把每张床上放一个枕头以简化问题。如果第k张床上放了h个枕头，则第(k+d)、(k-d)张床上至少放(h-d)个枕头，而且这是可以做到的。让枕头构成以k为塔尖的金字塔形状是最优的，如果还有剩余的枕头，在合法的前提下随意放便是。让我们一层一层构建这个金字塔。两个指针l、r是塔底，让l左移、r右移。两者都无法移动，则退出，将答案加上剩下的枕头数/n向下取整。最后这一步很关键。先前是公差为1或2的等差数列求和，循环次数是
官方的解答是二分，用贪心验证。所需枕头数左右两边分别算。设k离一边的距离为y，按y和(h-1)的大小关系列式计算即可。当时往这方面想过，却没想到左右两边分开算，觉得分类讨论得好麻烦......
评论区发现不少人和我的思路相同，一些人也曾卡在l=1且r=n的情况下。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
ll n, m, k;
cin >> n >> m >> k;
ll l = k, r = k, ans = 1;
m -= n;
while (l != 1 || r != n) {
if (r-l+1 > m) {
cout << ans << endl;
return 0;
}
m -= r-l+1;
++ans;
l = max(l-1, 1LL);
r = min(r+1, n);
}
ans += m/n;
cout << ans << endl;
return 0;
}C - Pavel and barbecue
n个烤肉串在火盆上排成一列，给一个排列p和0-1序列{bi}，每秒钟把位置i的烤肉串挪到位置pi，如果bi=1，则翻转烤肉串。排列p和序列b共要修改多少处，才能使足够长的时间后，每个烤肉串以正反两种形态遍历了所有位置？修改后需保证p仍是排列。（1≤n≤2*10^5）
先考虑怎样使每个烤肉串遍历所有位置。排列能被分解为循环。一个循环内的烤肉不能到另一个循环中，所以，数一数循环的个数m，若m<1，则ans+=m。
仅当有奇数个1，烤肉转一圈回来改变了正反，从而两次经过某一位置是一正一反的。若b有偶数个1，则ans+=1。
理解题意花了好一会儿......
#include <cstdio>
using namespace std;
const int MAX_N = 2*1e5;
int p[MAX_N+1];
bool vis[MAX_N+1];
int main()
{
int n, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &p[i]);
int cnt = 0;
for (int i = 1; i <= n; ++i) {
int b;
scanf("%d", &b);
cnt += b;
}
if (!(cnt&1))
++ans;
int c = 0;
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
++c;
int j = i;
while (!vis[j]) {
vis[j] = true;
j = p[j];
}
}
}
if (c > 1)
ans += c;
printf("%d\n", ans);
return 0;
}D - Travel Card
三种票：一次20元，90分钟50元，1440分钟120元。一次1分钟。按严格递增的顺序给出时刻ti，求前i次最小花费和前(i-1)次最小花费之差。1≤消费次数n≤105，0≤ti≤109。
设前i次最小花费为f[i]，DP方程容易列出来。如果有单调性，可以用二分查找或two-pointer优化转移。直观上单调性是有的，岂有消费(i+1)次比消费i次还便宜的道理？
保留方案，但第(i+1)次不去，这样也是合法的，由最优性知f[i]≤f[i+1]。
当时没有想通，犹豫了一会儿，还剩1分钟时写完了代码，却有bug。主要是定义意识不够。f[i]只考虑前i次，这个问题有最优子结构，所以这样是正确的。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 1e5;
int t[MAX_N], f[MAX_N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", &t[i]);
f[0] = 20;
puts("20");
for (int i = 1; i < n; ++i) {
int j1 = lower_bound(t, t+i, t[i]-89) - t - 1, j2 = lower_bound(t, t+i, t[i]-1439) - t - 1;
f[i] = f[i-1] + 20;
f[i] = min(f[i], (j1 >= 0 ? f[j1] : 0) + 50);
f[i] = min(f[i], (j2 >= 0 ? f[j2] : 0) + 120);
printf("%d\n", f[i]-f[i-1]);
}
return 0;
}E - Nikita and stack
栈有两个操作：push(x)和pop()，对空栈pop()不会有任何改变。m个操作，编号1,2,...,m后打乱顺序给出。对于给出的前i个操作，输出按编号从小到大执行这些操作后栈顶的数，空栈输出-1。（1≤m≤10^5）
本想维护执行前i个操作后的栈，难以实施。联想到判定括号匹配的方法，考虑括号序列，入栈左括号，出栈右括号。左括号+1，右括号-1，求个前缀和，则待求的为最靠右的前缀和与i的相等的右括号的位置。这个限制有点复杂啊......让我们改求后缀和，则待求的为最靠右的后缀和为1的位置。看起来能用线段树之类的维护。先是直接存储后缀和为1的位置，写了两行发现合并的时候知道左子区间后缀和为1的位置在哪儿并没有什么用。没有做到Think twice, code once。瞥了一眼官方题解，发现官方题解也是这个思路，并说用线段树维护。
这个问题的结构似乎可以在线段树上二分。往左还是往右，取决于什么呢？如果右子区间存在后缀和为1的位置，自然得往右走。考虑后缀和的最大值即可。这个量也很好合并。修改是单点修改。注意，如果往左子区间走，查询的后缀和需减去右子区间和。
#include <cstdio>
#include <algorithm>
#define ALL 1, 1, n
using namespace std;
const int MAX_N = 1e5;
int x[MAX_N+1];
struct Segment_tree {
int sum[MAX_N*4], mx[MAX_N*4];
void up(int o)
{
int lc = o*2, rc = o*2+1;
sum[o] = sum[lc] + sum[rc];
mx[o] = max(mx[rc], mx[lc] + sum[rc]);
}
void modify(int p, int v, int o, int l, int r)
{
if (l == r) {
sum[o] = mx[o] = v;
return;
}
int m = (l+r)/2;
if (p <= m) modify(p, v, o*2, l, m);
else modify(p, v, o*2+1, m+1, r);
up(o);
}
int query(int v, int o, int l, int r)
{
if (mx[o] < v) return -1;
if (l == r)
return l;
int m = (l+r)/2, lc = o*2, rc = o*2+1;
return mx[rc] >= v ? query(v, rc, m+1, r) : query(v-sum[rc], lc, l, m);
}
} T;
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int p, t;
scanf("%d %d", &p, &t);
if (t) {
scanf("%d", &x[p]);
T.modify(p, 1, ALL);
} else
T.modify(p, -1, ALL);
int q = T.query(1, ALL);
printf("%d\n", q == -1 ? -1 : x[q]);
}
return 0;
}F - Bacterial Melee
n群细菌排成一列，每一群的种类用一个小写英文字母表示。一群可以进攻相邻的另一群，被攻击者的种类变为攻击者的种类，也可以选择不进攻。求n群细菌种类的方案数模(10^9+7)。（1≤n≤5000）
试图直接DP，却发现不能只考虑一个子串。让我们来找找性质。
对于样例babb，有以下结果： > aaaa aaab aabb abbb baaa baab babb bbaa bbab bbba bbbb
没有abab、baba或abaa。这启发我们，所有可到达的局面与原始情况相比，每种字符的相对顺序不变，可以缺失。用官方解答中的描述，定义comp(s)为把s中连续相同字符压缩成一个得到的新串，如comp(aaabbca)=abca，s可变换到t当且仅当comp(t)是comp(s)的子序列。
接下来就有两种思路了。一是针对comp(s)进行DP，再乘上一个组合数。二是直接搞：
设原串为s，变换到t，设f[i][j]为t的后缀i，t[i]=s[j]的方案数。定义pos(i, c)为s的后缀i中第一个字符c出现的位置，未出现赋为-1，则
pos可以预处理。时间复杂度f[i][j+1]进行转移，时间复杂度降至
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
const int MAX_N = 5000, SIGMA_SIZE = 26;
int pos[MAX_N][SIGMA_SIZE], f[MAX_N][MAX_N];
char s[MAX_N+1];
int main()
{
int n;
scanf("%d %s", &n, s);
for (int i = 0; i < n; ++i)
s[i] -= 'a';
fill_n(pos[n-1], SIGMA_SIZE, -1);
pos[n-1][s[n-1]] = n-1;
for (int i = n-2; i >= 0; --i) {
copy(pos[i+1], pos[i+1]+SIGMA_SIZE, pos[i]);
pos[i][s[i]] = i;
}
fill_n(f[n-1], n, 1);
for (int i = n-2; i >= 0; --i) {
f[i][n-1] = f[i+1][n-1];
for (int j = n-2; j >= 0; --j)
f[i][j] = ((ll)f[i][j+1] - (pos[j+1][s[j]] >= 0 ? f[i+1][pos[j+1][s[j]]] : 0) + f[i+1][j] + MOD) % MOD;
}
int ans = 0;
for (int j = 0; j < SIGMA_SIZE; ++j)
ans = (ans + f[0][pos[0][j]]) % MOD;
printf("%d\n", ans);
return 0;
}