Dispwnl

Crazy Up

LOJ刷题记录

最近做了一些LOJ的动态规划的题…… 区间类动态规划「一本通 5.1 例 1」石子合并题解简单的区间$dp$ 代码 # include<iostream> # include<cstring> # include<cstdio> # include<algorithm> using namespace std; const int M...

Posted by Dispwnl on October 24, 2018

[APIO2007]动物园

题目题目描述新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上，包含一大圈围栏，每个围栏里有一种动物。如下图所示：你是动物园的公关主管。你要做的是，让每个参观动物园的游客都尽可能高兴。今天有一群小朋友来到动物园参观，你希望能让他们在动物园度过一段美好的时光。但这并不是一件容易的事——有些小朋友喜欢某些动物，而有些小朋友则害怕某些动物。例如， Alex 喜欢可爱的猴子...

Posted by Dispwnl on October 23, 2018

[ZROI80]World Of Our Own

题目题目描述小C在研究数组的xor。她有一个长度为$n$的数组$A$。她每次会把$a_{i-1}$和$a_i$异或起来，然后$A$的长度会变成$n - 1$ 这么操作了$n - 1$次之后得到了长度为$1$的数组。她想知道在操作过程中每次的$a_1$为多少? 为了避免输出过大，请输出第$j$次操作后的$a_1 \times (j + 1)$的异或和($0 \leq j \...

Posted by Dispwnl on October 18, 2018

[ZROI79]Reason For Living

题目题目描述小B准备设计施工方案。设计图是一个$n$个点$m$条边的图，小B每次施工可以取图中一个还没有完工的生成森林把它完工。为了加快施工效率，每次取的时候小B都会最大化当前这个生成森林的边数。请你帮他找出一个符合要求的施工方案。如果有多个方案，输出任意一种即可。输入格式第一行两个整数$n$, $m$。后面$m$行，每行两个数$a_i, b_i$表示一条边，保证没...

Posted by Dispwnl on October 17, 2018

[ZROI78]Last mile of the way

题目题目描述小A从仓库里找出了一棵$n$个点的有根树，1号节点为这棵树的根，树上每个节点的权值为$w_i$, 大小为$a_i$。现在他心中产生了$Q$个疑问，每个疑问形如在$x$的子树里，选出一些大小和不超过$s$的节点(不可以重复选一个节点)，最大权值和可以为多少。输入格式一行一个整数$n$。 $n - 1$行两个整数$u_i$, $v_i$表示一条边。 $n$行每行两个...

Posted by Dispwnl on October 17, 2018

[ZROI367]陈太阳与路径

题目题目描述陈太阳说要有树，这个世界便有了树。陈太阳说要有一棵$n$个节点的树，一棵随机选择的$n$个节点的有标号树便被召唤了出来。陈太阳说，要对于每个节点，计算出它是多少条路径的中点，答案便浮现在了每个节点旁。但是你没有陈太阳那么强，你只能写个程序计算这些答案了。一条$x$到$y$的路径，若其包含奇数条边，那么就没有中点。否则设这条路径有$m$条边，那么它的中点就是从$x$向$y$...

Posted by Dispwnl on October 17, 2018

[SCOI2009]迷路

题目题目描述 windy在有向图中迷路了。该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。输入输出格式输入格式：第一行包含两个整数，N T。接下来有 N 行，每行一个长度为 N 的字符串。第i行...

Posted by Dispwnl on October 17, 2018

[TOPCODER14676]OwaskiAndTree

题目题目大意给出一棵有根树，从根出发，走过一些节点每个节点有一个得分，可以重复经过节点，但是只有第一次经过会改变当前得分如果当前得分为负，会马上变成$0$ 求最大得分 Examples 0) {0, 1, 2, 3, 4, 5, 6, 7, 8} {1, 1, -1, -1, -1, -1, 1, 1, 1, 1} Returns: 4 1) {0, 0, 1, 2} {2...

Posted by Dispwnl on October 16, 2018

[LUOGU4198]楼房重建

题目题目描述小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线...

Posted by Dispwnl on October 16, 2018

[BZOJ4300]绝世好题

题目 Description 给定一个长度为n的数列ai，求ai的子序列bi的最长长度，满足bi&bi-1!=0(2<=i<=len)。 Input 输入文件共2行。第一行包括一个整数n。第二行包括n个整数，第i个整数表示ai。 Output 输出文件共一行。包括一个整数，表示子序列bi的最长长度。 Sample Input 3 1 2 3 Sample Outp...

Posted by Dispwnl on October 16, 2018