Znzryb's Blog
0%

Posted on

题目大意

题目描述

给定 nn 个秘密单词组成的列表，以及一个目标文本 TT。
目标文本 TT 由小写英文字母和符号 ? 组成。其中 ? 是通配符，可以匹配秘密单词中的任意一个字母。
你需要求出有多少种方法，可以将整个文本 TT 完全拆分为列表中的单词。
每个单词可以使用任意多次。
输出方案数对 109+710^9 + 7 取模的结果。

输入格式

第一行包含一个整数 nn (1≤n≤1001 \le n \le 100)。
接下来 nn 行，每行一个字符串 WiW_i (1≤∣Wi∣≤101 \le |W_i| \le 10)，保证所有单词互不相同。
最后一行包含一个字符串 TT (1≤∣T∣≤1001 \le |T| \le 100)。

样例 1

1
2
3
4
5
6
7
8
9
7
a
b
c
d
ab
bc
cd
ab?d

输出 1

1
11

样例 1 解释

目标文本为 ab?d。? 可以匹配任意字符，即此处的 ? 需要根据选用的单词被“填充”。
可能的拆分方式包括：

  1. [a, b, a, d] （第三个单词为 a，此时 ? 匹配 a）

  2. [a, b, b, d] （? 匹配 b）

  3. [a, b, c, d] （? 匹配 c）

  4. [a, b, d, d] （? 匹配 d）

  5. [ab, a, d]

  6. [ab, b, d]

  7. [ab, c, d]

  8. [ab, d, d]

  9. [a, bc, d]

  10. [a, b, cd]

  11. [ab, cd]

样例 2

1
2
3
4
2
a
b
??

输出 2

1
4

样例 2 解释

目标文本为 ??。
可能的拆分方式包括：

  1. [a, a]

  2. [a, b]

  3. [b, a]

  4. [b, b]

思路讲解

采用线性 DP 的方式啊，采用线性 DP 的方式。

这题的陷阱就是啊，至少是我踩中的陷阱啊。就是采用了区间 DP 的方式，因为毕竟这个数据范围比较小嘛，很容易想到区间 DP 啊。不过区间 DP 它会，虽然说二叉分裂是不同的，但是划分方式是相同的，是会有这种情况的发生。

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
for (int i=0;i<N;++i) {
    for (int len=1;len<=10;++len) {
        if (i-len+1<0) {
            break;
        }
        // 一个 string view 啊，这个 view 就是从 i 减 len 加一开始，长度为 len 的一个 view。
        string_view s_view(s.data()+i-len+1,len);
        ll valid_num=0;
        // 这个循环就是计算 valid num 的数量。说白了就是长度为 len 的合法单一划分数量。
        for (auto &ls:len_words_mtx[len]) {
            bool ok=true;
            for (int j=0;j<SZ(ls);++j) {
                if (ls[j]==s_view[j] || s_view[j]=='?') {

                }else {
                    ok=false;
                }
            }
            if (ok) {
                 valid_num++;
            }
        }
        // 从 i - len 处转移，一共有 valid num 种转移方法，所以说是乘法原理。
     // 注意 i - len 为小于零的时候是空，也是 1 种合法的方案。
        dp[i]+=(i-len<0?1:dp[i-len])*valid_num;
        dp[i]%=mod;
    }
}

AC代码

AC

https://codeforces.com/gym/106169/submission/363004216

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

Posted on

题目大意

题目名称：C. You can’t just take and divide（你不能只是拿来分析）

题目描述：
Anatoly 和 Antitoly 对资源的分配有不同的看法。Antitoly 正在开发一个由参数 nn 定义的理想社会模型。你需要帮他计算在区间 [1,n][1, n] 中，有多少个整数 xx 同时满足以下两个条件：

  1. xx 是奇数。

  2. xx 的因子个数是奇素数。

输入格式：
第一行包含一个奇整数 nn (3≤n≤111133 \le n \le 111^{13})。注意数据范围非常大，需使用能够处理大数的类型或高精度。

