Difference between revisions of "ACM-ICPC 2015 Asia Tsukuba Regional"

From EOJ Wiki
Jump to navigation Jump to search
 
(13 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
= ECNU Foreigners =
 +
 
== Problem A ==
 
== Problem A ==
  
Line 39: Line 41:
 
题解：枚举组合。由插板法，在极限情况下满足第一维和第二维小的也至多 $\binom{23}{9} \approx 8 \times 10^5$，对每种情况用多重组合公式算排列即可。
 
题解：枚举组合。由插板法，在极限情况下满足第一维和第二维小的也至多 $\binom{23}{9} \approx 8 \times 10^5$，对每种情况用多重组合公式算排列即可。
  
−
剩下的要比较数字本身的大小。可以考虑一种数位 DP 和状压 DP 的 mixture。要记录已经用过了哪些位、是否可以随便选。复杂度是 $mathcal{O} (n 2^n \cdot 10)$。还要乘以满足第一维和第二维的组合有多少个。剩下的问题是，这个东西会不会很多呢？U 大胆认为它不会，但 Z 觉得不大靠谱，所以先占机写了 G。
+
剩下的要比较数字本身的大小。可以考虑一种数位 DP 和状压 DP 的 mixture。要记录已经用过了哪些位、是否可以随便选。复杂度是 $\mathcal{O} (n 2^n \cdot 10)$。还要乘以满足第一维和第二维的组合有多少个。剩下的问题是，这个东西会不会很多呢？U 大胆认为它不会，但 Z 觉得不大靠谱，所以先占机写了 G。
  
 
== Problem F ==
 
== Problem F ==
Line 56: Line 58:
  
 
题解：首先用 dp 求出每个区间扩展成回文的最小代价和方案。然后按位枚举求出第 k 大。
 
题解：首先用 dp 求出每个区间扩展成回文的最小代价和方案。然后按位枚举求出第 k 大。
 +
 +
 +
= One,Two,Three,AK =
 +
 +
 +
== Problem A ==
 +
 +
Solved by Xiejiadong. 00:12:07(+)
 +
 +
非常温暖的签到。
 +
 +
== Problem B ==
 +
 +
Solved by oxx1108. 00:31:20(+)
 +
 +
题意：平面上从左到右放圆，问长至少要多少。
 +
 +
题解：枚举每个圆心最左放到哪儿，注意需要和之前所有圆算一下，不能只和左边那个圆算。
 +
 +
== Problem C ==
 +
 +
Solved by oxx1108. 02:34:32(+2)
 +
 +
题意：给一个有向图，两个人博弈，一个人给出步长，另一个人必须走那么多步，问至少几轮走到终点。
 +
 +
题解：将所有必胜态缩为一个点，然后迭代算下一层的必胜态。
 +
 +
忘加层数限制wa了两发。
 +
 +
== Problem D ==
 +
 +
Upsolved by oxx1108 && dreamcloud. (-6)
 +
 +
题意：在一个矩形内，每个人有一个直角的视野，在墙上挂钟使得每个人都能至少看到一个钟。
 +
 +
题解：单纯形法。某人敲错模板导致oxx自闭三小时……
 +
 +
== Problem E ==
 +
 +
Solved by dreamcloud. 01:26:11(+1)
 +
 +
题意：$s$序列含n位，$d_1d_2…d_n$ (都为0~9),
 +
 +
$sum(s) = d_1+d_2+...+d_n$
 +
 +
$prod(s) = (d_1+1) \times (d_2+1)...\times (d_n+1)$
 +
 +
$int(s)$为十进制下大小
 +
 +
定义$s_1 \lt s_2$如下 
 +
 +
（1）$sum(s_1) \lt sum(s_2)$
 +
 +
（2） $sum(s_1) = sum(s_2), and prod(s_1) < prod(s_2)$
 +
 +
（3） $sum(s_1) = sum(s_2), and prod(s_1) = prod(s_2), int(s_1) < int(s_2)$
 +
 +
问你有多少个 n长的串比给定的这个串小（每一位是由0~9组成，可以有前导0），大小的定义为：
 +
 +
题解：数位dp模拟一下即可
 +
 +
== Problem F ==
 +
 +
Upsolved by dream_cloud
 +
 +
题意：p 个进程，r 种资源，告诉你每个进程对各个资源的需求。判断从哪一次资源分配后无法靠安排之后的顺序解决死锁。
 +
 +
题解：二分答案，判断是否会导致死锁。判断的话，对每个资源建立一个优先队列（按照每个进程对该资源的需求排序），一开始所有进程都在申请第一个资源，只有需求量小于第一个资源现有量，才能转移到申请第二个资源，依次类推。直到一个进程得到了所有需要的资源，就把资源释放。有一些坑点。
 +
 +
== Problem G ==
 +
 +
Solved by Xiejiadong. 04:24:25(+)
 +
 +
题意：给出一个字符串，补成回文串，所有长度最小的情况中，求字典序为$k$的串。
 +
 +
题解：我们用$f[i][j]$表示字符串$i$到$j$区间变成回文串最小需要多少字符，$g[i][j]$表示最小字符数情况下的方案数。
 +
 +
直接区间dp，要注意重复情况的考虑，对于$s[l]=s[r]$的区间，不要再去用$max(f[l][r-1],f[l+1][r])$更新答案，就可以避免重复。
 +
 +
然后就是贪心了，从外向内一层一层的进去，如果当前的$s[l]=s[r]$，直接进去，否则判断在前半段还是后半段：比如$s[l]<s[r]$，那么前半段就是相对应的补齐$s[l]$对应的一个，后半对就是补齐$s[r]$对应的一个，然后继续向里。
 +
 +
== Problem H ==
 +
 +
Unsolved.
 +
 +
== Problem I ==
 +
 +
Unsolved.
 +
 +
== Problem J ==
 +
 +
Unsolved.
 +
 +
== Problem K ==
 +
 +
Unsolved.

Latest revision as of 04:53, 8 October 2018

ECNU Foreigners

Problem A

Solved by zerol. 00:15 (+)

温暖的签到。

Problem B

Solved by zerol & ultmaster. 00:24 (+)

题意：求最小距离，使得两块板之间可以塞下题给的所有木棍（不能交换顺序）。

题解：贪心往左放即可。依次计算每根木棍最左可以放到哪儿。

Problem C

Solved by ultmaster. 01:39 (+4)

题意：你在一个图上走。每次老大哥会从预先准备好的三个数中挑一个，然后你必须要走这么多步，你只能决定怎么走。你走投无路或者死循环了就输了。求你从起点到终点，在最坏情况下，要几轮？

题解：典型的博弈 DP。然而会有出现环的情况，在某些情况下某些点会算不对。不知道怎么搞……（其实是因为之前有个题没补）

在尝试了若干假算法之后，ultmaster 提出要不把这个东西迭代 1000 轮。然后就……顺利地 AC 了？

Problem D

Solved by kblack. 01:42 (+)

题意：在一个矩形内，每个人有一个直角的视野，在墙上挂钟使得每个人都能至少看到一个钟。

题解：直角视野对应周长上的一个区间，然后就是一个在环上丽娃河装路灯的问题。我们枚举第一个钟的位置，之后贪心地尽量靠后安装。

Problem E

Solved by ultmaster. 03:50 (+)

题意：定义一种带前导零的数之间的全序关系：按照如下三维依次从小到大：数位和、数位加 1 之积、数字本身大小。求在该意义下的 $n$ 位整数中比 $n$ 为整数 $x$ 小的数有多少个。

题解：枚举组合。由插板法，在极限情况下满足第一维和第二维小的也至多 $\binom{23}{9} \approx 8 \times 10^5$，对每种情况用多重组合公式算排列即可。

剩下的要比较数字本身的大小。可以考虑一种数位 DP 和状压 DP 的 mixture。要记录已经用过了哪些位、是否可以随便选。复杂度是 $\mathcal{O} (n 2^n \cdot 10)$。还要乘以满足第一维和第二维的组合有多少个。剩下的问题是，这个东西会不会很多呢？U 大胆认为它不会，但 Z 觉得不大靠谱，所以先占机写了 G。

Problem F

Solved by kblack. 04:22 (+9)

题意：$p$ 个进程，$r$ 种资源，判断从哪一次资源分配后无法靠安排之后的顺序解决死锁。

题解：无法避免死锁的点存在二分性，因为能跑完的进程一定先跑完更好，通过类似 [1] 的方式贪心判断是否能全部跑完，需要注意一些边界情况。

Problem G

Solved by zerol. 03:31 (+)

题意：给一个字符串 s，求所有 s 是其子序列的最短回文串中第 k 大的。

题解：首先用 dp 求出每个区间扩展成回文的最小代价和方案。然后按位枚举求出第 k 大。


One,Two,Three,AK

Problem A

Solved by Xiejiadong. 00:12:07(+)

非常温暖的签到。

Problem B

Solved by oxx1108. 00:31:20(+)

题意：平面上从左到右放圆，问长至少要多少。

题解：枚举每个圆心最左放到哪儿，注意需要和之前所有圆算一下，不能只和左边那个圆算。

Problem C

Solved by oxx1108. 02:34:32(+2)

题意：给一个有向图，两个人博弈，一个人给出步长，另一个人必须走那么多步，问至少几轮走到终点。

题解：将所有必胜态缩为一个点，然后迭代算下一层的必胜态。

忘加层数限制wa了两发。

Problem D

Upsolved by oxx1108 && dreamcloud. (-6)

题意：在一个矩形内，每个人有一个直角的视野，在墙上挂钟使得每个人都能至少看到一个钟。

题解：单纯形法。某人敲错模板导致oxx自闭三小时……

Problem E

Solved by dreamcloud. 01:26:11(+1)

题意：$s$序列含n位，$d_1d_2…d_n$ (都为0~9),

$sum(s) = d_1+d_2+...+d_n$

$prod(s) = (d_1+1) \times (d_2+1)...\times (d_n+1)$

$int(s)$为十进制下大小

定义$s_1 \lt s_2$如下

（1）$sum(s_1) \lt sum(s_2)$

（2） $sum(s_1) = sum(s_2), and prod(s_1) < prod(s_2)$

（3） $sum(s_1) = sum(s_2), and prod(s_1) = prod(s_2), int(s_1) < int(s_2)$

问你有多少个 n长的串比给定的这个串小（每一位是由0~9组成，可以有前导0），大小的定义为：

题解：数位dp模拟一下即可

Problem F

Upsolved by dream_cloud

题意：p 个进程，r 种资源，告诉你每个进程对各个资源的需求。判断从哪一次资源分配后无法靠安排之后的顺序解决死锁。

题解：二分答案，判断是否会导致死锁。判断的话，对每个资源建立一个优先队列（按照每个进程对该资源的需求排序），一开始所有进程都在申请第一个资源，只有需求量小于第一个资源现有量，才能转移到申请第二个资源，依次类推。直到一个进程得到了所有需要的资源，就把资源释放。有一些坑点。

Problem G

Solved by Xiejiadong. 04:24:25(+)

题意：给出一个字符串，补成回文串，所有长度最小的情况中，求字典序为$k$的串。

题解：我们用$f[i][j]$表示字符串$i$到$j$区间变成回文串最小需要多少字符，$g[i][j]$表示最小字符数情况下的方案数。

直接区间dp，要注意重复情况的考虑，对于$s[l]=s[r]$的区间，不要再去用$max(f[l][r-1],f[l+1][r])$更新答案，就可以避免重复。

然后就是贪心了，从外向内一层一层的进去，如果当前的$s[l]=s[r]$，直接进去，否则判断在前半段还是后半段：比如$s[l]<s[r]$，那么前半段就是相对应的补齐$s[l]$对应的一个，后半对就是补齐$s[r]$对应的一个，然后继续向里。

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Unsolved.

Retrieved from "http://acm.ecnu.edu.cn/wiki/index.php?title=ACM-ICPC_2015_Asia_Tsukuba_Regional&oldid=1828"