标签 constructive algorithms 下的文章

网络流 1

09-08-2022
笔记
0 comment

「codeforces - 1592F2」Alice and Recoloring 2：妙妙题，显然只会操作 $(1, 1)$ 和 $(n, m)$ ，分别记作操作 1 和操作 2。我们希望单点操作，所以考虑差分（trick），只是这个题的差分非常高妙。如果你直接对前缀做二维差分会发现操作 1 要修改四个点，操作 2 修改一个点，而操作 1 花费 $1$ ，2 花费 $2$ ，所以每个点可能被操作最多两次（考虑一种情况，即 $(1, 1)$ ， $(1, 2)$ ， $(2, 1)$ 是黑点， $(2, 2)$ 是白点）。xf 教我了一种高庙的差分，具体是 $c_{i, j} = a_{i,j} \oplus a_{i+1, j} \oplus a_{i, j+1} \oplus a_{i+1, j+1}$ ，这样差分操作 2 就修改四个点，操作 1 修改一个点，这样一个点就最多修改一次了，建出二分图即可。

最后的做法是，假设我全部用操作 1，然后反悔看最多能用多少次操作 2（因为会用在 $(i, j)$ 上用操作 2 的情况是 $(i, j)$ ， $(n, j)$ ， $(i, m)$ 都是黑点）。

最后 $(n, m)$ 是需要特判的。

各种意义上我不会的题，膜拜 xf。

char s[600];
int n, m, a[600][600];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i=1; i<=n; ++i) {
        cin >> s;
        for (int j=1; j<=m; ++j) {
            a[i][j] = s[j-1] == 'B';
        }
    }
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=m; ++j) {
            a[i][j] ^= a[i+1][j]^a[i][j+1]^a[i+1][j+1];
        }
    }
    mf_graph<int> g(n+m+2);
    const int src = n+m+1, ter = n+m+2;
    for (int i=1; i<n; ++i) {
        for (int j=1; j<m; ++j) {
            if (a[i][j] && a[n][j] && a[i][m]) {
                g.add_edge(i, j+n, 1);
            }
        }
    }
    for (int i=1; i<=n; ++i) g.add_edge(src, i, 1);
    for (int i=1; i<=m; ++i) g.add_edge(i+n, ter, 1);
    int ret = -g.flow(src, ter);
    a[n][m] ^= (-ret)&1;
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=m; ++j) ret += a[i][j];
    }
    cout << ret << "\n";
}

「codeforces - 1146G」Zoning Restrictions：还行的题。想到把每个点拆成 $h+1$ 个点，如果你定义状态 $(i, j)$ 表示第 $i$ 个点的高度为 $j$ 会发现并不优秀，改成高度大于等于 $j$ 会好一点。关于这题怎么想到 min-cut 的，可以这样考虑（which is also a common trick）：全局最理想的答案是 $h^2 \times n$ ，然而不一定合法，我们以最小的代价去把这个答案调整到合法，得到的一定是最优的答案，因此是 min-cut。然而这道题我们不会这样去想，这只是一些题的思路。对于这个题我们的想法是把所有的贡献取负，这样就成了最小值（）

这里涉及另一个思维上的 trick：最小割的源汇有什么意义？划分出的两个点集有什么意义？在这一题中我们不妨将点集 $S$ 中的事件称为「成立」， $T$ 中的事件称为「不成立」，这样就赋予了最小割意义。

这里给出构造网络的方案： $\lang(i, j), (i, j+1), -j^2\rang$ ， $\lang (j, 0), x_i+1, \infty \rang, \forall j \in [l_i, r_i]$ ， $\lang i, t, c_i \rang$ 。

考察意义：割掉第一类边的意义即令房子 $i$ 的高度为 $j$ ，这对答案的贡献为 $j^2$ ，我们对答案取了负，所以贡献为 $-j^2$ ，如果第二类边有流量则意味着付罚金，因为一个区间只需要付一次罚金，所以我们不能直接割掉第二类边，而是通过第二类边使得割掉第三类边有意义（断掉连通性）。

当然流量不可能是负的，所以选择给 $-j^2$ 加上 $h^2$ ，因为 $n$ 幢房子代表的每一条链必然割且仅割一条一类边，所以最后给答案加上 $h^2 \times n$ 即可。

const int inf = 0x3f3f3f3f;
int n, h, m, id[60][60], qwq;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> h >> m;
    for (int i=1; i<=n; ++i) {
        for (int j=0; j<=h+1; ++j) id[i][j] = ++qwq;
    }
    mf_graph<int> g(qwq+m+2);
    const int src = qwq+m+1, ter = qwq+m+2;
    for (int i=1; i<=n; ++i) {
        g.add_edge(src, id[i][0], inf);
    }
    for (int i=1; i<=n; ++i) {
        for (int j=0; j<=h; ++j) g.add_edge(id[i][j], id[i][j+1], h*h-j*j);
    }
    for (int i=1,l,r,x,c; i<=m; ++i) {
        cin >> l >> r >> x >> c;
        g.add_edge(i+qwq, ter, c);
        for (int j=l; j<=r; ++j) {
            g.add_edge(id[j][x+1], i+qwq, inf);
        }
    }
    cout << h*h*n-g.flow(src, ter) << "\n";
}

「codeforces - 1061E」Politics：第一步是想到把 tree 1 放左部 tree 2 放右部。然后进入这个题的 key step：将对于子树的限制（被钦定的结点个数）转化为对一个结点的限制。这里大部分的做法是：对于一个有限制的结点 $x$ ，将 $k_x$ 减去 $\displaystyle \sum_{y \in \text{subtree}(x), y \neq x} k_y$ ，从而我们的工作就变成了在「所有 $x$ 的子树中的有限制的结点的上方中钦定一些结点」。于是给出这题的建图（费用流）： $\displaystyle \lang s, x \in\textbf V_1,k_x-\sum_{y \in \text{subtree}(x), y \neq x} k_y, 0\rang$ ， $\displaystyle \lang x \in\textbf V_2, t,k_x-\sum_{y \in \text{subtree}(x), y \neq x} k_y, 0\rang$ ， $\lang up_i, up'_i, 1, a_i\rang$ ，其中 v_1 v_2 是两棵树的点集，up_i 是编号 $i$ 在 tree 1 中对应的结点的最近有限制祖先，up'_i 同理。

理解一下，一、二类边都对应每个结点的限制，第三类边就是反过来考虑（我们之前是对祖先 $x$ 考虑，要在子树中所有有限制的结点的上面钦定结点），现在我们对一个点 $x$ 考虑它对最近有限制祖先的贡献。如果钦定了编号 $i$ ，则会对答案造成 $a_i$ 的贡献，占据 up_i 和 up'_i 的空余可钦定数。

