2. IT
    3. 2016.08.11【初中部 NOIP提高组 】模拟赛C题解

    2016.08.11【初中部 NOIP提高组 】模拟赛C题解

    xiaoxiao2025-07-17  7
    这次比赛似乎后两题简单，前两题难....... T1 看完题目后第一反应就是01背包，但一看数据n,m<=100000，而01背包算法时间复杂度是O(nm)，但比赛时还是果断的01.......结果顺利的时超了......正解是优化的多重背包; T2 看完题目想到了暴力......当时用BFS坑了30分（其它答案错误.....）正解是装逼的DP，因为每个点都是由上面或左边过来的，就用二维DP过了； T3 找规律递推，递推公式：f[i,j]:=f[i-1,j]+f[i,j-1]+f[i-1,j-1](f[i,j]表示i个数有j个逆序列的方案); T4 把同行和同列的坐标的总量，然后枚举直角三角形的直角顶点，然后用和它同行点数乘和它同列点数就是总数（还要注意存数量时要压缩数组）； 加油！
    转载请注明原文地址: https://ju.6miu.com/read-1300772.html
    最新回复(0)