Odt03's blog

首先我们从朴素的多重背包转移开始分析。 对于 dpjdp_{j}dpj​ 来说，若 wiw_iwi​ 表示第 iii 个物品的体积， viv_ivi​ 表示第 iii 个物品的价值， kkk 表示选择了几个物品，则转移方程如下： dpj=max⁡k=0ki{dpj,dpj−k⋅wi+k⋅vi}\large{dp_{j}=\max\limits_{k=0}^{k_i} \{ dp_{j},dp_{j-k \cdot w_i} + k \cdot v_i \}} dpj​=k=0maxki​​{dpj​,dpj−k⋅wi​​+k⋅vi​} 时间复杂度 O(NW∑i=1Nki)O(NW \sum\limits_{i=1}^{N} k_i)O(NWi=1∑N​ki​) ，显然在大数据的情况下会 TLE 。 想要优化这个问题，我们要从转移的决策入手。 对于每一个决策点 dpjdp_jdpj​ ，它都是从 dpj−wi,dpj−2⋅wi,dpj−3⋅wi,…,dpj−k⋅widp_{j-w_i},dp_{j-2 \cdot w_i},dp_{j-3 \cdot w_i} , \ldots ,...

按位与和按位或 按位与 (&\And&) 是指在二进制下对两个数的每个数位分别进行与运算，例如： 5&7=(101)2&(111)2=(101)2=55 \And 7 = (101)_2 \And (111)_2 = (101)_2 =5 5&7=(101)2​&(111)2​=(101)2​=5 按位或 (∣|∣) 是指在二进制下对两个数的每个数位分别进行或运算，例如： 5 ∣ 6=(101)2 ∣ (110)2=(111)2=75 \ | \ 6 = (101)_2 \ | \ (110)_2 = (111)_2 =7 5 ∣ 6=(101)2​ ∣ (110)2​=(111)2​=7 注意：按位与（C++ 中为&）逻辑与（C++ 中为&&）、按位或（C++ 中为|）逻辑或（C++ 中为||）不同，请注意区别。 思路 这个题分三种情况。如果 m=nm=nm=n ，显然要操作的次数为 000 ，如果 n ∣ m=mn\ |\ m=mn ∣ m=m 或 n&m=mn \And m=mn&m=m...

题目中 你需要求出有多少整数可能成为 bbb 的众数。 想表达的意思应该是 你需要求出有多少种数可能成为 bbb 的众数。 吧。 所以你输出的是能成为众数的种类数，而不是个数。 解法： 这里我提供一种贪心的做法。 首先只需维护出每一种数出现的次数（因为题目只关心可能成为众数的数的数量）。 接下来我们思考怎样一种数才可能成为众数。 经过 kkk 次修改以后，一种数只有在被修改后出现次数大于等于被修改后出现次数最大的那种数的出现次数时才可以成为众数。 那么每一次修改是什么呢？ 想要让第 iii 种数成为众数，对于每一次修改，我们将除了第 iii 种数外的一个数修改为第 iii 种数。这样就让第 iii 种数出现的次数 +1+1+1 ，让除了第 iii 种数外的一种数出现的次数 −1-1−1 。不难想到，这样可以让第 iii 种数出现的次数最大。 具体来说，设第 iii 种数出现的次数为 viv_ivi​ ，那么它在被操作 kkk 次后出现的次数为 vi+kv_i+kvi​+k ，设经过操作后的最大出现次数为 xxx ，那么第 iii 种数能成为众数的条件是： vi+k≥xv_...

解法 语法题。 由于string每次用cin读入会自动屏蔽掉空格，所以我们只需要定义四个string型变量 a,b,c,da,b,c,da,b,c,d 。对于判断，首字母用s[i]==0，而整个字符串可以用string的性质，直接用s=="ding"就可以了。 注意，一个字符用单引号''括起来，字符串用双引号""括起来。 代码 123456789101112131415#include<bits/stdc++.h>using namespace std;int main(){ int n; cin>>n; while(n--){ string a,b,c,d; cin>>a>>b>>c>>d; //读入四个字符串 if(a[0]=='y'&&b[0]=='y'&&c=="ding"&&d=="zhen"){ ...

Solution: 本题是比较有意思的，我讲一种较好理解的证明方法。 对于每一个染色的连通块的点集 SSS，需要满足以下条件： ∑u:Sdeg(u)≤nS2\sum_{u:S}deg(u) \leq n_S^2 u:S∑​deg(u)≤nS2​ 对于每一个操作，我们寻找度数最大的没有被染色的点 uuu，依次询问 uuu 的临边，如果 uuu 的相邻点 vvv 被染色了，那么把 uuu 和 vvv 染成同一种颜色，否则把 uuu 和其所有临边染成一种新的颜色。 这种贪心的策略需要证明两种问题： 总的询问次数 ≤n\leq n≤n； 需要满足的上述条件。 · 对于每次询问的度数 deg(i)deg(i)deg(i) ， Code: 123456789101112131415161718192021222324252627282930313233343536373839404142// By 0x0F#include <bits/stdc++.h>using namespace std;//#define int long longinline int read() ...

