Difference between revisions of "2018 Multi-University, HDU Day 4"

From EOJ Wiki
Jump to navigation Jump to search
Line 2: Line 2:
  
 
Solved by zerol. 03:24 (+2)
 
Solved by zerol. 03:24 (+2)
 +
 +
题意:求 $f(n,m)=\sum_{i=0}^m \binom{n}{m}$ 范围和询问都是 1e5。
 +
 +
题解:$f(n,m)$ 可以 $O(1)$ 转移到 $f(n\pm 1,m)$ 和 $f(n,m\pm 1)$,然后莫队。
  
 
== Problem D ==
 
== Problem D ==

Revision as of 15:56, 1 August 2018

Problem B

Solved by zerol. 03:24 (+2)

题意:求 $f(n,m)=\sum_{i=0}^m \binom{n}{m}$ 范围和询问都是 1e5。

题解:$f(n,m)$ 可以 $O(1)$ 转移到 $f(n\pm 1,m)$ 和 $f(n,m\pm 1)$,然后莫队。

Problem D

Solved by ultmaster. 01:02 (+2)

题意:有 $n$ 道题目,每道题目有 $a_i$ 个正确答案和 $b_i$ 个错误答案。现在有 $n$ 个人,设计合理策略使得最高分最大。

题解:简单地认为策略是笛卡尔乘积。出了个假算法过了。

zerol: 必须要喷,___出题人,出假题导致 WA 到怀疑人生(虽然也不一定是正解),发现不对 std 假了就魔改题面,然后还是假的就加样例解释。好在队友 ultmaster 与出题人心有灵犀,一下子就 A 了。

ultmaster: 和 ___出题人 心有灵犀,我也是 ___?

Problem E

Solved by kblack. 02:32 (+)

题意:按斜角在一个无限矩阵中放置一个数列,求子矩阵的和。

题解:循环节为 $2L$,求前缀和以后分区域求和即可。

Problem G

Solved by zerol. 04:53 (+5)

Problem J

Solved by ultmaster. 02:13 (+)

题意:给一个每一块都有可能转坏了的 16 进制数独,让你把它转回来。

题解:送温暖的简单模拟题。由于题目没读清楚(只看了图)顺时针和逆时针搞反了调了半天,浪费半小时。

Problem K

Solved by ultmaster. 00:48 (+1)

题意:填 ? 使得表达式合法。

题解:把符号归成三类:1-9,0,+*。大概有三条规则:1. 刚开始和最后不能是 0;2. 0 后面必须是 +*;3. +0/*0/刚开始的 0 后面必须是 +*。使用这三条规则可以计算出每一位上可能的符号。然后一位一位填即可。注意好像不会发生冲突所以不用迭代到收敛;另外填的时候要注意不能篡改原式(没考虑到 WA1)。

Problem L

Solved by ultmaster. 00:07 (+)

温暖的签到题。(今天签的这么多一定是因为 kblack 迟到了。)