0 Kd_Limitless

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 30w+

[CF1394D] Boboniu and Jianghu 树形DP题解

题目描述输入输出一行一个整数表示答案样例输入1540 10 30 50 202 3 2 3 11 21 32 42 5输出1160输入251000000 1 1 1 11000000 1 1 1 11 21 31 41 5输出24000004输入310510916 760492 684704 32545 484888 933975 116895 77095 127679 989957402815 705067 705067 705067 6

2020-10-19 21:10:16

[CF908D] New Year and Arbitrary Arrangement 期望DP题解

题面样例输入11 1 1输出12输入23 1 4输出2370000006分析这道题显然是期望DP。由于终止状态有很多,不妨考虑 逆推。定义 dp[i][j][k]dp[i][j][k]dp[i][j][k] 为前面已有 iii 个 ′a′'a'′a′, jjj 个 ′b′'b'′b′, kkk 个 ′ab′'ab'′ab′ 的情况下,再在最后去掉一个字母后, ′ab′'ab'′ab′ 的期望个数。令 Pa=papa+pbPa = {pa \over {pa + pb}}

2020-10-06 19:13:34

[CF1265E] Beautiful Mirrors 期望DP题解

题意简述GM 有 n(1≤n≤2∗105)n(1≤n≤2*10^5)n(1≤n≤2∗105) 面镜子,他每天问其中一面镜子“GM 帅不帅”,iii 号镜子有 pi%(1≤pi≤100)p_i\%(1≤pi≤100)pi​%(1≤pi≤100) 的概率回答帅。第一天,GM 会从 111 号镜子开始问起。如果某天 GM 问了 i(i≠n)i(i≠n)i(i​=n)号镜子,并且镜子回答帅,那么第二天 GM 会问 i+1i+1i+1 号镜子。如果某天 GM 问了 nnn 号镜子,并且镜子回答帅,那么 GM 就

2020-10-05 07:48:57

[NOIP2018]普及组题解

有好久都没写博客呢了。。。标题统计签到题。#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>using namespace std;char a;int ans;int main() {// freopen("title.in", "r", stdin);// freopen("title.out", "w", stdout); while((

2020-08-26 22:34:09

明辨是非 并查集题解

题目描述给 nnn 组操作,每组操作形式为x y px\ y\ px y p。当 ppp 为 111 时,如果第 xxx 个变量和第 yyy 个变量可以相等,则输出YES,并限制他们相等;否则输出 NO,并忽略此次操作。当 ppp 为 000 时,如果第 xxx 个变量和第 yyy 个变量可以不相等,则输出 YES,并限制他们不相等;否则输出 NO,并忽略此次操作。输入格式第一行为一个正整数 nnn。 接下来 nnn 行每行三个整数:xxx, yyy,ppp

2020-08-12 17:31:18

[JSOI2008]Blue Mary的战役地图 Hash题解

题目描述Blue Mary最近迷上了玩Starcraft(星际争霸) 的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。由于Blue Mary的技术已经达到了一定的高度,因此,对于用同一种打法能够通过的战役地图,她只需要玩一张,她就能了解这一类战役的打法,然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法,因此Blue Mary需要你写一个程序,来帮助她判断哪些地图是属于同一类的。具体来说,Blue Mary已经将战役地图编码为n×nn \times nn×n

2020-08-09 20:39:21

「NOI2015」程序自动分析 并查集题解

题目描述在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本:假设x1x_1x1​,x2x_2x2​,x3x_3x3​,…代表程序中出现的变量,给定nnn个形如xi=xjx_i=x_jxi​=xj​或xi≠xjx_i≠x_jxi​​=xj​的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:x1=x2x_1=x_2x1​=x2​,x2=x3x_2=x_3x2​=x3​,x3

2020-08-09 20:08:37

TSP问题(旅行商问题) 状压DP求解