输出格式：
输出一个整数 RR，表示满足条件的 xx 的个数。

样例 1

1
2
3
4
5
输入：
3

输出：
0

样例 1 解释：

  • 1 的因子个数为 1（奇数但不是素数）。

  • 2 是偶数。

  • 3 的因子个数为 2（素数但不是奇数）。
    没有满足条件的数。

样例 2

1
2
3
4
5
输入：
5

输出：
0

样例 2 解释：

  • 接续样例 1，新增 4 和 5。

  • 4 的因子个数为 3（奇素数），但 4 本身是偶数。

  • 5 的因子个数为 2（偶素数）。
    没有满足条件的数。

样例 3

1
2
3
4
5
输入：
9

输出：
1

样例 3 解释：

  • 接续样例 2，新增 6, 7, 8, 9。

  • 6, 8 是偶数。

  • 7 的因子个数为 2。

  • 9 是奇数，且因子为 1, 3, 9，共 3 个。3 是奇素数，满足所有条件。
    故答案为 1。

样例 4

1
2
3
4
5
输入：
111

输出：
4

样例 5

1
2
3
4
5
输入：
9753113579

输出：
9563

思路讲解

ABC-383-D - 9 Divisors 

使用因数个数定理，或者说是约数个数定理。

image

其实使用约束个数定理不难得出如下的结论，那么 P 的 e1 次方就是我们所要枚举得出的这个数。

pe1; e1+1,p∈{3,5,7,11,⋯ }（除了2的所有素因数）p^{e1};\ e1+1,p\in\{3,5,7,11,\cdots\}（除了 2 的所有素因数）

由于 e1 是从这个 2 开始的，所以我们直接遍历的时间复杂度是 O(n)O(\sqrt n)。

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
void Solve() {
    ll N;
    cin >> N;
    sieve(1e7);
    ll ans=0;
    // 我们这里实际上是在遍历的是 e1 加一。
    for (auto e1:primes) {
        if (e1==2) continue;
        for (auto p:primes) {
            if (p==2) continue;
            __int128 num=1;
            // 因为我们上面便利的是 e1+1，所以说这边就乘 e1-1 次。
            for (int i=1;i<=e1-1;++i) {
                num*=p;
            }
            if (num>N) {
                if (p==3) {
                    cout<<ans<<"\n";
                    return;
                }
                break;
            }else {
                ++ans;
            }
        }
    }
}

AC代码

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

Posted on Edited on

题目大意

题目名称：E2. Interactive Graph (Hard Version)（交互式图困难版）

题目描述
这是一个交互题。
后台有一个包含 nn 个顶点和 mm 条边的有向无环图（DAG），图中没有自环和重边。
你的任务是在最多进行 n+mn + m 次询问的情况下，确定图中所有的边。

你可以进行如下格式的询问：
? k

系统会返回该图中按字典序排列的所有路径列表中的第 kk 条路径。

  • 路径定义：一个顶点序列 u1,u2,…,ulu_1, u_2, \dots, u_l，满足图中存在边 (ui,ui+1)(u_i, u_{i+1})。

  • 字典序定义：序列 aa 小于序列 bb 当且仅当 aa 是 bb 的真前缀，或者在两者第一个不同的位置上，aa 的元素小于 bb 的元素。

  • 返回格式：系统首先返回路径长度 qq。如果 q=0q=0，表示不存在第 kk 条路径；否则，随后返回 qq 个整数表示该路径的顶点序列。

  • 数据范围：1≤n≤301 \le n \le 30，1≤k≤2301 \le k \le 2^{30}。

输出格式
当你确定了所有边后，输出 ! m，随后输出 mm 行，每行两个整数 u,vu, v，代表存在一条从 uu 到 vv 的有向边。

样例

Input

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
3
5

1 1

2 1 2

3 1 2 4

3 1 2 5

2 1 3

3 1 3 4

3 1 3 5

1 2

1 3

1 4

1 5

1

0

2

1 1

1 2

