AtCoder Regular Contest 065

C - Daydream

Score : $300$ points

倒著來就行了，正著來會產生歧義匹配，$dreamer,dream$產生歧義，倒著來的話是確定的。

代碼

D - Connectivity

Score : $400$ points

用兩個并查集合并起來兩個圖，讓后開一個$map$，讓$mp[p1[i],p2[i]]++$，最后輸出即可。

代碼

E - Manhattan Compass

Score : $900$ points 切比雪夫距離 + 二分

題意：

給你$n$個點對，問從$a$出發，每次走$a$到$b$的曼哈頓距離，問能走到多少個點對。

$1\le n\le 1e5$

思路：

首先將曼哈頓距離轉換成切比雪夫距離，距離變成$max(abs(x_a?x_b),abs(y_a?y_b))$，顯然可以排序亂搞。

將$x,y$分兩次考慮，這里只考慮$x$，設$a?d$的曼哈頓距離是$d$。

將$x$從小到大排序，讓后離散化一下，將每個點$y$坐標插到對應的$x$的位置，之后遍歷$x$，找$x?d$的位置，這個時候已經保證了距離為$d$了，那么我們只需要滿足$abs(y?y_k)<=d$即可，可以在$x$這個位置存的$y$內二分找到位置算貢獻。

但是這樣直接寫遍歷所有位置去重顯然是會超時的，考慮優化一下。

有兩種，思路是一樣的，講一下簡單的。

我們還是找到位置，但是不是在$x?d$的這個位置找$y$，而是我們將$(x,y)$存到一個$pair$里面，讓后二分$(x?d,y?d),(x?d,y+d)$的位置，由于角上的位置會重復，我們算$y$的時候去掉即可。假設二分的位置是$(l,r)$，那么我們給$(l,r)$打一個懶標記，代表將$(l,r)$內的點合并起來，合并是為了方便最后求答案，答案一定是與$a$連通的。

這樣就可以了，注意細節即可。

代碼1

代碼2

F - Shuffling

Score : $900$ points $dp$

題意：

給你一個串$s$，依次進行$m$次操作，每次可以將$[l_i,r_i]$區間內的$s$隨意排序，問最終能生成多少不同的$01$序列，保證詢問的$l$升序。

$1\le n\le 3000,1\le m\le 3000$

這是一個又難又簡單的$dp$，考慮到$l$升序，我們設$dp[i][j]$表示到了第$i$個，前$i$個有$j$個$1$，轉移很簡單，就是$dp[i][j]+=dp[i?1][j],dp[i][j]+=dp[i?1][j?1]$，主要的問題是$j$的范圍。

先考慮這個范圍是否能構成，就是先看成$01$可以隨意分配，我們先求一下每個位置被覆蓋的區間最遠能到哪里，設為$maxr[i]$，那么$[1,maxr[i]]$區間內的$01$假設都可以分配給前$i$個，這樣能算出來前$i$個$1$的個數的上限和下限，讓后直接轉移即可。

雖然某個狀態可能是不存在的，但是不影響答案。

代碼

總結

以上是生活随笔為你收集整理的AtCoder Regular Contest 065的全部內容，希望文章能夠幫你解決所遇到的問題。

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