Dispwnl

Crazy Up

[TOPCODER12924]TypoCoderDiv1

题目题目大意一共有$n$场比赛，打一场比赛赢了$+d_i$rating，输了$-d_i$rating，如果rating不小于$2200$为$Div1$，否则为$Div2$ $Aufun$决定去炸鱼，因为ta的确有伟大的神力，ta可以决定每一场比赛的输赢，为了恐吓$Div2$选手，激怒$Div1$选手，ta想最大化他在组别间横跳的次数，为了炸鱼，如果不是第$n$场比赛，$Aufun$必须...

Posted by Dispwnl on October 15, 2018

[HDU5306]Gorgeous Sequence

题目题目大意给定一个序列，有三种操作：区间取$min$ 区间求和区间查询最大值多组数据 Sample Input 1 5 5 1 2 3 4 5 1 1 5 2 1 5 0 3 5 3 1 1 5 2 1 5 Sample Output 5 15 3 12 题解我真傻，真的，我以后再也不用宏定义max了听说是$jry$线段树的写法？难点是区间取$m...

Posted by Dispwnl on October 15, 2018

[USACO06MAR]产奶比赛Milk Team Select

题目 Description 约翰的N(1≤N≤500)头奶牛打算组队去参加一个世界级的产奶比赛(Multistate Milking Match-up，缩写为MMM)．她们很清楚其他队的实力，也就是说，她们派出的队只要能产出至少X(I≤X≤1000000)加仑牛奶，就能赢得这场比赛．每头牛都能为集体贡献一定量的牛奶，数值在-10000到10000之间（有些奶牛总是想弄翻装着其他奶牛产的...

Posted by Dispwnl on October 13, 2018

[JSOI2011]柠檬

题目 Description Flute 很喜欢柠檬。它准备了一串用树枝串起来的贝壳，打算用一种魔法把贝壳变成柠檬。贝壳一共有 N (1 ≤ N ≤ 100,000) 只，按顺序串在树枝上。为了方便，我们从左到右给贝壳编号 1..N。每只贝壳的大小不一定相同，贝壳 i 的大小为 si(1 ≤ si ≤10,000)。变柠檬的魔法要求，Flute 每次从树枝一端取下一小段连续的贝壳...

Posted by Dispwnl on October 12, 2018

一听名字就很可爱的猫树qwq

猫树听说叫猫树是因为发明者$immortalCO$（猫锟）觉得猫是一种很可爱的生物qwq 一道题：给定一个长度为$n$的序列，每次询问查询区间最大子段和线段树随便艹啊…… 复杂度是$O(n+qlogn)$(建树+查询) 这时候毒瘤出题人就说了：诶你这复杂度不优秀，要求查询不要带$log$ 这时候一种可爱的数据结构就蹦出来解决ta啦，也就是猫树，复杂度是$O...

Posted by Dispwnl on October 11, 2018

[Wannafly挑战赛21E]未来城市规划

题目题目描述乐乐做了个梦，梦见自己当了国王。乐乐王国有N座城市（编号从1~N，首都的编号为1）。乐乐王国的道路构成树状结构：首都1与几个大城市相连，这几个大城市又通过道路与一些稍小的城市相连……严格地说，这N座城市构成一棵有根树（1为树根），城市i的管理区域为以i为根的子树。道路都是双向的。经过每条道路需要收费，从城市A到城市B的花费为A到B的简单路径上所有道路的费用之和（不妨称之为...

Posted by Dispwnl on October 8, 2018

[HDU6315]Naive Operations

题目题目大意给定一个长度为$n$的排列$b$，需要维护一个长度同样为$n$的序列$a$ 有两种操作：给定区间$[l,r]$，$a_{l…r}$全部$+1$ 给定区间$[l,r]$，求$\sum_{i=l}^{r}\left\lfloor\frac{a_i}{b_i}\right\rfloor$ Sample Input 5 12 1 5 2 4 3 add 1 4 q...

Posted by Dispwnl on October 8, 2018

[HDU5215]Cycle

题目题目大意多组数据给定一个无向图，问是否存在奇环/偶环 Sample Input 3 1 0 3 3 1 2 2 3 3 1 4 4 1 2 2 3 3 4 4 1 Sample Output NO NO YES NO NO YES 题解判断奇环，只要判断这个图是否是一个二分图即可判断偶环，建立$dfs$树的时候，如果遇到返祖边，两个点之间的边数为奇数说明存在偶环 ...

Posted by Dispwnl on October 8, 2018

[CF827D]Best Edge Weight

题目题目大意给定一个带权无向图对于每条边，求其他边不变时这条边能出现在这个图的每一个最小生成树上，这条边满足条件的最大权值是多少 Examples input 4 4 1 2 2 2 3 2 3 4 2 4 1 3 output 2 2 2 1 input 4 3 1 2 2 2 3 2 3 4 2 output -1 -1 -1 题解如图，绿边表示非树边，蓝边表示...

Posted by Dispwnl on September 29, 2018

[CF1039C]Network Safety

题目题目大意给定一个$n$个点$m$条边的图，每个点都有一个权值$c_i$ 定义图为安全的条件为对于所有的边$(u,v)$都保证$c_u≠c_v$ 求对于任意的$x$，集合$s$中所有点的点权$xor~x$后图仍然安全，这样的$x$和$s$的组合的数量 Examples input 4 4 2 0 1 0 1 1 2 2 3 3 4 4 1 output 50 input 4 ...

Posted by Dispwnl on September 27, 2018