Znzryb's Blog
0%

Posted on Edited on

题目大意

题目描述
给定一个长度为 nn 的数组 aa 和一个参数 kk。如果一个数组 bb 满足以下条件，则称其为“很酷的”：
对于从 kk 到 nn 的每个下标 ii，子数组 [ai−k+1,ai−k+2,…,ai][a_{i-k+1}, a_{i-k+2}, \dots, a_i] 都是子数组 [bi−k+1,bi−k+2,…,bi][b_{i-k+1}, b_{i-k+2}, \dots, b_i] 的重新排列（即两个长度为 kk 的滑动窗口构成的多重集相同）。

现在给定数组 aa 和数组 bb。数组 aa 仅包含 11 到 nn 之间的整数；数组 bb 包含 11 到 nn 之间的整数以及 −1-1。
请判断是否可以通过将 bb 中所有的 −1-1 替换为 11 到 nn 之间的任意整数，使得最终的数组 bb 满足上述“很酷的”条件。

输入格式
第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试用例的数量。
每个测试用例的第一行包含两个整数 nn 和 kk（1≤k≤n≤2⋅1051 \le k \le n \le 2 \cdot 10^5）。
第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n（1≤ai≤n1 \le a_i \le n）。
第三行包含 nn 个整数 b1,b2,…,bnb_1, b_2, \dots, b_n（1≤bi≤n1 \le b_i \le n 或 bi=−1b_i = -1）。
保证所有测试用例中 nn 的总和不超过 2⋅1052 \cdot 10^5。

输出格式
对于每个测试用例，如果可以构造出满足条件的数组 bb，输出 YES，否则输出 NO。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Input
5
5 5
1 2 3 4 5
3 1 5 2 4
5 2
1 2 1 2 1
2 -1 -1 -1 -1
6 1
5 6 2 2 4 3
5 -1 -1 2 -1 3
2 1
1 2
2 -1
6 4
1 2 3 4 1 2
2 -1 3 -1 4 -1

Output
YES
YES
YES
NO
NO

样例解释第一个测试用例：k=5k=5。唯一的长度为 55 的子数组是整个数组本身。给定的 bb 已经是 aa 的一个重新排列，且没有 −1-1，满足条件，答案为 YES。
第二个测试用例：k=2k=2。我们可以将所有的 −1-1 替换，使得 b=[2,1,2,1,2]b = [2, 1, 2, 1, 2]。此时在 aa 和 bb 中，每一个长度为 22 的窗口要么是 [1,2][1, 2] 要么是 [2,1][2, 1]，它们互为重新排列，因此答案为 YES。
第四个测试用例：k=1k=1。长度为 11 的窗口意味着对应位置的元素必须完全相同。因为已知 a1=1a_1 = 1 而 b1=2b_1 = 2，两者不相等，所以无法满足条件，答案为 NO。

思路讲解

