昨晚1h20min做完了3個題，看下排名600左右，感覺穩可以上分了，于是看了下D構造？感覺不太會沒細想于是看了看E感覺好像和之前有一個題目很像（那個題我討論了好長時間），然后磨嘰磨嘰還有20min感覺寫不了一個題了，于是看了下排名仍然是600左右，于是上床睡覺了（玩手機）畢竟第二天早八這誰頂得住。

結果今天晚上發現我?被fst了，TLE我人傻了，本來晚上不想補題了，看見fst心情十分不爽，于是稍微改了改代碼就A了，我人傻了？？？

不過最終還加分了？2題還加分確實說明我菜

---

D. Dogeforces

二分抄代碼題解
上級嚴格比下級打，于是lca分數從小到大進行構造，用并查集維護連通關系，畢竟并查集就是一棵樹啊看代碼很容易理解

看上述題解即可

#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; constexpr int N=200010; int n,m; struct node {int u,v;int val;bool operator<(const node&o)const{return val<o.val||val==o.val&&u<o.u||val==o.val&&u==o.u&&v<o.v;} }b[510*510]; int fa[N],p[N],c[N]; int cnt,tot; int find(int x){return x==p[x]?x:p[x]=find(p[x]);} void prework() {cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){int val;cin>>val;if(i<j) b[++cnt]=(node){i,j,val};else if(i==j) c[i]=val;}for(int i=1;i<=n;i++) p[i]=i; } void solve() {tot=n;sort(b+1,b+1+cnt);for(int i=1;i<=cnt;i++){int u=find(b[i].u),v=find(b[i].v);if(u==v) continue;int top=max(c[u],c[v]);if(top==b[i].val){if(c[u]==b[i].val)p[v]=u,fa[v]=u;elsep[u]=v,fa[u]=v;}else if(top<b[i].val){++tot;p[tot]=tot;c[tot]=b[i].val;p[u]=p[v]=tot;fa[u]=fa[v]=tot;}} } void print() {cout<<tot<<'\n';for(int i=1;i<=tot;i++) cout<<c[i]<<' ';cout<<'\n';int rt=0;for(int i=1;i<=tot;i++) if(find(i)==i) rt=i;cout<<rt<<'\n';for(int i=1;i<=tot;i++)if(find(i)!=i) cout<<i<<' '<<fa[i]<<'\n'; } int main() {IO;prework();solve();print();return 0; }

題解？（×）
總結？（√）

要加油哦~
感覺越來越沒時間學這破東西了，只能熬夜打打cf了

總結

以上是生活随笔為你收集整理的codeforces1494 D. Dogeforces（构造）的全部內容，希望文章能夠幫你解決所遇到的問題。

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