首页 > 其他分享 >CF1718D Permutation for Burenka【贪心】

CF1718D Permutation for Burenka【贪心】

时间:2022-09-21 20:12:50浏览次数:78  
标签:Burenka ch 匹配 int vr CF1718D Permutation 区间 define

传送门


显然,两个数列相似当且仅当它们的笛卡尔树结构相同。

那么排列 \(p\) 给出了 \(a\) 所对应的笛卡尔树形态,据此我们容易求出树上每个空位上数的取值范围 \([l_i,r_i]\)。当然如果已经填的数不合法那么一定无解,这个可以先判掉。

然后我们会发现这个也是充分的,因为如果两个位置都满足限制但是不符合笛卡尔树结构,那么它们肯定在同一个由空位组成的连通块内,瞎交换一下总能达到合法。由此我们可以得到判定 \(T = S \cup \{d\}\) 合法的充要条件:存在一组将 \(T\) 中所有元素 \(v\) 和所有区间 \([l_i,r_i]\) 两两匹配的方案,使得 \(v \in [l_p,r_p]\)(\(p\) 为 \(v\) 所匹配的区间)。

对确定的 \(T\),我们有如下贪心的判定方法:每次选择最小的未被匹配的 \(v\),将其与右端点最小的、包含 \(v\) 且未被匹配的区间匹配。其正确性显然。这等价于将所有区间按 \(r\) 从小到大排序,每次选择 \([l_i, r_i]\) 中最小的未被匹配的 \(v\) 并删去。若不存在这样的 \(v\) 则无解,我们称这个区间为不合法区间。

考虑对 \(S\) 做上述贪心,这时候肯定至少有一个区间不合法,我们先把它抓出来。设这个区间为 \([l_i,r_i]\),那么显然应该有 \(d \leq r_i\),这时候我们就得到了合法的 \(d\) 的一个取值上界。然后我们假装这个区间已经被匹配了并继续贪心,如果又找到了一个不合法区间,那么肯定就没救了。证明比较容易,这里就不写了。

同理,倒过来贪一遍可以得到 \(d\) 的取值下界,由此可知 \(d\) 的取值范围 \([L,R]\)。事实上这是充分的:

原问题是二分图完备匹配的形式,我们尝试使用 Hall 定理描述其有解性。对于这类点向区间连边的匹配问题,一个经典结论是存在完备匹配当且仅当完全包含于 \([l,r]\) 的区间数量不大于 \([l,r]\) 中的元素数量。

因为这个太经典了所以这里就不证了。算了还是简单证一下好了,我们考虑右部选的点集 \(S\),它是一些不交区间的并,进一步我们可以发现这些不交区间在左部的点集也是独立的,然后就只需要考虑一个子区间的情况了。

令 \(c_{l,r}\) 为完全包含于 \([l,r]\) 的区间数量,\(f_{l,r} = c_{l,r} - \sum_{v \in T}[l \leq v \land v \leq r]\)。显然如果存在 \(f_{l,r} > 1\) 那又没救了。

考虑 \(f_{l,r} = 1\) 的区间 \([l,r]\),完全包含于 \([l,r]\) 的区间中至少有一个没得匹配,所以贪心过程中枚举到 \(r\) 时必然会找到这个不合法区间,因此有 \(R \leq r\)。同理可证 \(L \geq l\)。因此往 \([L,R]\) 中塞一个点后所有 \(f_{l,r} = 1\) 的区间全都变成 \(0\) 了,即充分性得证。

于是只需要求出 \([L,R]\) 即可。用 set 维护贪心的过程,时间复杂度 \(O(n \log n + q)\)。

code
/*
最黯淡的一个 梦最为炽热
万千孤单焰火 让这虚构灵魂鲜活
至少在这一刻 热爱不问为何
存在为将心声响彻
*/
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define int long long
#define mem(x, v) memset(x, v, sizeof(x))
#define mcpy(x, y, n) memcpy(x, y, sizeof(int) * (n))
#define lob lower_bound
#define upb upper_bound
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using namespace std;

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

const int MN = 3e5 + 5;
const int Mod = 1e9 + 7;
const int inf = 1e9;

inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }

inline int qPow(int a, int b = Mod - 2, int ret = 1) {
    while (b) {
        if (b & 1) ret = ret * a % Mod;
        a = a * a % Mod, b >>= 1;
    }
    return ret;
}

#define dbg

int N, Q, K, fl, p[MN], a[MN], d[MN];
int stk[MN], tp, ls[MN], rs[MN], f[MN];
vector <pii> vr;

