2022-9-30总结

岛屿观测

原题 P3616 Fucking Forest Park

题目需要求露出水面的连通块个数，我们没法直接维护，考虑每个连通块挑出来一个代表点，选最左边或者最右边都可，这时我们就需要求它左边比水面低，它自己比水面高的石头的个数，你可以将其看成一个二维数点，但是有更简单的做法：把询问差分一下，用比水面高的石头的个数减去它左边和它都比水面高的石头的个数即可，这样就变成一维数点了，树状数组维护即可。

#include <bits/stdc++.h>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("patrick.in", "r", stdin);
        freopen("patrick.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

const int N = 5e5+10;

int lim;
struct bit_array {
    int a[N];
    #define lowbit(i) (i&-i)
    void add(int pos, int val)
    {
        for(pos++; pos <= lim; pos += lowbit(pos))
            a[pos] += val;
    }
    int query(int pos)
    {
        int ans = 0;
        for(pos++; pos >= 1; pos -= lowbit(pos))
            ans += a[pos];
        return ans;
    }
};

struct query {
    int opt, h, id;
};

int n, m;
int h[N];
query q[N];
bit_array bit1, bit2;

int main()
{
    cin >> n >> m; lim = 5e5+1;
    for(int i = 1; i <= n; i++)
    {
        cin >> h[i];
        bit1.add(h[i], 1);
        bit2.add(min(h[i-1], h[i]), 1);
    }
    
    char opt; int k, p;
    int lastans = 0;
    for(int i = 1; i <= m; i++)
    {
        cin >> opt;
        if(opt == 'Q')
        {
            cin >> k; k ^= lastans;
            int ans1 = n-bit1.query(k-1);
            int ans2 = n-bit2.query(k-1);
            lastans = ans1-ans2;
            cout << lastans << "\n";
        }
        else
        {
            cin >> p >> k;
            p ^= lastans;
            k ^= lastans;
            bit1.add(h[p], -1);
            bit2.add(min(h[p-1], h[p]), -1);
            bit2.add(min(h[p], h[p+1]), -1);
            h[p] = k;
            bit1.add(h[p], 1);
            bit2.add(min(h[p-1], h[p]), 1);
            bit2.add(min(h[p], h[p+1]), 1);
        }
    }
}

简单算术

可以直接暴力区间dp, 有 $50$ 分的好成绩。

也可以设计一个 $f(i,j)$ 表示第 $i$ 个数有 $j$ 个左括号未被匹配的最大值，转移很简单。但是状态数是 $n^2$ 级别的，不太行。

考虑拆括号的过程，我们可以发现 $3$ 层以上的括号的表达式都可以被两层以内代替，所以上面那个状态的状态数就直接变成 $n$ 级别的了，转移也是 $O(1)$ 的，可以通过。

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("arithmetic.in", "r", stdin);
        freopen("arithmetic.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

typedef long long ll;
const int N = 2e5+10;

int n;
int a[N];
ll f[N][3];

bool less0[N];
void input();
void solve();

int main()
{
    int t; cin >> t;
    while(t --> 0) solve();
}

void solve()
{
    input();
    f[0][0] = 0;
    f[0][1] = f[0][2] = -1e18;
    for(int i = 1; i <= n; i++)
    {
        if(less0[i])
        {
            f[i][0] = f[i-1][0]-a[i];
            f[i][1] = max({f[i-1][0], f[i-1][1], f[i-1][2]}) - a[i];
            f[i][2] = max(f[i-1][1], f[i-1][2]) + a[i];
        }
        else
        {
            f[i][0] = max({f[i-1][0], f[i-1][1], f[i-1][2]}) + a[i];
            f[i][1] = max(f[i-1][1], f[i-1][2]) - a[i];
            f[i][2] = f[i-1][2] + a[i];
        }
    }
    cout << max({f[n][0], f[n][1], f[n][2]}) << "\n";
}

void input()
{
    cin >> n;
    cin >> a[1];
    for(int i = 2; i <= n; i++)
    {
        char ch;
        cin >> ch >> a[i];
        less0[i] = (ch=='-');
    }
}

问卷调查

因为题目保证每个点的度数和为奇数，所以不存在无解的情况。

考虑一条 $x$ 到 $y$ 的链，如果这些边的权值都相等，我们可以让这些边的方向都相同，这样这一整条链可以简化为一条从 $x$ 到 $y$ 的边。

如果是一个权值相同的环，直接绕环一圈即可把整个环消掉。

如果没有边权为 $2$ 的边，这样消完之后每个点最多连出去一条边，而每个点的度数和都是奇数，所以剩下的边使得所有点构成了一组完美匹配，我们可以给这些边任意定向，然后还原出消边之前的方案即可。

如果有边权为 $2$ 的边的话，就相当于把某些点对连成了环，这时候环上的边一定是 $1$ 和 $2$ 交替的，我们可以按 $1, -2, -1, 2$ (正负表示方向)的方式将环上的点的权值控制在 $[-1,1]$ 之内。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+5;
const int M = 2e6+5;

int n, m, tot;
int pre[M];
int v[N][2], id[N][2];

bool rev[M], ans[M];
bool dir[N][2], vis[N];

inline void add_edge(int x, int y, int p, int w)
{
    if(id[x][w] && v[x][w] == y)
    {
        int q = id[x][w];
        pre[p] = pre[q] = 0;
        id[x][w] = id[y][w] = 0;
        ans[p] = 1, ans[q] = dir[y][w];
        return void();
    }
    bool flag = true;
    if(id[x][w])
    {
        flag = false;
        int q = id[x][w];
        id[x][w] = 0;
        pre[q] = tot;
        rev[q] = dir[x][w];
        x = v[x][w];
    }
    if(id[y][w])
    {
        flag = false;
        int q = id[y][w];
        id[y][w] = 0;
        pre[q] = tot;
        rev[q] = dir[y][w]^1;
        y = v[y][w];
    }
    v[x][w] = y, v[y][w] = x;
    dir[x][w] = 1, dir[y][w] = 0;
    if(flag)
        id[x][w] = id[y][w] = p;
    else
        pre[p] = id[x][w] = id[y][w] = tot++;
}

inline void solve(int st)
{
    vis[st] = true;
    for(int x = st, w = 0; id[x][w]; w ^= 1)
    {
        ans[id[x][w]] = dir[x][w];
        int y = v[x][w];
        if(vis[y]) return;
        vis[x = y] = true;
    }
    for(int x = st, w = 1; id[x][w]; w ^= 1)
    {
        ans[id[x][w]] = dir[x][w]^1;
        int y = v[x][w];
        vis[x = y] = true;
    }
}

int main()
{
    cin >> n >> m;
    tot = m+1;
    for(int i = 1; i <= m; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;
        add_edge(x+1, y+1, i, w-1);
    }
    for(int i = 1; i <= n; ++i)
        if(!vis[i]) solve(i);
    for(int i = tot-1; i >= 1; --i)
        if(pre[i]) ans[i] = ans[pre[i]]^rev[i];
    for(int i = 1; i <= m; ++i)
        putchar(ans[i] ? '0' : '1');
}