当前位置:首页 >> 学科竞赛 >>

NOIP信息学竞赛技巧


1

竞赛技巧 ——by 齐朋辉

2

前言
? 作为一个完全没有OI经历的ACM选手。。 ? 以下内容纯属胡编乱造,切勿轻信 ==

3

方伯伯的玉米田
? N个数的序列,最多可以进行K次操作: ? 每次操作选择一个区间,讲这个区间内的 数字+1 ?

K次操作完之后,最长单调不降子序列的长 度是多少 ? 对于40%的数据,1<=n<=1000, 1<=K<=100, 1<=ai<=500 ? 对于100%的数据,1<=n<=10000, 1<=K<=500, 1<=ai<=5000

4

方伯伯的玉米田
? Dp[k][i] : 以第i个玉米为结尾,已经进行k 次操作之后,LNDS的最大长度 ? Dp[k][i] = 1 + max dp[k][j] a[j] <= a[i] dp[kk][j] a[j] + kk <= a[i] + k 朴素转移:N * K * N case1用树状数组优化: N * K * log N + N * K * K

5

方伯伯的玉米田
? Dp[k][u] : 最后一个玉米的高度为u,已经 进行k次操作之后,LNDS的最大长度 ? Dp[k][u] = max ( dp[j][v] + 1 ) ? v + j <= u + k, j <= k ? 二维线段树 ? 复杂度:N * K * logN * logK

6

方伯伯的玉米田
? Dp[k][u] : 最后一个玉米的高度为u,已经 进行k次操作之后,LNDS的最大长度 ? Dp[k][u] = max dp[k][v] + 1, v <= u dp[k + u – v][v] + 1, v>u 树状数组f[k]: max dp[k][u] 树状数组g[k + u]: max dp[u][k] 复杂度:N * K * (logN + logK)

7

方伯伯的商场之旅
? 假如一个数X的K进制表示为12312,那么X 就对应5堆石子:1,2,3,1,2 ? 移动石子的代价是移动石子数*移动距离 ? Cost(12312)=1*2+2*1+3*0+1*1+2*2=9 ? 现在要把L~R内每个数对应的石子各自合并 为一堆,求最小合并代价。

8

方伯伯的商场之旅
? ans(L, R) = ans(1, R) - ans(1, L – 1) ? 对于每一个x,最优决策点为重心 ? 设最优位置为p,a[p] = k,p左侧的石子 挪到p – 1的花费为sl,总石子数为cl,p右 侧的石子挪到p + 1的花费为sr,总石子数 为cr。

9

方伯伯的商场之旅
? ? ? ? ? ? ? 决策点 : 花费 p : sl + cl + sr + cr p – 1 : sl + k + sr + cr * 2 p + 1 : sl + cl * 2 + k + sr 设p为最右决策点,则 cost(p)<=min(cost(p – 1), cost(p + 1)) k + cr >= cl, k + cl >= cr

10

方伯伯的商场之旅
? 最优决策点可能有多个,我们选最右端的 那个 ? cost(p) <= cost(p – 1) ? cost(p) < cost(p + 1) ? k + cr >= cl, k + cl > cr ? 根据这两个条件按位DP即可。。各种枚举

11

方伯伯的商场之旅

12

A
? 设f(x)为x各位数字之和,例如f(123)=6, f(12)=3, f(3)=3, ? 给一个区间[l,r],求这个区间内x%f(x)=0的 个数

13

A
? ? ? ? ? ? 不会做 ==怎么办 打表 先暴力打表所有[1, 100000 * k]的答案 对于一个查询[1, n] [1, n / 100000 * 100000]的答案是已知的 暴力求出(n / 100000 * 100000,n]即可

14

A
? 枚举数位和sum ? 定义dp[sum][L][now][r]为总的数位和为 sum,长度为L,当前和为now,模sum为 r的数,有多少个 ? 枚举每一个sum,O(9*90*90*10)预处理

15

A
? ? ? ? 对于每一个cas,先枚举sum,然后按位DP 当前位从高位到低位开始扫描 高位取前缀,枚举当前位 当前位之前的数位和sl和模sum的值rl都是 确定的 ? 那么低位的数位和为sum – sl ? 设低位数字模sum为x ? 则(rl * 10^k + x) % sum = 0

16

最近黑点
? 一棵树,有n个节点,每个节点都有一个颜 色,黑色或者白色,初始时全部为黑色。 ? M个操作 ? 操作1:将u涂为黑色 ? 操作2:离u最近的黑色点

