1月14号之后将本篇内容更新到CSDN中,如果我看到了。
https://blog.csdn.net/qq_17807067/article/details/134909554
补题链接(英文题面):https://codeforces.com/contestInvitation/f9525e4ae38eefdd9062ae5f43d8c9fdee80ad6e
简单题:M,J
J. Mysterious Tree
题面大意:给你一棵树,这棵树只能是一个链或者是菊花,没有别的情况,菊花就是有一个点和其他点都有边,
其他点和其他点直接都没边。判断这棵树是链还是环,询问次数为 n/2向上取整+3
此题是交互题所以不可以使用cin.tie,define endl '\n',具体来说是使用cin.tie就不可以使用'\n'换行
原因:https://icpc.xidian.wiki/cce/cin-tie0
基本上是cfl单杀的一道题,询问1-2,3-4,5-6,最多询问n/2次就能找到菊花中心,如果没找到这样的边,说明
是链(奇数和偶数分开,需要特判两次,没找到一定是链),比赛的时候WA两次找出来的两个血汗特判。
一开始cfl给了思路之后我和z01去做题了,个人原因没听清思路WA两次,应该是谁给思路谁来写题,加上
中间一个敲代码的,保证给思路的要在线。
这种特判要从代码角度去考虑是否完备,顺着代码去考虑某一行是否有问题,思路上很难看出来。
找到这条边之后再去询问3次一定就能问出是链还是菊花,次数刚好。
-------------------------------------------------------------------------------------
M. V-Diagram
题目大意:给你一个序列,必然是一个先降后增的序列(V图),找出一个平均值最大的连续子V图。
这道题差不多是三个人一起想出来的,最后根据z01和cfl的思路点出如果某一边被选了,那么必然被全选,
结束战斗。
最终结果只能是V的左侧被全选 或者 V的右侧被全选 或者 全部选上,只有三种情况。
因为平均值特性 3 3,选上平均值不变,如果递增 3 4 5 6,选上平均值必然增大,所以全选。
造数据测试后,1发过,最稳的一题。
-------------------------------------------------------------------------------------
铜牌题:D,G
D. Operator Precedence
题目大意:(a1×a2)+(a3×a4)+···+(a2n−1×a2n)=a1×(a2+a3)×(a4+a5)×···×(a2n−2+a2n−1)×a2n
满足上述式子,其中条件是等式值不为0,ai的取值也不为0
比较可惜的是正式赛的时候没有做出来,赛后z01 3小时把这道题AC了
正式赛找了3个小时规律没找出来,尝试化简式子也都失败了。
打表代码写的有问题,某些n的取值找出来的不是第一个合法构造,导致规律找不出来。
同时样例也具有误导性质,前面给的是平方的规律,后面是没规律。
只能说这种Special Judge的样例看看就行,还是以自行思考为主。
尝试解式子的时候因为直接设了a1和a2n为1(根据样例设的)所以左右式项数还是不统一,没法做。
正确的是设a1或者a2n其中一个为1,因为右式是乘法,所以我们希望它不要乘的太大,另括号中的加法
均为2,-1,2,-1的构造,直接求和为1抵消。然后代入左式解出a2n的合法取值。
-------------------------------------------------------------------------------------
G. Snake Move
题目大意:给你一条蛇,可以WSAD走,也可以特殊操作执行自己缩短一个长度(不能把蛇头缩了)。
问蛇到矩阵中的所有点最快只要几次操作。
有思路但是题目读不太懂,这个最小操作是蛇一次就要移动完还是每次出发到达那个点的最小操作。
如果是每次出发就可以采用bfs遍历一次所有点来求出答案,对于某个被蛇身挡住的点,标记一下被
蛇身挡住的长度来当作答案,下次bfs答案来和他比较应该就可以了。(读不懂操作数也可以把bfs
代码敲出来看看和样例比较一下)
但是题目中最终输出的答案是连乘后对2^64取模,直接给long long爆了,不知道怎么解决所以最终还是
没敲代码。