Znzryb's Blog
0%

Posted on

题目大意

题目大意

Alice 和 Bob 在玩一个游戏。给定两个数组：包含 nn 个元素的数组 aa 和包含 mm 个元素的数组 bb。

两人轮流进行操作，Alice 先手。在每个回合中，玩家需要从数组 aa 中选择一个数字 xx，并从数组 bb 中选择一个数字 yy。

  • Alice 的规则：选择的 yy 必须能被 xx 整除。

  • Bob 的规则：选择的 yy 必须不能被 xx 整除。

选定 xx 和 yy 后，yy 会从数组 bb 中被移除（如果数组中存在多个相同的 yy，只移除其中一个），而 xx 仍然保留在数组 aa 中。无法进行合法操作（即无法选出满足自身规则的 xx 和 yy）的玩家将输掉游戏。

假设双方都采取最优策略，请判断谁会赢得游戏。

输入格式

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

对于每个测试用例：
第一行包含两个整数 nn 和 mm（1≤n,m≤1061 \le n, m \le 10^6）。
第二行包含 nn 个整数 aia_i（1≤ai≤n+m1 \le a_i \le n+m），表示数组 aa 的元素。
第三行包含 mm 个整数 bib_i（1≤bi≤n+m1 \le b_i \le n+m），表示数组 bb 的元素。

保证所有测试用例中 nn 的总和以及 mm 的总和均不超过 10610^6。

输出格式

对于每个测试用例，输出获胜者的名字：如果 Alice 赢，输出 Alice；如果 Bob 赢，输出 Bob。

样例输入

1
2
3
4
5
6
7
8
9
10
3
9 3
3 2 4 2 2 4 4 2 4
6 7 12
10 3
3 2 5 4 2 5 3 4 4 4
10 7 13
1 5
1
1 2 3 4 5

样例输出

1
2
3
Alice
Bob
Alice

样例解释

对于第一个测试用例，Alice 的获胜过程如下：

  1. Alice 的回合：选择 x=3,y=6x=3, y=6（66 能被 33 整除）。操作后 66 从数组 bb 中移除，此时 b=[7,12]b=[7, 12]。

  2. Bob 的回合：选择 x=3,y=7x=3, y=7（77 不能被 33 整除）。Bob 在这个回合只能选择 y=7y=7，因为对于 y=12y=12，数组 aa 中找不到任何不能整除它的 xx。操作后 77 从数组 bb 中移除，此时 b=[12]b=[12]。

  3. Alice 的回合：选择 x=4,y=12x=4, y=12（1212 能被 44 整除）。操作后 1212 从数组 bb 中移除，此时数组 bb 变为空。

  4. Bob 的回合：数组 bb 已经为空，Bob 无法进行任何操作，因此 Bob 输掉游戏，Alice 获胜。

思路讲解

OK，我们说回来。这个D为什么交了5发还是没过呢？主要是因为就是这个D，它的数据量比较大。使用Victor victor或者victor的这种调和级数写法呢，它这个时间会超。可以使用vis 数组标记所有 a 的倍数。这样子可以避免卡常。

1
2
3
4
5
6
7
8
9
10
ll cnt_un_divide=0,cnt_all_divide=0;
vector<char> vis(N+M+2);
for (auto a:A) {
    for (ll i=1;i<=N+M;++i) {
        if (i*a>N+M) {
            break;
        }
        vis[i*a]=true;
    }
}

然后为什么标题里面提了不要用 while 循环？是因为涉及累加的逻辑（在 D 的对拍暴力程序当中），直接 continue 以后，while 循环的这个累加就崩掉了。

AC代码

AC
https://codeforces.com/contest/2203/submission/364454955

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

image

后面还被系统测试阴了一手，把这个LCM改成128，用INT128就可以了，这个叫什么，当时其实我就知道这里应该是会有点问题的，想用这个128嘛，但是可能还是犹豫还是犹豫了。

1
2
3
4
i128 lcm128(i128 a,i128 b) {
    i128 res=a*b/__gcd(a,b);
    return res;
}

Posted on Edited on

题目大意

https://codeforces.com/contest/2203/problem/E

题目描述

