Znzryb's Blog
0%

Posted on Edited on

基本情况

https://codeforces.com/contest/2207

image

两道题目，排 2705 还可以，还不赖，感觉。

当然还是有进步的这个空间的。

心得感悟

就是这个 B，哎，感觉基本上是想到了，但是没关注到一个关键的这个数据范围限制。

一定要关注数据范围限制。

image

你看到这个，基本就知道简单的贪心和这个二分答案是解决不了的。

题目 A. 1-1

题目描述
给定一个长度为 nn 的 01 字符串 ss。
在一次操作中，如果存在某个位置 ii（2≤i≤n−12 \le i \le n-1）满足其左右相邻的字符均为 1（即 si−1=si+1=1s_{i-1} = s_{i+1} = 1），则可以随意将 sis_i 修改为 0 或 1。
该操作可以执行任意次（包括零次）。你需要求出经过操作后，最终字符串中 1 的数量的最小值和最大值。

输入格式
第一行包含一个整数 tt（1≤t≤5001 \le t \le 500），表示测试数据的组数。
每组数据包含两行：
第一行为一个整数 nn（3≤n≤1003 \le n \le 100），表示字符串的长度。
第二行为一个长度为 nn 的 01 字符串 ss。

输出格式
对于每组数据，输出两个整数，分别表示最终字符串中包含 1 的数量的最小值和最大值。

样例输入

1
2
3
4
5
6
7
8
9
4
3
111
6
011011
7
1011101
9
100101101

样例输出

1
2
3
4
2 3
3 5
4 7
5 7

样例解释
在第一组样例中：

  • 最小数量为 22。操作过程：111 →\rightarrow 101。

  • 最大数量为 33。不进行任何操作即可。

在第二组样例中：

  • 最小数量为 33。操作过程：011011 →\rightarrow 011111 →\rightarrow 010111 →\rightarrow 010101。

  • 最大数量为 55。操作过程：011011 →\rightarrow 011111。

https://codeforces.com/contest/2207/problem/A

就是贪心，不难发现，就是能操作的就操作（变为 1），那么得到就是最多的答案。

接着在能操作的就操作（变为 1），变好的这个串的前提下，然后能操作的就操作（变为 0），得到的就是最少的答案。

想到这样的方法，一个是 leetcode 好像做过类似思想的题目（和父亲讨论过，没做），还有就是我发现这个进行这个 1 操作后，继续进行 0 操作，得到的答案总归不是不优的，至少是比直接进行 0 操作一样，或者更好。

https://codeforces.com/contest/2207/submission/365935923

题目 C. Where’s My Water?

题目描述
给定一个高度为 hh、列数为 nn 的网格。在第 ii 列中，最底部的 aia_i 个格子是泥土，其上方的格子全是水。
你可以在任意一个水格子上放置排水口，最多可以放置两个。
每个排水口可以排走所有能够通过仅向下、向左或向右移动（且不穿过任何泥土格子）到达该排水口的水格子。被两个排水口共同覆盖的水格子只会被计算一次。
求在最多放置两个排水口的情况下，能够排走的最大水格子总数。

image

输入格式
第一行包含一个整数 tt（1≤t≤1031 \le t \le 10^3），表示测试数据组数。
每组数据第一行包含两个整数 nn 和 hh（1≤n≤20001 \le n \le 2000，1≤h≤1091 \le h \le 10^9），分别表示网格的列数和高度。
第二行包含 nn 个整数 aia_i（1≤ai≤h1 \le a_i \le h），表示第 ii 列泥土格子的高度。
保证所有测试数据中 nn 的和不超过 20002000。

输出格式
对于每组数据，输出一个单行整数，表示最多能排走的水格子数量。

样例

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

Output
14
43
0
170
3738738738
999999999

