LibreOJ Round #6

A 花煎

这个题解法很好想,二分一下就行了。但是刚拿到题的时候想复杂了,没有从指数这里入手而是各种想着怎么大力解不等式,浪费了比较多时间。

实际上暴力 DP 就行了。我们暴力算一下用$i$个小球的时候最大的乘积就行了,代码就不贴了。

B 花团

嗯,刚看到题,线段树分治。好像有$35pts$,但是这个复杂度最低肯定要$O(VQ)$吧,如果带个$\log$感觉很不可过的样子。然后因为线段树分治没有写过多少次。而且这个 DP 数组下传感觉非常麻烦。于是索性写了个std::unordered_map当 DP 数组了,然后太慢了,就只跑过了春暴力分 QAQ。

以为这个题给出了删除物品的时间,所以是个假在线。我们依旧线段树分治,每次分治到一个区间时,如果是第一次访问到左端点而且左端点是一个修改操作,就暴力覆盖一下就好了。

复杂度$O(VQ\log Q)$

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cmax(a,b)        a = ((a) > (b) ? (a) : (b))
#define cmin(a,b)        a = ((a) < (b) ? (a) : (b))
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pii            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

const int MAXN = 15005;
const int oo = 0x3f3f3f3f;

int Q, T, V, ans[MAXN], d = 0;
struct Querys{
    int o, v, w, e;
}qry[MAXN];
bool vaild[MAXN];

namespace Seg{
    int f[21][MAXN];
    vector<pii> t[MAXN << 2];
    void Cov(int le, int ri, int k, int L, int R, pii o){
        if (L <= le && ri <= R) {
            t[k].push_back(o);
            return;
        }
        int mi = (le + ri) >> 1;
        if (L <= mi)        Cov(le, mi, k << 1, L, R, o);
        if (mi + 1 <= R)        Cov(mi + 1, ri, k << 1 | 1, L, R, o);
    }
    void Work(int le, int ri, int k, int dep){
        if (vaild[le]) {
            if (qry[le].o == 1) {
                qry[le].e -= d;
                qry[le].v -= d;
                qry[le].w -= d;
                Cov(1, Q, 1, le, qry[le].e, make_pair(qry[le].v, qry[le].w));
            }
            vaild[le] = 0;
        }
        memcpy(f[dep], f[dep - 1], sizeof(f[dep]));
        up (i, 0, SZ(t[k]) - 1) {
            int v = t[k][i].fi, w = t[k][i].se;
            down (j, V, v) if (f[dep][j - v] != -1)
                cmax(f[dep][j], f[dep][j - v] + w);
        }
        if (le == ri) {
            if (qry[le].o == 2) {
                qry[le].v -= d;
                if (f[dep][qry[le].v] == -1) {
                    ans[le] = -1;
                    d = 0;
                }else {
                    ans[le] = f[dep][qry[le].v];
                    d = T * (ans[le] ^ 1);
                }
            }
            return;
        }
        int mi = (le + ri) >> 1;
        Work(le, mi, k << 1, dep + 1);
        Work(mi + 1, ri, k << 1 | 1, dep + 1);
    }
}using namespace Seg;

namespace solution{
    void Prepare(){
        scanf("%d%d%d", &Q, &V, &T);
        up (i, 1, Q) vaild[i] = 1;
        up (i, 1, Q) {
            scanf("%d", &qry[i].o);
            if (qry[i].o == 1) scanf("%d%d%d", &qry[i].v, &qry[i].w, &qry[i].e);
            if (qry[i].o == 2) scanf("%d", &qry[i].v);
        }
    }
    void Solve(){
        f[0][0] = 0;
        up (i, 1, V) f[0][i] = -1;
        Work(1, Q, 1, 1);
        up (i, 1, Q) if (qry[i].o == 2) {
            printf("%d %d\n", ans[i] == -1 ? 0 : 1, ans[i] == -1 ? 0 : ans[i]);
        }
    }
}

int main(){
    using namespace solution;
    Prepare();
    Solve();
    return 0;
}

C 花火

刚看到题,大力踩了个结论,先写了个暴力交了上去。暴力分拿满了,也就是猜的结论对了。
然后考虑怎么优化,尝试根据那个结论转换了一下模型。发现了一些单调性,然后加了一些剪枝多过了一档部分分。然后再往下就没有了。

这个题的解法其实和我前几天写的那个「World Final 2017」Money for Nothing是一样的。用 Claris 说的一个小套路。

首先我们发现,如果没有可以交换两个不相邻物品的话,那么答案就是逆序对数。因为每次的交换能且仅能消掉一个逆序对。然后我们接着考虑,如果交换两个不相邻,那么消掉的就是这中间的逆序对。所以暴力的做法就是枚举交换哪两个逆序对,然后统计一下$[l, r]$内有多少个数在$[a[r], a[l]]$的权值范围之间。

