啊！放寒假啦！

为了保持博客活着，也保持自己计算机水平不至于掉得太厉害，隔三差五回来划划水。

这次随便找了一场最近的Codeforces Div.2做一做题知道自己Div.1做不来了。讲道理，才过了半年多Div.2都变得这么简单了？

Codeforces 1099A Snowball

题目大意: 一个数 $w$ 从格子 $h$ 走到格子 $0$ ，每到达一个格子 $i$ 首先w += i。然后有两个格子 $d_1$ 和 $d_2$ ，在这两个格子分别w = max(w-u1,0)和w = max(w-u2,0) 。 $1 \le h \le 100, 1 \le d_1,d_2 \le h, d_1 \ne d_2$ 。

按照题意模拟就好了。复杂度 $O(h)$ 。

#include <bits/stdc++.h>
using namespace std;

#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int w,h,u1,d1,u2,d2; 
int main()
{
    w = rf(); h = rf(); u1 = rf(); d1 = rf(); u2 = rf(); d2 = rf();
    d2 > d1 ? u1^=u2^=u1^=u2,d1^=d2^=d1^=d2 : 0;
    for(; h >= d1; w += h--); w = max(w-u1,0);
    for(; h >= d2; w += h--); w = max(w-u2,0);
    for(; h; w += h--); printf("%d\n",w); return 0;
}

当然这是三段等差数列求和，可以 $O(1)$ 。

#include <bits/stdc++.h>
using namespace std;

#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
#define SUM(l,r) ((r-l+1)*(l+r)>>1) 
int w,h,u1,d1,u2,d2; 
int main()
{
    w = rf(); h = rf(); u1 = rf(); d1 = rf(); u2 = rf(); d2 = rf();
    d2 > d1 ? u1^=u2^=u1^=u2,d1^=d2^=d1^=d2 : 0;
    w = max(w+SUM(d1,h)-u1,0); w = max(w+SUM(d2,d1-1)-u2,0);
    w += SUM(0,d2-1); printf("%d\n",w); return 0;
}

由于原题范围太小，这个 $O(1)$ 居然没有 $O(h)$ 跑得快。

我居然没有完全忘掉我那诡异的码风

Codeforces 1099B Squares and Segments

题目大意: 将 $n$ 个正方形格子组合成一个平面图形，输出最小化的 $(水平投影长度+数值投影长度)$ 。 $1 \le n \le 10^9$ 。

根据均值不等式，水平投影投影长度和竖直投影长度应该尽可能接近。那么假设用了总长度为 $L$ ，如果 $L$ 是偶数，那么一定是 $\frac{L}{2} \times \frac{L}{2}$ 格子数最多；如果 $L$ 是奇数，那么一定是 $\frac{L}{2} \times (\frac{L}{2}-1)$ 格子数最多。

所以对 $n$ 开根然后讨论一下奇偶性就行了: 答案是 $2\lceil\sqrt n\rceil$ 或者 $2\lceil\sqrt n\rceil-1$ 。 $O(1)$ ，当然，你也可以认为开根是 $O(\log\log n)$ 。

#include <bits/stdc++.h>
using namespace std;

#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int main(){int n = rf(), l = ceil(sqrt(n)); printf("%d\n",(l<<1)-(l*(l-1ll)>=n)); return 0;}

Codeforces 1099C Postcard

题目大意: 给定一个长度为 $n$ 的可能带有小写英文字母、?、*的字符串。每个?可能删除其前面的一个字符，或者什么也不做；每个*可能删除其前面一个字符，或将前面一个字符复制任意若干次，或者什么也不做。操作后删除?和*。求是否能构造一个长度为 $k$ 的字符串并给出一个方案。 $n,k \le 200$ ，保证每个?和*前面一定是小写英文字母。

就是个分类讨论:

如果?和*全部用来删除都不够显然不行；

如果没有*那么只要 $k \gt n$ 一定不行；

如果 $k \le n$ ，选 $n-k$ 个?或*删掉就行了；

如果 $k \gt n$ 且有*，那么将某个*前面的字符复制 $k-n$ 次就行了。

$O(n+k)​$ 。

#include <bits/stdc++.h>
using namespace std;
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
string S, T; int n, m, k, a, b;
int main()
{
    cin >> S >> k; n = S.length(); a = count(S.begin(),S.end(),'?'); b = count(S.begin(),S.end(),'*');
    m = n-a-b; if(k<m-a-b || (!b&&k>m)) return !printf("Impossible\n");
    if(k <= m){for(rint i = 0; i < n; i++) if(m>k&&!isalpha(S[i+1])) i++, m--; else if(isalpha(S[i])) T += S[i];}
    else{for(rint i = 0, j = k-m; i < n; i++) if(S[i]=='*') for(; j-->0; T+=T.back()); else if(isalpha(S[i])) T += S[i];}
    cout << T << endl; return 0;
}

