10.28-10.29模拟考试解题报告

好久没写总结了

这几天都是上午下午连着考

所以貌似没时间

直接进入正题

【正题之前:这套题TM真的是NOIP模拟?】

Day1

1.rho

首先密度最大的时候肯定是一条边两个点

证明一下

假设有三个点两条边(肯定比三条边优吧)

那么密度为1

显然总能找到其中一条边两个点使1(当且仅当v1=v2=v3=0时等号成立(也许吧))

所以枚举每一条边就可以了

代码:

2.light

没A不写了

反正是最短路

3.permutation

没A不写了

反正不会主席树

 

Day2

1.triangle

先找规律

发现第n行第m列为2

然后就可以做了

先预处理出1到100000的阶乘

然后用费马小定理+快速幂 每次求逆元就好了

3

代码:

2.interval

我做的是非正解n方算法

枚举每一个k,向两边扩展

用m[i]记录向左扩展到i时区间最长值

可以发现从k到k扩展到的最右端点之间是不可能存在比k更优的结果的

于是搜完k直接从扩展到的最右端点+1处再扩展就好了

于是就能骗过了

代码:

3.bwg

这道题直接暴力 加一点剪枝就能过了【数据太水】

然而我不想写了

那就END了XD

说点什么

您将是第一位评论人!

提醒
wpDiscuz