2 2 1

Output

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


? 1

? 2

? 3

? 4

? 5

? 6

? 7

? 8

? 11

? 14

? 15

! 6
1 3
1 2
2 4
3 4
2 5
3 5

? 2

! 0

? 1

? 2

? 3

! 1
2 1

样例解释
以第一个测试用例为例：

  • n=5n=5。

  • 程序依次询问了第 1, 2, …, 15 条路径。

  • 例如，? 3 返回了 3 1 2 4，表示字典序第 3 小的路径是 1→2→41 \to 2 \to 4。

  • 通过这些路径信息，程序最终判断出图中有 6 条边，并输出了它们（如 1→31 \to 3, 1→21 \to 2 等）。

思路讲解

image

那么我们把我们可以记忆化的东西已经全部在图上标出来了。我们为什么要记忆化呢？其实我们的目标就在于，我们每次询问啊，我们都尽量想比较好的去找到它的出边，是吧？

如果有大量的这个路径，它实际上是没有什么信息的增量的。它大量的这个路径啊，就是它没有什么信息的增量。

比如说我们来看12这个路径，它就告诉了我们从12有一条出边。然后我们现在想要看1还有哪些出边，那么这个时候124、125实际上没有给我们带来信息的增量，但是13啊又给我们带来了信息的增量，但是134，135。但实际上又没有了信息的增量。所以我们就要想办法去跳过没有信息增量的东西。比如说12，它没有信息的增量。就是1~2以后，然后我们查找到 cnt 2实际上有3个，然后我们直接便利到12的时候，我们就直接跳到13，是不是就会好很多？

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
auto solve=[&](auto && self,ll u,ll cur_k) ->  void {
  // 以前已经遍历到过了，这里就直接 return 就好了。
  // 我们都是把返回值放在数组里面的，所以我们的返回类型是 void。
    if (cnt_ls[u]) {
        return;
    }
    vis[u]=1;
    cnt_ls[u]=1;
    while (true) {
        vector<ll> res=query(cur_k+cnt_ls[u]);
        auto it=find(all(res),u);
        // 这个 it 不能够往后移的，这个迭代器不能够往后移的
        // 那就说明没有 to 这个点了，我们就直接退出即可。
        if (it==res.end() || it==prev(res.end())) {
            return;
        }
        ll to=*next(it);
        self(self,to,cur_k+cnt_ls[u]);
        edges.push_back({u,to});
        cnt_ls[u]+=cnt_ls[to];
    }
};
ll cur_k=0;
for (ll u=1;u<=N;++u){
    if (!vis[u]) {
        solve(solve,u,cur_k+1);
    }
    // 注意，即便是已经被 vis 的点，就即便是已经遍历过的点，我们仍然需要去跳过这些点。
    // 跳过的方式就是给目前的这个 K 加上这个 cnt_ls[u]。
    cur_k+=cnt_ls[u];
}

AC代码

AC
https://codeforces.com/contest/2197/submission/362863587

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

Posted on Edited on

题目大意

题目大意

巴瑟普顿大学（Bithampton）有一条通往市中心的公交线路，沿途设有多个停靠站。当前有 nn 名学生在大学（第 0 站）排队等车，每位学生都有一个确定的目的地站点。

公交车按固定时间间隔发车，第一辆车在时刻 0 到达，之后每隔 rr 秒有一辆车到达。每辆公交车的容量无限，司机可以决定让队列最前端的多少人乘坐当前这辆车。

为了应对拥挤，公交公司规定了特殊的上下车规则：
如果车上有任何一名乘客的目的地是当前站点，则车上所有乘客都必须下车。未到达目的地的乘客随后需要重新上车继续行程。

时间计算规则如下：

  1. 上下车耗时：每有一名乘客上车或下车，公交车都需要等待 ww 秒。
  • 在起点上车：耗时为（上车人数 ×w\times w）。
  • 在途中站点下车：耗时为（车上总人数 ×w\times w）。
  • 在途中站点重新上车：耗时为（继续行程人数 ×w\times w）。
  1. 行驶耗时：站点之间的行驶时间给定。

