/ Vijos / 讨论 / 月赛 /

[置顶] <金秋重聚模拟赛> 通知&答疑 专用贴

Vijos已经很久没有办过比赛了。
但Vijos不希望被大家遗忘,并依然憧憬着给更多的小盆友带来一段难忘的回忆。

适逢金秋十月,桂花香飘。正是重聚的好时机。
于是我们决定,重新开始举办NOIP模拟赛。陪伴即将踏上NOIP赛场的小盆友们,蓄势扬帆。

题目难度:NOIP提高组
比赛链接:https://vijos.org/contest/59d0c6cbd3d8a127fd789176

评测机配置:

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 62
model name  : Intel(R) Xeon(R) CPU E5-2630 v2 @ 2.60GHz
stepping    : 4
microcode   : 0x428
cpu MHz     : 1199.865
cache size  : 15360 KB
physical id : 0
siblings    : 12
core id     : 0
cpu cores   : 6
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
flags       : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm epb tpr_shadow vnmi flexpriority ept vpid fsgsbase smep erms xsaveopt dtherm ida arat pln pts
bugs        :
bogomips    : 5199.65
clflush size    : 64
cache_alignment : 64
address sizes   : 46 bits physical, 48 bits virtual
power management:

除非题目说明,默认内存限制256MiB。
目前Java好像是坏的。。。


2017.10.2: 比赛准备中...
2017.10.5: 题目出好啦,感觉考点挺全面的呢...
2017.10.7:
17:53 还有一会比赛就要开始了,祝大家玩得开心
18:03 可以重复提交,最后一次为准
18:06 大家可以在这里提问
18:43 补充了第一题中d的范围
21:12 比赛还有不到一个小时就要结束了,大家加油
21:58 比赛即将结束,成绩将在赛后约5分钟内给出
21:59 感谢大家的参与,送给大家Pete Seeger的名曲Little Boxes,希望大家有一个愉快的夜晚
http://www.xiami.com/song/creDUeff19?spm=a1z1s.6659509.0.0.zbvUEu

22:05 题目将在15分钟内开放到题库中
22:14 题目已经加入到题库中,题解正在筹备中,也欢迎大家在题解区留下自己的想法


第一题、
需要分析出来每一条边的最大可能长度如果不是这两点间最短路径的长度 \(d\) ,那么就一定可以任意大。那么什么时候 \(i\) 到 \(j\) 的变长度可以不是 \(d\) 呢?一定是存在第三个点 \(k\) 满足 \(d(i,k)+d(k,j)=d(i,j)\)。这就得到了一个 \(O(n^3)\) 的算法。
作为拓展思考:这一题其实可以做到 \(O(n^2 \lg{n})\)。

第二题、
注意到 \(\phi(n)/(n-1)\) 展开后等于 \(n/(n-1)\) 乘上若干个 \(p/(p-1)\) 这里 \(p\) 是 \(n\) 的素因子,且 \(p\) 不会重复出现。那么换句话说除了前面 \(n/(n-1)\) 后面部分的结果与一个素因子在 \(n\) 中出现多少次没有关系。进而想到如果不考虑 \(n/(n-1)\) 只看后面部分的乘积,最优方案一定是最小若干个素数的乘积。也就是 \(2, 2\times 3, 2\times 3\times 5, 2\times 3\times 5\times 7, 2\times 3\times 5\times 7\times 11\)等。而多了 \(n/(n-1)\),答案应该是上述形式的倍数,且不会倍率非常大(因为 \(n\) 比较大的时候 \(n/(n-1)\) 几乎等于 \(1\))。这就得到了最终的算法。

第三题、
这一题是一道比较经典的数位类动态规划。
只需要注意到所谓的修改实际上不外乎在把最大的数字改成 \(0\) 和把最小的数字改成 \(9\) 之间,还需要稍微额外考虑一下最高位的特殊情况。