样例解释
在第一组样例中，网格列数为 77，高度为 44。通过在合适的位置放置两个排水口，最多可以排走 1414 个水格子。
在第二组样例中，网格列数为 88，高度为 1010。通过合理放置两个排水口，可以排走网格中全部的 4343 个水格子。
在第三组样例中，网格大小为 1×11 \times 1，且唯一的格子是泥土，没有水格子，无法放置排水口，因此输出 00。

https://codeforces.com/contest/2207/problem/C

不难发现，这道题目，应该是直接枚举两个的这个抽水的位置，然后 O(1)O(1) 计算其所抽的水。

当然，为了实现这个常数级别的计算，前面需要进行一个 O(n2)O(n^2) 的预处理。

不难发现，就是抽水棒两边的这个计算（也就是图中绿色部分的计算）是非常容易的。但是中间蓝色问号部分的计算，是这道题目的难点。

image

如果说随意的，错误的进行计算，那么 9 格子就被漏掉了。

image

通过模拟，我们发现，如果两点之间是一个这个山，那么应该以山峰为界，互不干扰。

image

那么山峰是什么东西？就是最大值嘛，这两点之间的最大值的这个坐标就是山峰所在位置。

1
2
3
4
5
6
7
8
9
10
for (int i=1;i<=N;++i) {
    for (int j=i;j<=N;++j) {
        ll lans=0;
        // 最大值位置
        ll pos=dp[i][j];
        lans=pre_area[i][1]+suf_area[i][pos]+pre_area[j][pos]+suf_area[j][N];
        lans-=M-H[i]+M-H[pos]+M-H[j];
        ans=max(ans,lans);
    }
}

https://codeforces.com/contest/2207/submission/365935937

Posted on Edited on

题目大意

题目大意

有一张地图，可以通过若干次贯穿整张纸的水平方向和垂直方向的折叠，最终被折叠成一个 1×11 \times 1 的正方形单位。每次折叠都发生在距离纸张边缘为整数个单位的位置。

当把这张地图重新完全展开时，所有的折痕会把纸张划分成一个 r×cr \times c 的正方形网格。任意两个相邻正方形之间共享的边即为一条长度为 11 的折痕。根据折叠方向的不同，折痕可以分为两种：

  • 峰折（Mountain fold）：向观察者方向折叠而成的凸起折痕。

  • 谷折（Valley fold）：背离观察者方向折叠而成的凹陷折痕。

题目给定一个 (2r−1)×(2c−1)(2r - 1) \times (2c - 1) 的字符矩阵，用来编码展开后的地图折痕状态。矩阵中第 ii 行第 jj 列的字符含义如下：

  • 当 ii 和 jj 均为奇数时，字符为 .，表示一个 1×11 \times 1 的正方形。

  • 当 ii 和 jj 均为偶数时，字符为 +，表示四个正方形相交的角。

  • 其他情况下，字符表示两个相邻正方形之间的折痕：M 表示峰折，V 表示谷折。

任务：给定上述字符矩阵，判断是否能通过上述合法的折叠过程（每次水平或垂直折叠贯穿当前的整张纸，直到折成 1×11 \times 1 大小），在现实中精准复现该矩阵所描述的折痕图案。如果可以，输出 YES，否则输出 NO。

样例及解释

样例输入

1
2
3
4
5
6
7
8
9
10
11
2
3 4
.V.V.M.
M+M+M+M
.M.M.V.
V+M+V+M
.M.M.V.
2 2
.M.
M+M
.M.

样例输出

1
2
YES
NO

样例解释
输入包含两个测试用例：

  • 第一个测试用例给出了一个 (2×3−1)×(2×4−1)(2 \times 3 - 1) \times (2 \times 4 - 1) 即 5×75 \times 7 的字符矩阵，代表一个 3×43 \times 4 的网格。该图案是可以通过规定的折叠方法真实得到的折痕分布，因此输出 YES。

  • 第二个测试用例给出了一个 3×33 \times 3 的字符矩阵，代表一个 2×22 \times 2 的网格。其四周的折痕全为 M（峰折），而在这种必须贯穿整张纸面进行折叠的规则下，无法在现实中构造出这样的折痕组合，因此输出 NO。

