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个国家来说,就没法合并了,因为下面两个国家的通路被之前的标记“挡住”了。
出题人的方法如下:
- k'=k-1;
- 使用BFS将所有国家同时向外扩张[k'/2](把水变陆地),[x]表示x取整数部分(向下取整);
- 最后一遍BFS计数,如果k'是奇数,那么允许“隔空”跳一步。
上面的例子中k'=1,[k'/2]=0,由于第2步比较显然,所以就不演示了,就是一定得所有国家一起扩张,否则还是会发生被“挡住”的情况。第3步,由于k'是奇数,所以可以允许踩一次水,2表示尝试踩的水,一样的字母表示同一个联盟:
1122211112111111111 12aaa2112a211112121 2aaaaa22aaa2112b2b2 2aaaaa2aaaaa2112b21 2aaaaa22aaa21112221 12aaa2112a21112c2c2 1122211112111112121
至于“隔空”跳到底代码怎么写,留给聪明的大家思考啦~
“隔空”跳会使得一些水被多次访问,但是有限,最多周围3个点(4个点的话就变成受困水了),所以这样做的复杂度是O(mn)。