NOIP信息學(xué)競賽技巧

1競賽技巧 ——by齊朋輝前言作為一個完全沒有OI經(jīng)歷的ACM選手。。以下內(nèi)容純屬胡編亂造，切勿輕信==方伯伯的玉米田N個數(shù)的序列，最多可以進(jìn)行K次操作：每次操作選擇一個區(qū)間，講這個區(qū)間內(nèi)的數(shù)字+1K次操作完之后，最長單調(diào)不降子序列的長度是多少對于40%的數(shù)據(jù)，1<=n<=1000,1<=K<=100,1<=ai<=500對于100%的數(shù)據(jù)，1<=n<=10000,1<=K<=500,1<=ai<=5000

方伯伯的玉米田Dp[k][i]:以第i個玉米為結(jié)尾，已經(jīng)進(jìn)行k次操作之后，LNDS的最大長度Dp[k][i]=1+max dp[k][j] a[j]<=a[i] dp[kk][j] a[j]+kk<=a[i]+k

樸素轉(zhuǎn)移：N*K*N case1用樹狀數(shù)組優(yōu)化： N*K*logN+N*K*K

方伯伯的玉米田Dp[k][u]:最后一個玉米的高度為u，已經(jīng)進(jìn)行k次操作之后，LNDS的最大長度Dp[k][u]=max(dp[j][v]+1)v+j<=u+k，j<=k二維線段樹復(fù)雜度：N*K*logN*logK

方伯伯的玉米田Dp[k][u]:最后一個玉米的高度為u，已經(jīng)進(jìn)行k次操作之后，LNDS的最大長度Dp[k][u]=max dp[k][v]+1, v<=u dp[k+u–v][v]+1, v>u

樹狀數(shù)組f[k]:maxdp[k][u]

樹狀數(shù)組g[k+u]:maxdp[u][k]

復(fù)雜度：N*K*(logN+logK)

方伯伯的商場之旅假設(shè)一個數(shù)X的K進(jìn)制表示為12312，那么X就對應(yīng)5堆石子：1,2,3,1,2移動石子的代價(jià)是移動石子數(shù)*移動距離Cost(12312)=1*2+2*1+3*0+1*1+2*2=9現(xiàn)在要把L~R內(nèi)每個數(shù)對應(yīng)的石子各自合并為一堆，求最小合并代價(jià)。

