Shooting Game

出题人:吴霜
知识点:排序

纯签到题。

算出分数,对分数和序号比较大小即可。

A Number Theoretical Problem

出题人:施杰
知识点:数论

签到题

给出一个正整数x和一个质数p,求模p下x的逆元。简单的使用费马小定理求逆元即可。

设置一个小小坑点,x的范围并没有加以特殊限制,所以需要判断一下x是否存在逆元。也就是判断一下是不是倍数。

City Supplies

出题人:宋宏康
知识点:BFS

首都总是在点1,要求每个城市到首都的最短距离,因为可能有多余的边,所以直接以1为根节点,跑一遍BFS,得到一颗以1为根节点的树,用数组记录树上所有节点的深度,深度就是节点到根节点的最短距离。花费是,所以要求2的x次方,最远的距离是所有点在一条直线上,可以用数组预处理好2的x次幂,最后累加就可。

Moving stones

出题人:吴迪
知识点:策略,模拟

由于数据较小,只需要每次找到最少的那堆尝试加石头,直至所有堆达到平均数或者遇见违法操作
(尝试从石头数为0的堆里取石头),每次重新排序即可,最多1000次后,如果还无法满足要求,
输出No即可。判断的时候可以注意,n=1时一定输出yes,n>1时,如果石头数全相等(包括全0),
也可以直接输出yes,n=4, 1 1 1 5这种有很多小于平均数的数据,是会出现中间过程尝试从石头数
为0的堆里取石头的操作的,应该输出No。

高斯消元可以得到解(解是选定各堆石头的次数),但难以验证整个解空间,尤其是难以验证过程是否尝试从石头数为0的堆里取石头,所以很难通过所有测试数据

windmill

出题人:索文杰
知识点:数学几何,模拟

题意:在平面内有很多点,其中一个点在一条直线L上,现在给出点在平面位置,直线L穿过的点和L的角度。直线开始绕着直线上的点顺时针旋转,当直线旋转过程中碰到其他点的时候,直线将离开原本的“轴”,将新碰到的点作为轴继续顺时针旋转。问直线旋转一定角度后,直线上的点是哪一个。

题解:需要细心的观察直线旋转的过程。直线在旋转过程中,总是保持一种“平衡”。由于题目限制了没有三点共线,在直线“左”和“右”侧的点的个数是不会变化的。

根据结论,我们可以感受到,当直线旋转360°后将会回到原位。故我们可以利用该结论将旋转度数缩小到360度以内。

之后有两种解法:

1.由于旋转角只有360°,可以直接暴力模拟旋转过程。其中,由于点数有限,可以简单预处理每一个点到其他点的角度,随后模拟过程,利用预处理值找出这个点在该角度下旋转的下一个碰撞点,这样就可以快速找到答案。

2.上述结论还告诉我们,假设直线有方向,则直线左右的点个数不变。故我们计算初始状态下点的个数,在计算结束状态下每个点所处的左右位置关系,即可快速找到答案。可以利用角度的单位向量与点向量的向量叉乘来排序。

A Simple Game

出题人:郁宙
知识点:博弈游戏

首先考虑n=1的情况,这个时候只有一个字符串。比较明显的是如果字符串只有一个0,没有1,是没有办法进行任何操作的;同时观察操作一和操作二:操作一会把1变成0,也就是说该串的1的个数减一,操作二会把连续的0变成1,该串的1的个数加一,也就是说每进行一次操作,原串1的个数的奇偶性就会发生变化。由于偶数次操作无法改变1的个数的奇偶性,所以只需要查看字符串中1的个数,如果是奇数,就是Alice赢,因为有限次操作后一定是Bob面对只有一个0无法操作的局面;否则是Bob赢。

这时候考虑n>1的情况,当所有串含1的个数都是偶数时,无论你选择对哪些串进行操作,对方只要也选这些串进行操作,就能继续保证所有串含1的个数都是偶数。由于是Alice先动,所以只有当所有串含1的个数都是偶数时,Alice才会输,其他情况则是Bob落败。

