日本春令营在线比赛第三天总结

日本春令营在线比赛第三天总结
第三天我没有忘记密码,这是因为我把密码存到了一个文本文档上,然后我就开始了比赛。第三天仍有一道题是交互题,另外两道题都是传统题。因为上次的原因,所以我决定做交互题。

一、constellation3
第一题叫做constellation3。
题目大意:有一张长为NNN宽为NNN地图,每一个位置是白色或黄色或黑色,已知删除一个黄色并变成黑色需要花cic_ici​级别,规定:如果有一个矩形,里面没有白色,却有两个及以上的黄色,则这片区域叫做星座。现在要求删除最少的黄色,将其改变为黑色,使地图中没有星座,求最少的删除的级别数。
数据范围和子任务如下:
D3T1
我的思路是:首先暴力搜索,枚举删掉的黄色,然后判断,可惜这种时间复杂度已经达到了指数级别了,所以我只能想别的办法了。动态规划,似乎可以。可是我不会写状态转移方程。好吧,这道题就只能0分了。
二、harvest
第二道题交做harvest,如下:
有一个圆形,其中有几个人和几棵苹果树在周围,现在他们要围着这个圆形走,走到一个有苹果的地方可以摘苹果,摘完苹果后过CCC秒又会长出来,求第TTT秒时编号为VVV的人有多少个苹果。
这道题的数据点很大:
D3T2
我发现TTT最大竟然是101810^{18}1018,就会感觉不会做了,但是我最后还是的打了一个暴力,现在一想,其实这道题可能用数学做好吧。我的暴力程序的时间至少是O(NMQT)O(NMQT)O(NMQT),如果真是要运行的话,可能一天都运行不完。
我现在就剩下第三题了,第三题是交互题,我该怎么办呢?
三、stray
第三题叫做stray,是一道交互题。
这道题的题目大意很奇怪,我看懂了一点,但是不知道它是说什么,大概是这样的:有一个城市,这个城市里有NNN个小镇MMM条道路,小镇的编号分别为000至N−1N-1N−1,这些道路都是双通的。有一只蚂蚁住在000号城市,一天一只猫来看它,这只猫在SSS镇(S≠0)(S≠0)(S​=0),她因为经常迷路,所以只好给她做一些标记,标记有AAA种类型,分别为000至A−1A-1A−1。现在要求一种策略使猫最快到达000号城市。
数据范围与子任务如下:
D3T3
这道题难倒我的还有另一个点,就是我不知道交互题怎么弄,虽然我想到了思路就是类似SPFASPFASPFA最短路或floydfloydfloyd最短路的方法,可是我不知道要怎么写啊,可见以后要多多学习这些非传统题的解题方法了。
四、第三天的总结
这天我没有拿一点分,但是我没有放弃,而是期盼着明天的比赛,真希望明天有提交答案题啊!我虽然没有拿到一点分,但是我却打了暴力也对了样例,这说明我的程序还算对的。
加油D4!

作者:linweitong2020