Contest Reviews(Updating)

时间:2023-09-24 12:40:20

现在每天至少一套题又不太想写题解……

那就开个坑总结下每场的失误和特定题目的技巧吧

2018.8.25【ZROI】

T3传送门

T1:找规律找崩了……

最好不要一上来就钻进大讨论,先想有没有普适规律

2018.9.1【ZROI】

传送门

2018.9.8【ZROI】

传送门

T1:拓扑+优先队列裸题,不过由于原序列仅拆成两条链,可以$O(n)$做

T2:简单容斥计算,由于总范围不大可以依据时间线性做,不断处理事件即可

T3:

1.直接上堆栈的思路:

(1)对于每个i向右做一遍是$O(n^2)$

(2)只扫一遍每次哈希判断前面有多少个和当前相同的值是$O(nlogn)$

(3)由上种方法发现同样的哈希值提供的贡献为$num*(num-1)/2$

这样用$Trie$树的每个节点来代替哈希值,最后一起统计答案是$O(n)$

2.我一开始想的思路:

每个点存$res$,对于当前字母能产生最多的合法序列为$res[pre-1]+1$

证明也很容易,如果12,34不满足则14,23一定不满足

为了能最快判断$pre+1$至$i-1$的可行性,可以采取不断跳的方式

复杂度能大致证明为$O(字符集*n)$

(1)括号序列相关首先还是要往堆栈上想!

为快速判断一个区间是否匹配看堆栈状态是否相同即可,可用哈希优化

为了优化掉判断哈希的$map$,可以再手写一个哈希或用$Trie$来计数

(2)有些难算复杂度的算法先写看实效

2018.9.9【ZROI】

T1:判断平均数是否合法套路:将$a[i]-mid$,查询是否有一段和大于0

T2:直接贪心

T3:$dp$转移出和为$sum$方案数,再用(总-不合法)算出含$v$的方案数

T4:将可行走的距离拆成每一步跑分层图最短路

注意:$priority_queue$重载要反着写,如果多个$INF$注意是否爆$longlong$!

2018.9.14【ZROI】

T1:CF向结论题

T2:判断贪心是否正确不能只看样例!

此题的$n$条链分两种长度,由于每条链必是序列上连续的一段,分当前两种选择转移

T3:一般这样建树建不出来的题都只考虑关键点!

(1)将无根树转为有根树

(2)提前算出每个点非关键路径引出的点的个数

(3)以每个关键点为起点暴力$dfs$计数,发现总状态$2^m*m!*(mlogn)^2$能接受

T4:此题虽然代码量小但还是有些不错的思路的

(1)发现答案和最短边有很大关系,将所有边减$mn$,这样省去权值为$mn$的个数计算

(2)每一个点的答案是一条末边为0的最短链

能证明这条链一般是一条单调递减的链,除了在中间出现无边可选的情况

于是可以将上界设为$2*min(dist(i,k))$跑最短路,在单调递减的情况下最短路的权值正确,否则上界会修正

Tip:完全图跑最短路用$O(n^2)$!

2018.9.15【ZROI】

题解传送门

2018.9.16【ZROI】

题解传送门

注意可行概率的计算:如果总方案数算的是组合,那么可行方案也只要算组合即可

2018.9.18【NFLS】

T1:重点要发现$A+B=S$不变,接着发现每次操作相当于$A=A*2%S$

大于某数就减去该数联想到取模,从而用快速幂处理

T2:考虑如果仅有行/列操作不会受影响,又由于行列值固定时减去的和也固定,因此贪心预处理后枚举即可

即使没有部分分的提醒,也要注意考虑简化后问题

T3:重点要发现固定某端点时两变量$f(x),R-L+1$的单调性,从而用线段树二分解决

2018.9.21【ZROI】

T3:主要要发现在树上同一符号的连通块的顺序任意

这样从下往上对每个连通块“合并果子式”贪心即可

T4:看看能否改变定义将范围更小的变量作为状态

想到列不等式来计数!

2018.10.16【ZROI】

传送门

T1:其实是思路很好想的一道题,明显用$set$维护点的有序位置和区间的最优解

(1)但由于要取最左边的解,对最左边的特殊情况的判断条件要写成小于等于

注意对于有条件的最优解在特殊情况下也要考虑该条件

(2)默认构造函数为name+{},否则写成name+()

T2:要了解拼接字符串的大小关系具有传递性

$a+b>b+a,b+c>c+b$则$a+c>c+a$

T3:如果中间数据含实数类型一定都要注意开$double$!