Alice 和 Bob 有一个初始为空的牌堆。游戏共进行 mm 回合，在第 ii 回合中，会发生以下事件：

  1. 一张数值为 aia_i 的牌被加入牌堆（保证加入的牌数值各不相同）。

  2. 如果牌堆中的牌数少于 33 张，该回合直接结束。

  3. 否则，Alice 从牌堆中选择一张牌，设其数值为 aa。

  4. 接着，Bob 在知道 Alice 选了哪张牌的情况下，从剩下的牌中选择一张牌，设其数值为 bb（b≠ab \neq a）。

  5. 最后，从剩下的 i−2i-2 张牌中等概率随机抽取一张牌，设其数值为 cc。

  6. 回合结束后，这三张牌被放回牌堆。

得分规则

在确定了 a,b,ca, b, c 的值后，Bob 的得分按以下规则计算：

  • 如果 ∣a−c∣≤∣b−c∣|a - c| \le |b - c|，Bob 得 00 分；

  • 如果 cc 的值严格介于 aa 和 bb 之间（即 a<c<ba < c < b 或 b<c<ab < c < a），Bob 得 00 分；

  • 其他情况下，Bob 得分为 ∣b−c∣|b - c|。

游戏目标

在每回合中，Alice 的目标是最小化 Bob 的期望得分，而 Bob 的目标是最大化他的期望得分。两人均采取最优策略。（注意：两人是根据真实期望得分来做最小化或最大化的决策，而非取模后的值）。

输入格式

第一行包含一个整数 mm（3≤m≤2⋅1053 \le m \le 2 \cdot 10^5），表示回合数。
第二行包含 mm 个整数 a1,a2,…,ama_1, a_2, \dots, a_m（1≤ai≤10121 \le a_i \le 10^{12}，所有 aia_i 互不相同），表示每回合加入牌堆的牌的数值。

输出格式

输出 m−2m-2 个整数，第 ii 个数表示在第 i+2i+2 回合中，双方在最优策略下 Bob 的期望得分对 998244353998244353 取模后的结果。

样例 1

1
2
3
4
5
6
7
8
Input:
5
1 10 3 11 7

Output:
0
499122177
665496236

样例 1 解释

这三个输出分别对应第 3,4,53, 4, 5 回合。真实的期望得分依次为 0,12,230, \frac{1}{2}, \frac{2}{3}。

样例 2

1
2
3
4
5
6
7
8
9
Input:
6
23 7 11 24 10 28

Output:
0
499122177
1
748683266

样例 2 解释

这四个输出分别对应第 3,4,5,63, 4, 5, 6 回合。真实的期望得分依次为 0,12,1,540, \frac{1}{2}, 1, \frac{5}{4}。

样例 3

1
2
3
4
5
6
7
8
9
10
11
12
Input:
9
4 10 7 1 16 5 9 12 2

Output:
0
499122178
2
499122178
798595484
831870296
427819010

样例 3 解释

真实的期望得分依次为 0,32,2,32,85,116,1170, \frac{3}{2}, 2, \frac{3}{2}, \frac{8}{5}, \frac{11}{6}, \frac{11}{7}。

思路讲解

通过模拟，我们发现，首先，选了 A 的位置以后，B 其实只有两种选择，B 必须紧紧挨着 A 选。

然后，我们就是要确定这个 A 的选择。我们可以采用一种二分两次的方法（我自己瞎想的）。或者你也可以三分。

image

图中的 res 就是使用树状数组查询的蓝色部分的这个查询结果。