image

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
void Solve() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int i = 1; i <= N; ++i) cin >> B[i];

    // target: 第一个窗口 a[1..K] 的多重集，b[1..K] 也必须是它的一个排列
    map<ll, ll> target;
    for (int i = 1; i <= K; ++i) target[A[i]]++;

    // free_count: 第一个窗口中，值完全自由（可任意选取）的位置数
    int free_count = 0;

    // 按模 K 将位置分成 K 条链：链 r 包含位置 r, r+K, r+2K, ...
    // 每条链恰好有一个位置落在第一个窗口（即位置 r 本身）
    //
    // 关键推导：窗口从 [i, i+K-1] 滑到 [i+1, i+K] 时，
    //   需要 -{b_i} + {b_{i+K}} = -{a_i} + {a_{i+K}}
    // 因此：
    //   - 若 a_i ≠ a_{i+K}：必须 b_i = a_i 且 b_{i+K} = a_{i+K}
    //   - 若 a_i = a_{i+K}：只需 b_i = b_{i+K}（不一定等于 a）
    //
    // 对一条链来说：
    //   - 若链中存在相邻位置 a 值不同（"固定链"），则整条链的 b 值全部被唯一确定为 a 值
    //   - 若链中所有 a 值全相同（"自由链"），则链上所有 b 值必须相等，但具体取什么值是灵活的

    for (int r = 1; r <= K; ++r) {
        // 检查链 r 是否所有 a 值都相同
        bool all_equal = true;
        for (int p = r; p + K <= N; p += K) {
            if (A[p] != A[p + K]) { all_equal = false; break; }
        }

        if (!all_equal) {
            // 固定链：链上每个位置 b[p] 必须等于 a[p]
            // 检查已给定的 b 值是否与 a 一致
            for (int p = r; p <= N; p += K) {
                if (B[p] != -1 && B[p] != A[p]) {
                    cout << "NO\n"; return;
                }
            }
            // 位置 r（第一个窗口中的位置）的 b 值确定为 a[r]，从 target 中扣除
            target[A[r]]--;
        } else {
            // 自由链：链上所有 b 值必须相等
            // 检查所有已给定的 b 值是否互相一致
            ll forced = -1;
            for (int p = r; p <= N; p += K) {
                if (B[p] != -1) {
                    if (forced == -1) forced = B[p];       // 第一个给定值，记录
                    else if (forced != B[p]) {              // 与之前的给定值矛盾
                        cout << "NO\n"; return;
                    }
                }
            }
            if (forced != -1) target[forced]--;  // 链的值已确定，从 target 扣除
            else free_count++;                    // 链的值完全自由，待分配
        }
    }

    // 最终检查：target 中剩余的值（还没被匹配的）必须恰好分配给 free_count 个自由位置
    // 且不能有任何值被"过度消耗"（计数变负）
    ll remaining = 0;
    for (auto& [v, cnt] : target) {
        if (cnt < 0) { cout << "NO\n"; return; }
        remaining += cnt;
    }
    // 剩余的值刚好够填满所有自由位置 → YES，否则 → NO
    cout << (remaining == free_count ? "YES" : "NO") << "\n";
}

AC代码

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

Posted on Edited on

题目大意

题目描述

对于一个长度为 nn 的未知序列 aa，定义其 AND-数组 f(a)f(a) 如下：

f(a)k=∑1≤i1<i2<⋯<ik≤nai1&ai2&⋯&aikf(a)k = \sum{1 \le i_1 < i_2 < \dots < i_k \le n} a_{i_1} \mathbin{\&} a_{i_2} \mathbin{\&} \dots \mathbin{\&} a_{i_k}

其中 1≤k≤n1 \le k \le n，&\mathbin{\&} 表示按位与操作。换句话说，f(a)kf(a)_k 是序列 aa 中所有长度为 kk 的子序列的按位与结果之和。

现在给定一个长度为 nn 的序列 bb，满足对于所有的 1≤i≤n1 \le i \le n，都有 bi≡f(a)i(mod109+7)b_i \equiv f(a)_i \pmod{10^9+7}。

请根据给定的序列 bb，构造并输出任意一个满足条件的序列 aa。

输入格式

第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试用例的数量。

每个测试用例包含两行：
第一行包含一个整数 nn（1≤n≤1051 \le n \le 10^5），表示序列 aa 和 bb 的长度。
第二行包含 nn 个整数 b1,b2,…,bnb_1, b_2, \dots, b_n（0≤bi<109+70 \le b_i < 10^9+7），表示序列 bb。

保证存在长度为 nn 且满足 0≤ai<2290 \le a_i < 2^{29} 的序列 aa 使得条件成立。
保证所有测试用例中 nn 的总和不超过 10510^5。

输出格式

对于每个测试用例，输出 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n（0≤ai<2290 \le a_i < 2^{29}），表示重构出的序列 aa。如果有多个满足条件的序列，输出任意一个即可。

样例输入

1
2
3
4
5
6
7
3
3
0 0 0
5
22 24 10 1 0
10
130 585 1560 2730 3276 2730 1560 585 130 13

样例输出

1
2
3
0 0 0
5 3 6 1 7
13 13 13 13 13 13 13 13 13 13

样例解释

在第二个样例中，若构造的序列 a=[5,3,6,1,7]a = [5, 3, 6, 1, 7]，其 f(a)4f(a)_4 的值为：
(a1&a2&a3&a4)+(a1&a2&a3&a5)+(a1&a2&a4&a5)+(a1&a3&a4&a5)+(a2&a3&a4&a5)=0+0+1+0+0=1(a_1 \mathbin{\&} a_2 \mathbin{\&} a_3 \mathbin{\&} a_4) + (a_1 \mathbin{\&} a_2 \mathbin{\&} a_3 \mathbin{\&} a_5) + (a_1 \mathbin{\&} a_2 \mathbin{\&} a_4 \mathbin{\&} a_5) + (a_1 \mathbin{\&} a_3 \mathbin{\&} a_4 \mathbin{\&} a_5) + (a_2 \mathbin{\&} a_3 \mathbin{\&} a_4 \mathbin{\&} a_5) = 0 + 0 + 1 + 0 + 0 = 1。
且 f(a)1=a1+a2+a3+a4+a5=22f(a)_1 = a_1 + a_2 + a_3 + a_4 + a_5 = 22。可以证明对于所有 1≤i≤51 \le i \le 5 均有 f(a)i=bif(a)_i = b_i，因此 a=[5,3,6,1,7]a = [5, 3, 6, 1, 7] 是一个合法的解。

思路讲解

AC代码

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

Posted on Edited on

题目大意

题目描述
给定两个以二进制字符串形式表示的非负整数 ss 和 tt。
请计算有多少组整数对 (a,b)(a, b) 满足：

  1. 取值范围：aa 和 bb 均在区间 [s,t][s, t] 内。

  2. 满足等式：a×b=(a or b)×(a and b)a \times b = (a \text{ or } b) \times (a \text{ and } b)

其中 or\text{or} 表示按位或运算，and\text{and} 表示按位与运算。
最终答案需要对 998244353998244353 取模。

输入格式
第一行包含一个整数 QQ（1≤Q≤201 \le Q \le 20），表示测试用例的数量。
接下来 QQ 行，每行包含两个 0101 字符串 SS 和 TT，分别表示非负整数 ss 和 tt 的二进制形式。
数据保证 ss 和 tt 的二进制形式无前导零，且满足 s≤ts \le t，1≤∣S∣,∣T∣≤5×1051 \le |S|, |T| \le 5 \times 10^5。

输出格式
对于每个测试用例，输出一行一个非负整数，表示满足条件的解的数量对 998244353998244353 取模后的值。

样例数据

输入

1
2
3
4
5
6
7
6
11 1000
1000 1001
0 100
11 111
10 111
0 11111

输出

1
2
3
4
5
6
18
4
17
17
24
454

样例解释
原题未提供具体的样例解释内容，此处按要求对样例数据的完整输入输出进行展示。

思路讲解

这道题目的数的规律我们很容易从这个打表看出来。

我们下面只打印了有序对：

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
33
34
35
36
37
38
39
40
[-] FAILURE: RUNTIME ERROR
i = [0]
j = [1]
bitset<10>(i) = [0000000000]
bitset<10>(j) = [0000000001]

-----------
i = [0]
j = [2]
bitset<10>(i) = [0000000000]
bitset<10>(j) = [0000000010]

-----------
i = [0]
j = [3]
bitset<10>(i) = [0000000000]
bitset<10>(j) = [0000000011]

-----------
i = [0]
j = [4]
bitset<10>(i) = [0000000000]
bitset<10>(j) = [0000000100]

-----------
i = [1]
j = [3]
bitset<10>(i) = [0000000001]
bitset<10>(j) = [0000000011]

-----------
i = [2]
j = [3]
bitset<10>(i) = [0000000010]
bitset<10>(j) = [0000000011]

-----------
cnt = [6]


不难看出，我们所要求的是：

image

当然，如果你要推出这个东西的话，你需要知道一个定理：

image

对于任意两个非负整数 aa 和 bb，我们设 x=a or bx = a \text{ or } b，y=a and by = a \text{ and } b。
在位运算中，有一个非常经典的定律，即它们的和永远保持不变：

x+y=a+bx + y = a + b

为什么？ 我们可以单独看某一个二进制位：

  • 如果 aa 和 bb 这一位都是 0，那么 xx 是 0，yy 也是 0。(0+0=0+0)(0+0 = 0+0)

  • 如果 aa 和 bb 这一位都是 1，那么 xx 是 1，yy 也是 1。(1+1=1+1)(1+1 = 1+1)

  • 如果 aa 和 bb 这一位是一个 1 一个 0，那么 xx (OR) 会拿到这个 1，yy (AND) 是 0。(1+0=1+0)(1+0 = 1+0)
    可以看出，无论哪种情况，进位和本质的值都不会丢失，所以 a or ba \text{ or } b 加上 a and ba \text{ and } b 必定等于 a+ba + b。

接着，我们把这两个式子联立，可以得到：

image

那么不难得到：

image

不过更难的应该是更进一步的这个求解。

HDU - 2089- 不要62

