Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1767 Solved: 1395
[Submit][Status][Discuss]
Description
给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。
Input
第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度
Output
所构成不重复矩形的个数
Sample Input
8
1
2
2
3
1
1
3
3
1
2
2
3
1
1
3
3
Sample Output
3
HINT
N<= 20
Source
矩阵的对角线一定是两条直径，所以求出直径条数cnt，ans=C(cnt,2)
哈哈哈哈，数组开小就RE啦
1 #include <cstdlib> 2 #include <cstdio> 3 4 inline void read(int &x) 5 { 6 x=0; register char ch=getchar(); 7 for(; ch>'9'||ch<'0'; ) ch=getchar(); 8 for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0'; 9 } 10 const int N(110); 11 int n,len,cnt,pos[N],ii[N],vis[N*1000]; 12 13 int Presist() 14 { 15 // freopen("A.in","r",stdin); 16 // freopen("A.out","w",stdout); 17 18 read(n); pos[1]=0; vis[0]=1; 19 for(int i=1; i<=n; ++i) 20 { 21 read(ii[i]),len+=ii[i]; 22 pos[i+1]=pos[i]+ii[i]; 23 vis[pos[i+1]]=i+1; 24 } len>>=1; 25 for(int i=1; i<=n&&pos[i]<=len; ++i) 26 if(vis[pos[i]+len]<=n&&vis[pos[i]+len]) ++cnt; 27 printf("%d",cnt*(cnt-1)/2); 28 return 0; 29 } 30 31 int Aptal=Presist(); 32 int main(){;}