17

最近黑点
? 只有白色变黑色,没有黑色变白色 ? 我们可以将m个查询分为sqrt(m)块 ? 每一块查询之后,跑一遍bfs预处理出所有 点到黑点的最近距离 ? 同一个块内的黑点,暴力查询即可

18

B
? 给一棵树,1为根节点,每个点都有一个权 值,初始时为0。 ? 现在给两种操作; ? A x k: 将x的点权+k,x的儿子点权+k+1, x的儿子的儿子点权+k+2,以此类推。 ? Q x: 查询以x为根的子树中,所有点的点权 和。

19

B
? O(N * Q)? So easy。。 ? O(sqrt(Q) * N) ? 是不是有点厉害。。

20

B
? 每一个更新操作对查询答案的贡献是叠加 在一起的 ? 所以可以分别计算出来然后叠加在一起 ? 这样我们就可以分块啦啦啦啦~

21

B
? 我们可以将每sqrt(Q)个查询分块 ? 每一块查询结束之后,跑一遍树形DP,预 处理出所有的答案 ? 然后对于每一个查询,只有同一个查询块 内的操作不在dp值里面,对于这些操作暴 力加进答案即可

22

B
? ? ? ? 树形DP dp[u] = sum(dp[v]) + val[u] (v是u的子节点) val[u]只和祖先有关,所以dfs的时候记录 一下就好

23

B
? 查询以u为根节点的子树 ? 对答案产生影响的操作只有u的祖先和u的 子节点

24

B
? O(Q * log N)? ? 树形转线形(dfs序列) ? 因为子树的dfs序列是连续的,所以相当于 区间更新区间查询 ? A x k : 我们可以分解为这样的两部分 ? x的子树全部+ k – dep[x] ? X的子树全部加上dep[u]即深度

25

B
? ? ? ? 操作1:x的子树全部+ k – dep[x] 操作2:X的子树全部加上dep[u]即深度 操作1:简单的线段树懒操作标记即可 操作2:每个位置加固定的数,对于线段树 的每一个节点,可以维护sum及cnt,分别 表示区间dep[x]的和,以及被操作次数

26

C
? 一个二维平面上有N个点(坐标均为整数) ,求存在多少个正方形,满足正方形的顶 点属于这N个点,且边平行于坐标轴

27

C
? 比较暴力的做法 ? 我们枚举一个x,然后枚举这条轴上的两个 点 ? 特点:随机数据是很容易AC的 ? 复杂度:极限情况O(N*N) ? 全部在一条x上 ? 同理枚举y

28

C
? 针对数据,我们要寻求一些奇葩的做法, 以期待出题人没有想到这样的做法,得到 更多的分数 ? 我们枚举一个x + y或x – y,即枚举对角线 上的两个点 ? 你想到了吗,反正我没有想到 ==

29

C
? 暴力出奇迹 ? 我们从数据的角度出发 ? 数据不管怎么出。。总有一个方向上的点 的个数是比较少的。。

30

C
? 对于每一个正方形的右下端点,我们判断 向上的方向和向左的端点,哪一个方向的 点数比较少,贪心的暴力枚举 ? 复杂度O(N*sqrt(N))

31

C
? 我们把所有的点按照x坐标分类,x相同属 于同一类Sx ? 若|Sx|<=sqrt(N),则在Sx中枚举两个点, 判断正方形是否存在 ? 若有两个集合|Sx1|>sqrt(N), Sx2>sqrt(N) ? 在Sx1和Sx2中找到一个y值相同的,判断正 方形是否存在 ? 复杂度:O(N*sqrt(N))

32

推荐题目
? http://codeforces.com/contest/444/pro blem/B ? http://codeforces.com/contest/506/pro blem/D

33

A
? 假设第i次取出的卡片是第pi种卡片,考虑 第i次操作,第i次操作完之后第pi种卡片减 少一个,第i+1次操作之后第pi堆的卡片减 少一个,因为第pi种卡片的个数和第pi堆的 数量是相等的,因此第pi堆的卡片个数总是 大于等于第pi种卡片个数(除了第一堆), 因此最后一个取出来的卡片一定为1,所以 取出所有卡片的概率为a1/n

34

B
? 首先求出所有的情况,然后减去三点共线 的情况。 ? 三点共线的情况可以分水平、竖直、斜的 三种情况,前两种可以很简单的处理出来 ,第三种情况可以三个点连成的线段对应 成的矩形的对角线,这样枚举矩形的边长 然后求gcd求解即可