你的目标是为每辆公交车分配乘客（即决定每次从队首取多少人上车），使得所有学生到达各自目的地的耗时中的最大值最小。

输入格式

第一行包含四个整数 n,b,r,wn, b, r, w (1≤n,b≤105,1≤r,w≤1061 \le n, b \le 10^5, 1 \le r, w \le 10^6)，分别表示乘客总数、站点总数、公交车发车间隔、上下车每人次的耗时。
第二行包含 bb 个整数 did_i (1≤di,∑di≤1061 \le d_i, \sum d_i \le 10^6)，表示从第 i−1i-1 站行驶到第 ii 站所需的时间。
第三行包含 nn 个整数 tit_i (1≤ti≤b1 \le t_i \le b)，按队列顺序给出第 ii 个人的目的地站点编号。

输出格式

输出一个整数，表示让所有人都到达目的地所需的最小的最大时间。

样例数据

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

Output
18

Input
4 2 1 10
3 2
1 2 2 1

Output
27

Input
5 3 3 3
2 2 1
3 3 2 1 1

Output
17

样例解释

在第一个样例中，最优策略是让所有 3 个人都乘坐第一辆车（时刻 0 到达）。

  1. 起点（大学）：3 人上车，耗时 3×1=33 \times 1 = 3 秒。此时车上人员目的地为 {2,3,1}\{2, 3, 1\}。

  2. 行驶至站点 1：耗时 2 秒。到达时刻 3+2=53+2=5。

  3. 站点 1：此时有一人（目的地为 1）需要下车。规则要求所有人下车。

  • 3 人下车，耗时 3×1=33 \times 1 = 3 秒。时刻 5+3=85+3=8。该乘客到达。
  • 剩余 2 人（目的地 2, 3）重新上车，耗时 2×1=22 \times 1 = 2 秒。时刻 8+2=108+2=10。

  1. 行驶至站点 2：耗时 2 秒。到达时刻 10+2=1210+2=12。

  2. 站点 2：此时有一人（目的地为 2）需要下车。

  • 2 人下车，耗时 2×1=22 \times 1 = 2 秒。时刻 12+2=1412+2=14。该乘客到达。
  • 剩余 1 人（目的地 3）重新上车，耗时 1×1=11 \times 1 = 1 秒。时刻 14+1=1514+1=15。

  1. 行驶至站点 3：耗时 2 秒。到达时刻 15+2=1715+2=17。

  2. 站点 3：最后一人下车。

  • 1 人下车，耗时 1×1=11 \times 1 = 1 秒。时刻 17+1=1817+1=18。该乘客到达。

所有乘客到达时间的最大值为 18。

思路讲解

这个 Opus 4.6给出的提示非常好，就是二分还是二分那个答案，答案就是最大的到达时间。但是，然后我们给出了一个中间量，我们给出了一个中间量，这个中间量是什么呢？这个中间量就是一辆车可以最长运行多长时间。不过我们其实没有意识到一件事情啊，就是其实一辆车可以最长运行多长时间，可以非常自然的使用这个答案推出来。

