10-24NOIP欢乐赛
——By 潘智力
|
题目名称 |
分火腿 |
无聊的会议 |
班服 |
|
时间限制 |
1s |
1s |
1s |
|
内存限制 |
64MB |
128MB |
128MB |
|
输入文件 |
hdogs.in |
meeting.in |
shirt.in |
|
输出文件 |
hdogs.out |
meeting.out |
shirt.out |
|
测试点个数 |
10 |
10 |
10 |
测评环境：windows系统
水题，众神轻虐
分火腿
（hdogs.pas/.c/.cpp）
时间限制：1s；内存限制 64MB
题目描述：
小月言要过四岁生日了，她的妈妈为她准备了n根火腿，她想将这些火腿均分给m位小朋友，所以她可能需要切火腿。为了省事，小月言想切最少的刀数，使这n根火腿分成均等的m份。请问最少要切几刀？
输入描述：
第一行一个整数T，表示有T组数据。
接下来T组数据，每组共一行，有两个数字n，m。
输出描述：
每组数据一行，输出最少要切的刀数。
样例输入：
2
2 6
6 2
样例输出：
4
0
数据范围：
100%的数据保证T<=1000；n,m<=2147483647。
/* 题目相当于一根长为n的火腿肠，切成m段，如果从整数部分切开则不需要代价，否则代价1 n根火腿切m份，每一份长n/m，我们发现对于 n/m * K 为整数的情况，就不用刀子切 k共有n/lcm(n/m,1)-1=gcd(n,m)-1个，所以最终要切m-gcd(n,m)次 */ #include<iostream> #include<cstdio> using namespace std; int n,m,T; int gcd(int x,int y){ if(y==0)return x; return gcd(y,x%y); } int main(){ freopen("hdogs.in","r",stdin); freopen("hdogs.out","w",stdout); scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); printf("%d ",m-gcd(n,m)); } }
无聊的会议
（meeting.pas/.c/.cpp）
时间限制：1s；内存限制 128MB
题目描述：
土豪学长作为一名光荣的学生会干部，每天要参加很多无聊的会议。他发现：他开会的会议桌一定是正n边形，n个干部坐在这个多边形顶点上。因为太无聊了，所以他想要数出所有的“完全”等腰三角形——这种等腰三角形的三个顶点一定全是给出n多边形的顶点，且三个顶点上坐的干部性别相同。
土豪学长是土豪，他用1000000000%10的佣金雇用你，让你帮他数。PS：如果两个“完全”等腰三角形三个顶点相同，计算时只算一个。
输入描述：
第一行一个数字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
/* 法一：可以假设男性为黑点，女性为白点。枚举一个等腰三角形的顶点，再枚举一个底边点。这个三角形就确定下来了。求同色三角形的个数。n2做法。 法二：所有等腰三角形的个数-所有异色等腰三角形的个数=所有同色三角形的个数。 枚举顶点，然后在枚举任一与他颜色不同的底边点（即为多边形上所有与它颜色不同的点的个数O（1）），求出异色边的数量。这样子有一种三角形（顶点与两底边点一个为同色，一个为异色）数了一次，有一种三角形（顶点与两底边点均为异色）数了两次。可以使其都计算两次。 计算顶点与一底边点一个为同色，一个为异色的三角行的个数：枚举两个底端点，保证其颜色不一样。n为奇数时，任意两个点都能形成底边。n为偶数时，奇偶性相同的点能形成底边。异色边都计算了两次，除以2，就是底边异色的个数。即为三角形的个数。 */ #include<iostream> #include<cstdio> #include<cstring> using namespace std; #define ll long long int T,n; char a[1000005]; ll calcu(){ ll ans=0; ans=(ll)n*((n-1)/2); if(n%3==0)ans-=n/3*2; return ans; } ll del(){ ll ans; if(n%2==1){ int s1=0,i,s0=0; for(i=0;i<n;i++){ if(a[i]=='0')s0++; else s1++; } ans=(ll)s1*s0*3; if(n%3==0){ s1=n/3;s0=n/3*2; for(i=0;i<n;i++){ if(a[i]!=a[(i+s1)%n])ans--; if(a[i]!=a[(i+s0)%n])ans--; } } return ans/2; } else { int i,s00=0,s01=0,s10=0,s11=0; for(i=0;i<n;i+=2){ if(a[i]=='0')s00++; else s01++; } for(i=1;i<n;i+=2){ if(a[i]=='0')s10++; else s11++; } ans=(ll)s00*s11*2;ans+=(ll)s01*s10*2; ans+=(ll)s00*s01*4;ans+=(ll)s10*s11*4; int n1,n2; n1=n/2; for(i=0;i<n;i++) if(a[i]!=a[(i+n1)%n])ans--; if(n%3==0){ int s1=n/3,s0=n/3*2; for(i=0;i<n;i++){ if(a[i]!=a[(i+s1)%n])ans--; if(a[i]!=a[(i+s0)%n])ans--; } } return ans/2; } } int main(){ freopen("meeting.in","r",stdin); freopen("meeting.out","w",stdout); scanf("%d",&T); int Case=0; while(T--){ Case++; scanf("%s",&a); n=strlen(a); printf("Case %d: %I64d ",Case,calcu()-del()); } return 0; }
班服
(shirt.pas/.c/.cpp)
时间限制：1s；内存限制 128MB
题目描述：
要开运动会了，神犇学校的n个班级要选班服，班服共有100种样式，编号1~100。现在每个班都挑出了一些样式待选，每个班最多有100个待选的样式。要求每个班最终选定一种样式作为班服，且该班的样式不能与其他班级的相同，求所有可能方案的总数，由于方案总数可能很大，所以要求输出mod 1000000007后的答案。
输入描述：
共有T组数据。
对于每组数据，第一行为一个整数n，表示有n个班级。
2~n+1行，每行有最多100个数字，表示第i-1班待选班服的编号。
输出描述：
对于每组数据，输出方案总数 mod 1000000007后的答案。
样例输入：
2
3
5 100 1
2
5 100
2
3 5
8 100
样例输出：
4
4
数据范围：
对于30%的数据，1<=T<=3, 1<=n<=3，每班待选样式不超过10种。
对于50%的数据，1<=T<=5, 1<=n<=5，每班待选样式不超过50种。
对于100%的数据，1<=T<=10, 1<=n<=10，每班待选样式不超过100种。
/* 把班级状压一下 f[i][j]表示前i件衣服达到j状态的方案 那么显然f[i][j]+=f[i-1][j] 若班级k可以穿i这件衣服，则f[i][j]+=f[i-1][j-(1<<(k-1))] */ #include<iostream> #include<cstdio> #include<cstring> #define mod 1000000007 using namespace std; int T,n,bin[11],a[11][110],f[110][1025]; bool flag; int qread(){ int i=0; char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch<='9'&&ch>='0'){i=i*10+ch-'0';ch=getchar();} if(ch==' ')flag=1; return i; } int main(){ freopen("shirt.in","r",stdin); freopen("shirt.out","w",stdout); scanf("%d",&T); for(int i=0;i<=10;i++)bin[i]=1<<i; while(T--){ memset(a,0,sizeof(a)); memset(f,0,sizeof(f)); scanf("%d",&n); for(int i=1;i<=n;i++){ flag=0; while(1){ int s=qread(); a[i][s]=1; if(flag==1)break; } } f[0][0]=1; int tot=(1<<n)-1; for(int i=1;i<=100;i++){ for(int j=0;j<=tot;j++){ f[i][j]=f[i-1][j]; for(int k=1;k<=n;k++) if(a[k][i]&&(j&(1<<k-1))) f[i][j]=(f[i][j]+f[i-1][j^(1<<k-1)])%mod; } } printf("%d ",f[100][tot]); } }