Dispwnl

Crazy Up

[HNOI2008]玩具装箱

题目题目描述 P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。 P教授有编号为$1…N$的$N$件玩具，第$i$件玩具经过压缩后变成一维长度为$C_i$.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单...

Posted by Dispwnl on March 20, 2018

[SDOI2017]树点涂色

题目题目描述 Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。 Bob可能会进行这几种操作： 1 x 把点x到根节点的路径上所有的点染上一种没有用过的新颜色。 2 x y 求x到y的路径的权值。 3 x 在以x为根的子树中选择一个点，使得这个点到根节点的...

Posted by Dispwnl on March 19, 2018

[ZJOI2012]网络

题目题目描述有一个无向图G，每个点有个权值，每条边有一个颜色。这个无向图满足以下两个条件： 1.对于任意节点连出去的边中，相同颜色的边不超过两条。 2.图中不存在同色的环，同色的环指相同颜色的边构成的环。在这个图上，你要支持以下三种操作： 0.修改一个节点的权值。 1.修改一条边的颜色。 2.查询由颜色c的边构成的图中，所有可能在节点u到节点v之间的简单路径上的节点的权值的...

Posted by Dispwnl on March 18, 2018

[LUOGU2766]最长不下降子序列问题

题目题目描述问题描述：给定正整数序列x1,…,xn。（1）计算其最长不下降子序列的长度s。（2）计算从给定的序列中最多可取出多少个长度为s的不下降子序列。（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的不下降子序列。编程任务：设计有效算法完成（1）（2）（3）提出的计算任务。输入输出格式输入格式：第1行有1个正整数n，表...

Posted by Dispwnl on March 18, 2018

[SCOI2012]奇怪的游戏

题目 Description Blinker最近喜欢上一个奇怪的游戏。这个游戏在一个N*M的棋盘上玩，每个格子有一个数。每次Blinker会选择两个相邻的格子，并使这两个数都加上 1。现在Blinker想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出-1。 Input 输入的第一行是一个整数T，表示输入数据有T轮游戏组成。每轮游戏的第一行有两个整数...

Posted by Dispwnl on March 16, 2018

[SCOI2014]方伯伯运椰子

题目题目描述四川的方伯伯为了致富，决定引进海南的椰子树。方伯伯的椰子园十分现代化，椰子园中有一套独特的交通系统。现在用点来表示交通节点，边来表示道路。这样，方伯伯的椰子园就可以看作一个有n+2个交通节点，m条边的有向无环图。n+1号点为入口，n+2号点为出口。每条道路都有6个参数，ui，vi，ai，bi，ci，di，分别表示，该道路从ui号点通向vi号点，将它的容量压缩一次要...

Posted by Dispwnl on March 15, 2018

[SCOI2010]序列操作

题目题目描述 lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0 3 a b 询问[a, b]区间内总共有多少个1 ...

Posted by Dispwnl on March 15, 2018

有上下界的网络流略解

原来整理的好像有点问题重新写了一下qwq 有上下界的网络流就是每条边都有一个$l$和$r$，然后每条边的流量$flow$必须满足$l\le flow\le r$ 一般分$4$种情况无源汇可行流一个烂大街的错误我会做这个！把每条边的容量设成$r-l$，然后求最大流，答案加上最大的$l$就完事了快夸我快夸我其实仔细想想就有问题，这样做不...

Posted by Dispwnl on March 14, 2018

[SDOI2014]旅行

题目题目描述 S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了...

Posted by Dispwnl on January 7, 2018

[USACO16OPEN]248

题目题目大意给定一个1*n的地图，在里面玩2048，每次可以合并相邻两个（数值范围1-40），问最大能合出多少。注意合并后的数值并非加倍而是+1，例如2与2合并后的数值为3。输入输出样例输入样例#1： 4 1 1 1 2 输出样例#1： 3 题解可以看出是区间$DP$ 对于每一个区间记录的是能构成的最大值因为是相邻的区间，思路是枚举每一个分界点即$i$从$2$枚举到...

Posted by Dispwnl on December 24, 2017