mcf_graph<int, int> g;
int src, ter, qwq, qaq;
int n, rtx, rty, q1, q2, a[600], bstx[600], bsty[600], upx[600], upy[600], parx[600], pary[600];
bsi<int> adjx[600], adjy[600];
int dfsx(int x, int pa, int t) {
    parx[x] = pa;
    if (bstx[x]) {
        t = x;
    }
    upx[x] = t;
    int sum = 0;
    for (auto y : adjx[x]) {
        if (y != pa) {
            sum += dfsx(y, x, t);
        }
    }
    if (bstx[x]) {
        if (bstx[x] < sum) fucked_up();
        qwq += bstx[x]-sum;
        g.add_edge(src, x, bstx[x]-sum, 0);
        return bstx[x];
    }
    return sum;
}
int dfsy(int x, int pa, int t) {
    pary[x] = pa;
    if (bsty[x]) {
        t = x;
    }
    upy[x] = t;
    int sum = 0;
    for (auto y : adjy[x]) {
        if (y != pa) {
            sum += dfsy(y, x, t);
        }
    }
    if (bsty[x]) {
        if (bsty[x] < sum) fucked_up();
        qaq += bsty[x]-sum;
        g.add_edge(x+n, ter, bsty[x]-sum, 0);
        return bsty[x];
    }
    return sum;
}
int getx(int x, int pa) {
    int res = 0;
    for (auto y : adjx[x]) {
        if (y != pa) res += getx(y, x);
    }
    if (bstx[x]) {
        return bstx[x];
    }
    return res;
}
int gety(int x, int pa) {
    int res = 0;
    for (auto y : adjy[x]) {
        if (y != pa) res += gety(y, x);
    }
    if (bsty[x]) {
        return bsty[x];
    }
    return res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> rtx >> rty;
    for (int i=1; i<=n; ++i) {
        cin >> a[i];
    }
    for (int i=1,x,y; i<n; ++i) {
        cin >> x >> y;
        adjx[x] += y, adjx[y] += x;
    }
    for (int i=1,x,y; i<n; ++i) {
        cin >> x >> y;
        adjy[x] += y, adjy[y] += x;
    }
    cin >> q1;
    for (int i=0,x; i<q1; ++i) {
        cin >> x >> bstx[x];
    }
    cin >> q2;
    for (int i=0,x; i<q2; ++i) {
        cin >> x >> bsty[x];
    }
    g = mcf_graph<int, int>(n*2+2);
    src = n*2+1, ter = n*2+2;
    dfsx(rtx, 0, 0), dfsy(rty, 0, 0);
    if (qwq != qaq) fucked_up();
    for (int i=1; i<=n; ++i) {
        if (upx[i] && upy[i]) {
            g.add_edge(upx[i], upy[i]+n, 1, -a[i]);
        }
    }
    auto [X, Y] = g.flow(src, ter);
    if (X != qwq) fucked_up();
    cout << -Y << "\n";
}

Nhk R1 Editorial

02-01-2022
笔记
0 comment

前言

这场比赛的锅貌似有点多…在准备的时候就已经推迟过三次，在这里为对各位比赛时造成的困扰抱歉。这是出题组第一次放比赛，欢迎批评指正。

主要问题在于 C 的数据造水了，hack 数据造反了于是没有 hack 到。D 的数据也不强。再次感到抱歉，并且努力做出改正。

最后重拾一下出比赛的初心以及发表一些 mozheng & Chuni 言论：罚金一百万元（不是），以及为自己的 Welcome to NHK 做一个 Sunny Side 式的收尾，或者称之为小结。总之都没差啦……虽然只是举个例子，但我们要告诉你的，就是这样的故事。

Oops!

A

给出两种构造方式：

考虑 $d$ 的每一位，如果当前位为 $0$ ，则不对答案产生影响；如果当前位为 $1$ ，又因为 $1\text{ xor }1\text{ xor }0=0,1\text{ or }1\text{ or }0=1$ ，所以把 $a,b,c$ 其中两个按位或上 $2^i$ 即可。
$\begin{cases}a=d\\b=\text{lowbit}(d)\\c=d\text{ xor }\text{lowbit}(d)\end{cases}$

当然这两种方式并无什么不同。无解的情况是 $d=2^n$ 。

#include<bits/stdc++.h>
int ans[3],d;
signed main() {
    scanf("%d",&d);
    if((d&-d)==d)    return puts("-1"),0;
    for(int now=0; d; d^=d&-d)    ans[now]|=d&-d,ans[(now+=1)%=3]|=d&-d;
    printf("%d %d %d\n",ans[0],ans[1],ans[2]);
    return 0;
}

#include<bits/stdc++.h>
int d;
signed main() {
    scanf("%d",&d);
    if((d&-d)==d)    return puts("-1"),0;
    printf("%d %d %d\n",d,(d&-d),d-(d&-d));
    return 0;
}

B

首先 $a_1=x_1$ ，考虑第二位，因为保证有解，所以 $x_2\mid x_1$ ，同理可得 $\forall i\in(1,n],x_i\mid x_{i-1}$ ，可以预见数据中最多有 $\log$ 个非 $1$ 数，于是不断往上推即可。

#include<bits/stdc++.h>
int n,x,pre,now,vis[2000100];
signed main() {
    scanf("%d\n%d",&n,&x);
    vis[pre=now=x]=1;
    printf("%d ",x);
    for(int i=1; i<n; ++i) {
        scanf("%d",&x);
        if(pre!=x)    pre=now=x;
        else    while(vis[now])    now+=pre;
        vis[now]=1;
        printf("%d ",now);
    }
    return 0;
}

C

首先我们有个 $\mathcal {O}(nm)$ 的暴力遍历做法，读者很容易想到这样遍历了太多冗余的点。

于是很自然地想到将一个块缩成一个点。具体的，对于每一列，我们将障碍物隔开的一列点看成一个点，这样的店最多有 $2k$ 个。

然后 dp 即可， $dp_i=[(\sum_{j=1}^idp_j)>0]$ 。

然后要注意一个块能否转移到另一个块的判断条件有细节：并不是看两个块是联通，而是定义 $mx_i$ 为能到达第 $i$ 个块的最低点（贪心），看从 $mx_j$ 起是否能到达 $mx_i$ ，再更新 $mx_i$ 。

当然好像有更简便的做法，余不会。