下面这个代码，核心的这个代码中的注释，我认为已经非常详细了。我就不多说了，这道题目核心就是这个 check 函数嘛，这个 check 函数的核心已经在上面讲过了。说白了二分答案，首先需要想的就是是不是一定要二分这个答案？可不可以二分其他的东西？当然了，这道题目当然了，就是如果发现你找了一个东西，但是你发现它好像没那么容易二分，或者你觉得好像有点奇怪。这个时候就需要想这个东西和答案之间是不是有什么关系。比如说我我们想到的这个参数，班次的最长运行时间，那么我们发现其实是和这个答案是有关系的。或者你可以换一种角度，就这个答案往往无法指导我们直接进行选择，进行抉择。我们需要对答案进行一些转化，以便指导我们，进行选择与抉择。

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
auto check=[&](ll b_ans) -> bool {
    ll idx=1;
    // 第几班次
    for (ll run=1;run<=N;++run) {
        if (idx>N) {
            return true;
        }
        ll st_run=(run-1)*R_wait;
        // 该班次最大运行时间
        ll mx_run=b_ans-st_run;
        if (mx_run<0 && idx<=N) {
            return false;
        }
        ll cur=0;
        ordered_set pbds;
        // 我们下面的注释里面详细说了为什么不需要算他的零站上去的那个情况，实际上已经被我们的二乘 pre 乘以 tim 给覆盖了。
        // pbds.insert(0);
        ordered_pair_set multi_pbds;
        ll mx_terminal=0;
        while (true) {
            if (idx>N) {
                return true;
            }
            // 我们目前是需要算，加上这个 IDX 对于我们目前运行时间的增量。
            // 这个增量分为两部分，一个是我们带来的增量，就是我们给等待时间所有的带来的增量。
            // 所有的站，所有在我们之前的站的等待时间（包括我们自己这一站），都需要加上我们下车的这个时间。
            ll terminal=t_ls[idx];
            mx_terminal=max(mx_terminal,terminal);
            ll pre=pbds.order_of_key(terminal)+1;
            // 你可能会说这个零站点到底是在哪里被加了呢？
            // 那么其实就是在这个 add，这个2× pre 乘以 W tim 里面，就我们就加了这个零站点。
            // 实际上，PRE 是包含 TERMINAL 这个站的，但是这个人在 TERMINAL 站，他下来以后就不会上去了。
            // 所以二乘以 PRE，那么实际上包含他在零站上去的这个情况。他在零站上去的情况正好弥补了
            // 我们多算的他在 TERMINAL 站下来的这个情况，
            ll add=2*pre*W_tim;
            if (pbds.find(terminal)==pbds.end()) {
                // 如果这个 terminal 之前没有出现过，那么所有在其之后的也需要贡献对这个 terminal 进行贡献。
                // 所以在其之后的原来就在他之后的点需要对这个 terminal 进行贡献。
                // 这里我们使用一个pair 实现的 multi pbds 实现。
                ll suf=SZ(multi_pbds)-multi_pbds.order_of_key({terminal,INF});
                // 所有在其后面的点都需要在该站下去以后再上来，所以说是 2*suf*W_tim
                add+=2*suf*W_tim;
            }
            if (cur+add+pre_sum[mx_terminal]>mx_run) {
                break;
            }
            cur+=add;
            pbds.insert(terminal);
            multi_pbds.insert({terminal,idx});
            ++idx;
        }
    }
    // 如果说大于 N 那么就说明所有的乘客都被处理完了。
    return idx>N;
};

AC代码

AC
https://qoj.ac/submission/2035388
AC
https://codeforces.com/gym/106129/submission/362933869

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

被 OPUS 4.6指出来的几个 bug。其实主要就是没有乘二，就是这个 pre 还有这个 suf 没有乘二，绷不住了。忘记了，他不仅要上来，还要下去。就是他不仅要下去，还要再上来。所以相当于这个浪费还是挺多的，需要2，需要乘2。

image

Posted on

题目大意

题目大意
有一只魔法山猫会对你进行 nn 次攻击，每次攻击有一个潜能值 pip_i。你最终受到的痛苦值为所有未被防御的攻击潜能值的 mex\text{mex}（即未出现在这些潜能值集合中的最小自然数）。

你拥有一个盾牌，激活后可以持续防御接下来的 dd 次攻击。盾牌失效后会强制进入冷却，冷却时间同样持续 dd 次攻击，冷却期间无法再次激活。你可以多次激活盾牌，最早可以在第 1 次攻击前激活。

请制定最佳防御策略，使得受到的痛苦值最小。

输入格式
第一行包含两个整数 nn 和 dd (1≤n≤1051 \le n \le 10^5, 1≤d≤n1 \le d \le n)，分别表示攻击总数和盾牌持续/冷却时间。
第二行包含 nn 个整数 p1,…,pnp_1, \dots, p_n (0≤pi<n0 \le p_i < n)，表示每次攻击的潜能值。