GAMING WITH MIA

出题人:施杰
知识点:dp 

给定一个长度为𝑛的序列,两两之间填运算符,问运算结果最大是多少。(人类智慧题?)

有一些很明显的结论:我们肯定希望1尽可能做加法;0的作用肯定是消除-1,否则就直接做加法;-1与-1“结对”相乘,可以得到1(做加法),我们肯定希望这样的“结对”尽可能多……

观察以后,sj发现最多不超过5个数连乘

比如2个数相乘的例子有:,……

那么3个数,4个数,5个数连乘分别是什么情况呢?



就只有上面这几种情况……为什么?如果是,做加法肯定更优。为什么会有上面的情况?比如类似:,可以自行感受一下,0此时不 需要消除-1。

有了上面的结论,这题就很好dp了( 表示前𝑖个数的最优值):


复杂度:𝑂(𝑛)

HAPPY FAIRY

出题人:索文杰
知识点:主席树、LCA、二分  

给一棵树(注意看树有多少条边),边上有权值,多次查询,问给定一个数𝐶,𝑃的最小值是多少,才能满足从𝑋到𝑌的唯一简单路径上,权值不在 范围内的边数不超过𝐾条。

本题首先想到的,肯定就是对每次查询,二分答案𝑃,判断路径上不在范围内的数的个数是否超过个。然后就会想到主席树。难点就在于这不是序列,而是树。最后就会想到树链剖分,结果一算复杂度超时了。

是否有办法进一步加速呢?如果仔细观察会发现,树链剖分是没必要的,直接用“树上主席树”即可。

复杂度:

本题特意造了卡掉树链剖分的数据,避免“明明算出来复杂度超时的做法竟然可以通过本题”……但是很可惜,最终本题有人剖分过了,终究是没有卡住!

IRRATIONAL GRAPH

出题人:施杰
知识点:最短路、拓扑序

给定一个有向图,每条边的边权可以为正、可以为负、也可以是零,问从给定源点出发到图上所有点的最短路分别有多少种走法。

我们先考虑边权只能为正的情况。很显然,由于边权为正,所以最短路一定是DAG,所以我们求出最短路后,按最短路重新建图,跑拓扑序并累加贡献即可。

下面是个例子(已经按最短路重新建图,源点是1):

拓扑序:1,2,3,4
初始化:令dp[1]=1;
分别累加dp[1]到dp[2]和dp[3];
最后将dp[2]和dp[3]累加到dp[4]。

当边权可以为负,也可以为零时,除了引入了负环,更是引入了“零环”(负环是走一圈权值和为负,“零环”就是走一圈权值和为零)!负环会导致最短路不存在(为负无穷),“零环”会导致答案无穷大(因为可以反复走)

对于负环的消除,出题人使用Bellman-Ford算法,完整跑完𝑛次以后,所有负环都会形成环,然后用时间暴力找环即可,Bellman-Ford算法复杂度。不要忘记,找到负环以后,所有负环上的点,以及与负环相连的点,都要置-1。

对于“零环”的消除,一个精心设计的DFS,可以在时间内消除所有“零环”。

消除负环和“零环”以后,除了与源点不相连的点,剩下的就是最短路为DAG且答案一定存在的情况了,本步骤也可以在时间内完成。

复杂度:

JUST A PURE DATA STRUCTURE PROBLEM

出题人:施杰
知识点:平衡二叉树

设计一种数据结构,可以维护序列插入、连续相同值的个数/值更改、单值更改/删除、单值查询功能。
对于本题,离线操作非常不容易,因为每个元素的位置是实时变化的。

相信大家读完题,直觉就是平衡二叉树(对于不知道的同学,补充说明一下:一般的二叉树维护的是数值,这里我们需要维护位置,方法就是在每个节点上维护子树大小即可,这与线段树主席树查询第𝑘小类似)。

实际上,本题的主要难点在于细节特别多,如果没有处理好相同值的合并,很有可能会导致各种意想不到的问题,比如RE。

复杂度:

语言描述起来不太方便,举个例子。
下图描述的就是序列:1,1,2,2,2,1,3,3,2

每个节点需要维护

1.保存的数
2.数的个数
3.子树大小

在二叉树上维护以上信息(同时要注意避免二叉树退化成链),就可以在时间内完成题目要求的所有操作。

注意:相邻节点保存的数一定是不同的!这样可以保证各种操作的效率,但是 无疑给更新与维护增加了负担。

The Islands

出题人:施杰
知识点:BFS

本题真的只考察了单一知识点——BFS,没有参合其他知识点,而且本来定位是简单题(划掉)……应该有多种做法,只要能过就行,数据是随机的,每组都是1s,不卡时间。

先梳理一下题目中给出的定义:
水(water):'.';
陆地(land):'#';
边界(border):最外圈的水,且最外圈一定是水;
岛(island):连接在一起的陆地(上、下、左、右四个方向);
受困水(trapped water):无法流向边界的水(上、下、左、右四个方向);
受困岛(trapped island):岛上的人无法直接走水路到边界,也就是说,岛周围的水都是受困水;
环绕岛(surroundings):困住水的岛(可能不止一个岛),这(些)岛环绕了一些水,使得这些水成为受困水;
国家(country):环绕岛及相关受困水和受困岛或某个孤立的岛;
联盟(alliance):如果国家之间含有土地,土地之间的曼哈顿距离小于等于k,则形成联盟。

现在给定地图和k,问有多少个联盟。

这里给个例子:

k=2
...................
..###....#.........
.#...#..#.#....#.#.
.#.#.#.#...#....#..
.#...#..#.#........
..###....#.....#.#.
...................

首先开一个和原图一样大的二维矩阵用来打标记,初值全是0。题目很有引导性,第一步就是找国家。从边界上任意一点开始沿着水流方向BFS,走过的地方都标记成1,那么就会得到国家(0的位置就是国家,无需区分受困岛和受困水,全当陆地就行):

1111111111111111111
1100011110111111111
1000001100011110101
1000001000001111011
1000001100011111111
1100011110111110101
1111111111111111111

估计本题要是问国家有几个,大家应该都会?但本题硬核的地方就是,怎么合并形成联盟的国家。

不是特别建议暴力枚举,点数很多(随机数据,国家很多),很有可能会超时……

直观的想法是找到一个国家,向外BFS最大k步,看看能否找到没有访问过的国家。这样做的复杂度会变得有些无法估计,因为每个点(主要是水)的访问次数和国家与k都有关系。有同学可能认为,访问过的点(水)打上标记不再访问就可以控制复杂度,但这样做严格来说是错的,如上面的例子,我们取最右边的部分看:

11111
10101
11011
11111
10101
11111

如果从上面的3个国家开始扩张,扩张经过的点用2表示:

22222
20202
22022
12221
10201
11111

如果刚好遇到这样的情况,那么,对于下面2个国家来说,就没法合并了,因为下面两个国家的通路被之前的标记“挡住”了。

出题人的方法如下:

  1. k'=k-1;
  2. 使用BFS将所有国家同时向外扩张[k'/2](把水变陆地),[x]表示x取整数部分(向下取整);
  3. 最后一遍BFS计数,如果k'是奇数,那么允许“隔空”跳一步。

上面的例子中k'=1,[k'/2]=0,由于第2步比较显然,所以就不演示了,就是一定得所有国家一起扩张,否则还是会发生被“挡住”的情况。第3步,由于k'是奇数,所以可以允许踩一次水,2表示尝试踩的水,一样的字母表示同一个联盟:

1122211112111111111
12aaa2112a211112121
2aaaaa22aaa2112b2b2
2aaaaa2aaaaa2112b21
2aaaaa22aaa21112221
12aaa2112a21112c2c2
1122211112111112121

至于“隔空”跳到底代码怎么写,留给聪明的大家思考啦~

“隔空”跳会使得一些水被多次访问,但是有限,最多周围3个点(4个点的话就变成受困水了),所以这样做的复杂度是O(mn)。