Preface

第一次體驗NOI，雖然不是正式選手，但是打打同步賽還是挺漲姿勢的，也算是體驗了一把。

Day1很爆炸，一方面是NOI題目的難度高于自身的水平，另一方面也出現(xiàn)了比較大的失誤，T1一個數(shù)組沒有清空導(dǎo)致樹的部分分全部爆0了；T3可能是蜜汁Hash寫掛（or 題意理解錯誤？）導(dǎo)致暴力（不過話說好多網(wǎng)絡(luò)賽的人T3都爆零了）

不禁想到如果是自身參加NOI雖然不太現(xiàn)實，出現(xiàn)這樣的SB錯誤會不會后悔呢？

后面兩題不會，靜候未來填坑。

---

歸程

整套題目看起來唯一可做的題目（對于我來說），所以讀完題目就馬上看了下部分分

woc，CCF這么良心的嗎？所以就來了一波大力分類討論：

• 前30pts(\(1\to 6\))：海拔僅有一種且為\(1\)，這不是良心送分么？我從終點開始往回刷一遍DJ（別問我為什么不用SPFA），每一次判斷洪水高度是否\(>1\)即可，若是直接輸出最短路徑（反正一條路都沒有了，只能靠腳了），否則輸出\(0\)（直接飆車到達即可）
• 后面的10pts（\(15\to16\)）：注意到數(shù)據(jù)范圍很小，我們還是先預(yù)處理。對于每一次詢問，我們從起點開始BFS，期間只能經(jīng)過高度大于洪水高度的邊，然后再所以能夠到達的點中找出離終點最近的點擊即可。
• 中間的25pts(\(7\to 11\))：保證數(shù)據(jù)為鏈or樹，由于樹的特殊性，我們直接考慮樹怎么做。首先最短路是要跑的（直接用DJ也行，不過自己再寫一個BFS什么的會更快），然后我們直接以終點為根，預(yù)處理出LCA數(shù)組（用來跳father）以及倍增數(shù)組（記錄每一段樹鏈上權(quán)值最小的邊）。考慮洪水淹沒的過程，只要一條邊斷了，這條路就不得不停止。所以我們樹上倍增找到第一條被淹沒的邊，然后在輸出這個點到根的路徑長度即可（用前面的兩個數(shù)組做類似于倍增LCA的過程）。
• 中間的15pts（\(13\to 14\))：這個我們注意到離線這個重要性質(zhì)。我們把所以操作讀進來，按洪水高度從大到小排個序。這時候我們發(fā)現(xiàn)對于操作的進行其實就是個不斷地給原圖加邊的一個過程，所以我們用并查集維護，順便維護每一個聯(lián)通塊內(nèi)的點距離終點最近的距離即可。

然后滿分算法蒟蒻就不會了，其實按照上面的離線方法是可以跑在線的情況的，只不過需要可持久化并查集。然后由于我很菜，一直都沒調(diào)出來，所以還是等著以后再填吧。

具體同步賽的時候由于樹的情況倍增數(shù)組沒有清空，所以少得了15pts（還好我把鏈和暴力一起做了），并且最后離線想到了懶得寫了（在剛T2,T3）

這里上分類討論CODE（能過前16組數(shù)據(jù)，所以在Luogu上這一題顯示過了，好像還很快）