同时存在更优的做法，为了代码的简便起见并没有作为 std，欢迎分享。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
#define LL long long
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
const int MAXN = 5005, MAXM = 1e7 + 5;
vector <int> v[MAXM], cx;
map <int, bool> vis;
map <int, int> lst;
struct Point {
    int X, Y, Y_;
}arr[MAXN];
int n, m, k, tot, mx, mn[MAXN];
int pre[MAXM];
bool dp[MAXN];
bool check(int x, int y) {
    if(arr[x].X == arr[y].X - 1) {
        if(arr[x].Y_ < arr[y].Y) return 0;
        if(arr[x].Y > arr[y].Y_) return 0;
        if(max(arr[y].Y, mn[x]) >= arr[y].Y && max(arr[y].Y, mn[x]) <= arr[y].Y_) {
            mn[y] = min(mn[y], max(arr[y].Y, mn[x])); return 1;
        }
        return 0;
    }
    if(arr[x].Y > arr[y].Y_) return 0;
    if(max(arr[y].Y, mn[x]) >= arr[y].Y && max(arr[y].Y, mn[x]) <= arr[y].Y_) {
        mn[y] = min(mn[y], max(arr[y].Y, mn[x])); return 1;
    }
    return  0;
}
int main() {
    int x, y;
    scanf("%d%d%d", &n, &m, &k); memset(mn, 0x3f, sizeof(mn));
    for(int i = 1; i <= k; i ++) {
        scanf("%d%d", &x, &y); v[x].push_back(y); cx.push_back(x); mx = max(mx, x);
    }
    sort(cx.begin(), cx.end());
    int Lst = 0;
    for(auto i : cx) {
        if(vis[i]) continue;
        pre[i] = 1;
        lst[i] = Lst; Lst = i; sort(v[i].begin(), v[i].end()); vis[i] = 1;
        int las = 0;
        for(auto j : v[i]) {
            if(j == las) { las ++; continue; }
            tot ++; arr[tot].X = i; arr[tot].Y = las; arr[tot].Y_ = j - 1; las = j + 1;
        }
        if(las <= m) tot ++, arr[tot].X = i, arr[tot].Y = las, arr[tot].Y_ = m;
    }
    for(int i = 1; i <= 10000000; i ++) pre[i] += pre[i - 1];
//    for(int i = 1; i <= tot; i ++) {
//        printf("%d %d %d\n", arr[i].X, arr[i].Y, arr[i].Y_);
//    }
    if(!tot) { printf("Yes"); return 0; }
    if(vis[0]) {
        if(arr[1].Y != 0) { printf("No"); return 0; }
        dp[1] = 1; mn[1] = 0;
    }
    else {
        for(int i = 1; i <= tot; i ++) if(arr[i].X == arr[1].X) dp[i] = 1, mn[i] = arr[i].Y, dp[i] = 1;
    }
    for(int i = 1; i <= tot; i ++) {
        for(int j = 1; j < i; j ++) {
            if(arr[j].X == arr[i].X) continue;
            if(((arr[j].X + 1 < arr[i].X && pre[arr[i].X - 1] - pre[arr[j].X] == 0) || arr[j].X + 1 == arr[i].X) && arr[j].X == lst[arr[i].X] && check(j, i)) {
                dp[i] |= dp[j];
            }
        }
    }
    if(vis[n]) {
        if(arr[tot].Y_ != m) { printf("No"); return 0; }
        if(dp[tot]) printf("Yes");
        else printf("No");
    }
    else {
        bool ans = 0;
        for(int i = 1; i <= tot; i ++) if(arr[i].X == mx) ans |= dp[i];
        if(ans) printf("Yes");
        else printf("No");
    }
    return 0;
}

D

你考虑维护 $n$ 个单调队列。第 $i$ 个单调队列的数满足： $\sum_{d=1}^ia_dc_d$ ，其中 $c_i$ 一定为正数。

每次我们取 $n$ 个单调队列的队头最小值 $r$ ，设其在第 $i$ 个队列，那么我们将 $a_d+r$ 放入第 $d$ 个队列中。（ $i<d\le n$ ）

可以证明，由于 $a$ 数组为正数，这样队列一定是单调的。

一直这样做 $k$ 次，取 $r_k$ 即可。时间复杂度： $\mathcal {O}(nk)$ 。数据可以（？）把带 $\mathrm {log}$ 做法卡掉。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <ctime>
#include <queue>
#define LL long long
using namespace std;
const int MAXN = 85;
queue <LL> que[MAXN];
int n, k, a[MAXN], num;
LL minn;
int main() {
    scanf("%d%d", &n, &k); k --;
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    que[0].push(0);
    for(int i = 1; i <= k + 1; i ++) {
        minn = 9e18;
        for(int j = 0; j <= n; j ++) if(!que[j].empty() && que[j].front() < minn) minn = que[j].front(), num = j;
        while(que[0].size()) que[0].pop();
        que[num].pop();
        for(int j = num; j <= n; j ++) que[j].push(minn + a[j]);
    }
    printf("%lld", minn);
    return 0;
}

E

$f_i(\Delta)$ 表示第 $v_i$ 这个点在坐标加 $\Delta$ 时距离自己最近的 $c$ 点的距离。那么这个画出来就是一条折线，由若干条斜率为 $1$ 或 $-1$ 的直线拼接而成。再设 $F(\Delta)=\sum\limits_{i=1}^{b}f_i(\Delta)$ ，也就是取 $\Delta$ 时，题面中要求的距离之和。

在折线的拐点上研究，设 $\textbf{G}_i$ 为 $f_i(\Delta)$ 图像上所有拐点的集合，再设 $\textbf{G}'=\bigcup\limits_{i=1}^{b}\textbf{G}_i$ 。w.l.o.g，提出两个数 $a,b,s.t.(a,f(a)),(b,f(b))\in\textbf{G}'$ ，且不存在 $c,s.t.(c,f(c))\in\textbf{G}',c-a>0,b-c>0$ ，即 $a,b$ 是紧相邻的。换而言之，就是把所有 $v$ 点的图像拼在一起，取两个相邻的 $a,b$ 拐点来研究。

现在我们可以求出 $F(a)$ ，以及拐点后的直线斜率，从而可以求出 $F(b)$ 。以此，扫一遍就行了。

我们举个例子来画图：

这个就是 $f(\Delta)$ 的图像（我把多个 $i$ 的拼在一起的）。现在假设我们取的 $a,b$ 两点就是图中的蓝点（当然， $a,b$ 之间没有其他拐点，因为 $a,b$ 是紧相邻的），这意味着我确定了 $a$ 点处的 $\Delta$ ，那么就可以算出 $F(a)$ 了，如此往后面扫，每次取最大值就行了。

