Latest revision as of 05:38, 31 August 2018

NEERC 11

某几题解[solutions]

Problem A

Solved by dreamcloud. 00:22

题意：签到题，求"/"和"\"围成的面积

题解："/","\",表示面积为0.5。"."，表示面积为1。每一行斜杠个数一定是偶数，那么第奇数和偶数斜杠之间的"."一定在多边形之内

Problem B

Solved by oxx1108. 00:42

题意：给小于$m$的数二进制编码，要求满足一堆性质的情况下用的数字最少。

题解：签到题，读懂题就会做了。

Problem C

Solved by Xiejiadong & oxx1108. 04:26(+1)

题意：给出每一个字母的点阵，求讲一个句子点阵变换成另一个句子的点阵最少需要几步。

题解：暴力预处理每一个字母在每一个位置为开始的最少需要改变多少的点阵位置。

然后就是跑dp，$f[i][j]$表示新句子的前$i$个字母，填到第$j$列最少需要改变的次数，暴力转移即可。

这道题目的输入非常繁琐，oxx完成了最复杂的一块；Xiejiadong写了最简单的dp一块，还写挂了，请来了oxx debug，发现了第一个字母前面空格个数不限的坑点。

Problem D

Solved by Xiejiadong. 01:12(+1)

题意：可以将两个字符串首位相接，或者取单个字符串，求本质不同的字符串有几个。

题解：用Trie树来跑，按照前缀和后缀分别构建Trie树，显然这样做是会重复的。而重复的一段必然是由于中间段相同所引起的。那么我们可以处理前缀的后缀和后缀的前缀相同的个数，来去重，类似于容斥。

Problem E

Solved by dreamcloud. 02:35(+1)

题意：签到题，给一些人，给你他们的家谱，问你他们的母系DNA是否一样。

题解：读懂题目是个很复杂的事情，只需要并查集。

Problem F

Unsolved.

Problem G

Solved by Xiejiadong. 02:25

题意：猜一个$1-n$之间的数，你每次给出一个猜的数，他会告诉你和答案$gcd$的结果，求这样猜，在最坏情况下，最多要猜几次。

题解：显然最坏情况下便是，让你猜的数是$1$，那么你需要猜遍所有的质数才可以猜到他。而质数是可以一起猜的，比如猜$2$、$3$，我们可以猜$2*3$。

也就是说，我们要尽可能把素数组合在一起，使得组数最小，而且每一组素数的乘积都$\le n$。

我们可以采用贪心的做法：每次取一个当前最大的数，然后用尽可能多的最小的数去和他凑在一起，组成一组。

直观上感觉出来的，不会证明。

Problem H

Unsolved.

Problem I

Solved by oxx1108. 01:27

题意：交互题，猜全排列，每次告诉你猜的序列与答案序列的最长子序列（不连续），要求在$5n^2$次数以下猜出来。

题解：从1开始枚举每个数的位置(其他数相对位置不变)，那么答案只可能$\pm1$或者不变，当$+1$的时候说明放到了恰当的位置，则可以继续枚举下一个数，若不存在则这个数原来一定已经在最长子序列中则不需要修改，上限$n^2$次。

Problem J

Unsolve.

Problem K

Solved Xiejiadong. 00:51

题意：给出一棵树，任意去掉一条边，求至少需要几条边，可以保证联通。

题解：按照叶子的dfs序劈成两半，依次连边。如果是奇数的话，把最中间的两个点连起来即可。

Problem L

Upsolved by dreamcloud

题意：有一座桥，从左往右有$n_1$条路，从右往左$n_2$条路，有一条路为待定。即早上有$(n_1+1)$条从左往右，晚上有$(n_2+1)$条从右往左，路改变方向需要等r个时刻。分别告诉你从1到m时刻的两个方向车数量。要求决定一个时刻改道路方向，使得所有车辆等待时间最小化。

题解：左往右与右往左是两个独立的问题，设$f[i]$表示i时刻开始左从右车道减少一条的答案。容易发现$f[i]$与$f[i + 1]$是有关系的。所以线性计算。首先计算出来$f[m+1]$即从左往右都是$(n_1+1)$，来开始减少车道。若从$(n_1+1)$减少到$n_1$，如果原来该时刻通过车辆少于$(n_1+1)$，那么什么都不做。否则说明有一辆车此时通过不了，需要找到后面最早有空余车道的时刻让其通过，这个只需要队列记录一下。所以可以$O(1)$转移。同理从右往左。

@@ Line 1: / Line 1: @@
 =NEERC 11=
