寫在前面的一些話

如果我NOIP沒退役，這大概會寫成一個系列吧，所以這算是系列的開始，要寫一些奇怪的東西？

首先解釋下什么叫“拔釘子”，其實就是在釘子上做題嘛......至于釘子具體是個什么東西就當面或者QQ問我好了=。=

然后如果寫成系列的話前面這些應該都是POI了，那就說說POI好了。我個人還是很喜歡POI的出題風格的，基本上沒有什么 Phantasm碼農題/仙人板板板子題/很超巨大無比數據結構題(這都是什么啊喂(#`O′) )。思路在解題中比較重要，然后細節有時候也比較需要注意，至于碼力這個東西在哪里都可以練......總的來說整體水平可以接受(至少有很多題是我這個馬上NOIP退役的蒟蒻能做的)，有一點就是經常出現智商題(2333)。當然也有一些很神仙的可能高于省選水平(?)的題，不過看到了可以繞著走就是了，反正只要有NOIP的水平應該都能找到一些可寫的題的=。=

然后POI一年好像有17道題，似乎是一年考好幾次試總起來的。國內的各個OJ基本上能覆蓋掉POI 2016及以前的題，所以這些題在網上或多或少都能找到題解，之前應該也有好多dalao都按年份刷過POI的。不過不知道為什么POI2017只有BZOJ上Claris搬的五道題，剩下的國內OJ好像都沒有......(但是為什么有POI2018的啊，釘子上都沒有啊=。=)

好了，廢話也說夠了，開始寫我的解題吧=。=

Round I

Flappy Bird

這題和 NOIP 2014 飛揚的小鳥 沒有什么關系......

因為這只鳥只要擦過最后一對柱子就可以了，所以我們正著掃一遍，對每個柱子用它和上個柱子的間隔維護小鳥可以飛到的上下邊界(上界是用來判無解的)，然后這樣一路維護到最后得到一個下界$minh$，答案就是$\left\lfloor \frac{x[n]+minh}{2} \right\rfloor$(點一下相當于可以飛兩格，可以自己畫畫)。注意小鳥能飛到的點的橫縱坐標之和一定是偶數，這個也需要維護一下=。=

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 long long n,x,t1,t2,t3,up,down,len,last; 6 int main () 7 { 8 scanf("%lld%lld",&n,&x); 9 for(int i=1;i<=n;i++) 10 { 11 scanf("%lld%lld%lld",&t1,&t2,&t3),len=t1-last; 12 down=max(down-len,t2+1),up=min(up+len,t3-1); 13 if((up-t1)&1) up--; if((down-t1)&1) down++; 14 if(up<down) printf("NIE\n"),exit(0); last=t1; 15 } 16 printf("%lld",(down+last)/2); 17 return 0; 18 } View Code

Divisibility

首先有一個性質(其實我們小學可能都學過，霧)：在B進制下一個數是B-1的倍數當且僅當其數位和是B-1的倍數

那么就很好做了，構造方法就是把所有數從大到小接起來，然后如果現在這個數不能整除被B-1整除就扣掉那個余數一位，這樣剩余位數是最多的，數就是最大的，然后每個詢問lower_bound一下就好了，注意邊邊角角的細節=。=

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=1000005; 6 long long b,q,k,res,tot,bit; 7 long long cnt[N]; 8 int main () 9 { 10 scanf("%lld%lld",&b,&q); 11 for(int i=0;i<b;i++) 12 { 13 scanf("%lld",&cnt[i]); 14 tot+=cnt[i]*i,bit+=cnt[i]; 15 } 16 res=tot%(b-1); 17 if(res) cnt[res]--,bit--; 18 for(int i=1;i<b;i++) 19 cnt[i]+=cnt[i-1]; 20 while(q--) 21 { 22 scanf("%lld",&k),k++; 23 long long pos=lower_bound(cnt,cnt+b,k)-cnt; 24 k<=cnt[b-1]?printf("%lld\n",pos):printf("-1\n"); 25 } 26 return 0; 27 } View Code

Difference Representations

出現了，智商題！

雖然這題非常CF，不太像OI題=。=

發現這個數列每隔兩個元素翻一番，所以一會就超過1e9(詢問的最大值)了。那么我們暴力預處理前面的數直到它加爆1e9(注意一定是加爆才行)，這說明奇數下標的元素和前面那個數的差值已經爆掉1e9了，那么再能湊出來一定是一個偶數下標的元素減去它前面那個元素。

先把預處理的數塞進map里，然后把預處理得到的所有數對的較大下標塞進一個數組$mem$里；對于每個詢問先嘗試在map里查一下，查不到就在$mem$里面二分出第一個小于它的位置$pos$，這樣$pos$前面的都會被湊出來，而后面的就要兩個兩個每次加$1$來湊，所以設預處理出last個數后爆掉1e9了，那么對于一個數$x$的答案就是$(last+2*(x-pos),last+2*(x-pos)-1)$

1 #include<map> 2 #include<cstdio> 3 #include<cstring> 4 #include<utility> 5 #include<algorithm> 6 using namespace std; 7 const int N=1e7+7,MAXX=1e9; 8 map<int,pair<int,int> > mp; 9 map<int,pair<int,int> >::iterator it; 10 int a[100],mem[N],T,p,rd; 11 void prework() 12 { 13 a[1]=1,a[p=2]=2,mp[1]=make_pair(2,1); 14 while(a[p]<=MAXX||p%2==1) 15 { 16 if((++p)&1) a[p]=2*a[p-1]; 17 else 18 for(int i=1;i<=a[p-1];i++) 19 if(mp.find(i)==mp.end()) 20 {a[p]=a[p-1]+i; break;} 21 for(int i=1;i<p;i++) 22 mp[a[p]-a[i]]=make_pair(p,i); 23 } 24 for(it=mp.begin();it!=mp.end();it++) 25 { 26 pair<int,pair<int,int> > pr=*it; 27 mem[++mem[0]]=pr.first; 28 } 29 } 30 int main () 31 { 32 prework(),scanf("%d",&T); 33 while(T--) 34 { 35 scanf("%d",&rd),it=mp.find(rd); 36 if(it!=mp.end()) 37 { 38 pair<int,pair<int,int> > pr=*it; 39 printf("%d %d\n",pr.second.first,pr.second.second); 40 } 41 else 42 { 43 int pre=lower_bound(mem+1,mem+1+mem[0],rd)-mem-1; 44 printf("%d %d\n",p+2*(rd-pre),p+2*(rd-pre)-1); 45 } 46 } 47 return 0; 48 } View Code

Sabotage

友善的二分答案+樹形DP檢驗

好像挺簡單的，設$dp[i]$表示最壞情況下$i$的子樹里有幾個叛徒，然后每次二分完DP一下就好了(霧

1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=500005; 7 const double eps=1e-6; 8 vector<int> son[N]; 9 int dp[N],siz[N]; 10 int n,k,rd,cnt; 11 double l,r,mid; 12 void DFS1(int nde) 13 { 14 siz[nde]=1; 15 for(int i=0;i<(int)son[nde].size();i++) 16 { 17 int goal=son[nde][i]; DFS1(goal); 18 siz[nde]+=siz[goal]; 19 } 20 } 21 void DFS2(int nde) 22 { 23 if(son[nde].empty()) 24 {dp[nde]=1; return;} 25 int maxx=0; 26 for(int i=0;i<(int)son[nde].size();i++) 27 { 28 int goal=son[nde][i]; DFS2(goal); 29 maxx=max(maxx,dp[goal]); 30 } 31 dp[nde]=((double)maxx/(double)(siz[nde]-1)>mid)?siz[nde]:maxx; 32 } 33 bool check() 34 { 35 memset(dp,0,sizeof dp),DFS2(1); 36 return dp[1]<=k; 37 } 38 int main() 39 { 40 scanf("%d%d",&n,&k); 41 for(int i=2;i<=n;i++) 42 { 43 scanf("%d",&rd); 44 son[rd].push_back(i); 45 } 46 l=0,r=1,DFS1(1); 47 while(r-l>eps) 48 { 49 mid=(l+r)/2; 50 check()?r=mid:l=mid; 51 } 52 printf("%lf",r); 53 return 0; 54 } View Code

Tourist

畫風突變，做不來，告辭

求競賽圖的哈密頓回路，反正我是棄了，哪位神仙會做一定讓我%1%

放個學長的鏈接吧=。=

Round 2

Sports competition

求一類特殊的二分圖匹配的新思路(i207M說lyd講過，我怎么不記得怕不是當時在摸魚)

我們將每個左部點連到的右部點互相連起來并記錄度數(只有一個右部點就連自己，度數加2)，然后就得到了一個基環樹森林。那么無解就是因為一棵基環樹里的度數超過了點數的二倍，說明這個聯通塊里的邊不夠分了。判完無解之后我們就嘗試把每棵基環樹上的邊定向來得到外向基環樹，如果可行說明有唯一解；具體來說就是看看每個聯通塊里都有沒有自環，如果有那么這棵基環樹一定可以定向成一棵外向基環樹，而沒有的話就可能有兩種定向，這樣統計完如果有唯一解再DFS一遍即可得出方案。

1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=1e6+6; 7 const long long mod=1e9+7; 8 int deg[N],sig[N],xnt[N],vis[N],cir[N],uni[N],outp[N]; 9 int p[N],noww[2*N],goal[2*N],val[2*N]; 10 int n,t1,t2,pw,cnt,tot; 11 vector<int> col[N]; 12 char rd[5]; 13 void link(int f,int t,int v) 14 { 15 noww[++cnt]=p[f],p[f]=cnt; 16 goal[cnt]=t,val[cnt]=v; 17 } 18 long long qpow(long long x,long long k) 19 { 20 if(k==1) return x; 21 long long tmp=qpow(x,k/2); 22 return k%2?tmp*tmp%mod*x%mod:tmp*tmp%mod; 23 } 24 void DFS(int nde,int fth) 25 { 26 if(sig[nde]) uni[tot]=true; 27 vis[nde]=true,col[tot].push_back(nde); 28 for(int i=p[nde];i;i=noww[i]) 29 if(goal[i]!=fth) 30 { 31 if(vis[goal[i]]) cir[tot]=goal[i]; 32 else DFS(goal[i],nde); 33 } 34 } 35 void mark(int nde,int fth) 36 { 37 vis[nde]=true; 38 for(int i=p[nde];i;i=noww[i]) 39 if(goal[i]!=fth) 40 { 41 outp[val[i]]=goal[i]; 42 if(!vis[goal[i]]) mark(goal[i],nde); 43 } 44 } 45 int main() 46 { 47 scanf("%d",&n); 48 for(int i=1;i<=n;i++) 49 { 50 scanf("%s",rd); 51 if(rd[0]=='T') 52 { 53 scanf("%d",&t1),sig[t1]=true; 54 link(t1,t1,i),deg[t1]+=2; 55 } 56 else 57 { 58 scanf("%d%d",&t1,&t2); 59 link(t1,t2,i),link(t2,t1,i); 60 deg[t1]++,deg[t2]++; 61 } 62 } 63 for(int i=1;i<=n;i++) 64 if(!vis[i]) tot++,DFS(i,-1); 65 for(int i=1;i<=tot;i++) 66 for(int j=0;j<(int)col[i].size();j++) 67 xnt[i]+=deg[col[i][j]]; 68 for(int i=1;i<=tot;i++) 69 { 70 if(xnt[i]>2*(int)col[i].size()) 71 printf("NIE\n0"),exit(0); 72 if(!uni[i]) pw++; 73 } 74 if(pw) printf("NIE\n%lld",qpow(2,pw)),exit(0); 75 memset(vis,0,sizeof vis); 76 for(int i=1;i<=tot;i++) 77 mark(cir[i],-1); 78 printf("TAK\n"); 79 for(int i=1;i<=n;i++) 80 printf("%d\n",outp[i]); 81 return 0; 82 } View Code

Sum of digits

驚了，CF怕不是出了個POI原題弱化版

這就是CF1070A Find a number的加強版，現在詢問數位和為$s$且能被$d$整除的第$k$小數(原題詢問最小的數)，當然數據范圍也減少了不少

然后我咕了，做法應該差不多吧

Strike

又出現了，智商題！

一開始把題想復雜了，問ztb他說可以用線段樹維護BFS序(不過這也算學到了，我以前從沒想過這種東西233)，結果后來又發現好像維護不了。然后i207M說他要寫寫試試，過了一會他告訴我他A了，根本不用線段樹，直接模擬即可=。=

對每個點記錄它是否存在和它有幾個兒子還存在，然后記錄當前點數和邊數按題意模擬即可，每次答案即點數-邊數，注意根節點特殊考慮一下

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=500005; 6 int exi[N],anc[N],son[N]; 7 int p[N],noww[2*N],goal[2*N]; 8 int n,T,t1,t2,rd,cnt,cnn,cne,root; 9 void link(int f,int t) 10 { 11 noww[++cnt]=p[f]; 12 goal[cnt]=t,p[f]=cnt; 13 } 14 void DFS(int nde,int fth) 15 { 16 anc[nde]=fth,exi[nde]=true; 17 for(int i=p[nde];i;i=noww[i]) 18 if(goal[i]!=fth) DFS(goal[i],nde),son[nde]++; 19 } 20 int main () 21 { 22 scanf("%d",&n); 23 for(int i=1;i<n;i++) 24 { 25 scanf("%d%d",&t1,&t2); 26 link(t1,t2),link(t2,t1); 27 } 28 cnn=n,cne=n-1,root=1; 29 DFS(1,0),scanf("%d",&T); 30 while(T--) 31 { 32 scanf("%d",&rd); 33 if(rd>0) 34 { 35 exi[rd]=false,cnn--,cne-=son[rd]; 36 if(rd!=root) 37 { 38 son[anc[rd]]--; 39 if(exi[anc[rd]]) cne--; 40 } 41 } 42 else 43 { 44 rd=-rd; 45 exi[rd]=true,cnn++,cne+=son[rd]; 46 if(rd!=root) 47 { 48 son[anc[rd]]++; 49 if(exi[anc[rd]]) cne++; 50 } 51 } 52 printf("%d\n",cnn-cne); 53 } 54 return 0; 55 } View Code

Shipping containers

紀念在釘子上的第一個Unaccepted(Runtime Error)，因為沒判斷越界的問題=。=

根號分類討論來均攤復雜度，對于距離$d$小于$sqrt(n)$的以$d$為間隔差分一下最后求前綴和，對于距離大于$sprt(n)$的直接暴力做，總復雜度$O(n$ $sqrt(n))$。注意空間可能比較緊，可以把標準調的小于根號$n$一些(釘子是按點測試而且大測試點基本都有3~4s，所以基本不會卡常)

1 #pragma GCC optimize(2) 2 #include<cmath> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 const int N=100005,Sqrt=290; 8 int dif[Sqrt][N],num[N]; 9 int n,m,t1,t2,t3,ed,blo; 10 int main () 11 { 12 scanf("%d%d",&n,&m),blo=min(288,(int)sqrt(n)); 13 for(int i=1;i<=m;i++) 14 { 15 scanf("%d%d%d",&t1,&t2,&t3),ed=t1+(t2-1)*t3; 16 if(t3<=blo) 17 { 18 dif[t3][t1]++; 19 if(ed+t3<=n) dif[t3][ed+t3]--; 20 } 21 else 22 for(int i=t1;i<=ed;i+=t3) num[i]++; 23 } 24 for(int i=1;i<=blo;i++) 25 for(int j=1;j<=n;j++) 26 { 27 if(j-i>=0) 28 dif[i][j]+=dif[i][j-i]; 29 num[j]+=dif[i][j]; 30 } 31 for(int i=1;i<=n;i++) 32 printf("%d ",num[i]); 33 return 0; 34 } View Code

?Pizza delivery

---

哇蒟蒻博主發現自己并沒有按年份刷的實力和時間，于是......

咕咕咕飛走

如果這只鶸NOIP沒退役他大概會回來補的，這之前大概POI的解題還得散著寫=。=

轉載于:https://www.cnblogs.com/ydnhaha/p/9851945.html

總結

以上是生活随笔為你收集整理的yd的拔钉子之路之 POI 2017的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。