noi2015专题

P1955 [NOI2015] 程序自动分析题解

题目在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设x1,x2,x3,⋯ 代表程序中出现的变量，给定n个形如xi=xj或xi!=xj 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2,x2=x3,x3=x4,x4

#128. 【NOI2015】软件包管理器

树链剖分裸题 wa了一发。。。。。是因为mark数组开小不把数组开在一起容易开错空间啊 #include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define MAXN 100010int seg[MAXN*4],sum[MAXN*4];int f

UOJ #131 BZOJ 4199 luogu P2178【NOI2015】品酒大会 (后缀自动机、树形DP)

UOJ #131 BZOJ 4199 luogu P2178【NOI2015】品酒大会 (后缀自动机、树形DP) 水是水，但是写出了不少问题，因此写一发博客。 https://www.luogu.org/problemnew/show/P2178https://www.lydsy.com/JudgeOnline/problem.php?id=4199http://uoj.ac/probl

[洛谷]P2150 [NOI2015] 寿司晚宴题解

就一水DP 待填坑

【数据结构树树链剖分】luogu_2146 [NOI2015]软件包管理器

题意给出一个以树表达的关系，每次选择一个点安装或卸载。如果卸载，那么它儿子们都要卸载。如果安装，那么它父亲们都要安装。求每次操作改变了多少点的状态。思路剖成链然后就是傻逼题。代码 #include <cctype>#include <cstdio>#include <string>#include <iostream>#include <algorithm>st

[NOI2015]品酒大会 [SAM]

传送门其实没有想象中难, 我们知道, 两个串的最长公共后缀就是 parent 树上的LCA 的len 对于出现次数, 枚举每一个 LCA, 然后 siz 乘一下因为如果 len 出现了, len - 1 也出现了, 所以求一个后缀和对于最大值, 我们维护子树最大与次大, 因为有负数, 所以还要维护次小与最小同样对最大值也求一个后缀最大 #include<bits/stdc+

[UOJ 130]【NOI2015】荷马史诗：哈夫曼树

点击这里查看原题二叉哈夫曼树教程：http://blog.csdn.net/shuangde800/article/details/7341289 这里是k叉哈夫曼树，依然采取贪心策略，不过需要注意的是首先要判断(n-1)%(k-1)是否为0，不为0则要添加权值为0的节点直到(n-1)%(k-1)=0 这是因为，每次合并操作会取出k个点，放进1个点，即每次减少k-1个点。而最终目标是使n个

[BZOJ4199] [Noi2015]品酒大会

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=4199 题目大意给定以i开始的所有子串权值为ai 给定以i开始的所有子串权值为a_i 询问所有子串中lcp(i,j)(从i开始和从j开始的子串)<=1..n−1的对数以及max{ai∗aj} 询问所有子串中lcp(i,j)_{(从i开始和从j开始的子串)}<=1..n-1的对数以

bzoj4197[Noi2015]寿司晚宴 [状压DP]

4197: [Noi2015]寿司晚宴 Time Limit: 10 Sec Memory Limit: 512 MB Submit: 652 Solved: 413 [Submit][Status][Discuss] Description 为了庆祝 NOI 的成功开幕，主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手，也被邀请参加了寿司晚宴。在晚宴上,主办方为

Codevs 4600 [NOI2015]程序自动分析

4600 [NOI2015]程序自动分析时间限制: 1 s 空间限制: 256000 KB 题目等级 : 黄金 Gold 传送门题目描述 Description 在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设x1,x2,x3,…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定

BZOJ4196 NOI2015 软件包管理器树链剖分

题意：给定一颗树，维护：1、给定一个节点，求该节点到根的路径上总点数-点权和，并将路径上的所有点的权值赋为1 2、给定一个节点，求该节点子树的点权和，并将子树中所有点的权值赋为0 题解：链剖裸题 #include <cstdio>#include <cstring>#include <cstdlib>#include <climits>#include <iostream>#

[NOI2015] 程序自动分析（并查集）

题解最后的结果与约束条件的顺序无关，可以先考虑相等条件，再考虑不等条件。由于题目中i和j的数据范围较大，需要用到离散化。代码 #include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <unordered_map>using namespace std;c

[NOI2015]荷马史诗 - Huffman树

题目描述追逐影子的人，自己就是影子。 ——荷马 llison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。一部《荷马史诗》中有 n 种不同的单词，从 1 到 n 进行编号。其中第 i 种单词出现的总次数为 wi。Al

【NOI2015】bzoj4198 荷马史诗

Description 追逐影子的人，自己就是影子。 ——荷马 Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。一部《荷马史诗》中有 n 种不同的单词，从 1 到 n 进行编号。其中第 i 种单词出现的

noi2015软件包管理器

【题目描述】你决定设计你自己的软件包管理器。不可避免的，你要解决软件包之间的依赖关系。如果A依赖B，那么安装A之前需安装B，卸载B之前须卸载A。0号软件包不依赖任何软件包。依赖关系不存在环(包括自环)。你的任务是，求出每次安装、删除操作会改变多少个包的状态。安装一个已安装的软件包，或者卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0 每

[NOI2015]品酒大会

传送门先对这个字符串求一下SA 考虑SA数组中第i位,暴力计算贡献就是向后枚举，然后计算枚举到的位与第i位之间height的最小值,然后对r==min(height)的贡献就是这一对数并且可以用他们的权值之积可以更新最大值考虑height较大的是不会对height较小的有贡献，就可以从height大的到height小的依次计算可以保证height较大的形成的集合通过当前height连