方伯伯的商場之旅ans(L,R)=ans(1,R)-ans(1,L–1〕對于每一個x，最優(yōu)決策點(diǎn)為重心設(shè)最優(yōu)位置為p，a[p]=k，p左側(cè)的石子挪到p–1的花費(fèi)為sl，總石子數(shù)為cl，p右側(cè)的石子挪到p+1的花費(fèi)為sr，總石子數(shù)為cr。

方伯伯的商場之旅決策點(diǎn):花費(fèi)p:sl+cl+sr+crp–1:sl+k+sr+cr*2p+1:sl+cl*2+k+sr設(shè)p為最右決策點(diǎn)，那么cost(p)<=min(cost(p–1),cost(p+1))k+cr>=cl,k+cl>=cr

方伯伯的商場之旅最優(yōu)決策點(diǎn)可能有多個，我們選最右端的那個cost(p)<=cost(p–1)cost(p)<cost(p+1)k+cr>=cl,k+cl>cr根據(jù)這兩個條件按位DP即可。。各種枚舉

方伯伯的商場之旅A設(shè)f(x)為x各位數(shù)字之和，例如f(123)=6,f(12)=3,f(3)=3,給一個區(qū)間[l,r],求這個區(qū)間內(nèi)x%f(x)=0的個數(shù)A不會做==怎么辦打表先暴力打表所有[1,100000*k]的答案對于一個查詢[1,n][1,n/100000*100000]的答案是的暴力求出〔n/100000*100000，n]即可A枚舉數(shù)位和sum定義dp[sum][L][now][r]為總的數(shù)位和為sum，長度為L，當(dāng)前和為now，模sum為r的數(shù)，有多少個枚舉每一個sum，O(9*90*90*10)預(yù)處理A對于每一個cas，先枚舉sum，然后按位DP當(dāng)前位從高位到低位開始掃描高位取前綴，枚舉當(dāng)前位當(dāng)前位之前的數(shù)位和sl和模sum的值rl都是確定的那么低位的數(shù)位和為sum–sl設(shè)低位數(shù)字模sum為x那么(rl*10^k+x)%sum=0最近黑點(diǎn)一棵樹，有n個節(jié)點(diǎn)，每個節(jié)點(diǎn)都有一個顏色，黑色或者白色，初始時全部為黑色。M個操作操作1：將u涂為黑色操作2：離u最近的黑色點(diǎn)最近黑點(diǎn)只有白色變黑色，沒有黑色變白色我們可以將m個查詢分為sqrt(m)塊每一塊查詢之后，跑一遍bfs預(yù)處理出所有點(diǎn)到黑點(diǎn)的最近距離同一個塊內(nèi)的黑點(diǎn)，暴力查詢即可B給一棵樹，1為根節(jié)點(diǎn)，每個點(diǎn)都有一個權(quán)值，初始時為0?，F(xiàn)在給兩種操作；Axk:將x的點(diǎn)權(quán)+k，x的兒子點(diǎn)權(quán)+k+1，x的兒子的兒子點(diǎn)權(quán)+k+2，以此類推。Qx:查詢以x為根的子樹中，所有點(diǎn)的點(diǎn)權(quán)和。BO(N*Q)？Soeasy。。O〔sqrt(Q)*N)是不是有點(diǎn)厲害。。B每一個更新操作對查詢答案的奉獻(xiàn)是疊加在一起的所以可以分別計(jì)算出來然后疊加在一起這樣我們就可以分塊啦啦啦啦~B我們可以將每sqrt(Q)個查詢分塊每一塊查詢結(jié)束之后，跑一遍樹形DP，預(yù)處理出所有的答案然后對于每一個查詢，只有同一個查詢塊內(nèi)的操作不在dp值里面，對于這些操作暴力加進(jìn)答案即可B樹形DPdp[u]=sum(dp[v])+val[u](v是u的子節(jié)點(diǎn)〕val[u]只和祖先有關(guān)，所以dfs的時候記錄一下就好B查詢以u為根節(jié)點(diǎn)的子樹對答案產(chǎn)生影響的操作只有u的祖先和u的子節(jié)點(diǎn)BO(Q*logN)？樹形轉(zhuǎn)線形〔dfs序列〕因?yàn)樽訕涞膁fs序列是連續(xù)的，所以相當(dāng)于區(qū)間更新區(qū)間查詢Axk:我們可以分解為這樣的兩局部x的子樹全部+k–dep[x]X的子樹全部加上dep[u]即深度B操作1：x的子樹全部+k–dep[x]操作2：X的子樹全部加上dep[u]即深度操作1：簡單的線段樹懶操作標(biāo)記即可操作2：每個位置加固定的數(shù)，對于線段樹的每一個節(jié)點(diǎn)，可以維護(hù)sum及cnt，分別表示區(qū)間dep[x]的和，以及被操作次數(shù)C一個二維平面上有N個點(diǎn)〔坐標(biāo)均為整數(shù)〕，求存在多少個正方形，滿足正方形的頂點(diǎn)屬于這N個點(diǎn)，且邊平行于坐標(biāo)軸C比較暴力的做法我們枚舉一個x，然后枚舉這條軸上的兩個點(diǎn)特點(diǎn)：隨機(jī)數(shù)據(jù)是很容易AC的復(fù)雜度：極限情況O(N*N)全部在一條x上同理枚舉yC針對數(shù)據(jù)，我們要尋求一些奇葩的做法，以期待出題人沒有想到這樣的做法，得到更多的分?jǐn)?shù)我們枚舉一個x+y或x–y，即枚舉對角線上的兩個點(diǎn)你想到了嗎，反正我沒有想到==C暴力出奇跡我們從數(shù)據(jù)的角度出發(fā)數(shù)據(jù)不管怎么出。?？傆幸粋€方向上的點(diǎn)的個數(shù)是比較少的。。C對于每一個正方形的右下端點(diǎn)，我們判斷向上的方向和向左的端點(diǎn)，哪一個方向的點(diǎn)數(shù)比較少，貪心的暴力枚舉復(fù)雜度O(N*sqrt(N))C我們把所有的點(diǎn)按照x坐標(biāo)分類，x相同屬于同一類Sx假設(shè)|Sx|<=sqrt(N)，那么在Sx中枚舉兩個點(diǎn)，判斷正方形是否存在假設(shè)有兩個集合|Sx1|>sqrt(N),Sx2>sqrt(N)在Sx1和Sx2中找到一個y值相同的，判斷正方形是否存在復(fù)雜度：O(N*sqrt(N))推薦題目://codeforces/contest/444/problem/B://codeforces/contest/506/problem/DA假設(shè)第i次取出的卡片是第pi種卡片，考慮第i次操作，第i次操作完之后第pi種卡片減少一個，第i+1次操作之后第pi堆的卡片減少一個，因?yàn)榈趐i種卡片的個數(shù)和第pi堆的數(shù)量是相等的，因此第pi堆的卡片個數(shù)總是大于等于第pi種卡片個數(shù)〔除了第一堆〕，因此最后一個取出來的卡片一定為1，所以取出所有卡片的概率為a1/nB首先求出所有的情況，然后減去三點(diǎn)共線的情況。三點(diǎn)共線的情況可以分水平、豎直、斜的三種情況，前兩種可以很簡單的處理出來，第三種情況可以三個點(diǎn)連成的線段對應(yīng)成的矩形的對角線，這樣枚舉矩形的邊長然后求gcd求解即可C暴力枚舉O(3^n)dp[i][A][B]:考慮前i個數(shù)，春熙的疑惑和為A，冬馬的異或和為B，的方案數(shù)O(n*M*M)M為ai的上界Cans=ans[A<B]+ans[A=B]=(3^n+ans[A=B])/2dp[i][A^B]:考慮前i個數(shù)，春熙和冬馬的異或和為A^B，的方案數(shù)O(n*M)Dans[i]=max(ans[i],ans[i–1]);有效狀態(tài)：區(qū)間的兩個端點(diǎn)，可以改變最大值或or值注意到：區(qū)間的兩個端點(diǎn)不可能同時為最大值，所以必有一個端點(diǎn)會改變區(qū)間的or和D枚舉區(qū)間的左端點(diǎn)向前找哪些位置會改變區(qū)間的or值因?yàn)?<=ai<2^15，所以合法的位置最多有15個對于每個合法位置，更新答案即可同理枚舉區(qū)間的右端點(diǎn)D這個題有很多非常好的性質(zhì)，使得我們可以有各種各樣的水法，所有的水法合并在一起，是可以得很多分?jǐn)?shù)的==D基于數(shù)據(jù)的隨機(jī)性：可以維護(hù)一個單調(diào)棧，暴力查找所有改變區(qū)間最大值的位置隨機(jī)數(shù)據(jù)情況下棧的大小不會太大D存在著一個L，