2020.10.07【普及组】模拟赛C组总结

    科技2024-11-28  18

    奇妙的文章目录

    总结T1 小x的数列(100)T2 小x的极限(90)T3 小x的字符串(0)T4 小x的最短路(0)完成情况

    总结

    这次凉了QAQ

    T1 小x的数列(100)

    题目大意:给你 n n n个数,让你排成一个序列,使其每对相邻的两个数不同。 这题是数学题,只需要判断有没有一个数超过了 ( n + 1 ) / 2 (n+1)/2 (n+1)/2就行了。

    T2 小x的极限(90)

    题目大意:给你两条式子,让你求出第一条式子除以第二条式子的峰值。 这一题我们发现,峰值只和每条式子的第一个值有关,所以我们只需要判断式子的长度,以及第一个值的大小就能得出答案。

    T3 小x的字符串(0)

    题目大意:给你两个长度为 n n n的字符串,只由数字和’?'组成。求满足有其中一项a比b大而有一项b比a大的方案数。

    这一题有两种方法:

    组合数,先求出总的方案数和不满足的方案数,然后相减。状态压缩dp,设 f i , j f_{i,j} fi,j表示填到第 i i i位,状态为 j j j的方案数。

    T4 小x的最短路(0)

    题目大意:每次踢出一个点,让你求踢出后每对点对的最短路总和。 这题能想到:如果顺着求,则每次都要更新。所以,要想不超时,必须倒着求(离线做法)。只要每次插入一个点,然后用这个点进行三次更新,就能在 n 3 n^3 n3的时间内求出答案。

    完成情况

    T1 T2 T3 T4
    Processed: 0.012, SQL: 8