名为青春的悖论β
http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1003&cid=832
Problem Description
In the world line 1.048596%
在反覆上演的夢境中，兩年前的梓川咲太坐在通往沙灘的階梯，心不在焉地看著七里濱的海。
這也一定是夢，接下來的進展他早已知曉。翔子小姐就要來了。
“咲太小弟今天的心情也處于低潮呢。”，翔子踩著輕快腳步現身，坐在咲太身旁。
“翔子小姐今天也有點煩人呢。”
“即使每天來到海邊也沒有治愈荒廢的心嗎？我來告訴你擺脫無聊的方法。我從一個朋友那邊聽來的。”出乎意料的，翔子小姐站了起來。
“難道是數質數嗎？別開玩...”，梓川咲太的話沒說完，就被翔子小姐拉到海邊，然后一起撿貝殼。
捧滿貝殼的梓川咲太，又被拉著用腳在沙灘上踩出圓環的形狀。
然后翔子小姐又把貝殼隨意的放在圓環上。
做完這一切后，翔子小姐又拉著咲太小弟站到了防波堤上面。
“那么咲太小弟，你知道這些貝殼里面能形成多少個不重復的矩形嗎？”
“兩個矩形不相同當且僅當選取的四個貝殼的位置不同哦。”
咲太小弟不過是普通的初中生，也許這個問題只有翔子小姐才知道如何解答。
“不要覺得自己不會哦，這無關能力的事情。”翔子小姐溫柔的說。
“我的朋友這樣說過，許多失敗了的未來，無法挽回的過去，但是肯定在這之后，會有連接到......”
......
咲太任憑情感漩渦驅使而想要轉身，但是做不到。
夢醒了。
?
?
Input
多組輸入輸出
對于每組樣例，第一行一個正整數n（n<=300），代表圓環上有多少個貝殼。
接下來n行分別為這n個貝殼所分割的各個圓弧的長度s(1<=s<=15)。
輸入保證：
1：每組樣例給出的圓弧的長度按順時針的順序給出。
2：所有樣例輸入的n的和不超過500
?
?
Output
對于每組樣例，輸出一個整數，代表能形成不同矩形的個數
?
?
Sample Input
?8 1 2 2 3 1 1 3 3
?
?
Sample Output
?3
Hint
樣例的圖如下
?C++版本一
數一下直徑就行了
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUGusing namespace std; typedef long long ll; const int N=10000; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m; int a[N],b[N]; bool BS(int x){int l=0;int r=n;int mid;while(l<=r){mid=(l+r)>>1;if(b[mid]==x) return 1;else if(b[mid]<x) l=mid+1;else r=mid-1;}return 0; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifwhile(~scanf("%d",&n)){int sum=0;a[0]=0;b[0]=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum+=a[i];b[i]=sum;}int ans=0;if(sum%2){cout << ans << endl;continue;}int cnt=0;for(int i=1;i<=n;i++){if(BS((b[i]+sum/2)%sum))cnt++;}ans=cnt*(cnt-1)/2-cnt/2;cout << ans/4 << endl;}// cout << "Hello world!" << endl;return 0; }?
C++版本二
https://www.cnblogs.com/MingSD/p/10050324.html
如果是矩形的話，那么一定是在直徑上，然后找到一個直徑，然后就枚舉可能存在的矩形，如果存在矩形，則弧長相等。
#include<bits/stdc++.h> using namespace std; #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); #define LL long long #define ULL unsigned LL #define fi first #define se second #define pb push_back #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lch(x) tr[x].son[0] #define rch(x) tr[x].son[1] #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) typedef pair<int,int> pll; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const LL mod = (int)1e9+7; const int N = 305; int a[N]; int n; int L = 0; inline int cal(int x, int y){if(x > n) x -= n;if(y > n) y -= n;if(x > y) swap(x, y);return min(a[y]-a[x], a[x]+L-a[y]); } int main(){while(~scanf("%d", &n)){for(int i = 2; i <= n; ++i){scanf("%d", &a[i]);a[i] += a[i-1];}scanf("%d", &L);L += a[n];int ans = 0;if(L&1) {printf("0\n");continue;}for(int i = 1; i <= n; ++i){for(int j = i+1; j <= n; ++j){if(cal(i,j) != L/2) continue;for(int k = i+1; k < j; ++k){for(int z = j+1; z < i+n; ++z){int t1 = cal(i,k), t2 = cal(j,z);if(t1 == t2) ans++;else if(t1 < t2) break;}}}}cout << ans/2 << endl;}return 0; }?
總結