/*
每个点处在每个区间的值是不相同的，但是是一个折线。
当它在[vi,vi+1]中间时，如果靠vi更近，则为与vi的距离，否则为与vi+1的距离。
那我们现在知道了每个点移动多少之后的答案。
这条折线有的地方是斜率-1，有的地方是斜率为+1.
那么我们把所有的折线加在一起。一共有ab个点，我们维护一下每一段的斜率，然后求下最大值就好…… 

1 1 1
0
0

4
10
3
0 0 1 1 3 3 3 3 4 4
0 1 4

13 2 9
2 9
0 1 2 3 5 6 7 11 12
*/ 
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<long long> pri;
const long long INF=1e18;
long long l,n,m,a[1010],b[1010],delup,deldown,sols[4000010],cur,ans,s,mxs;
double mxp;
struct line
{
    long long l,r,num;
}lin[2000010];
long long nothingtimes;
void donothing()
{
    ++nothingtimes;
}
long long ABS(long long x)
{
    return x>=0?x:-x;
}
long long lint;
int main()
{
    scanf("%lld %lld %lld",&l,&n,&m);
    for(long long i=1;i<=n;++i)    scanf("%lld",&a[i]);
    for(long long i=1;i<=m;++i)    scanf("%lld",&b[i]);
    deldown=0;
    delup=l-b[m];
    deldown<<=1;
    delup<<=1;
    for(long long i=1;i<=n;++i)//第i个目标点 
    {
        for(long long j=1;j<m;++j)//位于第j个与第j+1个点之间 距离都*2了，因为中点可能不在格点上。 
        {
            //靠左
            long long l=a[i]*2-(b[j]+b[j+1]),r=(a[i]-b[j])*2;
            if(l>delup||r<deldown||l>=r)    donothing();
            else
            {
                if(l<deldown)    l=deldown;
                if(r>delup)    r=delup;
                if(l>=r)    donothing();
                else
                {
                    lin[++lint].l=l;
                    lin[lint].r=r;
                    lin[lint].num=-1;
                }
            }
            //靠右 
            l=a[i]*2-b[j+1]*2,r=a[i]*2-(b[j]+b[j+1]);
            if(l>delup||r<deldown||l>=r)    donothing();
            else
            {
                if(l<deldown)    l=deldown;
                if(r>delup)    r=delup;
                if(l>=r)    donothing();
                else
                {
                    lin[++lint].l=l;
                    lin[lint].r=r;
                    lin[lint].num=1;
                }
            }
        }
        //在第1个前面
        long long l=a[i]*2-b[1]*2,r=delup;
        if(l>delup||r<deldown||l>=r)    donothing();
        else
        {
            if(l<deldown)    l=deldown;
            if(r>delup)    r=delup;
            if(l>=r)    donothing();
            else
            {
                lin[++lint].l=l;
                lin[lint].r=r;
                lin[lint].num=1;
            }
        }
        //在第n个后面
        l=deldown,r=a[i]*2-b[m]*2;
        if(l>delup||r<deldown||l>=r)    donothing();
        else
        {
            if(l<deldown)    l=deldown;
            if(r>delup)    r=delup;
            if(l>=r)    donothing();
            else
            {
                lin[++lint].l=l;
                lin[lint].r=r;
                lin[lint].num=-1;
            }
        }
    }
    for(long long i=1;i<=lint;++i)
    {
        pri.push_back(lin[i].l);
        pri.push_back(lin[i].r);
    }
    sort(pri.begin(),pri.end());
    pri.erase(unique(pri.begin(),pri.end()),pri.end());
    s=pri.size();
    for(long long i=1;i<=lint;++i)
    {
        lin[i].l=lower_bound(pri.begin(),pri.end(),lin[i].l)-pri.begin()+1;
        lin[i].r=lower_bound(pri.begin(),pri.end(),lin[i].r)-pri.begin()+1;
    }
    for(long long i=1;i<=lint;++i)
    {
        sols[lin[i].l]+=lin[i].num;
        sols[lin[i].r]-=lin[i].num;
    }
    mxp=-1;
    mxs=-1;
    for(long long i=1;i<=n;++i)
    {
        long long nowpos=a[i]*2+deldown,minn=INF;
        for(long long j=1;j<=m;++j)    minn=min(minn,ABS(nowpos-b[j]*2));
        cur+=minn;
    }
    if(cur<=l*2)
    {
        mxp=deldown;
        mxs=cur;
    }
    for(long long i=1;i<=s;++i)    sols[i]+=sols[i-1];
    for(long long i=1;i<s;++i)
    {
        if(cur>l*2)
        {
            long long tmp=cur+sols[i]*(pri[i]-pri[i-1]);
            if(tmp<=l*2)
            {
                mxs=l*2;
                mxp=(l*2-cur)*1.0/sols[i]+pri[i-1];
            }
            cur=tmp;
        }
        else
        {
            long long tmp=cur+sols[i]*(pri[i]-pri[i-1]);
            if(tmp<=l*2)
            {
                if(tmp>=mxs)
                {
                    mxp=pri[i];
                    mxs=tmp;
                }
            }
            else
            {
                mxp=(l*2-cur)*1.0/sols[i]+pri[i-1];
                mxs=l*2;
            }
            cur=tmp;
        }
    }
    if(mxp==-1)    printf("NO\n");
    else    printf("%.6lf\n",mxp/2);
    return 0;
}

F

首先我们定义 $sec(i)$ 表示包含 $0 \sim i-1$ 的最小区间。因为添加新的元素不会使区间变小，所以 $sec(i) \subseteq sec(i + 1)$ ，因此对于每个包含 $sec(i)$ 的区间，它肯定是包含 $sec(1\sim i)$ 。若这个区间并不包含 $sec(i + 1)$ ，则也可以得到这个区间不包含 $sec(i + 1 \sim n)$ 所以，这个区间的贡献应该是 $i$ 。

将这 $i$ 的贡献分别分到 $sec(1 \sim i)$ 中，我们的问题就变成了，每一次添加元素后， $\large\sum \limits_{j= 1}^{i}$ 包含 $sec(j)$ 的区间个数。考虑一次插入后答案的变化，同时规定 $sec(0) = \varnothing$ ：

一次插入的数 $x$ 一定满足 $\exists y \in [0, i - 1], x \in sec(y), x \notin sec(y + 1)$ 。而这个 $y$ 是唯一的（这个应该很好想吧）。

所以，我们可以预处理出每一个 $x$ 对应的 $y$ 。当插入 $x$ 的时候，相当于在所有 $sec(1 \sim y)$ 的左（或右）边增加了 $1$ 个点。

此时增加的区间数量即是 $sec(1 \sim y)$ 右（或左）边的点个数之和（注意，对于一个点是可以重复计算的），这里只需要用两个线段树分别记录 $sec(i)$ 左右当前各有多少点了。

Bonus：Solve it in $O(n)$ ！

#include <cstdio>
#include <algorithm>
using namespace std;

#define MAXN 1000000
#define L(p) (p << 1)
#define R(p) ((p << 1) | 1) 
#define make_mid(l,r) int mid = (l + r) >> 1

int s[MAXN + 5];
pair <int, int> si[MAXN + 5];
int sl[MAXN + 5], sr[MAXN + 5];
struct node {
    long long v;
    long long sign;
    int h, t;
}s1[(MAXN << 4) + 5], s2[(MAXN << 4) + 5];