inline void dfs1(int u) {
    if (!u) return;
    dfs1(ls[u]), dfs1(rs[u]);
    if (a[u]) f[u] = a[u] + 1;
    else f[u] = max(1, max(f[ls[u]], f[rs[u]]));
}
inline void dfs2(int u, int rb) {
    if (!u) return;
    if (!a[u]) vr.pb(mp(f[u], rb));
    else fl |= f[u] > rb, rb = a[u] - 1;
    dfs2(ls[u], rb), dfs2(rs[u], rb);
}
inline void work() {
    N = read(), Q = read();
    for (int i = 1; i <= N; i++) 
        p[i] = read(), ls[i] = rs[i] = 0;
    tp = 0;
    for (int i = 1; i <= N; i++) {
        while (tp && p[stk[tp]] < p[i]) ls[i] = stk[tp--];
        rs[stk[tp]] = i;
        stk[++tp] = i;
    }
    ls[0] = rs[0] = fl = 0;
    K = 0, vr.clear();
    for (int i = 1; i <= N; i++)
        a[i] = read(), K += !a[i];
    dfs1(stk[1]);
    dfs2(stk[1], inf);
    set <int> s;
    for (int i = 1; i < K; i++) 
        d[i] = read(), s.insert(d[i]);
    int L = 0, R = inf;
    auto cmp1 = [&](pii x, pii y) { 
        return x.fi > y.fi; 
    };
    sort(vr.begin(), vr.end(), cmp1);
    for (auto it : vr) {
        int l = it.fi, r = it.se;
        auto p = s.upb(r);
        if (p == s.begin() || *--p < l) {
            if (L) { fl = 1; break; }
            L = l;
        } else {
            s.erase(p);
        }
    } 
    auto cmp2 = [&](pii x, pii y) { 
        return x.se < y.se; 
    };
    sort(vr.begin(), vr.end(), cmp2);
    s.clear();
    for (int i = 1; i < K; i++) s.insert(d[i]);
    for (auto it : vr) {
        int l = it.fi, r = it.se;
        auto p = s.lob(l);
        if (p == s.end() || *p > r) {
            if (R < inf) { fl = 1; break; }
            R = r;
        } else {
            s.erase(p);
        }
    }
    while (Q--) {
        int x = read();
        puts(!fl && L <= x && x <= R ? "YES" : "NO");
    }
}

signed main(void) {
    int T = read();
    while (T--) work();
    return 0;
}

标签:Burenka,ch,匹配,int,vr,CF1718D,Permutation,区间,define
From: https://www.cnblogs.com/came11ia/p/16716826.html

相关文章

  • 47.permutations-ii 全排列 II
    题目链接:47.permutations-ii相比全排列,多了重复数字的干扰,可以参照带重复数字的组合问题来进行去重:if(used[i]==1)判断nums[i]是否已经在path中,if(i>0&&nums[i]......
  • 46.permutations 全排列
    问题链接:46.permutations依旧是用回溯法,与组合问题形成对比,组合问题每次只需要选i之后的数;排列则每次需要从0开始,但是不能重复,利用used[6]={0}这个used数组来记录数是......
  • CF1718D 题解
    设\(k\)为\(a\)中的空位数量。首先咱们转化这个“相似”的条件,发现它其实是说,笛卡尔树的结构相同。那么我们把p建笛卡尔树然后把a的数往上填。如果此时有上面小于下......
  • CF #814 D2 - Burenka and Traditions (hard version)
    DP+map优化转移Problem-D2-Codeforces题意给n(1<=n<=1e5)个元素的数组,每次操作可以选一个区间\([l,r]\)和一个非负整数x,花\(\lceil\frac{r-l+1}2\rc......
  • 学习随笔——codeforces题目Build Permutation解答
    摘要:本题属于构造算法,虽然简单但对思维提升有一定帮助题目原地址如下:https://codeforces.com/problemset/problem/1713/C题目截图如下:  关键词:构造算法,动态规划,*120......
  • STL next_permutation与prev_permutation函数
    刷剑指offer遇到元素排列问题No27字符串的排列函数使用题目描述:输入一个长度为n字符串,打印出该字符串中字符的所有排列,你可以以任意顺序返回这个字符串数组。例如......
  • CodeForces-1719D Burenka and Traditions
    BurenkaandTraditions贪心由于代价是向上取整的,因此可以直接考虑成两种方式:选择两个相邻的数,让他们同时异或上一个值选择一个数字,让他变成\(0\)由此可见,最多......
  • CF1718C Tonya and Burenka-179
    显然只需要考虑\(k\vertn\)。如果直接维护是\(O(nd(n)\logn)\)的,很寄。可以证明如果\(\frac{n}{k}\)不是素数则不优。这个很好理解,比如对于\(n=12,k=2,6\),所有\(......
  • 解题报告——P3477 [POI2008]PER-Permutation
    这道题如果不是任意模数的话还是比较平凡的(这道题的式子其实很好推,根据康托展开的思路,一位一位考虑,只不过是多重集,可能有重复情况,排除即可,每一位的式子为:\[ans_i=\dfrac{......
  • Codeforces 1713C - Build Permutation
    题意为给出一个长度为n的空数组,数组下标为0至n-1。我们需要在数组中的每个位置上填上合适的数A[i],使得i+A[i]为完全平方数。并且数组最后需为0至n-1的一个排列。......