Znzryb's Blog
0%

Posted on Edited on

思路讲解

这个检查器还是有点难想到怎么样去写的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
auto check=[&](ll mid){
    bool oka=false,okb=false;;
    FOR(i,0,mid){
        if(cnta[i]==0){
            oka=true;
        }
        if(cntb[i]==0){
            okb=true;
        }
    }
    if(oka && okb){
        return true;
    }
    ll cnt=0;
    FOR(i,0,mid){   // 只要不是强制的，一定可以让i都在A中，或者i都在b中
        if(!forced[i]) ++cnt;
    }
    if(cnt>=2) return true;
    return false;
};

AC代码

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

https://www.codechef.com/viewsolution/1179874822

我们的贪心做法用AI树状数组给过去了（其实我也想到了，但是我觉得复杂度也太离谱了吧，就没试）。

my solution is a kind of greedy.

It is not difficult to observe that delete the last element matched is the best, because it affect the least elements.

so just do it.

certainly, using vector or list can not go through all tests.

but if you using fenwick tree which can find the kth element, all problems will be solved.

AC代码

https://www.codechef.com/viewsolution/1179893708

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

image

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78683868

心路历程（WA，TLE，MLE……）

这个循环退出条件特别容易忘记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function<void(ll,ll,ll,ll)> dfs=[&](ll a,ll b,ll c,ll d){
    if(d>=b){  
        
    }else{
        swap(a,c);
        swap(b,d);
    }
    if(b==0 || d==0 || a==1 || c==1){
        return;
    }
    if(b<=1 && d<=1){
        if(b==0) a=1;
        if(d==0) c=1;
        ans*=__gcd(c,a);
        ans%=mod;
        return;
    }
    ll e=__gcd(a,c);
    ans*=binpow(e, b);
    ans%=mod;
    ll x=a/e;
    // dfs(e*x,b,e,b-d);
    dfs(x,b,e,d-b);
};

Posted on Edited on

题目大意

题目大意

给定一棵包含 2n2n 个节点的树，树上分布着 nn 种钥匙（编号 11 到 nn）和 nn 种锁（编号 11 到 nn）。每种钥匙和每种锁在树上恰好出现一次。

节点信息由数组 aa 给出：

  • 若 ai>0a_i > 0，表示该节点拥有编号为 aia_i 的钥匙。

  • 若 ai<0a_i < 0，表示该节点拥有编号为 −ai-a_i 的锁。

移动与收集规则

  1. 出发点：必须选择一个拥有钥匙的节点作为起点。

  2. 钥匙获取：到达（或经过）拥有钥匙的节点时，自动获得该钥匙。钥匙永久保留。

  3. 通行限制：只有当手中拥有编号为 kk 的钥匙时，才能进入拥有编号为 kk 的锁的节点。

目标
对于每一种钥匙 ii（1≤i≤n1 \le i \le n），判断：如果从拥有钥匙 ii 的节点出发，是否能够遍历树的足够多部分，从而收集到全部 nn 种钥匙。

输入格式

  • 第一行包含整数 TT，表示测试数据组数。

  • 每组数据包含：

    • 整数 nn。
    • 2n2n 个整数 a1,…,a2na_1, \dots, a_{2n}，表示节点上的物品。
    • 2n−12n-1 行，每行两个整数 u,vu, v，表示树边。

输出格式
对于每组数据，输出一个长度为 nn 的 01字符串。

  • 字符串第 ii 个字符对应编号为 ii 的钥匙作为起点的结果。

  • 若能收集所有钥匙输出 1，否则输出 0。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Input
4
1
1 -1
1 2
3
-3 2 1 -1 3 -2
1 2
1 3
2 4
2 5
3 6
3
1 -1 2 -2 -3 3
1 2
2 3
3 4
4 5
5 6
3
1 -3 2 -2 -1 3
1 2
2 3
3 4
4 5
5 6

Output
1
011
000
000