核心的这个做法这个 lambda 是这个东西，他能够在知道目前长度的情况下，求解出这个答案。

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
    auto find_ans = [&](ll len) -> ll {
        ll l = 0, r = len - 1;
        auto cal_left = [&](ll ia) -> ll {
            ll pa = processing_pos[ia];
            if (ia <= 2) {
                return 0;
            }
            ll res = tr.query(1, processing_pos[ia - 2]);
            ll pb = processing_pos[ia - 1];
            res = li_pos_to[pb].val * (ia - 2) - res;
            return res;
        };
        auto cal_right = [&](ll ia) -> ll {
            if (ia >= len - 1) {
                return 0;
            }
            ll pa = processing_pos[ia];
            ll pb = processing_pos[ia + 1];
            ll res = tr.query(processing_pos[ia + 2], N);
            res = res - li_pos_to[pb].val * (len - ia - 1);
            return res;
        };
        auto check1 = [&](ll p) -> bool {
            // 这个程序，只要左边比右边大，就 return false
            return cal_left(p) >= cal_right(p);
        };
        auto check2 = [&](ll p) -> bool {
            // 这个程序，只要左边比右边大，就 return false
            return cal_left(p) <= cal_right(p);
        };
        while (l < r) {
            ll mid = l + r >> 1;
            if (check1(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        ll ans1 = l;
        l = 1, r = len;
        while (l < r) {
            ll mid = l + r +1 >> 1;
            if (check2(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        ll ans2=l;
// #ifdef LOCAL
//         debug(ans1);
//         debug(ans2);
//         debug(cal_left(ans1));
//         debug(cal_right(ans2));
// #endif
        ll res=min(max(cal_left(ans1),cal_right(ans1)),max(cal_right(ans2),cal_left(ans2)));
        res%=mod;
        res*=binpow(len-2,mod-2);
        res%=mod;
        return res;
    };

AC代码

AC

https://codeforces.com/contest/2203/submission/364812724

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

虽然是权值线段树（树状数组），但是还是加的这个值。

image

不要搞反顺序了。

image

Posted on Edited on

题目大意

题目描述
给定两个整数 ss 和 mm。
你需要构造一个由非负整数组成的数组 a=[a1,a2,…,an]a=[a_1, a_2, \dots, a_n]，满足以下两个条件：

  1. 数组所有元素的和等于 ss，即 ∑i=1nai=s\sum_{i=1}^n a_i = s；

  2. 对于数组中的每一个元素 aia_i，都满足 ai & m=aia_i \ \& \ m = a_i（其中 &\& 表示按位与运算符）。换句话说，在每个数字 aia_i 的二进制表示中，只有当 mm 在相应位置上的二进制位也是 11 时，aia_i 在该位置上的二进制位才可以是 11。

判断是否至少存在一个满足条件的数组。如果存在，求出该数组的最小可能长度 nn；如果不存在，则输出 −1-1。

输入格式
第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试用例的数量。
每个测试用例包含一行，包含两个整数 ss 和 mm（1≤s,m≤10181 \le s, m \le 10^{18}）。

输出格式
对于每个测试用例，输出一个整数：
如果不存在这样的数组，输出 −1-1；
否则，输出满足条件的数组的最小可能长度 nn。

样例输入

1
2
3
4
5
6
7
6
13 5
13 3
13 6
1000000007 2776648
99999999999 1
998244353 1557287

样例输出

1
2
3
4
5
6
3
5
-1
-1
99999999999
642

样例解释
对于部分测试用例的分析如下：
当 s=13,m=5s=13, m=5 时，答案为 33，因为存在一个满足条件的数组 a=[5,4,4]a=[5, 4, 4]；
当 s=13,m=3s=13, m=3 时，答案为 55，因为存在一个满足条件的数组 a=[3,3,3,3,1]a=[3, 3, 3, 3, 1]；
当 s=13,m=6s=13, m=6 时，答案为 −1-1，因为不存在满足条件的数组。

思路讲解

说白了就是从高位到低位贪心，因为高位你也没办法减的更多了，高位只能影响更高位，而更高位之前已经尽力解决了。因此没有后效性。

1
2
3
4
5
6
7
8
9
10
11
12
13
auto check=[&](ll num_a) -> bool {
    ll opS=S;
    for (ll i=62;i>=0;--i) {
        if ((M>>i)&1) {
            ll cnt=opS/(1ll<<i);
            opS-=min(cnt,num_a)*(1ll<<i);
        }
    }
    if (opS==0) {
        return true;
    }
    return false;
};

AC代码

AC
https://codeforces.com/contest/2203/submission/364386484

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

Posted on Edited on

基本情况

image

两道题目，哎，还好这个B做的快是吧，绷不住了。

当然了，小号其实也无所谓。嗯，其实也还好不过之后呢，我觉得还是把这个号打上去以后，还是用这个号打。其实，你一直没分数，其实也没什么意思，就是那种比较刺激的那种感觉是吧。

OK，我们说回来。这个D为什么交了5发还是没过呢？主要是因为就是这个D，它的数据量比较大。使用Victor victor或者victor的这种调和级数写法呢，它这个时间会超。可以使用vis 数组标记所有 a 的倍数。这样子可以避免卡常。

1
2
3
4
5
6
7
8
9
10
ll cnt_un_divide=0,cnt_all_divide=0;
vector<char> vis(N+M+2);
for (auto a:A) {
    for (ll i=1;i<=N+M;++i) {
        if (i*a>N+M) {
            break;
        }
        vis[i*a]=true;
    }
}

然后为什么标题里面提了不要用 while 循环？是因为涉及累加的逻辑（在 D 的对拍暴力程序当中），直接 continue 以后，while 循环的这个累加就崩掉了。

A 就是一个向上取整除法，没什么好说的。

B 也简单，就是猜一下，我猜，只有这个 digit 总和小于 10 的情况下，题设条件才成立。注意前导 0，不要不小心进行操作后出现前导 0。

可以在排序前，对第一个数减 1，让其被操作后至少保留 1。

1
2
sn[0]--;
sort(all(sn),greater<>());

心得感悟

Posted on Edited on

题目大意

题目描述

给定一个长度为 nn 的合法括号序列 SS。

我们定义对 SS 的一个子序列进行向右循环移位操作：选中子序列所在的位置 i1,i2,…,iki_1, i_2, \dots, i_k，将这些位置上的字符同时更新为：

  • Si1←SikS_{i_1} \leftarrow S_{i_k}

  • Si2←Si1S_{i_2} \leftarrow S_{i_1}

  • Si3←Si2S_{i_3} \leftarrow S_{i_2}

  • …\dots

  • Sik←Sik−1S_{i_k} \leftarrow S_{i_{k-1}}

也就是说，选中的这些位置上的字符整体向右移动一位，最后一个字符移动到第一个被选中的位置。

例如，对于括号序列 ()(()())：

  • 若选中第 22 和第 44 个位置的字符（分别是 ) 和 (），移位后第 22 个位置变为 (，第 44 个位置变为 )，序列变成 ((())())。

  • 若选中第 22、33、55 个位置的字符（分别是 )、(、)），移位后第 22 个位置变为 )，第 33 个位置变为 )，第 55 个位置变为 (，序列变成 ())((())。

请计算有多少个非空子序列，使得在对其进行向右循环移位后，原序列 SS 仍然是一个合法的括号序列。由于答案可能很大，请输出其对 998244353998244353 取模的结果。

注：两个子序列如果选中的位置集合不同，则被认为是不同的子序列。

输入格式

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

  • 第一行包含一个偶数 nn（2≤n≤3000002 \le n \le 300000），表示括号序列的长度。

  • 第二行包含一个长度为 nn 的合法括号序列 SS。
    保证所有测试用例中 nn 的总和不超过 300000300000。

输出格式

对于每个测试用例，在一行中输出一个整数，表示满足条件的非空子序列数量对 998244353998244353 取模的结果。

样例输入

1
2
3
4
5
6
7
8
9
4
2
()
4
()()
6
(()())
10
()((())())

样例输出

1
2
3
4
2
8
28
312

样例解释

对于第二个测试用例 ()()，以下 88 个非空子序列在向右移位后能使原序列保持合法：

  • 仅选中位置 11：移位后序列为 ()()

  • 仅选中位置 22：移位后序列为 ()()

  • 仅选中位置 33：移位后序列为 ()()

  • 仅选中位置 44：移位后序列为 ()()

  • 选中位置 11 和 33：移位后序列为 ()()

  • 选中位置 22 和 33：移位后序列为 (())

  • 选中位置 22 和 44：移位后序列为 ()()

  • 选中位置 11、22、33：移位后序列为 (())

image

这个就是所谓的right shift操作，那么其实就是向右循环移动一位。题目给你一个正规合法的括号串，问你在所有子序列当中，哪些子序列在进行了right shift操作以后还是合法的括号串（注意，子序列进行了right shift操作后，会反作用于原来的正规合法括号串，那么我们就是要看原来的正规合法括号串，在进行了这个操作以后是否还合法）。

思路讲解

对括号串一个比较有用的工具就是这个把括号看成 1，-1，合法的括号串就是其前缀和时刻都不为负数。（当然末尾必须是 0）

这样子我们就能够非常直观的看出，循环移动的影响范围只是从其第一个子序列的 id，到最后一个子序列的 id，其他的启示是不会影响的，因为对于他们的前缀和来说，包含的元素没有变化，和自然也没有变化。

有很多人觉得这道题目是 dp，认为是什么计数 DP 什么之类的，我觉得这个很难算是一个 DP, 或者说你如果你告诉一个比较拉的人，跟他讲这道题是 DP，他肯定是做不出来的，嗯，它更多的还是根据一个性质，然后去进行这么一个做法吧。

首先啊，我们使用前缀和工具不难得出这一结论：

image

然后我们就要想办法使用该结论进行计数。

哦，我们解释一下这个代码里面的各个东西吧。首先是这个 sum_dp 其实指的是这个包含 ）的这个答案数量。lans 计算出来就是这个所有包含这一位 ）的这个答案。

我们现在的目标，就是需要计算一下，如果要给下面一个 ） 用的话，合法的，只包含（ 的子序列有几个 ？这个数量就是 valid_no_right，那么，我们其实就是要知道，当前，没有 ）的子序列（当然是合法的），有多少个？实际上，要求出这个值，最好的方法就是从 lans 里面去求。lans 实际上是 i 自家带的兵，然后从所有的其他地方的兵转移过来的，那么这个其他地方的兵分为从带 ）的兵和不带这个的兵。那么 lans-sum_dp 是什么东西呢？这样子看，实际上很难看出来，我们不妨从目标下手，我们其实就是要把所有带 i 这个 ） 的给除掉。

那么 lans−sumdplans-sumdp 实际上其实就是：

lans←2i−1−upi−invalidCnt(lans−1)×sumdplans\gets 2^{i-1-upi-invalidCnt}\\(lans-1)\times sumdp

这里一大长串的2的次方实际上就是最初的 lans。那么这里的 lans-1 实际上是把只选了） 的情况给去掉，我们之所以会产生困惑，其实是我因为我们对 lans 有疑问，实际上 lans 是强制选取 i 的 ）的，所以排除只选 ） 的情况，只需要 -1 即可。

1
2
3
4
5
6
7
8
ll lans=binpow(2,i-1-up_i-invalid_cnt);
lans*=(sum_dp+valid_no_right);
lans%=mod;
if (pre_sum[i]>1) {
    valid_no_right=lans-sum_dp;
}else {
    valid_no_right=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
for (int i=1;i<=N;++i) {
    if (s[i]=='(') {
        // 这个分支应该是没有什么问题
        // 因为这计数已经是顶格了，而且往前移动左括号，绝对是保险的
        ans+=binpow(2,i-1);
        ans%=mod;
        if (pre_sum[i]<=1) {
            invalid_cnt++;
        }
    }else {
        // 其实和等效第一位，第一位都没什么关系
        // 具体来讲，应该是：在所选子序列的元素中，如果出现形如 (((...) 的模式——即一段连续的（子序列意义上的）( 后面跟着一个 )，设第一个 '(' 在原串中的位置为 l，')' 的位置为 $r$，那么原串在 [l, r) 区间内不允许出现 pre_sum ≤ 1 的位置。
        // 这里不需要分这个 i 是 N 和不是 N 的情况，因为实际上来说，最后一个地方的前缀和一定是 0
        // 如果最后是 ( ，那么前缀和为负数的情况一定更早爆发了
        ll lans=binpow(2,i-1-up_i-invalid_cnt);
        lans*=(sum_dp+valid_no_right);
        lans%=mod;
        if (pre_sum[i]>1) {
            valid_no_right=lans-sum_dp;
        }else {
            valid_no_right=0;
        }
        sum_dp+=lans;
        sum_dp%=mod;
        ans+=lans;
        ans%=mod;
        up_i=i;
        invalid_cnt=0;
    }
}

AC代码

AC
https://codeforces.com/contest/2202/submission/364279343