这真的在送。

Codeforces 1099D Sum in the tree

题目大意: 给定一棵 $n$ 个点的树，每个点有非负权值 $a_i$ ，所有奇数层的点告诉你这个点到根的路径的权值和 $s_i$ 。构造一组 $a_i$ 满足上述条件且 $\sum a_i$ 最小。 $2 \le n \le 10^5$ 。

怎么感觉是个经典题的弱弱弱弱化版啊。只需要考虑偶数层点就好了，每个点一定要大于等于父亲，同理小于等于最小的儿子，在这个范围内可以自由选，那么贪心: 叶子节点越小越好，等与父亲，那么这个点 $a = 0$ ；其他节点越大越好，因为这些节点儿子数 $\ge 1$ ，那么这个点 $a$ 多 $1$ ，下面每个儿子都可以少 $1$ 。

树上递推一下并注意判断一下有没有解就行了。 $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define INF 0x3f3f3f3f
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int fa[MAXN+5], s[MAXN+5], m[MAXN+5], n; long long w;
int main()
{
    n = rf(); for(rint i = 2; i <= n; fa[i++] = rf()); memset(m+1,0x3f,n<<2); generate(s+1,s+n+1,rf);
    for(rint i = 1; i <= n; ~s[i]?m[fa[i]]=min(m[fa[i]],s[i]):0, i++); for(rint i = n; i; i--) if(s[i]<0) s[i] = m[i]<INF?m[i]:s[fa[i]];
    for(rint i = 1; i <= n; i++) if(s[i]<s[fa[i]]) return !printf("-1\n"); else w += s[i]-s[fa[i]]; printf("%I64d\n",w); return 0;
}

Codeforces 1099E Nice table

题目大意: 给定一个 $n \times m$ 的表格，每个格子只含有AGCT四个字符中的一个，修改尽可能少的格子使得每个 $2 \times 2$ 格子里的四个字符都不一样。 $2 \le n,m, n \times m \le 3 \times 10^5$ 。

第一个需要动脑子的题。

第一反应状压DP插头DP个鬼，一看数据范围就凉了。

不过注意到 $2 \times 2$ 这个限制是非常严苛的，可能可行方案不会很多，开始观察可行解的样子。

经过一番逻辑分析不难发现，只要第一行全确定了，那么整张棋盘似乎就确定了。

比如说:

假如第一行是这样的，那么第二行前两个只能是CT或者TC，但是TC的话第三个格子就没法填了，所以整个第二行只能这样:

按照同样的逻辑可以推第三行:

然后神奇的事情就出现了。第三行总是和第一行相等，那么同理可得奇数行都相等，偶数行都相等。

我们只要考虑前两行怎么填就行了。第一个 $2 \times 2$ 格子随便填，填完以后就相当于一个分组，上例中奇数列都是AC和CA二选一，偶数列都是GT和TG二选一。同一列里选哪个对左右两列没有影响，选那个影响最小的就可以了。所以枚举第一个 $2 \times 2$ 格子怎么填，后面贪心即可。

但注意我前面说的是:

经过一番逻辑分析不难发现，只要第一行全确定了，那么整张棋盘似乎就确定了。

似乎！

在上例中，如果第一行是ACACA呢？这样后面就没法确定了，但是这时候把棋盘转 $90°$ 就会发现和之前是一样的。所以将棋盘翻转再做一遍就行了。

这题居然一开始WA了一次: 我原来以为next_permutation在最后一个排列执行的时候只会返回false，原来它不仅返回false而且还把排列变成第一个排列。所以我已开始翻转棋盘用的是prev_permutation，后来发现两次都是next_permutation。奇怪了我搞了这么长时间OI居然第一次意识到。

后来又TLE了一次，因为我构造答案的时候每次都重开了一个 $3 \times 10^5$ 的vector，太慢了。改完就好了。复杂度 $O(4!nm)$ ，显然实际上是 $O(C_4^2nm)$ 。