样例解释（以第二组数据为例）

  • 配置：n=3n=3。
    • 节点 1：锁 3 (-3)
    • 节点 2：钥匙 2 (2)
    • 节点 3：钥匙 1 (1)
    • 节点 4：锁 1 (-1)
    • 节点 5：钥匙 3 (3)
    • 节点 6：锁 2 (-2)
    • 边连接结构：4-2-1-3-6，且 2-5 相连。即 1 是中心，连接 2 和 3；2 连接 4 和 5；3 连接 6。

image

  • 判定过程：

    1. 从钥匙 1 出发（位于节点 3）：
    • 初始拥有：{钥匙 1}。
    • 相邻节点：节点 1（锁 3，无钥匙 3，不可入），节点 6（锁 2，无钥匙 2，不可入）。
    • 结果：困在节点 3，无法收集所有。对应字符串第 1 位为 0。
    1. 从钥匙 2 出发（位于节点 2）：
    • 初始拥有：{钥匙 2}。
    • 相邻节点：节点 1（锁 3，不可入），节点 4（锁 1，不可入），节点 5（钥匙 3，可入）。
    • 移动到节点 5，获得钥匙 3。现有：{钥匙 2, 钥匙 3}。
    • 回到节点 2，尝试进入节点 1（锁 3）。因有钥匙 3，可入。
    • 到达节点 1 后，可前往节点 3（钥匙 1，可入）。获得钥匙 1。
    • 现有：{钥匙 1, 2, 3}。收集完毕。对应字符串第 2 位为 1。
    1. 从钥匙 3 出发（位于节点 5）：
    • 初始拥有：{钥匙 3}。
    • 前往节点 2（钥匙 2，可入）。获得钥匙 2。
    • 现有：{钥匙 2, 3}。后续过程同上，可收集完毕。对应字符串第 3 位为 1。

  • 最终输出：011。

思路讲解

首先，我们想到暴力，但是跑一次只需要 O(n)O(n)，也要 O(n2)O(n^2) 才能跑完。

于是面对这种复杂的问题，我们想到，需要分而治之。

我们先想，如果只有一个钥匙和一个门，那么合法的点在哪里那？

image

不难发现，肯定是在这边半颗树，也就是有钥匙的子树上的点才是合法的。

那么这个结论是非常显然的，那么现在问题在于我们有非常多的门，其实我们运用一下这个结论就会发现，我们只要不断往门上含有钥匙的子树上走，就行了，最后我们会得到一个联通块，检查一下这个联通块的联通性即可。

AC代码

https://vjudge.net/solution/64200130

心路历程（WA，TLE，MLE……）

那么一开始，我们选择的是纯 dfs 解决该问题，但是 WA 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vll valid;
void dfs(ll u, ll fa) {
    ll dfsm;
    if (A[u] < 0) {
        if (dir[u] <= 0)
            return;
        valid.clear();
        dfs(dir[u], u);
    } else {
        valid.PB(u);
        for (auto v : g[u]) {
            if (v == fa)
                continue;
            dfs(v, u);
        }
    }
}

主要原因是使用 dfs 时，没有一个全局的信息来参考。

比如下面这组 hack 数据，我的程序会错误地把 2，3 加入 valid 数组中，这个显然是有问题的。

这个其实是因为我们先走了节点 3 这条支路，又走了节点4。

image

于是我们继续在想，用树上差分固然可以解决此问题，但是总觉得有点杀鸡用牛刀了。使用纯 dfs 方案用办法解决此问题吗？

我们发现这个问题在于我们走完一条路了以后，我们需要知道这条路是封闭的，还是会继续往下走的？其实只要是会继续往下走的，其他路也不需要走了。

知道了这个以后，我们发现，其实不用改动很多，仅仅只需要加一个返回值，子树返回值为 1 时，我们直接开摆即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// return 1 表示的是可以往下走
// return 0 表示不可以往下走
int dfs(ll u, ll fa) {
    ll dfsm;
    if (A[u] < 0) {
        if (dir[u] <= 0)
            return 0;
        valid.clear();
        dfs(dir[u], u);
        return 1;
    } else {
        valid.PB(u);
        for (auto v : g[u]) {
            if (v == fa)
                continue;
            int ret=dfs(v, u);
            if(ret){
                return 1;
            }
        }
        return 0;
    }
}

然后就 AC 了。