/ Vijos / 讨论 / 月赛 /

[置顶] <又是一年省选季之春分邀请赛> 通知&答疑 专用贴

【Vijos——又是一年省选季之春分邀请赛】

2018年省选季vijos系列比赛第一场

开始于2018-03-24 18:00
结束于2018-03-24 23:00
共计三题

报名请移步: https://vijos.org/contest/5aa51237d3d8a1371223faba


3.24 14:14 比赛已经部署完毕,快告诉你身边的朋友们吧。
3.24 23:04 比赛已经结束感谢大家的参与,题目已经公开在了题库列表中。

题目简要分析:

第一题:
对于这种最大最小化的双人游戏,最基本的思路是分支定界的搜索,也就是alpha-beta剪枝,这就可以得到60分。
满分做法还需要用到启发式搜索,这里的启发式函数很容易找到:优先选取下一步获利最大(最小)的方案。
代码请参见 这一题的题解区

第二题:
这一题考察状态压缩动态规划,记 \(F[i][s]\) 表示 \(i\) 位数中状态是 \(s\) 的方案总数。
重点考虑 \(s\) 要记录什么,当然不需要记每一种数字的使用情况,只需要记有多少奇数被使用过了,以及里面有多少被用了偶数次,再者需要记录所有偶数中有多少用了奇数次就可以了(一个偶数如果没有被使用,它出现的次数依然是偶数——即0次)。这样 \(s\) 的状态总数大概不会超过70个。
将上述动态规划表示为矩阵乘法的形式,就可以快速解决这一题(等于是求一个矩阵A的幂次和)。

第三题:
注意到 \(2^{n-1}\times (n+1)\) 是答案的一个上界,所以不妨把每一个满足要求的数字都记为 \(2\) 的若干次幂乘上一个整数的形式。为了得到一个更大的数字,总是尝试将其中一个因子变成更大的因子(或者将1变成2,也就是再增加一个2)。所以若选择了一个目前最小的方案,则会额外增加不超过 \(\log n\) 个新的方案(注意需要去重)。
用小根堆来实现上面的操作,就可以解决这一题。

20 条评论

  • @ 2018-03-26 11:00:47

    有没有t2,t3题解和标程

  • @ 2018-03-25 21:01:32

    \(s\) 的状态总数大概不会超过70个

    \(3^5 \cdot 2^5 = 7776\) ,不应该是7k个么……是我哪里算错了?

    • @ 2018-03-25 21:04:04

      以及可以提供一下 T2 T3 标程做参考吗 @少女夜夜

    • @ 2018-03-26 00:36:54

      记 \(f(i,k,l)\) 是恰好有 \(i\) 位的合法数字的个数,且有:
      (1)\(0\) 到 \(9\) 中有 \(k\) 个数字出现了的次数不满足题目要求,也就是奇数出现了偶数次或者偶数出现了奇数次;且
      (2)其余的数字中(也就是出现了偶数次的偶数和出现了奇数次的奇数中)有 \(l\) 个是奇数。

      因为 \(0\le k\le 10\),\(0\le l\le 5\) 同时 \(k+l\le 10\),总共合法的 \((k,l)\) 不会超过 \(66\) 对。

  • @ 2018-03-24 23:22:08

    杯具。。。我T2方程弄出来了,看到 \(n \le 2^{60}\) 就怂了,没想到矩阵快速幂
    哦忘了
    @金爷爷哈哈 otz

  • @ 2018-03-24 23:04:43

    题解啥时候发啊~
    以及T1正解啥啊……我打了个节点排序的Minimax搜索+AlphaBeta剪枝混了60
    = =

  • @ 2018-03-24 19:16:42

    @少女夜夜: 难度······

  • @ 2018-03-24 18:26:17

    三题的内存限制?= =

    • @ 2018-03-24 18:27:11

      512m

    • @ 2018-03-24 21:45:56

      @少女夜夜: 请问T1的

      每一组数据时限为2秒。

      是指“输入包含多组数据”里面的每组吗?

    • @ 2018-03-24 21:55:58

      @panda_2134: 是每一次输入数据时限为2秒。

    • @ 2018-03-24 22:02:25

      @twd2: get

  • @ 2018-03-24 18:23:40

    现在他给定了正整数 n 与另外一个正整数 p,希望你找到第 nn 个(也就是第 n 小的)有至少 n 个素因子的整数,并输出其模 p 后的余数。

    然后

    输入有一行,包含两个由空格隔开的正整数,分别为 n 和 q。

    p?q?

    • @ 2018-03-24 18:24:23

      @ 少女夜夜

    • @ 2018-03-24 18:27:53

      @·: 哦写错了,都是p。

    • @ 2018-03-24 18:30:01

      已经修正了

    • @ 2018-03-24 19:15:30

      @少女夜夜: ok

  • @ 2018-03-24 12:57:46

    讲道理应该可以去洛谷宣传一下嘛,只要跟站长说一声

    毕竟vijos都在洛谷首页友链里面= =

    • @ 2018-03-24 14:16:56

      哦,忘记联系他们管理员了。
      没关系的啦!只是半个比赛而已。

  • @ 2018-03-24 12:53:16

    滋磁

  • @ 2018-03-24 11:51:46

    前排兹瓷

  • @ 2018-03-24 10:53:11

    @少女夜夜您要不要宣传一下,目测关注vijos的人不多

  • @ 2018-03-23 19:26:46

    前排兹瓷

  • @ 2018-03-21 21:21:19

    后排资瓷

  • @ 2018-03-17 15:48:04

    前排滋磁

  • @ 2018-03-14 15:35:18

    前排兹瓷

  • @ 2018-03-12 17:54:20

    前排资瓷

  • @ 2018-03-12 13:39:18

    前排资瓷

  • @ 2018-03-12 12:51:25

    前排资瓷

  • @ 2018-03-12 12:36:18

    前排资瓷

  • @ 2018-03-11 21:21:25

    前排资瓷

  • 1