- 博客(51)
- 收藏
- 关注
RSS订阅原创 【Luogu P6902】[ICPC2014 WF] Surveillance（倍增，贪心）
目录题目题目描述输入格式输出格式题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1样例 #2样例输入 #2样例输出 #2样例 #3样例输入 #3样例输出 #3提示思路代码题目题目描述The International Corporation for Protection and Control (ICPC) develops efficient technology for, well, protection and control. Nat
2022-09-12 17:42:32
322
原创 【Luogu P1450】[HAOI2008] 硬币购物（dp，容斥）
目录题目题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示数据规模与约定思路代码题目题目描述共有 44 种硬币。面值分别为 c_1,c_2,c_3,c_4c 1 ,c 2 ,c 3 ,c 4 。某人去商店买东西，去了 nn 次，对于每次购买，他带了 d_id i 枚 ii 种硬币，想购买 ss 的价值的东西。请问每次有多少种付款方法。输入格式输入的第一行是五个整数，分别代表 c_1,c_2,c_3,c_4, nc
2022-08-29 00:02:59
175
原创 【Luogu P2221】[HAOI2012] 高速公路（线段树，期望）
目录题目题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示数据规模与约定思路代码题目题目传送门题目背景Y901 高速公路是一条重要的交通纽带，政府部门建设初期的投入以及使用期间的养护费用都不低，因此政府在这条高速公路上设立了许多收费站。题目描述Y901 高速公路是一条由 n − 1 n-1n−1 段路以及 n nn 个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为 1 ∼ n 1 \sim n1∼n，从收费站 i ii 行驶到
2022-08-23 01:50:56
199
原创 【BZOJ 4765】普通计算姬（树状数组，分块）
目录题目DescriptionInputOutputSample InputSample Output思路代码题目题目传送门Description“奋战三星期，造台计算机”。小G响应号召，花了三小时造了台普通计算姬。普通计算姬比普通计算机要厉害一些。普通计算机能计算数列区间和，而普通计算姬能计算树中子树和。更具体地，小G的计算姬可以解决这么个问题：给定一棵n个节点的带权树，节点编号为1到n，以root为根，设sum[p]表示以点p为根的这棵子树中所有节点的权值和。计算姬支持下
2022-07-15 23:55:08
143
原创 【CF 629C】Famil Door and Brackets（dp，思维）
目录题目题面翻译描述输入输出数据规模题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1样例 #2样例输入 #2样例输出 #2样例 #3样例输入 #3样例输出 #3提示思路代码题目题面翻译描述Family Door 的生日就要到了，Gabi（Family Door的好朋友）想要给他买一个礼物。Gabi决定买一个只包含 ‘(’、‘)’ 的字符串，毕竟 Family Door 最喜欢的字符串是长度为 nn 的只包含 ‘(’、‘)’ 的字符串。我们称
2022-07-15 23:21:12
205
原创 【Luogu P4315】月下“毛景树”（树链剖分，线段树）
目录题目月下“毛景树”题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路代码题目月下“毛景树”题目描述毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬 毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果 “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数
2022-07-15 00:26:48
92
原创 【BZOJ 4127】Abs（树链剖分，线段树）
目录题目DescriptionInputOutputSample InputSample OutputHint思路代码题目题目传送门Description给定一棵树,设计数据结构支持以下操作1 \;u\;v\;d1uvd 表示将路径 (u,v)(u,v) 加 dd2\;u\;v2uv 表示询问路径 (u,v)(u,v) 上点权绝对值的和Input第一行两个整数 nn 和 mm，表示结点个数和操作数接下来一行 nn 个整数 a_ia i ,表示点 ii 的权值
2022-07-15 00:11:01
123
原创 【Luogu P2115】[USACO14MAR]Sabotage G（二分答案）
目录题目题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路代码题目题目描述Farmer John’s arch-nemesis, Farmer Paul, has decided to sabotage Farmer John’s milking equipment!The milking equipment consists of a row of N (3 ...
2022-07-14 23:21:55
106
原创 【LOJ 2392】「JOISC 2017 Day 1」烟花棒（二分答案，贪心）
目录题目题目描述输入格式输出格式样例数据范围与提示思路代码题目题目描述题目传送门题目译自 JOISC 2017 Day1 T3「手持ち花火 / Sparklers」有 NNN 人站在一条数轴上。他们人手一个烟花，每人手中的烟花都恰好能燃烧 TTT 秒。每个烟花只能被点燃一次。111 号站在原点，iii 号 (1≤i≤n)(1\leq i\leq n)(1≤i≤n) 到 111 号的距离为 。保证 X1=0X_1 = 0X1=0，X1,X2,...,XNX_1,X_2,...,X_NX1,X2
2021-11-14 23:17:11
1297
1
原创 【Luogu P4766】 [CERC2014]Outer space invaders（区间dp）
目录题目题目描述输入格式输出格式输入输出样例思路代码题目题目描述来自外太空的外星人（最终）入侵了地球。保卫自己，或者解体，被他们同化，或者成为食物。迄今为止，我们无法确定。外星人遵循已知的攻击模式。有 NNN 个外星人进攻，第 iii 个进攻的外星人会在时间 aia_iai 出现，距离你的距离为 did_idi，它必须在时间 bib_ibi 前被消灭，否则被消灭的会是你。你的武器是一个区域冲击波器，可以设置任何给定的功率。如果被设置了功率 RRR，它会瞬间摧毁与你的距离在 RRR 以内的所有
2021-09-30 16:47:04
138
原创 【Luogu P5189】[COCI 2010] ZUMA（区间dp）
目录题目题目描述输入格式输出格式输入输出样例说明/提示思路代码题目题目描述译自 COCI 2010.03.06 T4「ZUMA」Mirko 将 NNN 颗弹子排成一排，依次编号为 1…N1\ldots N1…N。iii 号弹子的颜色为 cic_ici。他发现，如果他触摸 ≥K\ge K≥K 颗连续的弹子，且这些弹子的颜色相同，魔法会使这些弹子消失；此后，这 KKK 颗弹子前面的弹子便与这 KKK 颗弹子后面的弹子相邻。Mirko 家里有很多弹子，他想在这 NNN 颗弹子之间（也可以在开头的弹子前
2021-07-16 18:11:53
321
1
原创 【Luogu P1792】[国家集训队] 种树（贪心）
题目原题传送门题目描述A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。园林部门得到指令后，初步规划出 nnn 个种树的位置，顺时针编号 111 到 nnn。并且每个位置都有一个美观度 AiA_iAi，如果在这里种树就可以得到这 AiA_iAi 的美观度。但由于A城市土壤肥力欠佳，两棵树决不能种在相邻的位置（iii 号位置和 i+1i+1i+1 号位置叫相邻位置。值得注意的是 111 号和 nnn 号也算相邻位置）。最终市政府给园林部门提供了 mmm 棵树苗
2021-07-12 16:47:39
321
原创 【ZOJ 3780】Paint the Grid Again（拓扑排序）
母鹿题目DescriptionInputOutputSample InputSample Output题意题目原题传送门DescriptionLeo has a grid with N × N cells. He wants to paint each cell with a specific color (either black or white).Leo has a magical brush which can paint any row with black color, or any
2021-07-12 14:57:00
159
原创 【Luogu P6922】[ICPC2016 WF]Longest Rivers（贪心）
目录题目题目描述题意翻译输入输出样例说明/提示思路代码题目题目描述The Chao Phraya River System is the main river system of Thailand. Its six longest rivers listed by decreasing length are:Tha Chin (765765765 km)Nan (740740740 km)Yom (700700700 km)Ping (658658658 km)Pa Sak (513513
2021-07-11 21:53:56
437
原创 【Luogu P7527】[USACO21OPEN] United Cows of Farmer John G（树状数组）
目录题目题目描述输入格式输出格式输入输出样例说明/提示思路代码题目题目描述农夫约翰合牛国（The United Cows of Farmer John，UCFJ）将要选派一个代表队参加国际牛学奥林匹克（International bOvine olympIad，IOI）。有 NNN 头奶牛参加了代表队选拔。她们站成一行，奶牛 iii 的品种为 bib_ibi。代表队将会由包含至少两头奶牛的连续区间组成——也就是说，对于满足 1≤l<r≤N1\le l<r\le N1≤l<r≤N
2021-07-11 17:01:47
248
原创 【Luogu P2607】[ZJOI2008] 骑士（树形dp）
目录题目题目描述输入格式输出格式输入输出样例说明/提示思路代码题目题目描述Z 国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的 Y 国发动了一场针对 Z 国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的 Z 国又怎能抵挡的住 Y 国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每
2021-07-11 16:10:06
178
原创 【Luogu P6441】[COCI2011-2012#6] PASTELE（二分答案，容斥，前缀和）
目录题目题目背景题目描述输入格式输出格式输入输出样例说明/提示思路题目题目背景Mirko 收到了一份礼物。题目描述这份礼物共包含 nn 支蜡笔。每只蜡笔的颜色由色光三原色组成：红、绿、蓝。分别用参数 Ri,Gi,BiR_i,G_i,B_iRi,Gi,Bi 表示。这只蜡笔的颜色就由这三个参数来决定。对于两支蜡笔 i,ji,ji,j，我们定义它们之间的差异值为 max(∣Ri−Rj∣,∣Gi−Gj∣,∣Bi−Bj∣)\max(|R_i-R_j|,|G_i-G_j|,|B_i-B_j|)max
2021-07-08 21:15:52
210
1
原创 【COCI 2007/2008 Final】数位相乘（数位dp）
目录题目题目描述输入输出样例输入样例输出思路代码题目题目描述我们定义 f(x)f(x)f(x) 表示 xxx 与它各个数位的数字的乘积.如: f(2612)=2612×2×6×1×2=62688f(2612)=2612\times 2\times 6\times 1\times 2=62688f(2612)=2612×2×6×1×2=62688.现给出正整数 LLL , RRR , 求有多少个正整数 xxx , 满足 L≤f(x)≤RL≤f(x)≤RL≤f(x)≤R.输入输出仅一行,为两个正整
2021-07-08 19:42:02
363
原创 【比赛题解】Codeforces Round #664 (Div. 2) Problem A~D
目录前言题解A. Boboniu Likes to Color BallsDescriptionExampleNoteSolutionCodeB. Boboniu Plays ChessDescriptionInputOutputExamplesNoteSolutionCodeC. Boboniu and Bit OperationsDescriptionInputOutputExamplesNoteSolutionCodeD. Boboniu Chats with DuDescriptionInputOu
2020-08-15 00:18:37
294
原创 【Luogu 2534】[AHOI2012] 铁盘整理（IDA*搜索）
死亡人口诈尸这里写自定义目录标题题目题目描述输入格式输出格式输入输出样例思路代码题目题目描述在训练中，一些臂力训练器材是少不了的，小龙在练习的时候发现举重器械上的铁盘放置的非常混乱，并没有按照从轻到重的顺序摆放，这样非常不利于循序渐进的锻炼。他打算利用一个非常省力气的办法来整理这些铁盘，即每次都拿起最上面的若干个圆盘并利用器械的力量上下翻转，这样翻转若干次以后，铁盘将会按照从小到大的顺序排列好。那么你能不能帮小龙确定，最少翻转几次就可以使铁盘按从小到大排序呢？例如：下面的铁盘经过如图所示的以下几个
2020-07-30 23:30:39
192
原创 【HDU 5542】The Battle of Chibi （dp，树状数组优化）
目录题目DescriptionInputOutputSample InputSample OutputHintSource思路朴素dp优化代码题目DescriptionCao Cao made up a big army and was going to invade the whole South China. Yu Zhou was worried about it. He though...
2019-08-15 21:53:39
498
2
原创 【BZOJ 1085】[SCOI 2005] 骑士精神（IDA*搜索，双向BFS)
目录题目DescriptionInputOutputSample InputSample Output思路1、双向bfs2、IDA*搜索IDDFSA*两种算法合并代码双向bfsIDA*搜索题目Description在一个 5×55 \times 55×5 的棋盘上有 121212 个白色的骑士和 121212 个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑 士的走法（它可以走到和...
2019-08-14 14:09:24
657
原创 【牛客网 2019 多校第七场】 A - String（贪心，枚举）
题目思路贪心 +++ 暴力枚举。这题要求截取最少数量的字符串，使得每个字符串在所有各自的循环字符串中字典序最小。首先，枚举截取字符串的开始位置。然后，枚举截取的长度（从长到短，贪心）。接着，截字符串。最后判断当前字符串是否为字典序最小的字符串。那么，判断的时候如何截取循环字符串呢？① 先从当前位置截取到最后，再从开始截取到当前位置，将这两段结合在一起。结合的操作string就...
2019-08-09 10:22:11
149
原创 【POJ 1151】 Atlantis（线段树，扫描线，离散化）
文章目录题目DescriptionInputOutputSample InputSample OutputSource思路代码题目DescriptionThere are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even i...
2019-08-08 10:35:05
218
原创 【CH 5105】Cookies（dp）
题目题目描述圣诞老人共有M个饼干，准备全部分给N个孩子。每个孩子有一个贪婪度，第 i 个孩子的贪婪度为 g[i]。如果有 a[i] 个孩子拿到的饼干数比第 i 个孩子多，那么第 i 个孩子会产生 g[i]*a[i]的怨气。给定N、M和序列g，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。输入格式第一行包含两个整数N,M。...
2019-08-06 11:21:33
225
原创 【POJ 1852】Ants（思维）
思路这题，是一道考验大家想象力 的题。做了这道题，我想起了洛谷的一句话。有些问题刚开始觉得无从下手。好好想一想，尽量别看题解，否则你会大呼“简单”。蚂蚁数上限1000000，爬行方式21000000种。（默默放弃这一题）这一题，两只蚂蚁碰面后，会转身再走。emmmm，给大家看两幅盗来的图。本来两只蚂蚁的行走轨迹：相遇转身后：（换魂大法好！）这不就相当于没有转身这个限制...
2019-08-04 11:04:25
216
2
原创 【POJ 2573】Bridge（思维）
题目Descriptionn people wish to cross a bridge at night. A group of at most two people may cross at any time, and each group must have a flashlight. Only one flashlight is available among the n people...
2019-08-04 10:35:45
240
原创 【HDU 6620】[2019 HDU 多校第四场] Just an Old Puzzle（思维，逆序对）
题目Problem DescriptionYou are given a 4 × 4 grid, which consists of 15 number cells and an empty cell.All numbers are unique and ranged from 1 to 15.In this board, the cells which are adjacent with...
2019-08-03 10:34:42
228
原创 【牛客网 2019 多校第三场】 J - LRU management （STL map）
题目思路emmmm。主要两种操作，插入，删除。第一想法STL暴力。很简单想到map，虽然比较暴力。据说map可能超时，所以我们使用unordered_map。模拟起来比较繁琐。代码#include <bits/stdc++.h> using namespace std;int n, m;struct node { int v; string m...
2019-07-27 17:44:47
144
原创 【牛客网 2019 多校第三场】 F - Planting Trees （思维，枚举）
题目思路疯狂想法：6层for循环，O(N6)算法。于是，看这句话：It is guaranteed that the sum of N3over all cases does not exceed 25 ⋅107肯定是让你想O(N3)算法。首先，枚举子矩阵的上下边界，维护上下边界的最大最小值。然后接着枚举右边界。可左边界怎么办呢，反正不能还枚举吧。左边界显然具有单调不降性。二分...
2019-07-26 16:04:47
118
原创 【HDU 6581】[2019 HDU 多校第一场] Vacation （思维，枚举）
题目Problem DescriptionTom and Jerry are going on a vacation. They are now driving on a one-way road and several cars are in front of them. To be more specific, there are n cars in front of them. The ...
2019-07-26 15:34:00
109
原创 【HDU 6578】[2019 HDU 多校第一场] Blank（dp）
题目Problem DescriptionThere are N blanks arranged in a row. The blanks are numbered 1,2,…,N from left to right.Tom is filling each blank with one number in {0,1,2,3}. According to his thought, the f...
2019-07-26 14:21:46
202
原创 【2019 暑假JSOI Day 2 T2】小说（二分+最短路）
题目【题目背景】由于小 X 是一位奆老， 奆老总是忙得一刻也停不下来。 他刚刚准备完食物， 小 X 童年的挚友小 S 和小 Z 来找他帮忙了……【题目描述】小 S 和小 Z 十分喜欢看网络写手“25” 的小说， 但由于需要付费才能阅读， 而小 S 和小Z 的零花钱有非常少， 他们只能找小 X 靠黑科技侵入给网站， 把小说给他们。然而小 X 又非常的爱慕虚荣， 他要小 S 和小 Z 到...
2019-07-11 17:22:26
237
原创 【2019 暑假JSOI Day 2 T1】招待（思维）
题目【题目背景】请了两位奆老来为自己种树， 小 X 也稍稍有些不好意思了， 于是他准备了一些零食和饮料来招待奆老们。然而， 小 X 有强迫症， 他希望自己和好基友们所有的零食和饮料的质量都要完全相同。【题目描述】由于小 X 是一个奆老， 所以他看不起普通商店里卖的电子秤， 他决定自己做一个。他的称重工具是一架由金子制成的天平， 这架天平的精度非常高， 可以达到纳克的标准，1g=10...
2019-07-11 16:56:14
332
原创 【2019 暑假JSOI Day 1 T3】 DNA（哈希）
题目【题目背景】小 X 身为奆老， 兴趣爱好广泛， 他还非常喜欢研究 DNA 序列……【题目描述】小 X 进行了一项关于 DNA 序列研究， 发现人某条染色体上的一段 DNA 序列中连续的 k个碱基组成的碱基序列与做题的 AC 率有关！ 于是他想研究一下这种关系。现在给出一段 DNA 序列， 请帮他求出这段 DNA 序列中所有连续 k 个碱基形成的碱基序列中， 出现最多的一种的出现次...
2019-07-11 16:20:35
806
1
原创 【2019 暑假JSOI Day 1 T2】 种树（dp）
种树（plant）【题目背景】事实上， 小 X 邀请两位奆老来的目的远不止是玩斗地主， 主要是为了抓来苦力， 替他的后花园种树……【题目描述】小 X 的后花园是环形的， 他想在花园周围均匀地种上 n 棵树， 但是奆老花园的土壤当然非同寻常， 每个位置适合种的树都不一样， 一些树可能会因为不适合这个位置的土壤而损失观赏价值。小 X 最喜欢 3 种树， 这 3 种树的高度分别为 10,...
2019-07-10 17:30:52
256
原创 【2019 暑假JSOI Day 1 T1】 斗地主（bfs）
前言去扬中浪了一圈，每天早上3题，180分左右徘徊。。。收获了若干包纸（去过的人都懂）以及一个词：奆佬。不多说了，开始补题，写题解题目描述【题目背景】众所周知， 小 X 是一个身材极好、 英俊潇洒、 十分贪玩成绩却依然很好的奆老。这不， 他又找了他的几个好基友去他家里玩斗地主了……【题目描述】身为奆老的小 X 一向认为身边人和自己一样的厉害， 他坚信你和他一样有未卜先知的能力，...
2019-07-10 16:53:18
356
1
原创 【POJ3468】 A Simple Problem with Integers （线段树）
题目描述You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for ...
2019-07-03 15:37:27
109
原创 【BZOJ 4394】[Usaco2015 dec] Bessie（bfs）
题目DescriptionAfter eating too much fruit in Farmer John’s kitchen, Bessie the cow is getting some very strange dreams! In her most recent dream, she is trapped in a maze in the shape of an N×M grid ...
2019-07-03 12:01:17
135
原创 【POJ 2176】Folding（区间dp）
题目描述Bill is trying to compactly represent sequences of capital alphabetic characters from ‘A’ to ‘Z’ by folding repeating subsequences inside them. For example, one way to represent a sequence AAAAA...
2019-07-03 11:35:43
167
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人