本题考虑使用二分答案。 思路 关于本题单调性的证明：因为显示器的宽度越大，一行能显示的宽度越多，所以显示需要的行数越少（单词总量不变）。所以显示器的宽度和显示需要的行数具有单调递减的关系，所以可以使用二分。 二分枚举显示器的宽度 www，然后计算以 www 为宽度显示单词需要的最少行数，如果需要的行数小于等于 mmm，则符合要求，否则不符合要求。 怎么计算呢？ 如果显示器的宽度 www 小于单词的最大宽度 mwmwmw，说明一个单词都无法放进显示器中，显然是不符合要求的。 令 sumsumsum 表示当前行已经用了多少宽度，cntcntcnt 表示当前用了多少行，一次枚举单词的长度 lil_ili​，如果当前宽度加上一个空格和 lil_ili​ 的长度大于 www，说明当前行已经放不下这个单词了，需要新开一行，让 cntcntcnt 加 111，并且让 sumsumsum 等于 lil_ili​，否则 sumsumsum 加上 lil_ili​ 和一个空格的长度。 时间复杂度：二分的复杂度是 O(log⁡n)O(\log n)O(logn)，计算一遍的复杂度是 O(n)O(n)O...

Solution： 设设个序列为 SSS，如果有一个位置 iii 满足 Si=Si−1S_i=S_{i-1}Si​=Si−1​，那么把 iii 的位置记录下来（也就是说记录两个数相同的位置），由于数据范围是 5×1055 \times 10^55×105 的，所以把位置可以用bool数组存下来，查询时如果 [l+1,r][l+1,r][l+1,r] 内没有被标记的位置，就是合法的，否则是不合法的，我们可以用线段树维护这个数组。 对于修改，显然修改后区间内数的相对关系是不会改变的，修改区间外数的相对关系当然也不会改变，可能改变的只有 [l−1,l][l-1,l][l−1,l] 和 [r,r+1][r,r+1][r,r+1]，所以我们只需要从新判断这两个位置的数的关系是相同的还是不同的，并作出修改就好了。 如何得知修改后每个数是 000 还是 111？我们可以维护一下每个数字被取反了几次，修改时区间加上 111，查询就是 (这个数被取反的次数mod  2+这个数原始的值)mod  2(这个数被取反的次数\mod 2 + 这个数原始的值) \mod 2(这个数被取反的次数mod2+这个...

思路 一种 vector<int>, vector<int> 的 map 做法，代码稍长一些但是特别好想。 先考虑 k=1k = 1k=1 时的做法，后面 kkk 增大时在原基础上改动一点就可以了。 看到左右括号，我们容易想到遇到左括号加 111，右括号减 111，记第到 iii 个位置的前缀和为 sumisum_isumi​。显然，区间 [l,r][l,r][l,r] 若是合法的，必须满足以下条件： 左括号和右括号的数量相等。 在任何位置，前面的右括号个数不能超过左括号。 用数学的形式表达，就是： sumr−suml−1=0sum_r - sum_{l-1} = 0sumr​−suml−1​=0。 对于 [l,r][l, r][l,r] 之间的任意一点 iii，满足 sumi−suml−1≥0sum_i - sum_{l - 1} \geq 0sumi​−suml−1​≥0。 移项，得： sumr=suml−1sum_r = sum_{l-1}sumr​=suml−1​。 对于 [l,r][l, r][l,r] 之间的任意一点 iii，满足 s...

在whk上咕咕的我终于回来了，这用的是数学方法。 Solution 首先 (pi−1)(qi−1)+1(p_i-1)(q_i-1)+1(pi​−1)(qi​−1)+1 什么也看不出来，先拆个括号，就会变成 pi⋅qi−pi−qi+2p_i·q_i-p_i-q_i+2pi​⋅qi​−pi​−qi​+2 这个样子，已知 pi⋅qi=nip_i·q_i=n_ipi​⋅qi​=ni​ 且 pi⋅qi−pi−qi+2=ei⋅dip_i·q_i-p_i-q_i+2=e_i·d_ipi​⋅qi​−pi​−qi​+2=ei​⋅di​ ，就可以得出来两个东西 pi⋅qip_i·q_ipi​⋅qi​ 和 pi+qip_i+q_ipi​+qi​ 。 pi+qip_i+q_ipi​+qi​ 过程： \begin{equation*} \begin{aligned} p_i·q_i-p_i-q_i+2 &= e_i·d_i \\ p_i+q_i &= -(e_i·d_i-p_i·q_i+2) \\ &= p_i·q_i-e_i·d_i...

蒟蒻刚学完线段树不久，写一篇线段树入门笔记。 线段树是一种二叉搜索树，是 OIOIOI 中很重要的数据结构。其支持单点修改，区间修改，单点查询，区间查询（最大最小值、求和）等操作。虽然比树状数组慢，但是它支持的操作更多。 线段树可以高效地解决具有区间性质的问题，例如区间求和，一次操作(修改，查询)就要遍历整个数组，单次操作时间复杂度 O(n)O(n)O(n) ，qqq 次修改复杂度 O(nq)O(nq)O(nq) ，远远超时。而线段树单次修改时间复杂度 O(log⁡n)O(\log n)O(logn) ， qqq 次修改复杂度 O(qlog⁡n)O(q \log n)O(qlogn) ，节约的不少时间。 线段树基本结构 比如一个长度为 555 的集合 {8,3,11,4,13}\{8,3,11,4,13\}{8,3,11,4,13} ，要维护他它的区间总和，建造出的线段树如下图所示： 如图所示，线段树的性质如下： 1.1.1. 线段树的每一个节点都管理着一段区间，其值为这一区间内需要维护的值，根节点（编号为 111 ）管理着整段区间 [1,n][1,n][1,n] ，叶子...