題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)由 $n$ 個(gè)點(diǎn)組成的競(jìng)賽圖，現(xiàn)在要求出一組點(diǎn)對(duì) $(A,B)$，滿(mǎn)足兩個(gè)點(diǎn)可以互達(dá)，且入度的絕對(duì)值之差最大

題目分析：結(jié)論題，先放結(jié)論：

結(jié)論：競(jìng)賽圖強(qiáng)連通縮點(diǎn)后的DAG呈類(lèi)似于鏈狀，前面的所有點(diǎn)向后面的所有點(diǎn)連邊，即拓?fù)湫蛟谇暗腟CC的任意一節(jié)點(diǎn)的入度嚴(yán)格小于拓?fù)湫蛟诤蟮腟CC的任意一節(jié)點(diǎn)入度

有了這個(gè)結(jié)論后，就可以 $O(n^2)$ 還原出所有的無(wú)向邊，按照入度絕對(duì)值之差貪心排序，每次詢(xún)問(wèn)度數(shù)較大的點(diǎn)是否可達(dá)度數(shù)較小的點(diǎn)即可

這里還有一個(gè)可以不用詢(xún)問(wèn)的做法，需要基于上述結(jié)論的一個(gè)擴(kuò)展，證明參考至：大牛博客

簡(jiǎn)單來(lái)說(shuō)就是：按照入度從小到大排序，如果到前 $i$ 個(gè)點(diǎn)的入度和恰好為 $\frac{i?(i?1)}{2}$，則出現(xiàn)了一個(gè)新的強(qiáng)連通分量，假設(shè)上一次符合條件的點(diǎn)是 $last$，則 $[lst+1,i]$ 區(qū)間中的點(diǎn)構(gòu)成了一個(gè)新的強(qiáng)連通分量

綜上直接掃一遍就可以實(shí)現(xiàn)了

代碼：

// Problem: E. Two Houses // Contest: Codeforces - CodeCraft-21 and Codeforces Round #711 (Div. 2) // URL: https://codeforces.com/contest/1498/problem/E // Memory Limit: 256 MB // Time Limit: 3500 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; pair<int,int>node[N]; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++) {int x;read(x);node[i]={x,i};}sort(node+1,node+1+n);LL sum=0,last=0;int ans1=0,ans2=0,mmax=-1;for(int i=1;i<=n;i++) {sum+=node[i].first;if(sum==i*(i-1)/2) {if(i-1!=last&&node[i].first-node[last+1].first>mmax) {mmax=node[i].first-node[last+1].first;ans1=node[i].second,ans2=node[last+1].second;}last=i;}}printf("! %d %d\n",ans1,ans2);return 0; } 超強(qiáng)干貨來(lái)襲 云風(fēng)專(zhuān)訪(fǎng)：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1498E Two Houses(交互+图论，结论题)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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