Thunder_S-CSDN博客

Solution由于操作不限次数，那么在总和一定的情况下，a1,a2,a3a_1,a_2,a_3a1,a2,a3 都可以是任意一个自然数。此时要让 ∣a1+a3−2×a2∣|a_1+a_3-2\times a_2|∣a1+a3−2×a2∣ 最小，我们可以令 a1=0a_1=0a1=0，那么就是让 a3=2×a2a_3=2\times a_2a3=2×a2，因此 a1+a2+a3a_1+a_2+a_3a1+a2+a3 如果是 3 的倍数，答案为 0。否则只能让 a3=2×a2+1a

2021-11-15 14:29:00 390

原创 CF682D

Solution比较经典的 dpdpdp。考虑 fi,j,kf_{i,j,k}fi,j,k 表示 SSS 到了第 iii 位，TTT 到了第 jjj 位，已经选择了 kkk 个子串的最大长度和。但是由于当前位能否匹配与上一位有关，因此再开一维 0/10/10/1 表示 i−1i-1i−1 和 j−1j-1j−1 是否匹配。转移：如果 Si=TjS_i=T_jSi=Tj，说明当前位可以匹配，那么 fi,j,k,1=max⁡(fi−1,j−1,k,1,fi−1,j−1,k−1,0)+1f_{i

2021-09-04 15:07:02 128

原创 2021“MINIEYE杯”中国大学生算法设计超级联赛（1） 1001 Mod, Or and Everything

题目大意给出 nnn，求 (nmod 1) or(nmod 2) or(nmod 3) or…or (nmod (n−1)) or(nmod n)(n\mod 1)\ or(n\mod2)\ or(n\mod 3)\ or\dots or\ (n\mod (n-1)) \ or(n\mod n)(nmod1) or(nmod2) or(nmod3) or…or (nmod(n−1)) or(nmo

2021-07-22 09:48:11 188

原创 #3255. 「JOI 2020 Final」奥运公交

Description&Data Constraint对于全部数据，2≤N≤200,1≤M≤5×104,1≤Ui,Vi≤N,Ui≠Vi,0≤Ci≤106,0≤Di≤1092\le N \le 200,1\le M \le 5\times 10^4,1\le U_i,V_i\le N,U_i\not= V_i,0\le C_i\le 10^6,0\le D_i\le 10^92≤N≤200,1≤M≤5×104,1≤Ui,Vi≤N,Ui=Vi,0≤Ci≤106,0≤Di≤109。

2021-07-22 08:09:39 206 1

原创 LOJ#3478「ROIR 2021 Day 2」好数

Description&Data Constraint1≤n≤1017，k∈{0,1}。1\le n\le 10^{17}，k\in\{0,1\}。1≤n≤1017，k∈{0,1}。Solution签到题考虑暴力。首先可以确定答案的位数和 xxx 是一样的。那么看到第二类好数是包括第一类好数的，就可以先枚举出第一类好数，再根据 kkk 来判断是否要构造第二类好数的第 2 种情况。先枚举一个数字 iii 表示所有数位上都是 iii，判断与 xxx 的大小关系。如果 k=1k=1k=

2021-07-21 20:27:16 135

原创 JZOJ 7186-Loj #3264 海报

Description&Data Constraint4≤n≤40000,0≤ai,vi≤109,1≤pi≤n,0≤q≤400004\le n\le 40000,0\le a_i,v_i\le 10^9,1\le p_i\le n,0\le q\le 400004≤n≤40000,0≤ai,vi≤109,1≤pi≤n,0≤q≤40000Solution考虑将题目的区间转换成线段树，然后在线段树上dp。设 fx,i,jf_{x,i,j}fx,i,j 表示线段树上节点为 xxx 代表的

2021-07-20 08:42:17 106

原创 JZOJ3661-Luogu P4284-Loj #2192 概率充电器

Description&Data Constraint著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器：“采用全新纳米级加工技术，实现元件与导线能否通电完全由真随机数决定！SHOI概率充电器，您生活不可或缺的必需品！能充上电吗？现在就试试看吧！”SHOI概率充电器由 n−1n-1n−1 条导线连通了 nnn 个充电元件。进行充电时，每条导线是否可以导电以概率决定，每一个充电元件自身是否直接进行充电也由概率决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电

2021-07-19 22:10:09 70

原创 JZOJ7197-Luogu P6877-Loj #3252 只不过是长的领带

Description&Data Constraint1≤N≤2×105,1≤Ai≤109,1≤Bj≤109(1≤i≤N+1,1≤j≤N)1\le N\le 2\times 10^5,1\le A_i\le10^9,1\le B_j\le10^9(1\le i\le N+1,1\le j\le N)1≤N≤2×105,1≤Ai≤109,1≤Bj≤109(1≤i≤N+1,1≤j≤N)Solution首先排序，将 AAA 和 BBB 从小到大排序，同时记录 AAA 中每个元素的排名。考虑贪

2021-07-19 17:12:55 83

原创 JZOJ7178-Luogu7405-雪玉/雪球

Description&Data ConstraintSolutionaia_iai 表示 iii 雪球的初始位置。考虑两个相邻雪球 i,j(i<j)i,j(i<j)i,j(i<j)，如果雪球 iii 到达的最右边在雪球 jjj到达的最左边的右边，那么雪球 iii 之后无论怎么往右走都无法增加质量，因为雪球 jjj 肯定在 iii 之前把雪清空。有了这个想法，先求出相邻两个雪球间的距离 disidis_idisi，然后从小到大排序。对于每次移动，记录向左的总路程（

2021-07-16 11:19:26 164 2

原创 JZOJ7177-鱼跃龙门

Description&Data Constraint1≤T≤100,1≤n≤10121\le T\le100,1\le n \le 10^{12}1≤T≤100,1≤n≤1012Solution简单来说，就是求满足 x(x+1)2%n=0\dfrac{x(x+1)}{2}\%n=02x(x+1)%n=0 的最小的 xxx 。推导一下：n∣x(x+1)2n|\dfrac{x(x+1)}{2}n∣2x(x+1)2n∣x(x+1)2n|x(x+1)2n∣x(x+1)枚举 a∣2na|

2021-07-16 09:20:42 89

原创 JZOJ3559-Luogu P2022-有趣的数

Description&Data Constraint让我们来考虑 1 到 NNN 的正整数集合。让我们把集合中的元素按照字典序排列，例如当 N=11N=11N=11 时，其顺序应该为： 1,10,11,2,3,4,5,6,7,8,91,10,11,2,3,4,5,6,7,8,91,10,11,2,3,4,5,6,7,8,9。定义 KKK 在 NNN 个数中的位置为 Q(N,K)Q(N,K)Q(N,K)，例如 Q(11,2)=4Q(11,2)=4Q(11,2)=4。现在给出整数 KKK 和 MM

2021-07-15 08:42:38 112

原创 JZOJ3447-摘取作物

Description&Data ConstraintFeather的农场里有 N×MN\times MN×M 块地，排列成 NNN 行，每行 MMM 块地。Feather在每块地里种植了不同的农作物。现在这些农作物都成熟了，可以摘取下来出售了。其中第i行第j列的地里的农作物的价值为 Wi,jW_{i,j}Wi,j。JackRabbit是Feather的好友，平时经常为Feather的农作物除草除虫。为了答谢JackRabbit，Feather决定把一部分农作物送给JackRabbit。Jac

2021-07-13 21:44:37 57

原创 JZOJ4486-最长公共子串

Description&Data Constraint1≤n,m≤2000,0≤l≤r≤n,0≤k≤1000001\le n,m\le2000,0\le l\le r\le n,0\le k\le 1000001≤n,m≤2000,0≤l≤r≤n,0≤k≤100000Solution首先一个显然的性质是：如果两个区间有重叠部分，这两个区间是可以合并的。然后就可以将题目给出的区间分成若干个不相交的区间。在两个区间中每个元素单独为一个区间。统计出每个元素所在区间的左端点 lil_ili 和

2021-07-12 22:04:37 84

原创 JZOJ3423-Vani和Cl2捉迷藏

Description&Data Constraintvani和cl2在一片树林里捉迷藏……这片树林里有 NNN 座房子，MMM 条有向道路，组成了一张有向无环图。树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。如果从房子 AAA 沿着路走下去能够到达 BBB，那么在 AAA 和 BBB 里的人是能够相互望见的。现在cl2要在这N座房子里选择 KKK 座作为藏身点，同时vani也专挑cl2作为藏身点的房子进去寻找，为了避免被vani看见，cl2要求这 KKK 个藏身点的任意

2021-07-12 16:01:04 162

原创 JZOJ3454-表白

Description&Data Constraint鸡腿是CZYZ的著名DS，但是不想追妹子的DS不是好GFS，所以鸡腿想通过表白来达到他追到妹子的目的！虽然你对鸡腿很无语，但是故事的设定是你帮助鸡腿找到了妹子，所以现在你必须帮助鸡腿安排表白来实现故事的结局！鸡腿想到了一个很高（sha）明（bi）的做法，那就是去找人来组成表白队伍来增强气势！鸡腿有很多好基友来帮忙，鸡腿数了数一共有N个人。但是鸡腿觉得大家排成两队来比较好看，而且鸡腿经过计算，第一队N1个人，第二队N2个人是最佳的队伍。问题

2021-07-11 21:30:43 74

原创 JZOJ5968-密码锁

Description&Data ConstraintSolution题外话：去掉了一张图片。回到题目。题目大意就是给出一个序列 aaa，每次操作可以使得序列 aaa 的一段区间在模 mmm 的意义下 +1 或 -1。求最少操作次数。如果没有模 mmm 的条件，那么就很简单。直接差分统计 max⁡(正数和，∣负数和∣)\max(正数和，|负数和|)max(正数和，∣负数和∣)。但是在加了模 mmm 的条件后，题目稍稍难了一点。依旧考虑差分，差分完排序，求出前缀和、后缀和。然后找到一

2021-07-11 20:55:58 124

原创 JZOJ3384-理科男

Description&Data Constraint吃过草莓刨冰之后，Vani和cl有些疲倦地坐在一个长椅上。“呐，玩得开心吗？”Vani忽然问道。“嗯……很，很开心的说。”“那么，我有一个问题想要问你呢。”cl的脸有点红了起来。“嗯……好吧。问、问吧……我会告诉你的哦……”“那好。对于一个分数A / B……”“嗯……哎？哎？！”“……就是这个问题。我觉得这个问题好纠结啊……”Vani淡定地说完这句话。“啊？！哈啊？！”对于给定的分数 A / B，求其在 K 进制下是有限小

2021-07-09 20:58:10 79

原创 JZOJ3400-旅行

Description&Data Constraint从前有一位旅者，他想要游遍天下所有的景点。这一天他来到了一个神奇的王国：在这片土地上，有n个城市，从1到n进行编号。王国中有m条道路，第i条道路连接着两个城市ai,bi，由于年代久远，所有的道路都已经不能使用。如果要修复第i条道路，需要wi的时间。为了更好的旅行，旅者想要将某些道路修复，使得1号城市能够到达n号城市，2号城市能够到达n-1号城市…k号城市能够到达n-k+1号城市。为了满足他的要求，请问最少需要多少时间去修复道路。无解请输出-1。

2021-07-07 19:57:43 193 1

空空如也

空空如也