void build (int p, int l, int r) {
    s1[p].h = l;
    s1[p].t = r;
    s1[p].sign = 0;
    s1[p].v = 0;
    s2[p].h = l;
    s2[p].t = r;
    s2[p].sign = 0;
    s2[p].v = 0;
    if (l == r) {
        return ;
    }
    make_mid (l, r);
    build (L(p), l, mid);
    build (R(p), mid + 1, r);
}
void downloadl (int p) {
    if (s1[p].sign && s1[p].h < s1[p].t) {
        s1[L(p)].sign += s1[p].sign;
        s1[R(p)].sign += s1[p].sign;
        s1[L(p)].v += (s1[L(p)].t - s1[L(p)].h + 1) * s1[p].sign;
        s1[R(p)].v += (s1[R(p)].t - s1[R(p)].h + 1) * s1[p].sign;
        s1[p].sign = 0;
    }
}
void downloadr (int p) {
    if (s2[p].sign && s2[p].h < s2[p].t) {
        s2[L(p)].sign += s2[p].sign;
        s2[R(p)].sign += s2[p].sign;
        s2[L(p)].v += (s2[L(p)].t - s2[L(p)].h + 1) * s2[p].sign;
        s2[R(p)].v += (s2[R(p)].t - s2[R(p)].h + 1) * s2[p].sign;
        s2[p].sign = 0;
    }
}
void changel (int p, int l, int r, long long x) {
    downloadl (p);
    if (s1[p].h >= l && s1[p].t <= r) {
        s1[p].v += x * (s1[p].t - s1[p].h + 1);
        s1[p].sign += x;
        
        return ;
    }
    make_mid (s1[p].h, s1[p].t);
    if (l <= mid) {
        changel (L(p), l, r, x);
    }
    if (r > mid) {
        changel (R(p), l, r, x);
    }
    s1[p].v = s1[L(p)].v + s1[R(p)].v;
}
void changer (int p, int l, int r, long long x) {
    downloadr (p);
    if (s2[p].h >= l && s2[p].t <= r) {
        s2[p].v += x * (s2[p].t - s2[p].h + 1);
        s2[p].sign += x;
        
        return ;
    }
    make_mid (s2[p].h, s2[p].t);
    if (l <= mid) {
        changer (L(p), l, r, x);
    }
    if (r > mid) {
        changer (R(p), l, r, x);
    }
    s2[p].v = s2[L(p)].v + s2[R(p)].v;
}
long long Suml (int p, int l, int r) {
    downloadl (p);
    if (s1[p].h >= l && s1[p].t <= r) {
        return s1[p].v;
    }
    
    long long sum = 0;
    
    make_mid (s1[p].h, s1[p].t);
    if (l <= mid) {
        sum += Suml (L(p), l, r);
    }
    if (r > mid) {
        sum += Suml (R(p), l, r);
    }
    
    return sum;
}
long long Sumr (int p, int l, int r) {
    downloadr (p);
    if (s2[p].h >= l && s2[p].t <= r) {
        return s2[p].v;
    }
    
    long long sum = 0;
    
    make_mid (s2[p].h, s2[p].t);
    if (l <= mid) {
        sum += Sumr (L(p), l, r);
    }
    if (r > mid) {
        sum += Sumr (R(p), l, r);
    }
    
    return sum;
}

int main () {
    int n;
    
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++) {
        int x;
        
        scanf ("%d", &x);
        s[x + 1] = i;//处理出i插入到的是哪个位置
    }
    build (1, 1, n);//初始两棵线段树
    //初始 sec(i)
    //----------------------------------------------
    si[1].first = s[1];
    si[1].second = s[1];
    for (int i = 2; i <= n; i ++) {
        si[i].first = min (si[i - 1].first, s[i]);
        si[i].second = max (si[i - 1].second, s[i]);
    }
    //----------------------------------------------
    //处理出 i 所对应的 y 且处理出到底是在 sec(y) 的左还是右
    for (int i = n - 1; i >= 1; i --) {
        for (int j = si[i + 1].first; j < si[i].first; j ++) {
            sr[j] = i;
        }
        for (int j = si[i + 1].second; j > si[i].second; j --) {
            sl[j] = i;
        }
    }
    
    long long ans = 0;//保存每次插入的答案
    long long Ans = 0;//保存最终答案
    
    for (int i = 1; i <= n; i ++) {
        if (sl[s[i]]) {
            ans += Suml (1, 1, sl[s[i]]);
            changer (1, 1, sl[s[i]], 1);
        }
        if (sr[s[i]]) {
            ans += Sumr (1, 1, sr[s[i]]);
            changel (1, 1, sr[s[i]], 1);
        }
        ans ++;//添加了 i 以后会多出 sec() ， 此处将其加入答案中
        changel (1, i, i, 1);
        changer (1, i, i, 1);
        Ans += ans;
    }
    printf ("%lld", Ans);
}

For some reason...

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
template<typename T=int> T read() {
    T x=0; char IO=getchar(); bool f=0;
    while(IO<'0' || IO>'9')    f|=IO=='-',IO=getchar();
    while(IO>='0' && IO<='9')    x=x*10+(IO&15),IO=getchar();
    return f?-x:x;
}
int n, a[1000100], mn[1000100], mx[1000100], pos1[1000100], pos2[1000100];
ll ans, _ans;
struct segment_tree {
    ll sum[4000100], tag[4000100];
    void up(const int now) {sum[now] = sum[now<<1]+sum[now<<1|1];}
    void down(const int now, int l, int r) {
        if(!tag[now]) return;
        int mid = (l+r)>>1;
        tag[now<<1] += tag[now],tag[now<<1|1] += tag[now];
        sum[now<<1] += (mid-l+1)*tag[now],sum[now<<1|1] += (r-mid)*tag[now];
        tag[now] = 0;
    }
    void go(int x, int y, ll k, const int now=1, int l=1, int r=n) {
        if(l > y || r < x) return;
        if(l >= x && r <= y) return tag[now] += k,sum[now] += (r-l+1)*k,void();
        int mid = (l+r)>>1; down(now, l, r);
        go(x, y, k, now<<1, l, mid),go(x, y, k, now<<1|1, mid+1, r);
        up(now);
    }
    ll ask(int x, int y, const int now=1, int l=1, int r=n) {
        if(l > y || r < x) return 0;
        if(l >= x && r <= y) return sum[now];
        int mid = (l+r)>>1; down(now, l, r);
        return ask(x, y, now<<1, l, mid)+ask(x, y, now<<1|1, mid+1, r);
    }
} t1, t2;
signed main() {
    freopen("sh.in", "r", stdin);
    freopen("sh.out", "w", stdout);
    n = read();
    for(int i = 1; i <= n; ++i) a[read()+1] = i;
    mn[1] = mx[1] = a[1];
    for(int i = 2; i <= n; ++i) mn[i] = min(mn[i-1], a[i]),mx[i] = max(mx[i-1], a[i]);
    for(int i = n-1; i; --i) {
        for(int j = mx[i+1]; j > mx[i]; --j) pos1[j] = i;
        for(int j = mn[i+1]; j < mn[i]; ++j) pos2[j] = i;
    }
    for(int i = 1; i <= n; ++i) {
        if(pos1[a[i]]) ans += t1.ask(1, pos1[a[i]]),t2.go(1, pos1[a[i]], 1);
        if(pos2[a[i]]) ans += t2.ask(1, pos2[a[i]]),t1.go(1, pos2[a[i]], 1);
        ans++,_ans += ans;
        t1.go(i, i, 1),t2.go(i, i, 1);
    }
    cout << _ans << "\n";
    return 0;
}

