战略游戏[SDOI2018]

https://www.luogu.com.cn/problem/P4606 题解每次是试图摧毁一个城市和它连着的所有边,发现如果摧毁的不是一个割点那么就不会有任何影响,所以先建出原图的圆方树 每次选择了若干个关键节点,建出这些关键节点在圆方树上的虚树,有一个显而易见的结论: 答案即为虚树上(包括在虚树的某条边上)所有非关键节点的圆点个数 虚树上所有的叶子节点都一定是关键节点 断掉一个非关键...

最佳团体[JSOI2016]

https://www.luogu.com.cn/problem/P4322 题解网上怎么这么多O(n^3\log n)假做法啊。。。一条链就卡掉了 假设0号节点是根 建出表示依赖关系的图 发现正好有n条边且每个点的父亲都比它编号小所以正好是一棵树 那么原问题就是要在树上取一个包含根的性价比最高的连通块 看到”性价比”考虑使用01分数规划 假设x_i\in \{0,1\}表示第i个人选不选 ...

按位或[HAOI2015]

题目描述刚开始你有一个数字0,每一秒钟你会随机选择一个[0,2^n-1]的数字,与你手上的数字进行或(C++, C 的 |, Pascal 的 or)操作。选择数字i 的概率是p[i](保证0\le p[i]\le 1,\ \sum p[i]=1) 问期望多少秒后,你手上的数字变成2^n-1。 题解min-max容斥: \max(S)=\sum\limits_{T \subset S \ca...

无归岛[HNOI2009]

题目描述https://www.luogu.com.cn/problem/P4410 题解原图显然是一个仙人掌(似乎还有些别的性质 但是其实没什么必要) 先考虑树的情况,题意即为不能同时选择相邻的两点,设f[x][0/1]表示选/不选x时,x子树内的最大战斗力 f[x][0]=\max\limits_{y\in son(x)} (\max(f[y][0],f[y][1]))f[x][1]=\...

仓库建设[ZJOI2007]

题目描述https://www.luogu.com.cn/problem/P2120 题解设S_i=\sum\limits_{j=1}^{i} p_j,T_i=\sum\limits_{j=1}^{i} p_j*a_j $S_i$即为前i个工厂的物品总数,T_i为前i个工厂都把所有物品运到工厂1的总花费(虽然不能运到仓库1) 设f_i表示把前i个工厂的物品都运到仓库里且在i工厂处建立仓库的...

征途[SDOI2016]

题目描述Pine 开始了从S地到T地的征途。 从S地到T地的路可以划分成h段,相邻两段路的分界点设有休息站。Pine 计划用m天到达T地。除第n天外,每一天晚上 Pine 都必须在休息站过夜。所以,一段路必须在同一天中走完。Pine 希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。 帮助 Pine 求出最小方差是多少。 设方差是v,可以证明,v*m^2是一个整数。...

区间[NOI2016]

题目描述在数轴上有n个闭区间从1至n编号,第i个闭区间为[l_i,r_i] 现在要从中选出m个区间,使得这m个区间共同包含至少一个位置。换句话说,就是使得存在一个x,使得对于每一个被选中的区间[l_i,r_i] 对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间[l_i,r_i]的长度定义为(r_i-l_i)即等于它的右端点的值减去左端点的值。 求所有合法方...

文件路径[BOI2015]

题目描述https://www.luogu.com.cn/problem/P6843 题解题目实际在求这样一个东西:给定一棵树和边权,你可以在树中加上一条长为S的有向边 对于每个叶子节点问:是否能构造出一条从根节点出发以该节点为终点的长为K的路径 设有一个叶子节点x 情况1根到x的路径长等于`$K$ 那显然答案就是 Yes 情况2走了一次附加的有向边使得路径长为`$K$ 考虑这条有向边的终点...

仙人掌[ZJOI2017]

题目描述https://www.luogu.com.cn/problem/P3687 题面里咋还有张图啊,就不放这了 题解首先,如果原图不是仙人掌,显然答案为0 如果原图是一棵树,那么我们可以选择若干条边不相交的路径,如果某条路径长度大于一,就将路径的两个端点间加一条边,那么这样构造出来的图一定是一个仙人掌 所以原问题实际在问有多少种方案用若干条边不相交的路径覆盖原图 设f[x]表示考虑x的...

寻找车位[Code+#3]

题目描述access_globe 有一个巨大的停车场,这个停车场有N行,每行有M个车位。为了美观,access_globe 在建立这个停车场时,规定这个停车场必须是长条形的,即N\ge M。每个车位都是一个正方形的区域。 最近,access_globe 正在为抽不到 Missing Poster 而苦恼,因此他请你帮他维护这个停车场。你需要支持两个事件: 一辆车停到某一个车位中,或一辆车从...