首页 > 代码库 > 09day1

09day1

词编码

模拟

【问题描述】

一个发送机可以通过一条隧道发送一些以二进制代码组成的单词。在其尽头的接受机可以使用特殊技术恢复到最初的单词。每个单词最初都由0和1组成。所有的单词最初长度都为n(4<=n<=1000)。当穿过隧道之后单词可能发生以下几种情况之一:

(1)任意(一个)0 被 1 取代;

(2)任意(一个)符号被删除;

(3)一个符号(0 或 1)被插入到任何位置;

(4)不改变。

我们知道最初的单词都具有以下性质:有 1 的位置号的总和是 n+1 的倍数,或者是 0。

【输入】

n 和转换后的单词,每个单词占一行。单词数不大于 2001,不会有其他任何东西,除了空格和空行。

【输出】

你的程序应该打印输出原始序列的词,注意换行。

若有多解,操作 4 有限,不行则按操作 1、2、3 优先。同一操作,按操作位置最先的优先(从左到右数起 1、2、3…n)。对于操作 2,先在被删数列添 0,不行再添 1。

如果没有答案则输出-1。

【输入样例】

4

0000

011

1011

11011

【输出样例】

0000

0110

1001

1111

【解题过程】

按照题目要求的优先顺序依次模拟即可。

但是不能无脑模拟,要加优化。用 a[i] 记录 i...n 中有几个 1,用 b[i] 记录 i...n 中的 1 的位置和。然后模拟的时候就不用进行字符串的操作了。

第一次提交80 分。没有部分和优化超时两个点。

(虽然现在还没 A 掉但是我会尽量在 NOIP 之前把这道水题 A 掉以增加信心的。)

?

笨笨粉刷匠

动态规划

【问题描述】

笨笨太好玩了,农田荒芜了,彩奖用光了,笨笨只好到处找工作,笨笨找到了一份粉刷匠的工作。

笨笨有 n 条木板需要被粉刷。每条木板被分成 m 个格子,每个格子要被刷成红色或蓝色。笨笨每次粉刷,只能选择一条木板上一段连续的格子,然后涂上一种颜色,已知每个格子最多只能被粉刷一次。

如果笨笨只能粉刷 t 次,他最多能正确粉刷多少格子。

一个格子如果未被粉刷或被粉刷成错误颜色,就算粉刷错误。

【输入】

第一行三个数 n,m,t;

接下来 n 行,每行一个长度为 m 的字符"0"表示红色,"1"表示蓝色。

【输出】

一个整数,最多能正确粉刷的格子数。

【输入样例】

3 6 3

111111

000000

001100

【输出样例】

16

【数据规模】

1≤n,m≤50,0≤t≤2500。

【解题过程】

很明显有个背包在里面,把 t 次粉刷分配给 n 块板,要求最大收益。所以我们只要计算出每块板粉刷 k 次所能得到的收益。

在这里纠结了很久,我最初的想法是O(N^6) 的动规(丧心病狂),用 f(a, i, j, k) 表示在木板 a 的区间 [i, j] 上粉刷 k 次能得到的最大收益,然后枚举中间点将其分为两个部分,并枚举左右两边各粉刷的次数。

然后又想了很久才想到比较靠谱的算法(是有多弱?):用 f(a, i, j) 表示在木板 a 的区间 [1, i] 上粉刷 j 次能得到的最大收益,则

f(a, i, j) = max{ f(a, k, j-1)+PAINT(k+1, i) }, 1<=k<i

其中PAINT(k+1, i) 取以下三种操作的最大收益:

  1. 将 [k+1, i] 整个区间涂成同一种颜色(显然应该涂格子数较多的那种颜色)
  2. 涂区间中最长的红色连续区间
  3. 涂区间中最长的蓝色连续区间

然后在预处理 PAINT(a, b) 的时候我又脑洞大开,开始准备写线段树求最长的连续颜色区间,后来想想貌似可以 RMQ?再后来发现直接对于每个区间暴力扫一遍就好了嘛。

初次提交 AC。

?

笨笨的电话网络

二分答案+最短路

【问题描述】

多年以后,笨笨长大了,成为了电话线布置师。由于地震使得某市的电话线全部损坏,笨笨是负责将电话线接到该市的负责人。

该市周围分布着 N(1≤N≤1000)根按 1..N 顺次编号的废弃的电话线杆,任意两根电话线杆间都没有电话线相连。一共 P(1≤P≤10000)对电话线杆间可以拉电话线,其余的由于地震使得无法被连接。第 i 对电话线杆的两个端点分别为 Ai,Bi,它们间的距离为 Li(1≤Li≤1000000)。数据保证每对(Ai,Bi)最多只出现 1 次。编号为 1 的电话线杆已经接入了全国的电话网络,整个市的电话线全都连到了编号为 N 的电话线杆上。也就是说,笨笨的任务仅仅是找一条将 1 号和 N 号电话线杆连起来的路径,其余电话线杆并不一定要连入电话网络。

电信公司决定支援灾区免费为该市连接 K(0≤K≤N)对由笨笨指定的电话线杆。对于此外的那些电话线,需要为它们付费,总费用等于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。

如果需要连接的电话线杆不超过 K 对,那么总支出为 0。

笨笨需要计算一下,将电话线引到震中市最少需要在电话线上花多少钱?

【输入】

输入文件的第一行包含三个用空格隔开的整数:N,P 和 K。

第二行到第 P+1 行:每行分别都为三个用空格隔开的整数:Ai,Bi 和 Li。

【输出】

输出文件中仅包含一个整数,表示在这项工程上的最小支出。如果任务不可能完成,则输出-1。

【输入样例】

5 7 1

1 2 5

3 1 4

2 4 8

3 2 3

5 2 9

3 4 7

4 5 6

【输出样例】

4

【解题过程】

首先很明显免费的 K 条肯定是路径中最大的 K 条,所以要二分枚举最终选择的路径中按边权从大到小排序后的第 K+1 条边的权值是多少,这个权值就是最后的费用。二分出来之后,我一开始用了 DFS 判断解的正确性,O(N!) 不靠谱。然后又想了一会儿,想到可以用最短路验证,具体来说就是二分枚举出一个边权 mid 后,把图中权值大于 mid 的边设为 1,权值小于 mid 的边设为 1,然后从 1 到 N 做最短路,求出的最短路如果 <= K,那么这个解就可行,继续二分。

初次提交 10 分左右,原因是一开始是枚举权值,后面改成了在边集数组中枚举,但是忘了改相应的函数参数等等。

09day1