题目描述某乡有nnn个村庄(1≤n≤161\leq n \leq 161≤n≤16),有一个售货员,他要到各个村庄去售货,各村庄之间的路程sss(0<s<10000<s<10000<s<1000)是已知的,且AAA村到BBB村与BBB村到AAA村的路大多不同。为了提高效率,他从商店出发到每个村庄一次,然后返回商店所在的村,假设商店所在的村庄为SSS,他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。输入格式村庄数nnn,商店所在村庄和各村之间的

2020-08-01 15:47:53

树状数组 模板总结

前言此博客主要贴模板,若还未学习树状数组的同学请未进。(dalaodalaodalao除外)概念树状数组(BinaryBinaryBinary IndexedIndexedIndexed Tree(B.I.T)Tree(B.I.T)Tree(B.I.T)也称作FenwickFenwickFenwick TreeTreeTree)是一个区间查询和单点修改复杂度都为log(n)log(n)log(n)的数据结构。主要用于查询任意两点之间的所有元素之和。lowbitlowbit是什么?lowbit(

2020-07-27 20:02:40

数三角(count.cpp)题解

题目描述这是一个数三角的游戏。长度为111或sqrt(2)sqrt(2)sqrt(2)的小木棍放在一个网格上。如图所示,有水平的,垂直的或对角的。对角放置的木棍可以交叉。将木棍随意地放在网格上得到的图案可能不含三角形,也可能含一个或多个三角形。如下图所示(aaa),(bbb),(ccc),(ddd)和(eee)分别含有222,555,121212,000,000个三角形。你的任务是写一个程序数出一个图案中的三角形个数。输入格式输入文件count.incount.incount.in包括N+1N

2020-07-25 20:35:56

震惊!全网最详细的STL总结!

前言禁止转载,违者必究。STL,即Standard Template Library。相信大家都知道这是啥,以下为基本的STL模板总结。1.queuequeuequeuequeue,队列,是实现"先进先出"的容器,,不可用下标或迭代器访问。头文件:#include <queue>定义方式:queue <typename> name;其中typenametypenametypename指数据类型(如intintint、charcharchar、结构体、容器等),n

2020-07-22 19:46:29

「CF149D」括号涂色 区间DP好题

题目描述Petya遇到了一个关于括号序列的问题: 给定一个字符串SSS,它代表着正确的括号序列,即 “(((” 与 “)))” 是匹配的。例如:“(())()(())()(())()” 和 “()()()”是正确的,“)())())()”与“(()(()(()”则不是正确的。 在正确的括号序列中,一个左边的括号一定是匹配一个右边的括号(反之亦然)。例如,在下图中,第 333 个括号匹配第 666 个括号,第 444 个括号匹配第 555 个括号。现在你需要对一个正确的括号序列做涂色操作,严格满足以下三个

2020-07-19 21:08:09

「NOIP 2013」火柴排队 题解

题目描述涵涵有两盒火柴,每盒装有 nn 根火柴,每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列, 同一列火柴的高度互不相同, 两列火柴之间的距离定义为:∑(ai−bi)2\sum (a_i-b_i)^2∑(ai​−bi​)2。其中 aia_iai​ 表示第一列火柴中第 iii 个火柴的高度,bib_ibi​ 表示第二列火柴中第 iii 个火柴的高度。每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输

2020-07-10 17:17:15

「IOI 1998」Polygon (区间DP题解)

题目翻译“多边形游戏”是一款单人益智游戏。游戏开始时,给定玩家一个具有NNN个顶点NNN条边(编号1∼N1 \sim N1∼N)的多边形,如图1所示,其中N=4N = 4N=4。每个顶点上写有一个整数,每个边上标有一个运算符 +++(加号)或运算符 ×\times×(乘号)。第一步,玩家选择一条边,将它删除。接下来在进行 N−1N-1N−1 步,在每一步中,玩家选择一条边,把这条边以及该边连接的两个顶点用一个新的顶点代替,新顶点上的整数值等于删去的两个顶点上的数按照删去的边上标有的符号进行计算得到

2020-06-26 10:26:21

能量项链 区间DP题解

题目描述原题来自:NOIP 2006在 Mars 星球上,每个 Mars 人都随身佩带着一串能量项链。在项链上有 NNN 颗能量珠。能量珠是一颗有头标记和尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记必定等于后一颗珠子的头标记。因为只有这样,通过吸盘——Mars 人吸收能量的器官的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可被吸盘吸收的能量。如果一颗能量珠头标记为 mmm,尾标记为 rrr,后一颗能量珠头标记为 rrr,尾标记为 nnn,则聚合后释放出 m×r×

2020-06-20 10:59:42

前缀单词 DP题解

写在前面这道题是我以前做的,回顾这道题的时候觉得这道题好就写了一篇。题目描述一组单词是安全的,当且仅当不存在一个单词是另一个单词的前缀,这样才能保证数据不容易被误解。现在你手上有一个单词集合SSS,你需要计算有多少个子集是安全的。注意空集永远是安全的。输入格式第一行一个数 n(n<=50)n(n <= 50)n(n<=50),表示集合的大小,以下 nnn 行。每行一个由构成′a′......′z′'a' ......'z'′a′......′z′的字符串。输出格式安全子集的

2020-06-19 20:23:31

「JOISC 2014 Day4」挂饰(背包DP)题解

题目翻译JOI 君有 nnn 个装在手机上的挂饰,编号为 1…n1 \ldots n1…n。 JOI 君可以将其中一些挂饰装在手机上。JOI 君的挂饰有一些与众不同——其中的一些挂饰附有挂钩,你可以将其他挂饰挂在挂钩上。iii 号挂饰有 AiA_iAi​ 个挂钩。每个挂件要么直接挂在手机上,要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有 111 个。此外,每个挂件有一个安装时会获得的喜悦值,用一个整数来表示。如果 JOI 君很讨厌某个挂饰,那么这个挂饰的喜悦值就是一个负数。JOI 君想要最大化

2020-06-16 15:00:52

「CEOI2018」Cloud computing DP题解

题目描述Johnny 成立了 Bytecomp,一个提供云计算能力的公司。这样的公司通常拥有许多快速计算机,客户可以在其上进行计算。但是 Johnny 还没有购买任何计算机。于是他前往一家计算机商店,收到了包含全部 nnn 台可用的计算机的清单。每台计算机都可以用三个属性描述:处理器的核心数量 cic_ici​,时钟频率 fif_ifi​ 以及价格 cic_ici​。每台计算机包含 cic_ici​ 个不会互相干扰的核心,所以它们可以被分配给不同的任务。当客户订购资源时,她会指定所需的核心数 Cj

2020-06-13 11:51:05

《低价购买》题解

题目给定一段时间内股票的每日售价(正16位整数)。你可以选择在任何一天购买股票。每次你选择购买时,当前的股票价格必须严格低于你之前购买股票时的价格。编写一个程序,确定你应该在哪些天购进股票,可以使得你能够购买股票的次数最大化。例如,下面是一个股票价格时间表: Day 1 2 3 4 5 6 7 8 9 10 11 12Price 68 69 54 64 68 64 70 67 78 62 98 87如果每次购买都必须遵循当前股票价格严格低于之前购买股票时的价格,那么投资

2020-06-06 20:21:11

《三角形牧场》DP题解

题目描述奶牛建筑师Hei想建造围有漂亮白色栅栏的三角形牧场。她拥有N(3≤N≤40)块木板,每块的长度Li(1≤Li≤40)都是整数,她想用所有的木板围成一个三角形使得牧场面积最大。请帮助Hei小姐构造这样的牧场,并计算出这个最大牧场的面积。输入格式第1行:一个整数N。第2…N+1行:每行包含一个整数,即是木板长度。输出格式仅一个整数:最大牧场面积乘以100然后舍尾的结果。如果无法构建,输出-1。样例输入511334样例输出692思路看到这道题目,我的第一感觉是用贪心

2020-06-06 18:20:08

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。