[2023] 9.24总结

Chancylaser · 2023-09-24 15:23:03 · 个人记录

省流： 上午挂分，下午讲题补题，晚上补题写题。

继 9.22 后离谱后，今天也是离谱的一天。

时间安排

用了个很假的做法，写完了T1，甚至过了大样例。

写后面的题，打暴力。

想在T2拿到更高的分数，然后也没拿到。

交题

总结

1. 感觉自己解法写假了就赶快思考。即使过了大样例。

2. 感觉自己解法写假了就赶快思考。即使过了大样例。

3. 感觉自己解法写假了就赶快思考。即使过了大样例。

傻逼，输麻了。

简要题解

T1：出租车

发现是稀疏图，做 n 遍dij跑完两两最短路后，清空图。然后 n^2 枚举 i 和 j，如果 dis[i][j]\ge a[i]，就建边 i \to j。然后在 s 再跑一遍最短路就行了。

T2： 拍卖会

神仙DP题。
发现了可以转换成n行m列的矩阵进行DP。然后设了一个非常神仙的状态。

T3： 序列

首先你需要会 O(1) 求 [1,x] 二进制下 popcount 为奇数的个数，然后线段树维护即可。

T4： 清除病毒

假设你在一棵n个点的树上选了 x 个点，那么方案数显然为 C_n^x。选定某个固定点对的方案数为 C_{n-2}^{x-2}（先在n个点上强制选两个点，然后剩下的乱选。）。

那么能够选到某个点对的概率即为 \frac{C_{n-2}^{x-2}}{C_{n}^{x}}。

然后不是给你 m 个距离参数嘛，用淀粉汁求一求就好了。然后算出来所有满足 m 个距离参数的点对，成上面的概率公式即可求出期望。