CF297E Mystic Carvings

2022-09-23 02:52:05 字數 1294 閱讀 7085

\(\rm update\ on\ 2020.02.11\):在cf的題庫中a了這道題,將標題和題目連結更改。

一個環上有標號為\(1\)到\(2n\)的頂點,每個頂點連線一條無向邊。要求選擇\(3\)條不重複的邊在頂點處建熊洞(共\(6\)個),且每條邊的兩個頂點的距離相同,詢問其方案數。

距離定義為在環上從一個頂點到另一個頂點所經過的最少熊洞數量-1。

\(3\)條弦在一個圓中的相交情況只有如下五種:

我們發現,滿足題目要求的只有2號和5號。而這兩種圖形的方案都不是很好計算,所以考慮計算出不滿足題目條件的圖形個數。

假設我們先求出了\(l[i],r[i]\)表示第\(i\)條弦的左右分別有多少條與它不相交的弦,那麼圖1的情況就有\(\sum^_l[i]\times r[i]\)種,而圖3和圖4都有共同點:3條弦中都有兩條弦滿足另外兩條線分別於它相交和相離,所以方案數就是\(\frac\).

那麼現在的問題就是如何求\(l[i],r[i]\),容易發現,一條弦在另一條弦的左/右邊,其實就是判斷這兩條線所連線的點的大小,分類討論+二維偏序即可。

時間複雜度\(o(n\log n)\)

#include #include #include using namespace std;

typedef long long ll;

const int n=300010;

int n,l[n],r[n];

ll ans1,ans2;

struct node

a[n];

struct bit

int ask(int x)

}bit;

bool cmp1(node x,node y)

int main()

sort(a+1,a+1+n,cmp1);

for (int i=1;i<=n;i++)

memset(bit.c,0,sizeof(bit.c));

for (int i=n;i>=1;i--)

memset(bit.c,0,sizeof(bit.c));

sort(a+1,a+1+n,cmp2);

for (int i=1;i<=n;i++)

ans1=1ll*n*(n-1)*(n-2)/6;

for (int i=1;i<=n;i++)

printf("%i64d",ans1-ans2/2);

return 0;

}