无聊的会议

无聊的会议（更新正解）

（meeting.pas/.c/.cpp）

时间限制：1s；空间限制 128MB

题目描述：

土豪学长作为一名光荣的学生会干部，每天要参加很多无聊的会议。他发现：他开会的会议桌一定是正n边形，n个干部坐在这个多边形顶点上。因为太无聊了，所以他想要数出所有的“完全”等腰三角形——这种等腰三角形的三个顶点一定全是给出n多边形的顶点，且三个顶点上坐的干部性别相同。

土豪学长是土豪，他用1000000000%10的佣金雇用你，让你帮他数。

输入描述：

第一行一个数字T，表示有T组数据。

接下来有T组数据，每组数据共一行。这一行给出一个长度为n的字符串，表示正n边形n个顶点上干部的性别。1为男，0为女。

输出描述：

对于第i组数据：输出”Case i: ans”(不带引号)，ans为“完全”等腰三角形的数量。

样例输入：

0001

10001

1101010

111010

样例输出：

Case 1: 1

Case 2: 0

Case 3: 1

Case 4: 3

Case 5: 2

数据范围：

40%的数据保证n<=20

100%的数据保证 n<=10^6

所有数据保证T<=10

【题目分析】

注意土豪学长非常的土豪，他会支付给你1000000000%10这么多工资！

暴力枚举三个点，然后计算三条边，注意三条边不是长度，而是节点差，因为在正多边形中节点差一样距离就一样，注意理解z的求值，把正多边形拆成一条链，因为没有判重，所以计算结果的时候/3

　　正解当我们枚举了顶点和底边点，就可以确定这个等腰三角形，这样复杂度就下降到了n^2，只需要枚举两个点。

　　　　要求所有同性等腰三角形的个数=所有等腰-异性等腰

　　　　只要满足顶端点和底边点不同，一定为异性，枚举顶端点，比较底边点，只要两个点不一样那么这条边所在的三角形也不一样，但是这样出现一个问题，有的三角形数了2次，有的数了1次。这样底端点不一样的三角形少算了一次，只要在加上一次，就变成都计算两次。不是两个异色点都能作为一个底边，能够作为底边的条件是两个点链接分割圆变成两个弧，其中至少有一个弧上有奇数个点，

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=2000010;
int T,n,ans,sum,cas,x,y,z;
char s[maxn];
int main()
{
    freopen("meeting.in","r",stdin);
    freopen("meeting.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s);
        n=strlen(s);ans=0;sum=0;
        for(int i=0;i<n;i++)
            s[i+n]=s[i];
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n+i;j++)
                for(int k=j+1;k<n+i;k++)
                    if(s[i]==s[j]&&s[j]==s[k]){
                    x=j-i;y=k-j;z=n*2-k+i-n;
                    if(x==y&&y==z)sum++;
                    else if(x==y||y==z||x==z)ans++;
                }
        ans/=3;
        if(n%3==0)ans+=sum/3;
        printf("Case %d: %d
",++cas,ans);
    }
    return 0;
}