Q779’s Blog

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]) \] ...

AT3913 XOR Tree 题解 题目链接：AT3913 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\) 首先可以想到： 边权不好处理，将其转化为点权 不过如果直接转化为点权似乎还是不好弄 q779想到这就没了 我们知道异或有自反性 \((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]...

CF19B Checkout Assistant 题解 题目链接：CF19B Checkout Assistant 题意：Bob 来到一家现购自运商店，将 \(n\) 件商品放入了他的手推车，然后到收银台付款。每件商品由它的价格 \(c_i\) 和收银员扫描它的时间 \(t_i\) 秒定义。 当收银员正在扫描某件商品时，Bob 可以从他的手推车中偷走某些其它商品。Bob 需要恰好 \(1\) 秒来偷走一件商品。Bob 需要付给收银员的最少钱数是多少？请记住，收银员扫描商品的顺序由 Bob 决定。 这个题确实有点难想，因为它的背包容量和物品都是与 \(n\) 有关的 观察题目的性质，我们需要带走所有的 \(n\) 件物品 而第 \(i\) 件物品可以花费 \(c_i\) 的价格带走 \(t_i+1\) 件物品 为什么是 \(+1\) ？因为它本身也会被带走 题目要求的是带走这 \(n\) 件物品的最小花费，可以看出这是一个01背包 但是背包的大小并不是很好确定 因为选择的物品它们的 \(\sum (t_i+1)\) 很可能会超过 \(n\) 那么最多会超过多少呢？不难发现背包容...

CF219D Choosing Capital for Treeland 题解 题目链接：CF219D Choosing Capital for Treeland 题意：Treeland国有n个城市，这n个城市连成了一颗树，有n-1条道路连接了所有城市。每条道路只能单向通行。现在政府需要决定选择哪个城市为首都。假如城市i成为了首都，那么为了使首都能到达任意一个城市，不得不将一些道路翻转方向，记翻转道路的条数为k。你的任务是找到所有满足k最小的首都。 随便找一个点 \(rt\) 跑一遍dfs，求出这个 \(dp[rt]\) 的值 然后 \(dp[u] \to dp[v]\) 的转移显然与 \((u,v)\) 有关 判断一下然后转移一下就没了 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(2e5+15) struct Edge { int u,v,next; ...

CF294B Shaass and Bookshelf 题解 题目链接：CF294B Shaass and Bookshelf 题意：Shaass has \(n\) books. He wants to make a bookshelf for all his books. He wants the bookshelf’s dimensions to be as small as possible. The thickness of the \(i\) -th book is \(t_{i}\) and its pages’ width is equal to \(w_{i}\) . The thickness of each book is either \(1\) or \(2\) . All books have the same page heights. Shaass puts the books on the bookshelf in the following way. First he selects some of the books and put th...

CF374C Inna and Dima 题解 题目链接：CF374C Inna and Dima 题意： Inna和Dima在商店买了一张 n * m 的桌子，桌子的每一个单元格上都有一个字符，字符集为(“D”,“I”,“M”,“A”)。 Inna实在是太爱Dima了，所以她想在桌子上找出一条最长的路线，使得这条路线中包含尽可能多的Dima的名字（有序，即必须是连续的DIMA）。 Inna的路线选取方式会遵循以下原则： 1.一开始，Inna会在桌子上找到所有的”D”，把他们作为起点。 2.Inna会在当前格子的周围四个相邻的格子中选取一个格子，她会从”D”走到”I”，从”I”走到”M”，从”M”走到”A”。这样，她就认为自己走完了一次Dima的名字。 3.Inna每走完一个格子，就会在该格子四周相邻的四个格子中选一个走，即上下左右四个方向，（当然，她不能走出这张桌子）。Inna从不跳过一个字母。因此，从字母”D”开始，她总是走到字母”I”，从字母”I”开始，她总是走到字母”M”，从字母”M”开始，她总是走到字母”A”，从字母”A”开始，她总是走到字母”D”。 因为桌子的不同，...

CF346B Lucky Common Subsequence 题解 题目链接：CF346B Lucky Common Subsequence 题意： 通过删除一个字符串中的某些元素而不改变其余元素的顺序，可以派生出该字符串的一个子序列。例如，序列 BDF 是 ABCDEF 的子序列。 字符串的子字符串是该字符串的连续子序列。 例如，BCD是ABCDEF的子串。 现在你得到了两个字符串 \(s_1,s_2\) 和另一个名为 virus 的字符串。你的任务是找到 \(s_1\) 和 \(s_2\) 的最长公共子序列，同时不包含 virus 子字符串。 串长均小于等于 \(100\) 。 升级版的最长公共子序列问题（LCS问题） 考虑增加一维，称为「与 \(c\) 串的匹配度」，即： 设 \(f(i,j,k)\) 表示 \(a\) 串匹配到第 \(i\) 位，\(b\) 串匹配到第 \(j\) 位，且最长公共子序列与 \(c\) 串匹配到第 \(k\) 位的某个串。 显然当 \(a_i \ne b_j\) 时，有 \[ f(i,j,k) \uparrow \max\left\{f...

CF41D Pawn 题解 题目链接：CF41D Pawn 题意：国际象棋棋盘最底行站了一个兵。 它只有两种行动方式： 向上左或向上右走。 它可以选择从最低行哪个节点开始他的旅程。 每个格子上有0-9颗豌豆，而士兵想移动到最上一行并且积累到尽可能多的豌豆。同时，因为这个士兵必须把豌豆平均分给自己和他的k个兄弟，他所收集到的豌豆必须是k+1的倍数。请找到他可以收集到的最多豌豆，并确定他的操作序列。 规定士兵不能手动扔出豌豆，并且他必须捡起所到达的每一个格子的所有豌豆。 输入格式： 第一行三个整数 \(n,m,k(2 \le n,m \le 100, 0 \le k \le 10)\) 行数、列数、士兵的兄弟们。 接下来一个 \(n \times m\) 的矩阵，每个元素均是0-9的整数（不空格），描述该格的豌豆。第一行被认为是最上一行，最后一行被认为是最下一行。 输出格式： 如果不能收集到k+1倍数的豌豆，输出-1. 否则，输出第一行一个整数，为最多豌豆数；第二行一个整数，为士兵开始移动的位置；第三行包括n-1个字母L 或 R，表示士兵的行动序列。 如果有多种收集到相同且是k+1...