输出格式
输出一个整数，表示可以达到的最小痛苦值。

样例 1

1
2
5 1
0 1 0 1 0
1
0

解释：d=1d=1。可以在第 1、3、5 次攻击时激活盾牌（防御区间为 [1,1],[3,3],[5,5][1,1], [3,3], [5,5]），冷却区间为 [2,2],[4,4][2,2], [4,4]。此时只有潜能为 1 的攻击击中你，mex({1,1})=0\text{mex}(\{1, 1\}) = 0。

样例 2

1
2
5 2
0 1 0 1 0
1
2

解释：d=2d=2。无论如何安排，冷却期间总会漏掉潜能为 0 和 1 的攻击。击中你的集合包含 {0,1}\{0, 1\}，mex≥2\text{mex} \ge 2。

样例 3

1
2
14 2
8 1 1 0 0 2 0 1 2 1 0 6 4 2
1
2

image

可以像图上一样防御。

样例 4

1
2
4 2
0 1 2 0
1
1

解释：最早只能在第 1 次攻击前激活，无法同时防御住第 1 个和第 4 个潜能为 0 的攻击（因为防御完第 1 个后，盾牌在第 2、3 个攻击期间防御，第 4 个攻击时可能刚结束或者在冷却，取决于具体激活时机，但无法跨越防御第 1 个和第 4 个而不防御中间的）。选择防御第 2、3 个攻击，漏掉第 1、4 个攻击（潜能均为 0），mex({0,0})=1\text{mex}(\{0, 0\}) = 1。

思路讲解

这道题目其实不是很难，其实就是维护一下可行域就可以了。

那么初始的可行域是从一，就是初始的可行域的左起点是 Max 一和 P 减 d 加一。右起点就是 P。然后在后面的过程当中，我们去不断的更新左起点。一旦当左起点它比右起点还大的时候，左起点比右起点大的时候呢，这个时候就说明我们需要新开一个区间了。然后我们新开区间的左起点，就是可行域的左端点，就是 L 加2乘以 d 和 P 减 d 加一中取一个 max 如果说然后这个可行域的 R 就是 P 。如果说 L 大于 R 那就说明就进不了可行域。就这个是错的，就 return false 就好了。

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
// 哦，这道题目的难点就在于这个 check 函数
// 负责检查该 VAL 是否可以被我们的防御魔法所全部覆盖
auto check=[&](ll val) -> bool {
    if (g[val].empty()) {
        return true;
    }
    // 维护一段可行起点区间
    // 下面是起始的可行域。
    ll l=max(1ll,g[val][0]-D+1),r=g[val][0];
    for (int i=1;i<g[val].size();++i) {
        ll p=g[val][i];
        ll to_l=max(l,p-D+1);
        // 我们先要检查一下这个 L 啊，这个 L 如果超过这个 R 了以后，我们就需要新建一段区间了。
        if (to_l>r) {
            l=max(l+2*D,p-D+1);
            r=p;
            if (l>r) {
                return false;
            }
        }else {
            l=to_l;
        }
    }
    return true;
};

AC代码

AC
https://qoj.ac/submission/2032675
AC
https://codeforces.com/gym/106129/submission/362772763

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

这个 check 函数是负责什么呢？是负责检查该 VAL 是否可以被我们的防御魔法所全部覆盖。直接采用这个贪心啊，它其实是没那么简单的。因为虽然说第一个我们肯定是要覆盖的，但是呢我们并不一定要在第一个位置就启用这个防御魔法，我们可以在其更前面的位置启用这个防御魔法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 哦，这道题目的难点就在于这个 check 函数
auto check=[&](ll val) {
    ll st=-INF;
    for (auto p:g[val]) {
        if (p-st+1<=D) {
            continue;
        }
        if (p-st+1<=2*D) {
            return false;
        }
        st=p;
    }
    return true;
};