-* 某题题解[[http://www.doc88.com/p-7364584446751.html solutions]]
+* 某几题解[[http://www.doc88.com/p-7364584446751.html solutions]]
 == Problem A ==
-Solved . 00:34
+Solved by dreamcloud. 00:22
-== Problem B ==
+题意：签到题，求"/"和"\"围成的面积
-Upsolved by oxx1108.(-16)
+题解："/","\",表示面积为0.5。"."，表示面积为1。每一行斜杠个数一定是偶数，那么第奇数和偶数斜杠之间的"."一定在多边形之内
-垃圾题目毁我青春
+== Problem B ==
-题意：求题意比较难懂。（题意巨坑）
+Solved by oxx1108. 00:42
-给一些物品，每个可以取或者不取，想要不大于$c$的最大物品重量和。
+题意：给小于$m$的数二进制编码，要求满足一堆性质的情况下用的数字最少。
-一开始随机有一个A序列（01串），每一位表示物品取还是不取。
-每次给一个随机B序列的重量和，随机方式是在A序列上随机修改一位01。
+题解：签到题，读懂题就会做了。
-每次有三个选项，可以拿新的B串代替A串，不做任何操作，或者结束操作直接返回（答案就为现在的B串）。
+== Problem C ==
-要求操作次数少于1000。
+Solved by Xiejiadong & oxx1108. 04:26(+1)
-题解：直接先将01串变为全0，然后变为全1，然后就可以计算出每个物品的质量，状压算出最大状态，最后随机到答案。
-由于没看到一开始A序列随机死活过不了。
-== Problem C ==
-Solved by Xiejiadong.02:53(+9)
+题意：给出每一个字母的点阵，求讲一个句子点阵变换成另一个句子的点阵最少需要几步。
-题意：给每个人分配一个相同的长度，使得每个人可以在自己的区间里面找出互不重叠的区间。
+题解：暴力预处理每一个字母在每一个位置为开始的最少需要改变多少的点阵位置。
-题解：用long double来二分答案，然后暴力枚举分母，找出分数的表示。
+然后就是跑dp，$f[i][j]$表示新句子的前$i$个字母，填到第$j$列最少需要改变的次数，暴力转移即可。
-需要注意精度问题，wa到自闭。
+这道题目的输入非常繁琐，oxx完成了最复杂的一块；Xiejiadong写了最简单的dp一块，还写挂了，请来了oxx debug，发现了第一个字母前面空格个数不限的坑点。
 == Problem D ==
-Unsolved.
+Solved by Xiejiadong. 01:12(+1)
-题意：
+题意：可以将两个字符串首位相接，或者取单个字符串，求本质不同的字符串有几个。
-题解：
+题解：用Trie树来跑，按照前缀和后缀分别构建Trie树，显然这样做是会重复的。而重复的一段必然是由于中间段相同所引起的。那么我们可以处理前缀的后缀和后缀的前缀相同的个数，来去重，类似于容斥。
 == Problem E ==
-Solved by oxx1108.02:29(+1)
+Solved by dreamcloud. 02:35(+1)
-题意：给定一些砝码箱，每个砝码箱里有若干个10的次幂的砝码。求能够称出$x$至少需要几个箱子。
+题意：签到题，给一些人，给你他们的家谱，问你他们的母系DNA是否一样。
-题解：从个位开始贪心放，讲所有能取的都扔进一个一个优先队列，每次都取最大的放即可。
+题解：读懂题目是个很复杂的事情，只需要并查集。
-忘了考虑1e18，wa了一发。
 == Problem F ==
@@ Line 60: / Line 51: @@
 Unsolved.
-题意：
+== Problem G ==
-题解：
+Solved by Xiejiadong. 02:25
-== Problem G ==
+题意：猜一个$1-n$之间的数，你每次给出一个猜的数，他会告诉你和答案$gcd$的结果，求这样猜，在最坏情况下，最多要猜几次。
-Solved by dreamcloud.02:01(+1)
+题解：显然最坏情况下便是，让你猜的数是$1$，那么你需要猜遍所有的质数才可以猜到他。而质数是可以一起猜的，比如猜$2$、$3$，我们可以猜$2*3$。
-dreamcloud:罚时是不会数位dp的oxx贡献的。
+也就是说，我们要尽可能把素数组合在一起，使得组数最小，而且每一组素数的乘积都$\le n$。
-题意：[0，n]中有多少个数满足k进制下，和-k进制下表达一样
+我们可以采用贪心的做法：每次取一个当前最大的数，然后用尽可能多的最小的数去和他凑在一起，组成一组。
-题解：转换一下题意，就变成了一个数取k进制之后，$a_m,a_{m-1},……a_3,a_2,a_1,a_0$,要满足$a_m,,……,0,a_2,0,a_0$,即奇数位一定是0，数位dp一下。
+直观上感觉出来的，不会证明。
 == Problem H ==
-Solved by dreamcloud.01:34
+Unsolved.
-题意：给你一个字符串s，求它有多少个子序列，满足重构之后是回文串。(重构指的是将子序列中的字符任意交换位置)
-题解：子序列重构是回文，其实就是最多只有一个字母出现次数是奇数。利用hash异或和来维护前缀中每个字母出现的次数为奇还是为偶。从前往后扫，要么每个字母都是偶数，要么枚举一个字母出现奇数，只需要看前面该状态有多少个。类似于EOJ七月月赛。
 == Problem I ==
-Unsolved.
+Solved by oxx1108. 01:27
-题意：
+题意：交互题，猜全排列，每次告诉你猜的序列与答案序列的最长子序列（不连续），要求在$5n^2$次数以下猜出来。
-题解：
+题解：从1开始枚举每个数的位置(其他数相对位置不变)，那么答案只可能$\pm1$或者不变，当$+1$的时候说明放到了恰当的位置，则可以继续枚举下一个数，若不存在则这个数原来一定已经在最长子序列中则不需要修改，上限$n^2$次。
 == Problem J ==
-Solved by Xiejiadong. 03:59(+1)
+Unsolve.
-题意：从0出发，用$a$次$\pm 1$,$b$次$\pm 2$,$c$次$\pm 3$遍历所有的$0$到$a+b+c$点。
-题解：先把$c$次$\pm 3$的处理掉。我们通过向右、向左、再向右三部分，把前面的一部分填满，并且最后填的一个的左边已经全部填满，右边全部没有填过
-再向右一步一步填，剩下一个$\pm 1$用来在最后改变方向，剩下的$\pm 2$我们用过向右、转弯、向左来填满右边剩下的部分
-注意各类情况的处理与细节问题
 == Problem K ==
-Unsolved.
+Solved Xiejiadong. 00:51
-题意：
+题意：给出一棵树，任意去掉一条边，求至少需要几条边，可以保证联通。
-题解：
+题解：按照叶子的dfs序劈成两半，依次连边。如果是奇数的话，把最中间的两个点连起来即可。
 == Problem L ==
-[[File:QQ20180827-132716@2x.png|200px|thumb|right|左手路径]]
+Upsolved by dreamcloud
-Upsolved by Xiejiadong.
-题意：给定一个点阵，点阵中本身存在障碍物，现在要求用一个最小的正方形填在没有障碍物的子矩阵中作为障碍，使得无法从$(1,1)$走到$(n,m)$，求这个最小正方形的边长和左上角的坐标。
-题解：首先是两个概念，一张点阵中从$(1,1)$到$(n,m)$不再联通的条件是，那个正方形同时切断了图中的左手路径和右手路径
-所谓左手路径就是从$(1,1)$开始一直向右，左手一直扶在墙上所走出的路径，如右图：
-右手路径的解释正好与之相对应。
-走左手路径的方式是：如果前进方向的左边一直有墙，一旦前面碰墙，右转；如果左边没有墙了，左转；如果左边和前面以及右边都有墙，掉头。右手路径的处理方式与之相反。
-处理完了路径，我们只需要枚举我们要填正方形的左上角的左边，然后二分正方形的边长，具体二分是：
-* 如果该边长所覆盖的区域本身有障碍，缩小边长
-* 如果该边长所覆盖的区域没有左手路径或者右手路径，增大边长
-这样一来，我们剩下的问题就是怎么$O(1)$的回答当前正方形区域有没有障碍和有没有左右手路径了
+题意：有一座桥，从左往右有$n_1$条路，从右往左$n_2$条路，有一条路为待定。即早上有$(n_1+1)$条从左往右，晚上有$(n_2+1)$条从右往左，路改变方向需要等r个时刻。分别告诉你从1到m时刻的两个方向车数量。要求决定一个时刻改道路方向，使得所有车辆等待时间最小化。
-对有障碍和左右手路径的坐标分别标记，然后处理一下前缀和，就可以直接查询当前区间里面是否有障碍和左右手路径了
+题解：左往右与右往左是两个独立的问题，设$f[i]$表示i时刻开始左从右车道减少一条的答案。容易发现$f[i]$与$f[i + 1]$是有关系的。所以线性计算。首先计算出来$f[m+1]$即从左往右都是$(n_1+1)$，来开始减少车道。若从$(n_1+1)$减少到$n_1$，如果原来该时刻通过车辆少于$(n_1+1)$，那么什么都不做。否则说明有一辆车此时通过不了，需要找到后面最早有空余车道的时刻让其通过，这个只需要队列记录一下。所以可以$O(1)$转移。同理从右往左。

Difference between revisions of "2011-2012 ACM-ICPC Northeastern European Regional Contest (NEERC 11)"