NOIP信息学竞赛技巧.ppt

1竞赛技巧 ——by齐朋辉

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

方伯伯的玉米田N个数的序列，最多可以进行K次操作：每次操作选择一个区间，讲这个区间内的数字+1K次操作完之后，最长单调不降子序列的长度是多少对于40%的数据，1=n=1000,1=K=100,1=ai=500对于100%的数据，1=n=10000,1=K=500,1=ai=5000

?方伯伯的玉米田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*logN+N*K*K

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

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

?方伯伯的商场之旅假设一个数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内每个数对应的石子各自合并为一堆，求最小合并代价。

?方伯伯的商场之旅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。

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

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

?方伯伯的商场之旅

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

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

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

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

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

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

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

BO(N*Q)？Soeasy。。O〔sqrt(Q)*N)是不是有点厉害。。

B每一个更新操作对查询答案的奉