「loj - 3022」「cqoi 2017」老 C 的方块

10-12-2021
笔记
0 comment

link。

good题，考虑像 国家集训队 - happiness 一样在棋盘上搞染色，我毛张 @shadowice1987 的图给你看啊

你像这样奇数层以 red -> blue -> green -> yellow 为一个周期，偶数层 yellow -> green -> blue -> red，就会发现给出的形状都包括恰好四种颜色和一条黑线。那现在就好搞了，就是要在每个连通块里面删除至少一种颜色的全部方块（包括黑线），有这样几种选择：全绿 / 全黄 / 全黑线（即破环红或蓝中的一个），像图右侧一样建图就好了。

#include<bits/stdc++.h>
using namespace std;
enum Color { red=1,blue,yellow,green };
const long long INF=0x3f3f3f3f;
template<class Kap> struct Net {
    const long long n;
    struct Arc {
        long long to, rev; Kap cap;
    };
    vector<long long> lev,iter;
    vector<vector<Arc>> e;
    std::queue<long long> q;
    Net(long long n):n(n),e(n),lev(n),iter(n) {}
    void add(long long one,long long ano,Kap cap) {
        // printf("  %lld  %lld  %lld\n",one,ano,cap);
        e[one-1].push_back((Arc){ano-1,(long long)(e[ano-1].size())+(one==ano),cap});
        e[ano-1].push_back((Arc){one-1,(long long)(e[one-1].size())-1,0});
    }
    Kap solve(long long s,long long t) { return solve(s-1,t-1,std::numeric_limits<Kap>::max()); }
    bool Getlayer(long long s,long long t) {
        lev.assign(n,0);
        while(q.size())    q.pop();
        lev[s]=1;
        q.emplace(s);
        while(q.size()) {
            long long now=q.front();
            q.pop();
            if(now==t)    break;
            for(long long i=0; i<(long long)(e[now].size()); ++i) {
                long long y=e[now][i].to; Kap cap=e[now][i].cap;
                if(!lev[y] && cap)    lev[y]=lev[now]+1,q.emplace(y);
            }
        }
        return lev[t];
    };
    Kap Augment(long long now,Kap up,long long t) {
        if(now==t)    return up;
        Kap rlow=0;
        for(long long& i=iter[now]; i<(long long)(e[now].size()); ++i) {
            if(!up)    break;
            long long y=e[now][i].to; Kap& cap=e[now][i].cap;
            if(lev[y]==lev[now]+1 && cap) {
                Kap f=Augment(y,min(up,cap),t);
                if(f<=0)    continue;
                cap-=f; e[y][e[now][i].rev].cap+=f; up-=f; rlow+=f;
            }
        }
        if(!rlow)    lev[now]=n+1;
        return rlow;
    };
    Kap solve(long long s,long long t,const Kap inf) {
        lev.assign(n,0); iter.assign(n,0); Kap res=0,tmp;
        while (Getlayer(s,t)) {
            iter.assign(n, 0);
            if((tmp=Augment(s,inf,t)))    res+=tmp;
            else    break;
        }
        return res;
    }
};
long long r,c,n,celx[100100],cely[100100],celw[100100],S,T,co[100100];
map<long long,long long> mp;
bool valid(long long x,long long y) { return x>=1 && x<=r && y>=1 && y<=c; }
long long getid(long long x,long long y) { return 1ll*(x-1)*c+y; }
signed main() {
    scanf("%lld %lld %lld",&c,&r,&n);
    for(long long i=1; i<=n; ++i)    scanf("%lld %lld %lld",&cely[i],&celx[i],&celw[i]),mp[getid(celx[i],cely[i])]=i;
    // for(long long i=1; i<=n; ++i)    printf("  ---- %lld %lld %lld\n",celx[i],cely[i],celw[i]);
    for(long long i=1; i<=n; ++i) {
        if(cely[i]%4==0)    co[i]=(celx[i]&1)?3:1;
        else if(cely[i]%4==1)    co[i]=(celx[i]&1)?1:3;
        else if(cely[i]%4==2)    co[i]=(celx[i]&1)?2:4;
        else    co[i]=(celx[i]&1)?4:2;
    }
    // char tmp[5][10]={"tmp","red","blue","yellow","green"};
    // for(long long i=1; i<=n; ++i)    puts(tmp[co[i]]);
    // for(long long i=1; i<=n; ++i)    printf(" %lld",co[i]);
    // puts("");
    // 1 for red, 2 for blue, 3 for yellow, 4 for green
    Net<long long> G(n+2); S=n+1; T=n+2;
    for(long long i=1; i<=n; ++i) {
        if(co[i]==yellow /*yellow*/) {
            G.add(S,i,celw[i]);
            if(valid(celx[i],cely[i]-1)) {
                long long j=mp[getid(celx[i],cely[i]-1)];
                if(j && co[j]==red)    G.add(i,j,INF);
            }
            if(valid(celx[i],cely[i]+1)) {
                long long j=mp[getid(celx[i],cely[i]+1)];
                if(j && co[j]==red)    G.add(i,j,INF);
            }
            // printf(" --- %lld %lld\n",celx[i],cely[i]);
            if(valid(celx[i]-1,cely[i])) {
                long long j=mp[getid(celx[i]-1,cely[i])];
                if(j && co[j]==red)    G.add(i,j,INF);
            }
            if(valid(celx[i]+1,cely[i])) {
                long long j=mp[getid(celx[i]+1,cely[i])];
                if(j && co[j]==red)    G.add(i,j,INF);
            }
        }
        else if(co[i]==green /*green*/) {
            G.add(i,T,celw[i]);
            if(valid(celx[i],cely[i]-1)) {
                long long j=mp[getid(celx[i],cely[i]-1)];
                if(j && co[j]==blue)    G.add(j,i,INF);
            }
            if(valid(celx[i],cely[i]+1)) {
                long long j=mp[getid(celx[i],cely[i]+1)];
                if(j && co[j]==blue)    G.add(j,i,INF);
            }
            if(valid(celx[i]+1,cely[i])) {
                long long j=mp[getid(celx[i]+1,cely[i])];
                if(j && co[j]==blue)    G.add(j,i,INF);
            }
            if(valid(celx[i]-1,cely[i])) {
                long long j=mp[getid(celx[i]-1,cely[i])];
                if(j && co[j]==blue)    G.add(j,i,INF);
            }
        }
        else if(co[i]==red) {
            if(valid(celx[i],cely[i]+1)) {
                long long j=mp[getid(celx[i],cely[i]+1)];
                // if(celx[i]==1 && cely[i]==1 && j)    printf("  --  %lld %lld %lld %lld %lld\n",celx[i],cely[i],celw[i],getid(celx[i],cely[i]),mp[getid(celx[i],cely[i])]);
                if(j && co[j]==blue)    G.add(i,j,min(celw[i],celw[j]));
            }
            if(valid(celx[i],cely[i]-1)) {
                long long j=mp[getid(celx[i],cely[i]-1)];
                // if(celx[i]==1 && cely[i]==1 && j)    printf("  --  %lld %lld %lld %lld %lld\n",celx[i],cely[i],celw[i],getid(celx[i],cely[i]),mp[getid(celx[i],cely[i])]);
                if(j && co[j]==blue)    G.add(i,j,min(celw[i],celw[j]));
            }
            if(valid(celx[i]+1,cely[i])) {
                long long j=mp[getid(celx[i]+1,cely[i])];
                // if(celx[i]==1 && cely[i]==1 && j)    printf("  --  %lld %lld %lld %lld %lld\n",celx[i],cely[i],celw[i],getid(celx[i],cely[i]),mp[getid(celx[i],cely[i])]);
                if(j && co[j]==blue)    G.add(i,j,min(celw[i],celw[j]));
            }
            if(valid(celx[i]-1,cely[i])) {
                long long j=mp[getid(celx[i]-1,cely[i])];
                // if(celx[i]==1 && cely[i]==1 && j)    printf("  --  %lld %lld %lld %lld %lld\n",celx[i],cely[i],celw[i],getid(celx[i],cely[i]),mp[getid(celx[i],cely[i])]);
                if(j && co[j]==blue)    G.add(i,j,min(celw[i],celw[j]));
            }
        }
    }
    printf("%lld\n",G.solve(S,T));
    return 0;
}