image

给你一个这样的矩阵，问可不可能折纸做到？

思路讲解

AC代码

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

Posted on Edited on

题目大意

P13825 【模板】线段树 1.5

题目描述

如题，已知一个长度为 nn

的数列 {ai}\{a_i\}（1≤i≤n1 \leq i \leq n），初始时 aa 序列满足 ai=ia_i = i。你需要进行下面两种操作：

  1. 将某区间每一个数加上 kk。

  2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 n,mn, m，分别表示该数列数字的个数和操作的总个数。

接下来 mm 行每行包含 33 或 44 个整数，表示一个操作，具体如下：

  1. 1 l r k：将区间 [l,r][l,r] 内每个数加上 kk。

  2. 2 l r：输出区间 [l,r][l,r] 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例 #1

输入 #1

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

输出 #1

1
2
3
9
9
18

说明/提示

对于 30%30\% 的数据，n≤8n \le 8，m≤10m \le 10。

对于 50%50\% 的数据，n≤105n \le {10}^5。

对于 100%100\% 的数据，1≤m,k≤1051 \le m,k \le {10}^5，1≤l≤r≤n≤1091 \leq l \leq r \leq n\leq 10^9。

思路讲解

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

/* 
 * 2026-03-08  P13825 【模板】线段树 1.5 动态开点线段树
 * AC https://www.luogu.com.cn/record/266006147
 *
 */
struct Tag {
    // 在母串中的这个位置
    ll add=0;
    bool need_apply=false;
    void apply(const Tag &t) {
        add+=t.add;
        need_apply=true;
    }
};

struct Info {
    ll l=0,r=0;
    i128 sum=0;
    static Info merge(const Info &a,const Info &b) {
        Info res=a;
        res.r=b.r;
        res.sum+=b.sum;
        return res;
    }
    void apply(const Tag&t) {
        if (!t.need_apply) {
            return;
        }
        ll len=r-l+1;
        sum+=len*t.add;
    }
};

// 我认为还是用 C++14 的写法，把你要写的东西传进去比较好，不容易写错
template<class I=Info,class T=Tag>
struct SEG {
    // 如果不需要泛型，可以用下面的来替代
    // using I=Info;
    // using T=Tag;
    struct Node {
        I info;
        T tag;
        Node* rs=nullptr;
        Node* ls=nullptr;
    };

    void init_node(Node *u,ll l,ll r) {
        u->info.l=l;
        u->info.r=r;
        u->info.sum=i128(u->info.l+u->info.r)*(u->info.r-u->info.l+1)/2;
    }

    Node* root=nullptr;
    ll N;

    static bool isIntersect(ll l1, ll r1, ll l2, ll r2) {
        if (!(l1 > r2 || r1 < l2)) return true;
        return false;
    }

    SEG(ll N):N(N) {
        root=new Node();
        root->info.l=1;
        root->info.r=N;
        init_node(root,1,N);
    }

    void extend(Node *u) {
        if (u->ls==nullptr) {
            u->ls=new Node();
            init_node(u->ls,u->info.l,(u->info.l+u->info.r)>>1);
        }
        if (u->rs==nullptr) {
            u->rs=new Node();
            init_node(u->rs,((u->info.l+u->info.r)>>1)+1,u->info.r);
        }
    }

    void push(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        extend(u);
        if (u->tag.need_apply) {
            u->ls->info.apply(u->tag);
            u->rs->info.apply(u->tag);
            u->ls->tag.apply(u->tag);
            u->rs->tag.apply(u->tag);
            u->tag={};
        }
    }
    void pull(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        u->info=I::merge(u->ls->info,u->rs->info);
    }
    void modify(Node*u,ll l,ll r,const T& t) {
        if (u->info.l>=l && u->info.r<=r) {
            u->info.apply(t);
            u->tag.apply(t);
            return;
        }
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            modify(u->ls,l,r,t);
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            modify(u->rs,l,r,t);
        }
        pull(u);
    }

    Info query(Node *u,ll l,ll r) {
        if (u->info.l>=l && u->info.r<=r) {
            return u->info;
        }
        Info res;
        bool is_get=false;
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            res=query(u->ls,l,r);
            is_get=true;
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            if (!is_get) {
                res=query(u->rs,l,r);
            }else {
                res=I::merge(res,query(u->rs,l,r));
            }
        }
        return res;
    }
};