#include <bits/stdc++.h>
using namespace std;
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
char T[5] = "ACGT"; vector<string> A, O, R; vector<char> v[2]; int n, m, w, ans, t[2]; bool f, ansf;
inline void Trans(vector<string> &A){O.resize(m); for(rint i = 0, j; i < m; i++) for(O[i].resize(n), j = 0; j < n; O[i][j] = A[j][i], j++); A = O; O.clear(); n ^= m ^= n ^= m;}
inline int Diff(string &s, vector<char> v){int res = 0; for(rint i = 0; i < m; res += s[i]!=v[i&1], i++); return res;}
inline void Color(string &s, vector<char> v){for(rint i = 0; i < m; s[i] = v[i&1], i++);}
inline void Solve()
{
    for(rint i = w = 0, j = 0; i < n; i++, j ^= 2)
    {
        v[0] = {T[j],T[j|1]}; v[1] = {T[j|1],T[j]};
        t[0] = Diff(A[i],v[0]); t[1] = Diff(A[i],v[1]);
        w += min(t[0],t[1]); Color(O[i],v[t[0]>t[1]]);
    }
    if(w < ans) R = O, ansf = f, ans = w;
}
int main()
{
    n = rf(); m = rf(); ans = n*m; A.resize(n); for(rint i = 0; i < n; cin >> A[i], i++);
    O.resize(n); for(rint i = 0; i < n; O[i].resize(m), i++); do{Solve();}while(next_permutation(T,T+4),next_permutation(T,T+4)); Trans(A); f = 1;
    O.resize(n); for(rint i = 0; i < n; O[i].resize(m), i++); do{Solve();}while(next_permutation(T,T+4),next_permutation(T,T+4)); if(ansf) Trans(R);
    for(auto &s:R) cout << s << endl; return 0;
}

上述代码中用while里面两次next_permutation就是为了把 $4!$ 优化为 $A_4^2$ ，不过 $C_4^2$ 就懒得做了。

Codeforces 1099F Cookies

题目大意: 给定一棵 $n$ 个点的树，其中 $i$ 号点上有 $x_i$ 个价格为 $t_i$ 的物品，从 $i$ 的父亲到达 $i$ 的路费是 $l_i$ 。你从根节点开始向下移动到某个点再返回(你自己决定怎么走)，目的是在总花费不超过 $T$ 的前提下买到尽可能多的物品(你自己觉得买哪些)。但在这个过程中，你的敌人会在你到达点 $i$ 之后割断一条 $i$ 到其儿子的边，目的是让你买到的物品尽可能少。求双方最优策略时你的物品数。 $2 \le n \le 10^5, 1 \le T \le 10^{18}, 1 \le t_i, x_i \le 10^6, 0 \le l_i \le 10^9$ 。

我居然会做这道题。只能说明这场Div.2有点简单？

仔细观察不难发现两个过程是独立的，先求出 $f[i]$ 表示到达点 $i$ 再回去时能买到的最多物品(因为路费总长是确定的，物品贪心选就行了)。如果 $f[i]$ 有了不就是个次大值树上递推么。怎么求 $f[i]$ 呢？

这不是裸的树上可持久化线段树二分么！

空间复杂度有点吓人，用离线代替可持久化不就好了。

于是只需要DFS一遍，在DFS的过程中用线段树维护从根到当前点的路径的物品形成的一个优先队列(就是线段树维护桶排的桶)，然后在线段树上二分求出物品数即可。显然可以树状数组上二分，欢迎大家访问我的树状数组黑科技讲义。

复杂度瓶颈在线段树。 $O(n \log(\max \lbrace t_i \rbrace))$ 。

#include <bits/stdc++.h>
using namespace std;
#define R 1048576
#define MAXN 100000
#define ll long long
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define mid (lef+rig>>1)
#define rint register int
inline ll rf(){ll r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
vector<int> e[MAXN+5]; ll c[(R<<2)+5], s[(R<<2)+5], f[MAXN+5], T, Ans; int x[MAXN+5], t[MAXN+5], fa[MAXN+5], l[MAXN+5], n;
#define PS(p) (c[p] = c[lc(p)]+c[rc(p)], s[p] = s[lc(p)]+s[rc(p)])
void ED(int p, int lef, int rig, int i, int v){lef^rig?i<=mid?ED(lc(p),lef,mid,i,v):ED(rc(p),mid+1,rig,i,v),PS(p):(c[p]+=v,s[p]+=1ll*i*v);}
ll QU(int p, int lef, int rig, ll K){return s[p]>K?lef^rig?s[lc(p)]>K?QU(lc(p),lef,mid,K):QU(rc(p),mid+1,rig,K-s[lc(p)])+c[lc(p)]:K/lef:c[p];}
void DFS(int p, ll K)
{
    if((K-=l[p])<=0) return; ED(1,1,R,t[p],x[p]); f[p] = QU(1,1,R,K); ll w1 = 0, w2 = 0;
    for(auto v:e[p]) DFS(v,K), f[v]>w1?w2=w1,w1=f[v]:f[v]>w2?w2=f[v]:0; ED(1,1,R,t[p],-x[p]); f[p] = max(f[p],w2);
}
int main()
{
    n = rf(); T = rf(); generate(x+1,x+n+1,rf); generate(t+1,t+n+1,rf); for(rint i = 2; i <= n; e[fa[i]=rf()].push_back(i), l[i++] = rf()<<1);
    DFS(1,T); Ans = f[1]; for(auto v:e[1]) Ans = max(Ans,f[v]); printf("%I64d\n",Ans); return 0;
}

不要再吐槽我的码风了！！！

扫描二维码即可在手机上查看这篇文章，或者转发二维码来分享这篇文章: