Znzryb's Blog
0%

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

Posted on Edited on

题目大意

题目描述
Evelyn 和 Todd 正在进行一场游戏。游戏开始时有一个包含 NN 个整数的多重集合 SS，以及一个初始为空的数组 vv。两人轮流进行操作，每回合当前玩家从 SS 中选择一个元素，将其添加到数组 vv 的末尾，并将其从 SS 中移除。

当 SS 为空时游戏结束。此时计算数组 vv 中的逆序对数量（即满足 i<ji < j 且 vi>vjv_i > v_j 的索引对的数量）。如果逆序对数量为偶数，则 Evelyn 获胜；如果为奇数，则 Todd 获胜。

两人都充分了解游戏并采用最优策略进行。对于给定的多重集合 SS，有以下四种可能的结果：

  • 无论谁先手，Evelyn 必胜（输出 E）。

  • 无论谁先手，Todd 必胜（输出 T）。

  • 无论先手是谁，先手玩家必胜（输出 F）。

  • 无论先手是谁，后手玩家必胜（输出 S）。

输入格式
第一行包含一个整数 NN（1≤N≤1051 \le N \le 10^5），表示多重集合 SS 中的元素数量。
第二行包含 NN 个整数 S1,S2,…,SNS_1, S_2, \ldots, S_N（1≤Si≤N1 \le S_i \le N），表示多重集合 SS 中的元素。

输出格式
输出一个大写字母，表示在双方最优策略下的游戏结果（E、T、F 或 S）。

样例一

输入

1
2
3
1 1 1

输出

1
E

样例一解释
无论 Evelyn 和 Todd 如何从多重集合 {1,1,1}\{1, 1, 1\} 中选择元素，最终得到的数组都将是 [1,1,1][1, 1, 1]。由于该数组中没有逆序对（数量为 00，是偶数），因此无论谁先手，Evelyn 都将获胜。

样例二

输入

1
2
3
3 1 2

输出

1
S

思路讲解

第 49 届 ICPC区域赛沈阳站——D. Dot Product Game

不过好像其实没什么关系。

当一个数被塞入这个 v 之中的时候， 其实，其对 inv 的贡献已经确定了。

image

呃，不过我感觉我们的思路有点问题，我们来看看 gemini 的回答：

image

image

我们发现，所有两两配对的部分，其贡献都为 0。

贡献为 0 的部分，就把它丢掉，少即是好。我们删除的部分，不仅这个贡献为 0，对于博弈论来说，他们两者的操作还是这个互为镜像的。

image

然后，转换成这样了，变成 0/1 的这个奇偶性游戏了，我们会发现，最后一个手握自由改变奇偶性机会的人，就是赢家。

这个是因为，无论前面怎么变化，奇偶性要么是 0，要么是 1，我如果手握这个选择，我就可以选对自己有利的，想保持就保持，想改变就改变。

image

我们发现，选择 S 中第一个大的数字（采用 0-based，其实也就是第二大的数字），一定可以改变奇偶，因此，我们会发现，倒数第二个操作的人，就是赢得这个游戏的人，因为其是最后一个手握自由改变奇偶性机会的人。

那么答案就非常明显了。

1
2
3
4
5
6
7
8
9
if (odd_freq_cnt <= 1) {
    cout << "E\n";
    return;
}
if (odd_freq_cnt % 2 == 0) {
    cout << "F\n";
}else {
    cout << "S\n";
}

AC代码

AC
https://codeforces.com/gym/106416/submission/368226851

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

Posted on Edited on

题目大意

image

一开始对题面的理解有问题，我以为他可以保留折扣机会，但是实际上不行，不能保留。

题目描述

给定 NN 个顾客的商品购买需求，第 ii 个需求对应的商品价格为偶数 AiA_i。

商店有一项优惠活动：每完成 XX 次全价购买后，下一次购买单件商品可以获得 50% 的折扣。此次打折购买不计入下一次获取折扣所需的 XX 次全价购买中。

你可以自由决定这 NN 件商品的购买顺序。但为了满足发货时间限制，第 ii 个需求对应的商品，必须在你的前 i+Ki+K 次购买中完成。

由于顾客已经提前支付了全额费用，你通过折扣节省下来的金额即为你个人的利润。请计算并输出你能获得的最大总利润（即所有打折购买商品原价的一半的总和）。

输入格式

第一行包含三个整数 NN、XX 和 KK（1≤N,X≤2×1051 \le N, X \le 2 \times 10^5，0≤K≤2×1050 \le K \le 2 \times 10^5），分别表示需求数量、获得折扣所需的全价购买次数，以及延迟发货的限制参数。
第二行包含 NN 个偶数 A1,A2,…,ANA_1, A_2, \dots, A_N（2≤Ai≤1092 \le A_i \le 10^9），依次表示每个需求商品的价格。

输出格式

输出一个整数，表示你能获得的最大总利润。

样例 1

输入：

1
2
3 1 0
6 4 14

输出：

1
2

样例 1 解释

由于 K=0K=0，第 ii 个需求必须在第 ii 次购买时完成。因此购买顺序被严格固定为 [6, 4, 14]。只有第二次购买（价格为 44）可以享受半价折扣，能获得的最大利润为 4/2=24 / 2 = 2。

样例 2

输入：

1
2
3 1 1
6 4 14

输出：

1
7

样例 2 解释

由于 K=1K=1，第 ii 个需求必须在前 i+1i+1 次购买内完成。合法的购买顺序包括 [6, 4, 14]、[6, 14, 4]、[4, 6, 14] 以及 [14, 6, 4]。
其中，顺序 [6, 14, 4] 是最优的：在花费全价购买价格为 66 的商品后，可以对价格为 1414 的商品使用折扣，从而获得最大利润 14/2=714 / 2 = 7。

思路讲解

呃，这个问他问的太早了。其实知道了，不能够保留这个折扣机会，那么其实倒过来看就非常 easy 的一件事情了。

为什么反向处理呢？我们不难发现，一个数，更早被处理完全没有任何问题，但是不能更晚被处理。

或者，可以这么说，正过来看，ddl 是 ddl，也就是截止时间，但是反过来看，ddl 是激活时间。

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
ll gen_ans(const map<ll, vector<ll> > &ddl_price, ll N, ll X) {
    ll ans = 0;
    // gen_sorted_st(ddl_price, st1);
    multiset<ll> st_small;
    multiset<ll,greater<>> st_big;
    // gen_sorted_st(ddl_price, st2);
    for (int i = N; i >= 1; --i) {
        auto it = ddl_price.find(i);
        // 有没有 ddl 是 i 的商品？我们对其进行激活
        if (it != ddl_price.end()) {
            for (auto price: it->second) {
                st_big.insert(price);
                st_small.insert(price);
            }
        }
        if (i % (X + 1) == 0) {
		        // 折扣的时候选择大的数字
            ll add=*st_big.begin();
            ans+=add/2;
            st_erase(st_small,st_big,add);
        } else {
		        // 平时抛弃小的数字
            ll add=*st_small.begin();
            st_erase(st_small,st_big,add);
        }
    }
    return ans;
}

AC代码

AC
https://codeforces.com/gym/106416/submission/368218310

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