AC代码

AC
https://www.luogu.com.cn/record/266006147

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

不要忘记初始化这个根节点。

image

Posted on Edited on

题目大意

题目设定
给定一个包含 kk（1≤k≤261 \le k \le 26）首短歌的曲库，分别用前 kk 个大写英文字母表示。
由这 kk 首歌可以生成一个无限长的母带（master track）tt。生成方式为：不断重复这 kk 首歌，但在每一次重复整个曲库时，都会将当前序列的第一首歌移动到序列的末尾。
例如，当 k=4k = 4 时，曲库初始为 ABCD，那么母带 tt 就是无限长的字符串 ABCD BCDA CDAB DABC ABCD ...。

有一个长度为 nn 的播放列表，初始时全部为空白。在此问题中，播放列表和母带均从 1 开始索引。

操作要求
需要对播放列表执行 qq 次操作，操作分为以下两种：

  1. + i a b：将播放列表中从位置 aa 到 bb（包含两端）的片段，替换为母带 tt 中从位置 ii 开始、长度为 b−a+1b - a + 1 的子串。

  2. ? a b：查询播放列表中从位置 aa 到 bb（包含两端）的片段。输出 kk 个整数，其中第 jj 个整数表示该片段中第 jj 个英文字母（即第 jj 首歌）的出现次数。

输入格式
第一行包含三个空格分隔的整数 kk、nn 和 qq。
接下来 qq 行，每行描述一个操作，格式为 + i a b 或 ? a b。

输出格式
对于每一个 ? a b 操作，输出一行包含 kk 个空格分隔的整数，表示查询的结果。

数据范围
1≤k≤261 \le k \le 26
1≤n≤1091 \le n \le 10^9
1≤q≤1051 \le q \le 10^5
每次操作中：1≤i≤1091 \le i \le 10^9，1≤a≤b≤n1 \le a \le b \le n

样例输入

1
2
3
4
5
4 10 4
+ 7 2 6
+ 2 8 10
+ 9 1 4
? 4 9

样例输出

1
1 2 1 1

样例解释
在此样例中，k=4k = 4 且 n=10n = 10。母带 tt 为 ABCDBCDACDABDABC...。
播放列表初始为空，我们用星号代表空白部分：**********。

  1. 执行 + 7 2 6：
    我们需要一个长度为 6−2+1=56 - 2 + 1 = 5 的子串。
    母带 tt 中从位置 7 开始、长度为 5 的子串是 DACDA。
    将播放列表中第 2 到第 6 首歌替换为该子串，此时播放列表变为：DACDA****。

  2. 执行 + 2 8 10：
    播放列表第 8 到 10 的位置被替换后变为：DACDA*BCD。

  3. 执行 + 9 1 4：
    覆盖掉前 4 个位置的歌曲，播放列表最终变为：CDABDA*BCD。

  4. 执行 ? 4 9：
    查看当前播放列表中第 4 到第 9 首歌，对应片段为 BDA*BC。
    需要输出 A、B、C、D 四个字母在此片段内分别出现的次数。因此，输出 1 2 1 1。

思路讲解

其实还是很明显的动态开点线段树。我说白了是个动态开点线段树的云玩家，我都看出来是动态开点线段树了。

P13825 【模板】线段树 1.5（指针式动态开点线段树）

既然是这个动态开点线段树，我们想一想，我们的 apply 函数如何书写吧。

其实最重要的是，在知道母带上 l，r 的情况下，求出母带上的 cnt 数组。

get_range_cnt，可以变为 get_pref_cnt®-get_pref_cnt(l - 1)，是一个非常经典的套路。

