首页 > 代码库 > 无聊的会议
无聊的会议
无聊的会议
（meeting.pas/.c/.cpp）
时间限制：1s；空间限制 128MB
题目描述：
土豪学长作为一名光荣的学生会干部，每天要参加很多无聊的会议。他发现：他开会的会议桌一定是正n边形，n个干部坐在这个多边形顶点上。因为太无聊了，所以他想要数出所有的“完全”等腰三角形——这种等腰三角形的三个顶点一定全是给出n多边形的顶点，且三个顶点上坐的干部性别相同。
土豪学长是土豪，他用1000000000%10的佣金雇用你，让你帮他数。
输入描述：
第一行一个数字T，表示有T组数据。
接下来有T组数据，每组数据共一行。这一行给出一个长度为n的字符串，表示正n边形n个顶点上干部的性别。1为男，0为女。
输出描述：
对于第i组数据：输出”Case i: ans”(不带引号)，ans为“完全”等腰三角形的数量。
样例输入：
5
0001
01
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
#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\n",++cas,ans); } return 0;}
无聊的会议
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。