然后我们考虑把这个问题映射到二维平面上,考虑每个左上的点,如果存在$i < j, a[j] < a[i]$ 那么无论如何$j$都不可能在最优的决策里。因为选$i$一定比$j$优。对于右端点同理。然后我们 yy 一下,可以发现这个对于每个左端点的最优决策一定是单调的。然后就可以采用上面说的哪种方法来做了。

复杂度:$O(N\log ^ 2N)$,卡了一上午常数卡不过去,放弃梦想。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define up(i,j,n)        for (register int i = j; i <= n; ++i)
#define down(i,j,n)    for (register int i = j; i >= n; --i)
#define cmax(a,b)        a = ((a) > (b) ? (a) : (b))
#define cmin(a,b)        a = ((a) < (b) ? (a) : (b))
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pii            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

const int MAXN = 3e5 + 5;
const int oo = 0x3f3f3f3f;

inline int read(){
    char ch = getchar(); int x = 0, f = 1;
    while (ch > '9' || ch < '0') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

int N, a[MAXN], num[MAXN], top = 0, lower[MAXN], lowc, upper[MAXN], uppc, mx = 0;
bool vaild[MAXN];
ll ans = 0;

namespace Seg{
    struct tree {
        int son[2], siz;
    }t[MAXN * 20];
    int root[MAXN], cnt = 0;
    int NewNode(int s0, int s1, int siz){
        cnt++;
        t[cnt].son[0] = s0; t[cnt].son[1] = s1; t[cnt].siz = siz;
        return cnt;
    }
    void Build(int le, int ri, int &k, int o){
        k = NewNode(t[k].son[0], t[k].son[1], t[k].siz + 1);
        if (le == ri) return;
        int mi = (le + ri) >> 1;
        if (o <= mi)     Build(le, mi, t[k].son[0], o);
        else            Build(mi + 1, ri, t[k].son[1], o);
    }
    int Query(int le, int ri, int k, int L, int R){
        if (L <= le && ri <= R) return t[k].siz;
        int mi = (le + ri) >> 1, sum = 0;
        if (L <= mi)    sum += Query(le, mi, t[k].son[0], L, R);
        if (mi + 1 <= R)    sum += Query(mi + 1, ri, t[k].son[1], L, R);
        return sum;
    }
    int calc(int le, int ri, int L, int R){
        int sum = Query(1, N, root[ri], L, R) - Query(1, N, root[le - 1], L, R);
        return sum;
    }
}using namespace Seg;

namespace solution{
    void Work(int le, int ri, int dl, int dr){
        int mi = (le + ri) >> 1, cur = -1, dm;
        up (i, dl, dr) if (lower[i] >= upper[mi] && a[lower[i]] < a[upper[mi]]){
            int tmp = calc(upper[mi], lower[i], a[lower[i]], a[upper[mi]]) - 2;
            if (tmp > cur) {
                cur = tmp;
                dm = i;
            }
        }        
        cmax(mx, cur);
        if (le <= mi - 1) Work(le, mi - 1, dl, dm);
        if (mi + 1 <= ri)    Work(mi + 1, ri, dm, dr);
    }
    void Prepare(){
        N = read();
        up (i, 1, N) a[i] = read();
        up (i, 1, N) num[++top] = a[i];
        sort(num + 1, num + top + 1);
        up (i, 1, N) a[i] = lower_bound(num + 1, num + top + 1, a[i]) - num;
        up (i, 1, N) {
            root[i] = root[i - 1];
            Build(1, N, root[i], a[i]);
        }
        up (i, 2, N) ans += calc(1, i - 1, a[i], N);
        up (i, 1, N - 1) if (calc(i + 1, N, 1, a[i]))
            vaild[i] = 1;
    }
    void Solve(){
        int cur = 0;
        up (i, 1, N) if (a[i] > cur && vaild[i]) {
            cur = a[i];
            upper[++uppc] = i;
        }     
        cur = oo;
        down (i, N, 1) if (a[i] < cur) {
            cur = a[i];
            lower[++lowc] = i; 
        }
        reverse(lower + 1, lower + lowc + 1);
        Work(1, uppc, 1, lowc);
        printf("%lld\n", ans - (mx << 1 | 1) + 1);
    }
}

int main(){
    using namespace solution;
    Prepare();
    Solve();
    return 0;
}

D 花札

看题,嗯,博弈,关掉。

于是题都没有看完就关掉了。其实是一个还比较简单的题吧。我们发现这个实际上是在一个二分图上移棋子的模型,然后这个有个结论,一个人有必胜策略当且仅当他的棋子在所有最大匹配中。可以来简单证明一下:

首先,如果存在一个最大匹配,那个点不在最大匹配上。那么他要么不能移动棋子,就输了;要么就只能移动到一个最大匹配的点上,那么另一个人把他移动到他所匹配到的点上,这个时候这个点肯定也是不一定在最大匹配上的。这个时候就回到了上一步。那么一定必败。

而如果这个点在所有的最大匹配上。这个时候我们把点移动到它的匹配上,这个时候上一个点就不可以访问了,我们就把这个点视作删掉。这时这个点也就是之前说的不一定在最大匹配上的点了,于是可以沿用上面的证明。

证明完后,考虑怎么求关键点。可以直接暴力构造二分图,但是复杂度太高了,只有暴力分。下面直接说正解。我们先优化一下建图,对于每个颜色和点数建点,然后从每个点连向他们即可。然后对于每个点,如果他一定在最大匹配上,那么就是说如果看做最小割,他和$S$的边是一定要割掉的。这里可以参考我之前写的这道题「BZOJ-1791」最小割。对于一定在最小割中的边,需要满足的是首先这条边被割掉了,其次就是$s$一定要在$S$集中,而$t$一定不在$S$集中,而且在残余网络上存在$S\rightarrow s$的边,因为这个题里$s$就是$S$,所以只要保证$t$不在$S$集里就行了。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cmax(a,b)        a = ((a) > (b) ? (a) : (b))
#define cmin(a,b)        a = ((a) < (b) ? (a) : (b))
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pii            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

const int MAXN = 2e5 + 5;
const int oo = 0x3f3f3f3f;

int N, M, ID[MAXN][2], vc[MAXN], cc[MAXN], V, C, S, T, cnt = 0;
pii ali[MAXN], shi[MAXN];

namespace Maxflow{
    struct edge {
        int y, next, flow, rev;
    }e[MAXN << 4];
    int LINK[MAXN], cur[MAXN], len = 0, level[MAXN];
    deque<int> q;
    inline void ins(int x, int y, int flow, int rev){
        e[++len].next = LINK[x]; LINK[x] = len;
        e[len].y = y; e[len].flow = flow; e[len].rev = len + rev;
    }
    inline void Ins(int x, int y, int flow){
        ins(x, y, flow, 1);
        ins(y, x, 0, -1);
    }
    bool makelevel(){
        up (i, 1, cnt) level[i] = -1;
        q.push_back(S); level[S] = 0;
        while (!q.empty()) {
            int node = q.front(); q.pop_front();
            Auto(i, node) if (level[e[i].y] == -1 && e[i].flow) {
                level[e[i].y] = level[node] + 1;
                q.push_back(e[i].y);
            }
        }
        return level[T] != -1;
    }
    int addflow(int node, int flow){
        if (node == T) return flow;
        int maxflow = 0, d;
        for (int &i = cur[node]; i && maxflow < flow; i = e[i].next) if (level[e[i].y] == level[node] + 1 && e[i].flow)
            if (d = addflow(e[i].y, min(e[i].flow, flow - maxflow))) {
                maxflow += d;
                e[i].flow -= d;
                e[e[i].rev].flow += d;
            }
        if (!maxflow) level[node] = -1;
        return maxflow;
    }
    void Dinic(){
        while (makelevel()) {
            memcpy(cur + 1, LINK + 1, sizeof(int) * cnt);
            while(addflow(S, oo));
        }
    }
}using namespace Maxflow;

namespace solution{
    void Prepare(){
        scanf("%d%d", &V, &C);
        scanf("%d", &N);
        S = ++cnt; T = ++cnt;
        up (i, 1, N) scanf("%d%d", &ali[i].fi, &ali[i].se);
        scanf("%d", &M);
        up (i, 1, M) scanf("%d%d", &shi[i].fi, &shi[i].se);
        up (i, 1, N) ID[i][0] = ++cnt;
        up (i, 1, M) ID[i][1] = ++cnt;
        up (i, 1, V) vc[i] = ++cnt;
        up (i, 1, C) cc[i] = ++cnt;
        up (i, 1, N) {
            Ins(S, ID[i][0], 1);
            Ins(ID[i][0], vc[ali[i].fi], 1);
            Ins(ID[i][0], cc[ali[i].se], 1);
        }
        up (i, 1, M) {
            Ins(ID[i][1], T, 1);
            Ins(vc[shi[i].fi], ID[i][1], 1);
            Ins(cc[shi[i].se], ID[i][1], 1);
        }
    }
    void Solve(){
        Dinic();
        makelevel();
        up (i, 1, N) puts(level[ID[i][0]] == -1 ? "1" : "0");
    }
}

int main(){
    using namespace solution;
    Prepare();
    Solve();
    return 0;
}