Solution -「SCOI 2016」萌萌哒

11-05-2021
笔记
0 comment

Description

Link.

给定一个长度为 $n$ 的数组让你填数，需要满足 $m$ 个形如 $([l_{1},r_{1}],[l_{2},r_{2}])$ 的要求，这两个区间填好后需要一样，问方案数。

Solution

Let us only consider one limit $([l_{1},r_{1}],[l_{2},r_{2}])$ , the number of ways is $10^{r-l+1}$ .
Connecting every $i\in[l_{1},r_{1}]$ and $j\in[l_{2},r_{2}]$ , we can construct a graph.
Counting the number of connected subgraphs, denoted as $x$ , the answer is $9\times10^{x-1}$ , and the complexity is $\mathcal{O}(n^{2}\alpha(n))$ .
Each interval could be splited into $\log_{2}r-l+1$ subintervals, so that we can solve this in $\mathcal{O}(n\log_{2}n\alpha(n))$ .

#include <bits/stdc++.h>
typedef long long ll;
#define sf(x) scanf("%d",&x)
#define ssf(x) scanf("%lld",&x)
struct DSU {
    int fa[100010];
    void init(int l) {
        std::iota(fa + 1, fa + l + 1, 1);
    }
    int find(int x) {
        return (x ^ fa[x]) ? fa[x] = find(fa[x]) : x;
    }
    void ins(int x, int y) {
        if (x ^ y)
            fa[x] = y;
    }
} dsu[20];
int n, m, opl0, opr0, opl1, opr1;
ll ans = 1;
int main() {
    sf(n), sf(m);

    for (int i = 0; i ^ 20; ++i)
        dsu[i].init(n);

    while (m-- > 0) {
        sf(opl0), sf(opr0), sf(opl1), sf(opr1);
        int cur0 = opl0, cur1 = opl1;

        for (int i = 19; ~i; --i) {
            if (cur0 + (1 << i) - 1 <= opr0) {
                dsu[i].ins(dsu[i].find(cur0), dsu[i].find(cur1));
                cur0 += (1 << i);
                cur1 += (1 << i);
            }
        }
    }

    for (int j = 19; j; --j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            dsu[j - 1].ins(dsu[j - 1].find(i), dsu[j - 1].find(dsu[j].find(i)));
            dsu[j - 1].ins(dsu[j - 1].find(i + (1 << (j - 1))), dsu[j - 1].find(dsu[j].find(i) + (1 << (j - 1))));
        }
    }

    for (int i = 1; i <= n; ++i)
        if (dsu[0].fa[i] == i)
            ans = ans * (ans == 1 ? 9 : 10) % 1000000007;

    printf("%lld\n", ans);
    return 0;
}

Solution Set -「CF 1520」

09-05-2021
笔记
0 comment

「CF 1520A」Do Not Be Distracted!

Link.

模拟。

#include<bits/stdc++.h>
char now;
char get_char(){char res=getchar();while(res<'A' || res>'Z')    res=getchar(); return res;}
bool vis[26];
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T-->0)
    {
        scanf("%d",&n);
        int ans=0;
        for(int i=1;i<=n;++i)
        {
            char cur=get_char();
            if(cur!=now)
            {
                now=cur;
                if(vis[cur-'A'])    ans=1;
            }
            vis[cur-'A']=1;
        }
        puts(ans?"NO":"YES");
        memset(vis,0,sizeof vis);
    }
    return 0;
}

「CF 1520B」Ordinary Numbers

Link.

按位考虑。

#include<bits/stdc++.h>
typedef long long ll;
int main()
{
    int T;
    scanf("%d",&T);
    while(T-->0)
    {
        ll ans=0,n;
        scanf("%lld",&n);
        for(ll pw=1;pw<=n;pw=pw*10+1)    for(int now=1;now<=9;++now)    if(pw*now<=n)    ++ans;
        printf("%lld\n",ans);
    }
    return 0;
}

「CF 1520C」Not Adjacent Matrix

Link.

用 flows 的 trick 来构造， $(i+j)$ 为奇先填，为偶后填。