第四题、
一道比较常规的数据结构题。作为NOIP模拟题,我给出的建议算法是分块,尤其注意到所有符号都是 \(0\) 或 \(1\) ,所以实际上还可以压位。
当然也存在一般的做法,就是利用Splay维护字符串Hash,并支持相关的修改和询问。

32 条评论

  • @ 2017-10-08 22:52:14

    竟然错过了!!!

  • @ 2017-10-08 17:17:29
    
    
  • @ 2017-10-08 13:49:38

    第一题最小生成树是不是可以O(n^2)

  • @ 2017-10-08 10:33:13

    请问第一题怎么O(n^2lgn)啊?

  • @ 2017-10-07 22:15:03

    开放了

  • @ 2017-10-07 21:42:33

    请问代码长度限制?

    • @ 2017-10-07 21:44:33

      128M

    • @ 2017-10-07 21:51:03

      @doc: 请问这真的是代码长度不是内存限制吗?

    • @ 2017-10-07 21:57:40

      @ZH~:感觉不应该是128M,这个是twd2和我说的,我认为是128K

    • @ 2017-10-07 22:02:56

      真的是128M

    • @ 2017-10-07 22:24:01

      搞错了,好像是16M

  • @ 2017-10-07 20:41:34

    T3:特殊说明 0 是一位数字

    是什么意思

    • @ 2017-10-07 20:49:33

      就是说 \(0\) 不是T3中要求的合法数字

    • @ 2017-10-07 20:50:24

      @doc: 谢谢回答

  • @ 2017-10-07 20:02:07

    T3,是否存在将123修改为1123的操作

    • @ 2017-10-07 20:50:06

      123不可能变成1123,你只能修改一位,不能新增一位

  • @ 2017-10-07 17:59:06

    真棒!

  • @ 2017-10-07 17:57:12

    开始于
    2017-10-07 04:00
    结束于
    2017-10-07 08:00
    这个时间怎么回事??

    • @ 2017-10-07 18:00:06

      您的时区设置的不对吧~

  • @ 2017-10-07 17:48:31

    做好了爆零的准备

  • @ 2017-10-07 17:38:30

    更新。

  • @ 2017-10-07 16:16:08

    似乎马上要开始辣

  • @ 2017-10-07 14:28:25

    大家也组一波队吧

  • @ 2017-10-07 14:28:10

    欢迎大家来挑战

  • @ 2017-10-07 14:27:59

    我们机房组成bj80_416

  • @ 2017-10-06 13:31:10

    资瓷

  • @ 2017-10-05 20:21:07

    资瓷

  • @ 2017-10-05 19:09:26

    手动置顶

  • @ 2017-10-05 00:47:27

    更新:出题人说题目出难了= =

    • @ 2017-10-05 22:30:30

      那我这个蒟蒻就要爆零啦!

    • @ 2017-10-07 09:59:10

      @lrj124: 不,您这个大佬还是可以AK虐全场

    • @ 2017-10-07 10:04:18

      @学习阶段的刘锦钰: 您才是大佬,您才能AK虐全场,我这个蒟蒻不行

  • @ 2017-10-05 00:16:22

    支持

  • @ 2017-10-04 22:01:48

    Interesing

  • @ 2017-10-04 11:43:48

    支持!!!

  • @ 2017-10-04 11:00:41

    大Vijos又...复活了...

  • @ 2017-10-02 20:41:05

    支持!

  • @ 2017-10-02 20:16:11

    zhichizhichi

  • @ 2017-10-02 16:06:02

    滋磁

  • @ 2017-10-02 10:00:46

    支持

  • @ 2017-10-01 21:53:20

    围观神犇屠苣

  • @ 2017-10-01 18:56:37

    支持 =-=

  • @ 2017-10-01 18:50:59

    前排

  • @ 2017-10-01 18:49:50

    ——爷爷,你当年最喜欢用的OJ办比赛了!
    ——什么?快把我从棺材里扶起来!

  • 1