Q779’s Blog

洛谷P2458 [SDOI2006]保安站岗 题解 题目链接：P2458 [SDOI2006]保安站岗 题意： 五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。 已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。 一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。 请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。 注意到这道题目可能会有相邻两个都不放保安的情况 首先想到记录一个结点是否放，以及其儿子、儿子的儿子是否放 但是这样比较麻烦 考虑设 \(dp[u][0/1/2]\) 表示 \(u\) 结点： \(0\) 表示被自己覆盖（自己放保安） \(1\) 表示被儿子覆盖（某个（或某些）儿子放保安） \(2\)...

洛谷P2016 战略游戏 题解 题目链接：P2016 战略游戏 题意： Bob 要建立一个古城堡，城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。 注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。 请你编一程序，给定一树，帮 Bob 计算出他需要放置最少的士兵。 注意这里是相邻的边，不是相邻的结点 显然我们需要记录与子结点所连的边是否被监视 于是有 \[ dp[u][0]=\sum dp[v][1]\\ dp[u][1]=\sum \min(dp[v][0],dp[v][1]) \] 然后就没了 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; #define int...

洛谷P4084 [USACO17DEC]Barn Painting G 题解 题目链接：P4084 [USACO17DEC]Barn Painting G 题意：题意：给定一颗N个节点组成的树，3种颜色，其中K个节点已染色，要求任意两相邻节点颜色不同，求合法染色方案数。 这个题太水了 设 \(dp[u][1/2/3]\) 表示 \(u\) 结点涂 \(1/2/3\) 颜色的方案数 根据加法原理， 如果 \(u\) 已经有颜色了，那么 \[ dp[u][j] = \sum dp[v][k]\times [k\ne j]\times [j=\text{val[u]}] \] 否则 \[ dp[u][j] = \sum dp[v][k]\times [k\ne j] \] 时间复杂度 \(O(n)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #inclu...

洛谷P1122 最大子树和 题解 题目链接：P1122 最大子树和 题意： 小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。于是当日课后，小明就向老师提出了这个问题： 一株奇怪的花卉，上面共连有 \(N\) 朵花，共有 \(N-1\) 条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。 老师想了一会儿，给出了正解。小明见问题被轻易攻破，相当不爽，于是又拿来问你。 一眼树形dp 这道题就是要在树上找一个极大权值连通块 显然我们不知道连通块是什么样的，但是不急 树形dp的核心是从子树转移状态 \[...

洛谷P3205 [HNOI2010]合唱队 题解 题目链接：P3205 [HNOI2010]合唱队 题意： 为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 \(n\) 个人，第 \(i\) 个人的身高为 \(h_i\) 米（\(1000 \le h_i \le 2000\)），并已知任何两个人的身高都不同。假定最终排出的队形是 \(A\) 个人站成一排，为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终棑排出的队形中： 第一个人直接插入空的当前队形中。 对从第二个人开始的每个人，如果他比前面那个人高（\(h\) 较大），那么将他插入当前队形的最右边。如果他比前面那个人矮（\(h\) 较小），那么将他插入当前队形的最左边。 当 \(n\) 个人全部插入当前队形后便获得最终排出的队形。 例如，有 \(6\) 个人站成一个初始队形，身高依次为 \(1850, 1900, 1700, 1650, 1800, 1750\...

UVA1629 切蛋糕 Cake slicing 题解 题目链接：UVA1629 切蛋糕 Cake slicing 题意：这个翻译够烂的，直接看pdf 翻译：有一个n行m列(1<=n,m<=20)的网络蛋糕上有k个樱桃。每次可以用一刀沿着网络线把蛋糕切成两块，并且只能够直切不能拐弯。要求最后每一块蛋糕上恰好有一个樱桃，且切割线总长度最小。 输入输出格式 输入格式:每次输入有若干组数据。每组数据第一行有三个正整数n m k(行，列，樱桃个数)，之后的k行每行两个正整数(樱桃的坐标) 输出格式:输出有若干行，对应每组数据。每行输出两个正整数(id,最小的切割长度) 输入输出样例 输入样例: 3 4 3 1 2 2 3 3 2 输出样例: Case 1: 5 首先普通的二维枚举好像不行 数据范围这么小，于是考虑从小的矩形向大的矩形更新 设 \(dp[x_1][y_1][x_2][y_2]\) 表示矩形的左下角为 \((x_1,y_1)\) ，右上角为 \((x_2,y_2)\) 时的最小花费 方便起见，下面转移方程中的 \(dp[x_1][y_1][x_2][y_2]\...

UVA1437 String painter 题解 题目链接：UVA1437 String painter 题意：There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can change a segment of characters of a string to any other character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What’s the minimum number of operations? 1 &...

洛谷P2890 [USACO07OPEN]Cheapest Palindrome G 题解 题目链接：P2890 [USACO07OPEN]Cheapest Palindrome G 题意： Keeping track of all the cows can be a tricky task so Farmer John has installed a system to automate it. He has installed on each cow an electronic ID tag that the system will read as the cows pass by a scanner. Each ID tag’s contents are currently a single string with length M (1 ≤ M ≤ 2,000) characters drawn from an alphabet of N (1 ≤ N ≤ 26) different symbols (namely, the lower-case roman alpha...

洛谷P2851 [USACO06DEC]The Fewest Coins G 题解 题目链接：P2851 [USACO06DEC]The Fewest Coins G 题意： Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that the smallest number of coins changes hands, i.e., the number of coins he uses to pay plus the number of coins he receives in change is minimized. Help him to determine what this minimum number is. FJ wants to buy T (1 ≤ T ≤ 10,000) cents of supplies. The currency system has N...

洛谷P4170 [CQOI2007]涂色 题解 题目链接：P4170 [CQOI2007]涂色 题意： 假设你有一条长度为 \(5\) 的木板，初始时没有涂过任何颜色。你希望把它的 \(5\) 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 \(5\) 的字符串表示这个目标：\(\texttt{RGBGR}\)。 每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成 \(\texttt{RRRRR}\)，第二次涂成 \(\texttt{RGGGR}\)，第三次涂成 \(\texttt{RGBGR}\)，达到目标。 用尽量少的涂色次数达到目标。 考虑区间dp 设 \(dp[i][j]\) 表示涂区间 \([i,j]\) 的最小花费 当 \(i=j\) 时，有 \[ dp[i][j]=1 \] 当 \(i\ne j\) 时， 若 \(a[i]=a[j]\) ，此时只需要 \([i+1,j]\) 或 \([i,j-1]\) 首次涂的时候多涂一格即可 \[ dp[i][j]=\min(dp[i+1][j],dp[i][j-1]) \] ...

AT_apc001_f XOR Tree 题解 题目链接：AT_apc001_f XOR Tree 题意： 给你一棵有 \(N\) 个节点的树，节点编号从 \(0\) 到 \(N-1\) ， 树边编号从 \(1\) 到 \(N-1\) 。第 \(i\) 条边连接节点 \(x_i\) 和 \(y_i\) ，其权值为 \(a_i\)。 你可以对树执行任意次操作，每次操作选取一条链和一个非负整数 \(x\)，将链上的边的权值与 \(x\) 异或成为该边的新权值。 问最少需要多少次操作，使得所有边的权值都为 \(0\) 。 \(2\le N \le10^5,0\le x_i,y_i \le N-1,0\le a_i \le 15\) 首先可以想到，边权不好处理，将其转化为点权 不过如果直接转化为点权似乎还是不好弄 本人想到这就没了 我们知道异或有自反性 \((p\oplus q \oplus p = q )\) 等性质 则考虑将点权定义为 \(\text{val}(u) = \bigoplus\limits_{v_i \in V \land (u,v_i) \in E}w(u,v_i...

CF149D Coloring Brackets 题解 题目链接：CF149D Coloring Brackets 题意：给出一个配对的括号序列（如 “\(\texttt{(())()}\)”、“\(\texttt{()}\)” 等，“\(\texttt{)()}\)”、“\(\texttt{(()}\)”是不符合要求的），对该序列按照以下方法染色。 一个括号可以染成红色、蓝色或者不染色。 一对匹配的括号需要且只能将其中一个染色。 相邻两个括号颜色不能相同（但都可以不染色）。 求符合条件的染色方案数，对 \(1000000007\) 取模。 容易发现这个题目就是个区间dp 但是仅仅用 \(dp[l][r]\) 并不能表示出两侧括号的颜色 因此设 \(dp[l][r][i][j]\) 为区间 \([l,r]\) 内且左右两侧的颜色分别为 \(i,j\) 时的方案数 （0为不染色，1为红，2为蓝） 考虑边界：当 \(l+1=r\) 时，有 \[ \text{()} \] dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r]...