#include<cstdio> #include<cctype> #include<cstring> #include<queue> #include<algorithm> using namespace std; const int N=2e5+5,M=4e5+5,MINER_N=1505,P=21; struct edge {int to,next,v,h; }e[M<<1]; struct data {int num,s;bool operator <(const data a) const { return a.s<s; } }; struct double_edge {int l,r,s; }a[M]; struct ques {int x,h,id; }b[N>>1]; priority_queue<data> small; int n,m,q,k,s,ans,x,y,l,h,cnt,head[N],dis[N],t,que[MINER_N],f[N][P],father[N][P],sum[N],fa[N],Ans[N>>1]; bool flag,vis[N],get[MINER_N]; inline char tc(void) {static char fl[100000],*A=fl,*B=fl;return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++; } inline void read(int &x) {x=0; char ch; while (!isdigit(ch=tc()));while (x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc())); } inline void write(int x) {if (x>9) write(x/10);putchar(x%10+'0'); } inline void double_add(int x,int y,int v,int h) {e[++cnt].to=y; e[cnt].next=head[x]; e[cnt].v=v; e[cnt].h=h; head[x]=cnt;e[++cnt].to=x; e[cnt].next=head[y]; e[cnt].v=v; e[cnt].h=h; head[y]=cnt; } inline int min(int a,int b) {return a<b?a:b; } inline void clear(void) {memset(head,-1,sizeof(head)); cnt=ans=0; flag=1;memset(f,0,sizeof(f)); memset(sum,0,sizeof(sum)); } inline void Dijkstra(int s) {memset(dis,63,sizeof(dis)); memset(vis,0,sizeof(vis));small.push((data){s,0}); dis[s]=0;while (!small.empty()){int now=small.top().num; small.pop();if (vis[now]) continue; vis[now]=1;for (register int i=head[now];~i;i=e[i].next)if (dis[e[i].to]>dis[now]+e[i].v){dis[e[i].to]=dis[now]+e[i].v;small.push((data){e[i].to,dis[e[i].to]});}} } inline void reset(int now) {for (register int i=0;i<P-1;++i)if (father[now][i]) father[now][i+1]=father[father[now][i]][i],f[now][i+1]=min(f[now][i],f[father[now][i]][i]); } inline void DFS(int now,int fa) {register int i; father[now][0]=fa; reset(now);for (i=head[now];~i;i=e[i].next)if (e[i].to!=fa) f[e[i].to][0]=e[i].h,sum[e[i].to]=sum[now]+e[i].v,DFS(e[i].to,now); } inline void solve1(int x,int h) {write(ans=(h>=1?dis[x]:0)); putchar('\n'); } inline void solve2(int x,int h) {for (register int i=P-1;i>=0;--i)if (father[x][i]&&f[x][i]>h) x=father[x][i];write(ans=sum[x]); putchar('\n'); } inline void solve3(int x,int h) {register int i,H=0,T=1; memset(get,0,sizeof(get));que[1]=x; get[x]=1; int res=dis[x];while (H<T){int now=que[++H];for (i=head[now];~i;i=e[i].next)if (e[i].h>h&&!get[e[i].to]) res=min(res,dis[e[i].to]),get[e[i].to]=1,que[++T]=e[i].to;}write(ans=res); putchar('\n'); } inline bool cmp1(double_edge a,double_edge b) {return a.s>b.s; } inline bool cmp2(ques a,ques b) {return a.h>b.h; } inline int getfa(int k) {return k^fa[k]?fa[k]=getfa(fa[k]):k; } inline void unionn(int x,int y) {int fx=getfa(x),fy=getfa(y);if (fx!=fy) {if (dis[fx]<dis[fy]) fa[fy]=fx; else fa[fx]=fy;} } inline void solve4(void) {register int i,p=1; for (i=1;i<=q;++i)read(b[i].x),read(b[i].h),b[i].id=i;sort(a+1,a+m+1,cmp1); sort(b+1,b+q+1,cmp2);for (i=1;i<=n;++i) fa[i]=i;for (i=1;i<=q;++i){while (p<m&&a[p].s>b[i].h) unionn(a[p].l,a[p].r),++p;Ans[b[i].id]=dis[getfa(b[i].x)];}for (i=1;i<=q;++i)write(Ans[i]),putchar('\n'); } int main() {//freopen("return.in","r",stdin); freopen("return.out","w",stdout);register int i; read(t);while (t--){read(n); read(m); clear();for (i=1;i<=m;++i){read(x); read(y); read(l); read(h); a[i]=(double_edge){x,y,h};double_add(x,y,l,h); if (h^1) flag=0;}if (m!=n-1) Dijkstra(1); else DFS(1,0); read(q); read(k); read(s);if (!k&&q==100000&&!flag&&m!=n-1) { solve4(); continue; }while (q--){read(x); read(y); x=(1LL*x+k*ans-1)%n+1; y=(1LL*y+k*ans)%(s+1);if (flag) { solve1(x,y); continue; }if (m==n-1) solve2(x,y); else solve3(x,y);}}return 0; }

---

冒泡排序

那個板子其實剛開始是錯的而且同步賽好像并沒有更正

蒟蒻表示這種數(shù)學(xué)向的題目太恐怖，所以一直企圖切出前\(11\)個點的狀壓DP

然而什么也沒搞出來，最后交了個全排列證明我曾經(jīng)來過水了8分

---

你的名字

字符串什么也不會好吧Hash的奇技淫巧我還是挺熟練的的菜雞表示看到題目直接棄療。

直奔12pts的Hash暴力而去，最后爆\(0\)了，我應(yīng)該是看錯題意了。

反正一堆dalao說著線段樹套SAM就水過，我還是回去老老實實學(xué)ACWA自動機吧

---

Postscript

反正我太菜了也沒什么關(guān)系只要不是真的NOI爆炸我還是可以接受的

爭取明年同步賽不要翻低級錯誤吧不敢說出去NOI的我

轉(zhuǎn)載于:https://www.cnblogs.com/cjjsb/p/9457858.html

總結(jié)

以上是生活随笔為你收集整理的NOI Day1线上同步赛梦游记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。