- 博客(33)
- 收藏
- 关注
RSS订阅原创 【阿里云天池龙珠计划SQL训练营打卡】
本笔记为阿里云天池龙珠计划SQL训练营的学习内容，链接为：https://tianchi.aliyun.com/specials/promotion/aicampsql；
2023-11-06 16:55:44
50
原创 46届ICPC区域赛（沈阳站）解题报告
46届ICPC区域赛（沈阳站）解题报告【待更新】传送门ABCDEFGH题意题解TagsCodeIJKLMvp传送门The 2021 ICPC Asia Shenyang Regional ContestABCDEFGH题意给定一个连通的无向图，给出边重构图的构造方法，取重构图中没有共同点的边，使得边权和最大(n⩽105,m⩽2∗105n\leqslant10^5,m\leqslant2*10^5n⩽105,m⩽2∗105）题解很快发现没法把边重构图建出来（菊花图直接卡爆），只
2022-04-29 15:24:29
1613
原创 [CF1072D]Codeforce 1072 D. Minimum path
Codeforce 1072 D. Minimum path传送门DescriptionInputOutputExampleInput#1Output#1Input#2Output#2Input#3Output#3NoteHintSolutionCode传送门CF1072DDescriptionYou are given a matrix of size n×nn×nn×n filled ...
2018-10-22 19:01:17
489
原创 [BZOJ1500][NOI2005]维修数列
传送门BZOJ1500DescriptionInput输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。 第2行包含N个数字，描述初始时的数列。 以下M行，每行一条命令，格式参见问题描述中的表格。 任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。 插入的数字总数不超...
2018-06-12 23:57:31
209
原创 [BZOJ3223][JoyOI 1729] 文艺平衡树
传送门BZOJ3223Description您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1 Input第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数 接下来m行每行两个数[l,r] 数...
2018-06-12 00:49:21
133
原创 [BZOJ1208][HNOI2004]宠物收养所
传送门BZOJ1208Description最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程...
2018-06-05 23:04:28
150
原创 [BZOJ4196][NOI2015]软件包管理器
传送门BZOJ4196DescriptionLinux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/CentOS使用的yum，以及OSX下可用的h...
2018-05-22 23:52:23
184
原创 矩形
没有传送门。Description因为对polo忍无可忍， dzf使用圣剑在地上划出了许多纵横交错的沟壑来泄愤。这些沟壑都严格与X轴平行或垂直。 polo嘲笑了dzf无聊的行为，然后做了一件更加无聊的事。他蹲下来数这些沟壑的条数。数着数着，polo意识到一个问题，那就是因为圣剑的威力太大，划出的沟壑太多，地面就会塌陷。而如果两条水平的沟壑和两条垂直的沟壑相交组成了一个矩形，那么塌陷的危险...
2018-05-20 21:22:33
220
原创 [POJ2104][SPOJ3946] K-th Number
传送门POJ2104SPOJ3946DescriptionYou are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data ...
2018-05-19 01:12:39
206
原创 [BZOJ3747][POI2015]Kinoman
传送门BZOJ3474Description共有m部电影，编号为1~m，第i部电影的好看值为w[i]。 在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。 你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看...
2018-05-15 23:58:44
133
原创 [USACO12JAN][SPOJ10502][Luogu3041]Video Game Combos
传送门SPOJ10502Luogu3041DescriptionBessie is playing a video game! In the game, the three letters ‘A’, ‘B’,and ‘C’ are the only valid buttons. Bessie may press the buttons in any order she likes;...
2018-05-11 19:27:11
194
原创 [51Nod1103]N的倍数
传送门51Nod1103Description一个长度为N的数组A，从A中选出若干个数，使得这些数的和是N的倍数。 例如：N = 8，数组A包括：2 5 6 3 18 7 11 19，可以选2 6，因为2 + 6 = 8，是8的倍数。 如果有多组合法方案, 输出任意一组即可.Input第1行：1个数N，N为数组的长度，同时也是要求的倍数。(2 <= N <= 500...
2018-04-21 03:04:27
184
原创 阅读（Read）
没有原题似乎来自某校模拟赛….Description热爱看书的你有N本书, 第i本书的种类为A[i]. 你希望每天能够看一本书, 但是不希望连续两天看种类相同的书. 为了达成这个条件, 你需要选择一些书不看, 作为一个好学生, 你希望不看的书尽可能少, 求最少可以有多少书不看.Input为了避免输入文件过大, 我们采取如下方式生成A[i]. 第一行读入两个个整数M, K. ...
2018-04-21 02:44:18
985
原创 [CodeVS1187]最大Xor路径
传送门CodeVS1187DescriptionMT神牛非常喜欢出Xor的题，在WC2011的时候，MT神牛出了一道非常经典的Xor最大路径题。 Bird向MT神牛学习，思考了许多关于Xor路径的问题，有一天，Bird想到了一个问题，给出一个序列，求这个序列的连续子序列的Xor值最大。 如1 3 4 8，最大的Xor子序列当然是3 xor 4 xor 8=15了。 Bird实在太...
2018-04-13 02:49:51
436
原创 [POJ3070]Fibonacci
传送门POJ3070DescriptionIn the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13...
2018-04-02 20:22:59
264
原创 [洛谷1262]间谍网络
传送门洛谷1262Description由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握...
2018-03-23 18:17:55
261
原创 建造高铁
不知道哪儿的题。DescriptionBSNY在规划一个国家的高铁建设。这个国家有n个城市，编号从0到n-1，首都建在0点。高铁建设划归首先要保证所有城市能全部连通，于是BSNY设计了m条高铁，保证了所有城市相互连通。 其次就是时间和费用问题，对BSNY来说，他要保证从首都出发到任何城市的时间总和最小(令sum=dist[1]+dist[2]+…+dist[n-1]，要求最小化sum)。...
2018-03-20 18:45:47
260
原创 [ZOJ3555][GDKOI2014模拟]树的直径
找不到原题了….Description科学家在观测一棵大树，这棵树在不断地生长，科学家给这棵树的每个节点 编了号。开始的时候，这棵树很小只有4 个节点，一号点为根，其他三个节点挂在上面。 在接下来的M 次观察中，科学家每次都能看见这棵树从叶子处长出新的两 个节点来。如果当前这棵树有N 个节点，那么这棵树的新的两个节点的编号分 别为N+1，N+2。科学家记录下了这棵树生长的过程，需要...
2018-03-17 00:04:03
199
原创 最小生成树是否唯一（次小生成树）
哪有什么传送门….Description给定一个连通无向图，有n个点和m条边。你需要去掉一些边，保留长度最小的边，使得图仍然连通，求保留边的最小长度是多少？ 上述问题即为最小生成树问题。为了增加难度，我们还想知道，保留最小边集的方案是否唯一，也就是最小生成树的边是否唯一。如果唯一，输出最小长度；如果不唯一，输出“Not Unique!”。Input第一行输入T，表示有T组...
2018-03-07 09:52:03
4535
2
原创 [Vijos1579]宿命的PSS
传送门Vijos1579(这是个什么鬼题库？？）Description最小生成树P.S.S在宿命的指引下找到了巫师Kismi。P.S.S希望Kismi能帮自己变成一个完全图。Kismi由于某些不可告人的原因，把这件事交给了你。 PS: 可以保证，这个最小生成树对于最后求出的完全图是唯一的。Input输入的第一行是一个整数n，表示生成树的节点数。 接下来有n-1行，每行有三个...
2018-03-07 09:48:33
231
原创 [HDU4081]Qin Shi Huang's National Road System
秦始皇的国家道路系统传送门HDU4081Description（略去长段对秦始皇的介绍…） Qin Shi Huang undertook gigantic projects, including the first version of the Great Wall of China, the now famous city-sized mausoleum guarded ...
2018-03-06 23:28:04
160
原创 [CodeVS1163]“访问”艺术馆
没有传送门Description皮尔是一个出了名的盗画者，他经过数月的精心准备，打算到艺术馆盗画。艺术馆的结构，每条走廊要么分叉为二条走廊，要么通向一个展览室。皮尔知道每个展室里藏画的数量，并且他精确地测量了通过每条走廊的时间，由于经验老道，他拿下一副画需要5秒的时间。你的任务是设计一个程序，计算在警察赶来之前，他最多能偷到多少幅画。Input第1行是警察赶到得时间，以s为
2018-01-11 11:14:39
184
原创 [POJ2411]Mondriaan's Dream铺砖块
[POJ2411]Mondriaan’s Dream铺砖块传送门POJ2411Description现有n* m的一块地板，需要用1*2的砖块去铺满，中间不能留有空隙。问这样方案有多少种 Input输入n，m（1<=n, m<=11) 有多组输入数据，以m=n=0结束 Output输出铺砖块的方案数Sample Input1 2 1 3 1 4 2 2 2 3 2 4 2 11 4
2018-01-09 09:55:24
239
原创 小明的喷漆计划
小明的喷漆计划Description小明极其喜欢涂鸦，总是在墙上涂上各种颜色的漆。现在小明得到一个任务，需要喷涂一段空白围墙，且单位长度内的颜色都是相同的。小明有一种喷涂工具，它可以给任意长度的一段墙面涂上任意颜色的漆，这样的操作计为一次操作。小明要完成这个任务，又想使得操作次数尽量少，就请你帮他解决这个问题吧。Input有多组输入数据。 每组包含一个长度不超过100的字符串（均由小写字母组成）
2018-01-04 08:46:02
355
原创 [洛谷1108]低价购买
传送门LG1108Description“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(2^16范围内的正整数)，你可以选择在哪些天购买这
2017-12-28 18:31:58
171
原创 [HDU3033]I love sneakers!（分组背包）
HDU[3033]I love sneakers!传送门HDU3033Description经过几个月的艰苦学习，Iserlohn终于赢得了全额奖学金。作为一个运动鞋狂热爱好者，他决定用所有的钱在运动鞋商店进行消费。 有一些球鞋Iserlohn要收集，如Air Jordan 和 Nike Pro。而每个品牌已发布各种产品。由于，Iserlohn绝对是一个运动鞋狂热，他意欲购买每个品牌至少有一个产
2017-12-26 11:07:04
156
原创 [BZOJ1787][Ahoi2008]Meet 紧急集合
传送门BZOJ1787一道不错的LCA模板题方法1：对于每次读入的x,y,z，求三个LCA，分别计算取最小值。方法2：求两两LCA，其中两个相同，答案为另一个，然后计算距离。下面的代码采用了方法1.....emmmmm.....虽然看上去比2要暴力，反正能过......#include #include #include #include #include usi
2017-12-16 17:20:19
161
原创 [bzoj2097][Usaco2010 Dec]Exercise 奶牛健美操
题目链接BZOJ2097洛谷3000简单抽象一下题意就是去掉n个结点的树上最多m条边，使得剩下的所有路径中最长值最小，求这个最小值。以这样的问法出现，我们可以考虑二分答案法。如果使最小值为x的方案存在，则使最小值为x+1的方案必然存在。不存在同理。所以很明显这题是具有二分性的。然后就是如何判断方案的存在性 这里用到树形DP和贪心。f[u]
2017-10-07 20:28:07
309
原创 [NOIP2016]Day1T3 换座位
题目链接洛谷P18502016NOIP Day1 T2 T3难度互换真的坑死人啊..........floyd+DP 就是写起来有点眼花的危险.....可以先跑个最短路把两两教室间的最短距离先预处理出来blue_tree大佬(field)说：v才300你不用floyd难道跑Dijkstra???注意一下重边就好然后就是概率DPf[i][k][j]表示第i个时...
2017-09-08 00:33:15
415
原创 [BZOJ3282/LGOJ3690] Link-Cut Tree 模板题
原题链接LCT模板题没什么解释 先存个档{Beginner_df016}var i,j,k,n,m,top,x,y,id:longint; s,v,fa,q,rev:array[0..300007]of longint; c:array[0..300007,0..2]of longint;procedure swap(var a,b:longint);var t:longint
2017-09-07 15:59:44
259
原创 [HDU1512]Monkey King
原题链接点击打开链接LGOJ1456点击打开链接题目大意呢就是一开始有n只孤独的猴子，然后他们要打m次架，每次打架都会把自己和朋友中最强的拉出来跟别人打，打完之后两人战斗力就会减半。每次打完架就会成为朋友（正所谓不打不相识....）。问每次打完架之后那俩猴子最强的朋友战斗力还有多少。朋友不打架，若朋友打架就输出-1.注意 有多组输入数据分析1.每次要找自
2017-09-05 23:37:09
258
原创 工件调度
题源 湖北省宜昌市第一中学 陈凡 《冲刺NOIP2008模拟题12》【问题描述】Jam的工厂新进了一批货，需要赶紧加工，工厂有许多加工机器，对于这些货物来说是绰绰有余了，但是他想合理安排加工方式，使每个加工机器都被充分利用。例如：他希望工件在8小时内加工完成，已知这里有5个工件，按顺序，需要消耗的时间依次为5 2 4 4 3，即5个工件要在8小时内完工。当然，你...
2017-09-02 11:23:48
420
原创 [NOIP2015]Day2T2 子串
题目链接_洛谷点击打开链接很容易想到DP....f[i][j][k]表示B串匹配到第i位，A串使用到第j位，共分为k段的方案数对于第j位匹配第i位，有以下两种情况....①A串 ******X Z****** ......j-1 j...... B串 **X Z*** ..i-1 i... 这一情况不需要多开一段 故...
2017-09-02 11:13:17
201
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人