#include<bits/stdc++.h>
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T-->0)
    {
        scanf("%d",&n);
        if(n==2)    puts("-1");
        else
        {
            int cur=0;
            static int ans[110][110];
            for(int i=1;i<=n;++i)    for(int j=1;j<=n;++j)    if((i+j)&1)    ans[i][j]=++cur;
            for(int i=1;i<=n;++i)    for(int j=1;j<=n;++j)    if((i+j)&1^1)    ans[i][j]=++cur;
            for(int i=1;i<=n;++i,puts(""))    for(int j=1;j<=n;++j)    printf("%d ",ans[i][j]);
        }
    }
    return 0;
}

「CF 1520D」Same Differences

Link.

式子移项。

#include<bits/stdc++.h>
typedef long long ll;
int a[200010],cnt[500010];
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T-->0)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i)    scanf("%d",&a[i]),a[i]-=i,a[i]+=200000,++cnt[a[i]];
        ll ans=0;
        for(int i=1;i<=n;++i)    ans+=cnt[a[i]]-1;
        printf("%lld\n",ans/2);
        for(int i=1;i<=n;++i)    --cnt[a[i]];
    }
    return 0;
}

「CF 1520E」Arranging The Sheep

Link.

所有牛往中间那头牛走。

#include<bits/stdc++.h>
typedef long long ll;
#define All(x) (x).begin(),(x).end()
int fuck[1000010];
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T-->0)
    {
        scanf("%d",&n);
        int tot=0;
        for(int i=1;i<=n;++i)
        {
            char now=getchar();
            while((now^    '.') && (now^'*'))    now=getchar();
            if(now=='*')    fuck[++tot]=i;
        }
        int mpos=int(std::ceil(tot/2.0));
        ll ans=0;
        for(int i=1;i<=tot;++i)    ans+=std::abs(fuck[i]-fuck[mpos]+mpos-i);
        printf("%lld\n",ans);
    }
    return 0;
}

「CF 1520F1」Guess the K-th Zero (Easy version)

Link.

二分维护答案区间，询问 $\log_{2}$ 次。

#include<bits/stdc++.h>
#define fl fflush(stdout)
int n,t,k;
int q(int l,int r){int res=0; printf("? %d %d\n",l,r); fl; scanf("%d",&res); return res;}
int main()
{
    scanf("%d %d",&n,&t);
    while(t--)
    {
        scanf("%d",&k);
        int l=1,r=n,ans=0;
        while(l<=r)
        {
            int mid=(l+r)>>1,tmp=mid-l+1-q(l,mid);
            if(tmp>=k)    r=mid-1,ans=mid;
            else    k-=tmp,l=mid+1;
        }
        printf("! %d\n",ans);
        fl;
    }
    return 0;
}

「CF 1520F2」Guess the K-th Zero (Hard version)

Link.

把二分记忆化下来，用 std::map 和 BIT 实现。

#include<bits/stdc++.h>
#define fl fflush(stdout)
int n,t,k;
struct FWT
{
    #define l(x) ((x)&-(x))
    int tr[200010];
    FWT(){memset(tr,0,sizeof tr);}
    void i(int x){for(;x<=n;x+=l(x))    ++tr[x];}
    int $(int x){int r=0; for(;x;x^=l(x))    r+=tr[x]; return r;}
    int f(int l,int r){return $(r)-$(l-1);}
}fw;
std::map<std::tuple<int,int>,int> mp;
int q(int l,int r){
    if(mp.find(std::tie(l,r))==mp.end())
    {
        int res=0;
        printf("? %d %d\n",l,r);
        fl;
        scanf("%d",&res);
        mp[std::tie(l,r)]=res;
        return res;
    }
    else    return mp[std::tie(l,r)]+fw.f(l,r);
}
int main()
{
    scanf("%d %d",&n,&t);
    while(t--)
    {
        scanf("%d",&k);
        int l=1,r=n,ans=0;
        while(l<=r)
        {
            int mid=(l+r)>>1,tmp=mid-l+1-q(l,mid);
            if(tmp>=k)    r=mid-1,ans=mid;
            else    k-=tmp,l=mid+1;
        }
        printf("! %d\n",ans);
        fl;
        fw.i(ans);
    }
    return 0;
}

「CF 1520G」To Go Or Not To Go?

Link.

广搜。

#include<bits/stdc++.h>
typedef long long ll;
#define sf(x) scanf("%d",&x)
#define ssf(x) scanf("%lld",&x)
const int wax[4]={1,-1,0,0},way[4]={0,0,1,-1};
int n,m;
ll w,dis0[2010][2010],dis1[2010][2010],a[2010][2010];
bool Inside(int x,int y){return !(x<1 || x>n || y<1 || y>m);}
void Compute_0()
{
    std::queue<std::tuple<int,int>> q;
    q.emplace(1,1);
    dis0[1][1]=1;
    while(!q.empty())
    {
        int nowx,nowy;
        std::tie(nowx,nowy)=q.front();
        q.pop();
        for(int k=0;k<4;++k)
        {
            int tox=nowx+wax[k],toy=nowy+way[k];
            if(Inside(tox,toy) && !dis0[tox][toy] && ~a[tox][toy])    dis0[tox][toy]=dis0[nowx][nowy]+1,q.emplace(tox,toy);
        }
    }
    for(int i=1;i<=n;++i)    for(int j=1;j<=m;++j)    --dis0[i][j];
}
void Compute_1()
{
    std::queue<std::tuple<int,int>> q;
    q.emplace(n,m);
    dis1[n][m]=1;
    while(!q.empty())
    {
        int nowx,nowy;
        std::tie(nowx,nowy)=q.front();
        q.pop();
        for(int k=0;k<4;++k)
        {
            int tox=nowx+wax[k],toy=nowy+way[k];
            if(Inside(tox,toy) && !dis1[tox][toy] && ~a[tox][toy])    dis1[tox][toy]=dis1[nowx][nowy]+1,q.emplace(tox,toy);
        }
    }
    for(int i=1;i<=n;++i)    for(int j=1;j<=m;++j)    --dis1[i][j];
}
int main()
{
    sf(n),sf(m),ssf(w);
    for(int i=1;i<=n;++i)    for(int j=1;j<=m;++j)    ssf(a[i][j]);
    Compute_0(),Compute_1();
    ll mxtmp=std::numeric_limits<ll>::max();
    ll ans=~dis0[n][m]?w*dis0[n][m]:mxtmp,ozd=mxtmp;
    for(int i=1;i<=n;++i)    for(int j=1;j<=m;++j)    if(~dis1[i][j] && a[i][j]>=1)    ozd=std::min(ozd,a[i][j]+w*dis1[i][j]);
    for(int i=1;i<=n;++i)    for(int j=1;j<=m;++j)    if(~dis0[i][j] && a[i][j]>=1 && ozd!=mxtmp)    ans=std::min(ans,w*dis0[i][j]+a[i][j]+ozd);
    if(ans==mxtmp)    puts("-1");
    else    printf("%lld\n",ans);
    return 0;
}