3
24
2015
0

20150325省选模拟测试#3

A.给出一个序列a[i],每个元素属于[1,n]。m个操作,子区间每次可以修改一个a[i]或者询问当前有多少个子区间内没有重复的颜色。n,m<=10W 30%n,m<=1000 

题解: 考虑枚举左端点,r[i]表示i到r[i]这段区间没有重复的颜色且r[i]最大。那么i对ans的贡献就是r[i]-i+1。

    容易知道随着i的增加,r[i]不减。所以计算一次所有的r[i]是O(n)的。

    这样可以拿30分。

    然后再乱搞一下,每次修改只会影响i-r[i]包含x的i。

    那么我们lower-bound一下,把这一段暴力算一算。

    复杂度不好估计。。。随机数据跑的很快。。。构造的估计就呵呵了。。。

 

UPD:居然有90 233 数据略弱了。。。

B.看了题面就弃疗了。

C.n*m的方格,要求在每个格子里填上-9的数,并且相邻的数之和<=某个数(给出的)。求在格子里填的数的总和。

题解:50%n,m<=3 呵呵 我 暴力枚举每一行用的数字。。。

   满分做法据说是网络流,不明觉厉。

Category: 模拟赛 | Tags: | Read Count: 517

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com