1
2
3
4
5
6
7
8
array<int, 26> get_range_cnt(ll l, ll r) {
    auto R = get_pref_cnt(r);
    auto L = get_pref_cnt(l - 1);
    for (int i = 0; i < k; ++i) {
        R[i] -= L[i];
    }
    return R;
}

AC代码

AC
https://codeforces.com/gym/106262/submission/365836934

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

image

image

image

Posted on Edited on

题目大意

题目总结

Bob 有 nn 瓶酒精饮料，标号为 11 到 nn。已知第 ii 瓶饮料包含 viv_i 单位的液体体积，其中有 aia_i 单位是纯酒精（0≤ai≤vi0 \le a_i \le v_i）。因此，第 ii 瓶饮料的酒精浓度为 ai/via_i / v_i。每瓶饮料是完全均匀的，从中取出任意体积的液体，其酒精浓度均保持不变。

Bob 可以从这些瓶子中选择任意组合，并从每瓶中取出任意体积（不必须为整数）的液体进行混合。

现在提出一个挑战：
令 V=∑i=1nviV = \sum_{i=1}^n v_i 为所有瓶子中液体的总体积。
在 [0,V][0, V] 区间内均匀随机生成一个实数 ss（目标总体积）；
在 [0,1][0, 1] 区间内均匀随机生成一个实数 ff（目标酒精浓度）。

请计算：Bob 能够成功调配出总体积恰好为 ss、且酒精浓度恰好为 ff 的饮品的概率是多少？（输出结果与标准答案的绝对或相对误差需不超过 10−810^{-8}）。

输入格式
第一行包含一个整数 nn（2≤n≤2×1052 \le n \le 2 \times 10^5）。
第二行包含 nn 个整数，依次为 v1,v2,…,vnv_1, v_2, \dots, v_n（1≤vi≤1091 \le v_i \le 10^9）。
第三行包含 nn 个整数，依次为 a1,a2,…,ana_1, a_2, \dots, a_n（0≤ai≤vi0 \le a_i \le v_i）。

样例输入

1
2
3
3
350 750 330
140 131 16

样例输出

1
0.19356182654786474591

样例解释
在这个样例中，所有液体的总体积 V=350+750+330=1430V = 350 + 750 + 330 = 1430。

我们可以考虑两种具体的情况：
第一种情况：假设生成的 s=500s = 500 且 f=313f = \frac{3}{13}。此时 Bob 是可以成功调配的。例如，他可以从第 11 瓶中取出 97750377\frac{97750}{377} 单位的液体，从第 33 瓶中取出 90750377\frac{90750}{377} 单位的液体。
调配出的总体积为 97750377+90750377=188500377=500\frac{97750}{377} + \frac{90750}{377} = \frac{188500}{377} = 500。
调配出的酒精浓度为：

97750377×140350+90750377×16330500=313 \frac{\frac{97750}{377} \times \frac{140}{350} + \frac{90750}{377} \times \frac{16}{330}}{500} = \frac{3}{13}

第二种情况：假设生成的 s=814s = 814 且 f=0.1234567f = 0.1234567。此时 Bob 是无法完成调配的，因为利用他现有的饮料集合无法混合出该体积和浓度的饮品。

综合考虑所有可能在给定范围内均匀生成的 ss 和 ff 的数值对 (s,f)(s, f)，Bob 能够成功调配的概率约为 0.193561826547864745910.19356182654786474591。

思路讲解

把概率，转化为可行域面积占总面积的比重，这一点对两参数随意取的概率问题特别有用。

image

具体而言，我们的这个分段函数应该长这样：

image

其不定积分是长这样的，带进去值，算一下定积分即可。

image

AC代码

AC
https://qoj.ac/submission/2106344
AC
https://codeforces.com/gym/106262/submission/365722146

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

注意，分段函数不是线性的，而是一个分段反比例函数。

image

不要一会用 x，一会用 v，但是代表同一个意思。

image