这道题目和普通的数位 dp 最大的不同的就是，你一定要同时考虑这个低位和高位。

image

具体而言，为什么相减会出现问题呢？

image

那么我们上面讲了不能这么做，然后下面我们来讲讲应该怎么做。

image

然后下面是一种比较 shi 的实现方式，因为就是分类讨论。

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
33
34
35
36
37
constexpr int moves[][2] = {{0, 0}, {1, 0}, {1, 1}};
auto execute_dp(const string &l, const string &r) {
    array<array<ll, 2>, 2> dp = {};
    dp[0][0] = 1;
    for (int i = 0; i < (int) l.size(); ++i) {
        int r_bit = r[i] - '0', l_bit = l[i] - '0';
        array<array<ll, 2>, 2> ndp = {};
        for (auto &[a_r,b_l]: moves) {
            for (int status_r = 0; status_r <= 1; ++status_r) {
                for (int status_l = 0; status_l <= 1; ++status_l) {
		                // 受限制的时候，不可以超过上界
                    if (status_r == 0 && a_r > r_bit) {
                        continue;
                    }
                    // 受限制的时候，不可以越过下界
                    if (status_l == 0 && b_l < l_bit) {
                        continue;
                    }
                    // 继承原来的状态
                    ll to_r = status_r, to_l = status_l;
                    // 不一样而且合法？那就变为这个 1 状态（即不受限制状态，因为已经偏离了前缀了）
                    if (a_r != r_bit) {
                        to_r = 1;
                    }
                    if (b_l != l_bit) {
                        to_l = 1;
                    }
                    ndp[to_r][to_l] += dp[status_r][status_l];
                    ndp[to_r][to_l] %= mod;
                }
            }
        }
        swap(dp, ndp);
    }
    return dp;
    // return (dp[0][0] + dp[0][1] + dp[1][0] + dp[1][1]) % mod;
}

在知道 dp 数组以后，答案像下面这样子求：

1
2
3
4
5
6
7
8
9
ll gen_ans(const auto &dp, ll l, ll r) {
    ll ans = (dp[0][0] + dp[1][1] + dp[0][1] + dp[1][0]) % mod;
    ans = 2 * ans - (r - l + 1);
    ans %= mod;
    if (ans < 0) {
        ans += mod;
    }
    return ans;
}

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=17914

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=17962

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

Posted on Edited on

图论中，找最大环是 NP-hard 问题，所以不可能找最大环。

找“最大环”（即无向图或有向图中的最长简单环，Longest Cycle Problem）是一个经典的 NP-Hard 问题。它和旅行商问题（TSP，Traveling Salesperson Problem）有着极深的渊源，本质上它们都是哈密顿环（Hamiltonian Cycle）问题的衍生和泛化。

我们可以从以下几个方面来理解为什么它是 NP-Hard，以及它和 TSP 的共性所在：

1. 为什么找最大环是 NP-Hard 问题？

在计算复杂性理论中，证明一个问题是 NP-Hard 的最标准方法，就是将一个已知的 NP-Hard/NP-Complete 问题规约（Reduce）到它。对于“最大环”问题，最直接的规约对象就是哈密顿环问题。

  • 哈密顿环问题：给定一个包含 VV 个顶点的图，问是否存在一个简单环，它恰好经过图中的每一个顶点一次？这是一个非常著名的 NP-Complete 问题。

  • 规约过程：假设你拥有一个能够在多项式时间内求出任意图“最大简单环”的神奇算法。现在给你一个未知的图，你只需要运行这个神奇算法求出图中的最大环，然后看看这个最大环的长度是不是正好等于顶点总数 VV。

    • 如果等于 VV，说明图里存在哈密顿环。
    • 如果小于 VV，说明图里不存在哈密顿环。

图图论中，找最大环是 NP-hard 问题，所以不可能找最大环，这是因为找出最大环的方法可以非常轻松的判定以及找到图中的哈密顿环。

存在欧拉回路的这个条件也很简单**，就是每个顶点的度数都是偶数，那么一定存在一条欧拉回路（在联通无向图中）**

欧拉路径存在的充要条件（在无向连通图上），就是奇数度数节点数量等于0 或者 2（也就是要么是一条回路，也就是 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
if (odd_cnt!=0 && odd_cnt!=2) {
    cout<<"NO\n";
    return;
}

