C. Longest Simple Cycle

題意：

有n條鏈，第i條鏈上有c[i]個(gè)點(diǎn)，a[i]為第i條鏈的頂點(diǎn)與第i-1條鏈的連接點(diǎn)，b[i]為第i條鏈的最后一個(gè)點(diǎn)與第i-1條鏈的連接點(diǎn)。通過上面的方法連接鏈會(huì)產(chǎn)生很多的環(huán)，問這些環(huán)的最大長(zhǎng)度。
看樣例

4 3 4 3 3 -1 1 2 2 -1 2 2 3

第二列共4個(gè)點(diǎn)，第二列最上面的點(diǎn)連接了第一列的點(diǎn)1（從上往下編號(hào)），第二列最下面的點(diǎn)連接了第一列的點(diǎn)2
最后建圖得：

題解：

我們從右往左枚舉環(huán)的左邊界，
假設(shè)當(dāng)前位置在i，當(dāng)前環(huán)包含的點(diǎn)為sum（sum包含環(huán)從右邊界到i-1位置的上下兩個(gè)端點(diǎn)，此時(shí)還未閉環(huán)）
x和y分別記錄a[i+1]和b[i+1]的最小值和最大值（即第i列的上下界）
開始分類討論：
如果x == y，說明這個(gè)環(huán)結(jié)束了（閉環(huán)了），必須以i為新的右邊界繼續(xù)進(jìn)行枚舉
如果sum + x + c[i] - y +1 < c[i] 說明以i為新的右邊界組成的環(huán)一定會(huì)大于原有的環(huán)（如果左邊界在i的左邊）。因此我們就舍棄原有的環(huán)，以i為右邊界繼續(xù)向左枚舉答案
如果sum + x + c[i] - y +1 >= c[i] ,說明當(dāng)前環(huán)比以i為右端點(diǎn)組成的新環(huán)更大，因此保留原有環(huán)，繼續(xù)向左枚舉。
枚舉過程中記錄最長(zhǎng)閉環(huán)的長(zhǎng)度

代碼：

#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <map> #include <queue> #include <vector> #include <set> #include <bitset> #include <algorithm> #define LL long long #define PII pair<int,int> #define x first #define y second using namespace std; const int N=1e5+5; int a[N],b[N],c[N]; int main() {int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&c[i]);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) scanf("%d",&b[i]);LL ans=0,sum=0; //sum表示當(dāng)前環(huán)包含的點(diǎn)數(shù)，ans記錄環(huán)的最大值int x=1,y=c[n]; //與上述作用相同for(int i=n;i>1;i--) //從右往左進(jìn)行枚舉{if(x==y||sum+x+c[i]-y+1<c[i]) sum=c[i]; //符合條件1，3，以i為新的右邊界來組成環(huán)，新環(huán)的初始長(zhǎng)度為c[i]else sum+=x+c[i]-y+1; //符合條件2，繼續(xù)使用原有環(huán)，并更新sum的長(zhǎng)度，將i鏈加入sumx=min(a[i],b[i]);y=max(a[i],b[i]); //記錄新的x,y值ans=max(ans,sum+y-x+1); //記錄最大值}printf("%lld\n",ans); //注意，答案有可能爆int}return 0; }

總結(jié)

以上是生活随笔為你收集整理的C. Longest Simple Cycle的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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