题号 | A | B | C | D | E | F | G | H | I | J | K |
---|---|---|---|---|---|---|---|---|---|---|---|
状态 | O | O | O | O | - | - | - | - | - | O | O |
O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试
比赛时间
2020-05-20 13:00-18:00
提交记录
D: Accepted 2020-05-20 17:39:39
D: Runtime Error(ACCESS_VIOLATION) 2020-05-20 17:19:16
D: Time Limit Exceeded 2020-05-20 17:05:43
J: Accepted 2020-05-20 16:48:33
C: Accepted 2020-05-20 16:41:33
C: Wrong Answer 2020-05-20 16:35:54
C: Wrong Answer 2020-05-20 16:30:29
J: Wrong Answer 2020-05-20 16:26:31
J: Wrong Answer 2020-05-20 16:22:36
K: Accepted 2020-05-20 13:57:23
B: Accepted 2020-05-20 13:36:47
A: Accepted 2020-05-20 13:14:42
有一个函数$f(x)=\left \lfloor \sqrt(n) \right \rfloor$,问对于给定的$n$,$f^k(n)=1$的最小$k$,如果$k\gt5$输出“TAT”
$n$的取值到$10^{100}$,很容易想到在一定范围外$k$就大于$5$了,试一下发现$1^18$就大于$5$,所以判断一下长度小于$18$的时候就暴力看多少次,否则就输出“TAT”
两个长度为n的序列$h,c$,$c$给出,$h$是长度为$n$的任意排列,求公式 $\sum_{i=1}^{n}c_i*[h_{i-1}\leq h_i\;and\;h_{i+1} \leq h_i]$ 另$h_0 = 0,h_{n+1}=0$
$n\leq 10^3,0\leq c_i\leq 10^3$
看到h是排列,觉得能造成括号中条件的排列数是固定的,遂打表,发现在位置1,n产生这种情况的概率是$\frac{1}{2}$,其他位置产生这种情况的概率是$\frac{1}{3}$,然后按照这个依次乘c就行。
给一个$n\times m$的棋盘,问$\text{king,rook,knight,queen}$的先手胜负情况
基本上都是靠先SG函数打表再总结规律,但是$\text{queen}$实在总结不出来,最后优化到$O(NM)$的打表就过了(代码写得贼丑
solved by Zars19
给出元素为$\{0,1,2\}$的$N\times M$的矩阵,对某个格子进行操作时对该位置的值加$2$,四周分别加$1$,结果都是模$3$意义下的。给出的矩阵最终必能在$2NM$次操作内化为全$0$,输出一种操作。
题解:模$3$意义下的高斯消元,对于每一个位置$a_{i,j}+2\times opt_{i,j}+\sum opt_{i+dx,j+dy}\equiv 0 \pmod 3$。格子至多$30\times 30$个,看起来$O(N^3M^3)$好像不太行,但事实上每一个方程所关联到的变量不多,矩阵较为稀疏,注意if(!a[mxline][i])continue;
即可。
code:
有一条在坐标轴上的河,一条船目前在$(0,a)$,水流速度$v_2$延x轴,船的速度$v_1$始终指向原点,问船需要多久到达原点。
$0\leq a,v_1,v_2 \leq 100$
给出N个点,问是否存在四元组$(A,B,C,D)$其中$A<B,C<D$,$A!=B or C!=D$,使得$A$和$B$之间的曼哈顿距离等于$C$和$D$之间的曼哈顿距离
$T\leq 50$
$N\leq 10^5$
$0\leq$坐标范围$\leq 10^5$
发现给定的坐标范围比较小,因而两点间曼哈顿距离的种类最多有2*坐标范围种,根据鸽巢原理,答案必可以在2*坐标范围+1次找到,所以即使看似是$O(n^2)$的遍历求解实际复杂度也是$O($坐标范围$)$的,因而直接暴力即可。
_wzx27开到A发现可打表找范围做,提交,正确。
Zars19发现J是可做物理题,和_wzx27讨论,好像要积分,然后不会。
发现很多人过B,读题,infinity37提出概率大概是固定的。
infinity37找到1/3和1/2概率规律,提交B,正确。
三人讨论K题,过得人太多了,感到迷惑。
infinity37提出曼哈顿距离种数依赖于坐标范围,种数不多,鸽巢原理暴力即可,Zars19附和。
infinity37提交K题,正确。
_wzx27开到D题发现可做,提出爆搜DP说。
Zars19加入D题资源开发,提出贪心说(后证实为假)。
infinity37阐述了C题概况,手玩得到king解和castle猜想
_wzx27和Zars19加入进行一些讨论
讨论了knight平局问题,king解打表得到证实,castle猜想可以直接归纳证明。
进行了很多对queue的讨论,Zars19打了一些表(虽然最后不太有用)
_wzx27提出C题皇后的O(NM)做法。去写C
_wzx27提交C题,wa两次后正确。
infinity37去积分了,得到J题柿子,Zars19和_wzx27以为然。
infinity37提交J题,wa了2次,其间更正了下无解条件。
infinity37使用G++提交J题,正确,之前疑似是选用C++编译器导致的精度问题。
Zars19提出D题高斯消元说,开始写。
Zars19提交D题,由于没有continue掉多解消元时主对角线上元素为0的情况TLE一次。然后出现了令人疑惑的RE
种种推理下没有道理RE,扩大数组范围再交,数据范围可能假了,D正确。
大家这次状态比上次好,不过可能是因为题比上次的可做,区分度没有把我们区分出去,不过我不太行好几个题反应很迟钝orz。rank1是8题,比我们题多的一般会做出来相对更可做的G(我错了这好像是我的树DP)和不太可做我们没开到的E(好像是主席树)或者I(字符串DP)。罚时有点多,6题里面我们很靠后了,对一些套路更熟悉的话有些题应该可以更快想到,另外交题的时候可以冷静一点。
这次比赛签到题过的比较快,但是中部用了很多时间解题,说明我们的解题速度还有待加强,同时认识到了我们在博弈论上有一些缺陷,那么就这么愉快的决定了,这周就学博弈论()
这次做得比上次好一点,可能是因为简单一点(不过为什么会有物理题啊)。不过感觉自己手速和思维都好慢啊,有待提高。以及知识点不够全,有些题不怎么有思路,还是得拓宽知识面才行。