vector<ll> ans_ls;
auto dfs=[&](auto && self,ll u) -> void {
    while (!g[u].empty()) {
        auto it=g[u].begin();
        auto [to,id]=*it;
        g[u].erase(it);
        g[to].erase({u,id});
        self(self,to);
        ans_ls.push_back(id);
    }
};
dfs(dfs,max(start_node,g.begin()->first));
// 判断图是否联通，如果不联通，也是错的。
if (SZ(ans_ls)!=N) {
    cout<<"NO\n";
    return;
}
reverse(all(ans_ls));
cout<<"YES\n";
for (auto u:ans_ls) {
    cout<<u<<" ";
}
cout<<"\n";

为什么 Euler 路径红色这样子写有问题呢？其实也很容易理解，因为我们要把 ans_ls 反过来的呀！所以说，肯定需要先遍历完后续的点，才能塞入这条边啊！其实简单来说，就是要和正常的反过来！

image

Codeforces Round 1081 (Div. 2)-CF-1081-E. Swap to Rearrange（按值进行图论建模）（欧拉回路）

Codeforces Round 1026 (Div. 2)-CF-1026-E. Melody

Posted on Edited on

题目大意

题目描述

给定二维平面上的 NN 只猫的坐标，保证没有任何两只猫的 XX 坐标相同，也没有任何两只猫的 YY 坐标相同。

你需要设计一条符合以下规则的回路（包含 mm 个步骤，问候 mm 只不同的猫）：

  1. 选择一个起点 (x0,y0)(x_0, y_0)，并面向四个基本方向（东、南、西、北）之一。

  2. 在第 ii 步（1≤i≤m1 \le i \le m）中：

  • 选择一个距离 ki>0k_i > 0，沿着当前方向直线前进 kik_i 的距离，此时必须恰好停在一只之前从未问候过的猫的位置。
  • 问候这只猫。
  • 不改变方向，继续直线前进 kik_i 的距离，到达点 (xi,yi)(x_i, y_i)。
  • 左转或右转 90 度，面向一个新的基本方向。
  1. 完成所有 mm 步后，必须回到起点 (x0,y0)(x_0, y_0)，并且面向初始方向。

整条路线的总长度为 ∑i=1m2ki\sum_{i=1}^{m} 2k_i。如果 m=0m=0，则路线长度为 00。
请计算并输出符合上述规则的路线的最大总长度。

（注：由于猫的 XX 和 YY 坐标互不相同，平面上任意水平或垂直的直线上最多只有一只猫。因此题目等价于：在平面上寻找一个边平行于坐标轴且边数偶数的闭合多边形，该多边形的每一条边的中点都恰好是一只猫，求该多边形的最大周长。）

输入格式

第一行包含一个整数 NN（1≤N≤40001 \le N \le 4000），表示猫的数量。
接下来 NN 行，每行包含两个整数 XX 和 YY（−108≤X,Y≤108-10^8 \le X, Y \le 10^8），表示一只猫的坐标。
保证没有任何两只猫的 XX 坐标相同，也没有任何两只猫的 YY 坐标相同。

输出格式

输出一个整数，表示符合条件的路线的最大总长度。

样例 1

输入

1
2
3
4
5
6
5
1 2
2 1
0 0
-1 -2
-2 -1

输出

1
0

样例 1 解释
虽然存在一条长度为 16 且经过所有猫的回路，但它不符合规则，因为沿途位于 (0,0)(0,0) 的猫会被问候两次，而题目要求每次经过的猫都必须是之前未曾问候过的。

样例 2

输入

1
2
3
4
5
6
7
6
4 0
0 4
2 -1
-1 2
-4 3
3 -4

输出

1
32

样例 2 解释
存在一条长度为 32 的路线，可以完美经过并问候所有 6 只猫。每只猫都恰好位于路线某条直线段的正中点。

样例 3

输入

1
2
3
4
5
6
7
8
7
2 1
0 -1
5 5
3 0
4 4
6 2
1 -2

输出

1
24

样例 3 解释
在给定的 N=7N=7 只猫中，可以选择其中的 m=6m=6 只猫构成一条合法的路线，其能达到的最大长度为 24。

image

思路讲解

这个数据是 O(n2)O(n^2) 的。

这个还是非常适合图论建模的。

image

这个上面的是不难看出的。

AC代码

AC

https://codeforces.com/gym/106416/submission/368359863

我的 TLE 代码（应该没什么问题，但是这个题目对常数要求比较高）

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

image