35

C
? 暴力枚举 O(3^n) ? dp[i][A][B] : 考虑前i个数,春熙的疑惑和 为A,冬马的异或和为B,的方案数 ? O(n * M * M) ? M为ai的上界

36

C
? ans = ans[A < B] + ans[A = B] = (3^n + ans[A = B]) / 2 ? dp[i][A ^ B] : 考虑前i个数,春熙和冬马的 异或和为A ^ B,的方案数 ? O(n * M)

37

D
? ans[i] = max(ans[i], ans[i – 1]); ? 有效状态:区间的两个端点,可以改变最 大值或or值 ? 注意到:区间的两个端点不可能同时为最 大值,所以必有一个端点会改变区间的or 和

38

D
? 枚举区间的左端点 ? 向前找哪些位置会改变区间的or值 ? 因为0<=ai<2^15,所以合法的位置最多 有15个 ? 对于每个合法位置,更新答案即可 ? 同理枚举区间的右端点

39

D
? 这个题有很多非常好的性质,使得我们可 以有各种各样的水法,所有的水法合并在 一起,是可以得很多分数的 ==

40

D
? 基于数据的随机性:可以维护一个单调栈 ,暴力查找所有改变区间最大值的位置 ? 随机数据情况下栈的大小不会太大

41

D
? 存在着一个L,使得当x >= L时,ans[x + 1] = ans[x] ? 事实上对于大部分数据,这个L是非常小的 。。 ? 随机情况下L <= 10 ? So。。 ? 暴力枚举,限制区间长度<=10

42

D
? 还有一些其他的性质。。 ? 比如所有的最优区间,区间内一定有某一 个数,最高位为1 ? 还有当or值达到a[1] | a[2] | … | a[n]时,or 值就不会变大了。。 ? 很难出一组数据可以卡掉所有的非正解方 法

43

谢谢!
祝大家玩得开心!


相关文章:
信息学奥赛(NOIP)必看经典书目汇总
信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中教育_教育专区。信息学奥赛(...程序设计的方法 5、 《全国青少年信息学奥林匹克联赛模拟训练试卷精选》 王建德...
信息学奥赛(NOIP)必看经典书目汇总
信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中教育_教育专区。信息学奥赛(...吴文虎,王建德著,系统地介绍了计算机的基础知识和利用 方法 Pascal 语言进行程序...
2014 NOIP信息学奥赛——算法快速入门教程(中国计算机学会出版)
2014 NOIP信息学奥赛——算法快速入门教程(中国计算机学会出版)_学科竞赛_高中教育...算法是指为解决 一个问题而采用的方法和步骤;从程序计设的角度上讲,算法是指...
信息学奥赛(NOIP)必看经典书目汇总
信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中教育_教育专区。信息学奥赛(...程序设计的方法 5、 《全国青少年信息学奥林匹克联赛模拟训练试卷精选》 王建德...
NOIP信息学奥赛复赛做题指导
始终要 保持一个清晰的思路 ,只有这样你才可能找出正 确的解题方法,否则你将...信息学奥赛复赛竞赛策略 竞赛一共有 4 题,每题 100 分,共 400 分,比赛时间...
信息学奥赛NOIP初赛复习知识点
信息学奥赛NOIP初赛复习知识点_其它课程_高中教育_...2、与竞赛有关的知识: A:信息学奥赛相关的软件有...而对子树也采用同样方法处理:同层子树与它的根...
信息学奥赛NOIP初赛复习知识点+基本函数
信息学奥赛NOIP初赛复习知识点+基本函数_学科竞赛_高中教育_教育专区。信息学奥赛...是速度最快的排序方法 排序方法简单排序 (采用比较为主要 操作的算法) 时间复杂...
信息学奥赛训练计划(袁森龙)
使学生具备参加全国信息学奥林匹克竞赛分区联赛 NOIP (初赛、 复赛) 的能力。 ...学会程序的常用调试手段和技巧,在用 Pascal 解决问题的过程中引入基础算法的运用...
全国青少年信息学奥林匹克联赛大纲
(National Olympiad in Informatics in Provinces, 简称 NOIP)是全国信息学奥林匹克 竞赛(NOI)系列活动中的一个重要组成部分,旨在向中学生普及计算机基础知 识, ...
更多相关标签:
noip信息学竞赛题目 | noip考试技巧 | noip技巧 | noip完善程序技巧 | noip普及组复赛技巧 | noip骗分小技巧 | noip复赛技巧 | 信息学竞赛 |