2016-11-16试题解题报告
By shenben
11-15NOIP欢乐赛
|
题目名称 |
分火腿 |
无聊的会议 |
班服 |
|
时间限制 |
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。
无聊的会议
（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
班服
(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种。
T1代码：
#include<cstdio> #include<algorithm> #include<iostream> using namespace std; int n,m,T; #define name "hdogs" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); printf("%d ",m-__gcd(n,m)); } fclose(stdin); fclose(stdout); return 0; }
T2代码：
#include<cstdio> #include<cstring> #define ll long long #ifdef unix #define LL "%lld" #else #define LL "%I64d" #endif using namespace std; const int N=1e6+10; int T,n; char a[N]; ll calc(){ ll ans=0; ans=(ll)n*((n-1)/2); if(n%3==0) ans-=n/3*2; return ans; } ll del(){ ll ans=0; if(n&1){ int s0=0,s1=0; for(int i=0;i<n;i++){ if(a[i]=='0') s0++; else s1++; } ans=(ll)s0*s1*3; if(n%3==0){ s0=n/3*2; s1=n/3; for(int i=0;i<n;i++){ if(a[i]!=a[(i+s0)%n]) ans--; if(a[i]!=a[(i+s1)%n]) ans--; } } return ans/2; } else{ int s00=0,s01=0,s10=0,s11=0; for(int i=0;i<n;i+=2){ if(a[i]=='0') s00++; else s01++; } for(int i=1;i<n;i+=2){ if(a[i]=='0') s10++; else s11++; } ans=(ll)s00*s11*2+(ll)s01*s10*2+(ll)s00*s01*4+(ll)s10*s11*4; int n1=n/2; for(int i=0;i<n;i++){ if(a[i]!=a[(i+n1)%n]) ans--; } if(n%3==0){ int s0=n/3*2; int s1=n/3; for(int i=0;i<n;i++){ if(a[i]!=a[(i+s0)%n]) ans--; if(a[i]!=a[(i+s1)%n]) ans--; } } return ans/2; } } #define name "meeting" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); scanf("%d",&T); for(int i=1;i<=T;i++){ scanf("%s",a);n=strlen(a); printf("Case %d: ",i); printf(LL" ",calc()-del()); } fclose(stdin); fclose(stdout); return 0; } /*10分代码存档 #include<cstdio> #include<cstring> #include<algorithm> #include<set> using namespace std; struct node{ int x,y,z; node(int x=0,int y=0,int z=0):x(x),y(y),z(z){} bool operator <(const node &a)const{ if(x==a.x&&y==a.y)return z<a.z; if(x==a.x) return y<a.y; return x<a.x; } bool operator ==(const node &a)const{ return x==a.x&&y==a.y&&z==a.z; } }; set<node>ha; set<node>::iterator it; const int N=1e6+10; int cas,n,m,len; int ans,cnt,te[4]; char s[N]; #define name "meeting" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); scanf("%d",&cas); for(int i=1,len;i<=cas;i++){ scanf("%s",s+1); len=strlen(s+1); ha.clear(); if(len<3){printf("Case %d: %d ",i,0);continue;} s[++len]=s[1]; ans=0; for(int j=2;j<len;j++){ for(int L=j,R=j;L-1>=1&&R+1<=len;L--,R++){ if(s[L-1]==s[R+1]&&s[L-1]==s[j]){ te[0]=L-1;te[1]=j;te[2]=R+1==len?1:R+1; sort(te,te+3); cnt=unique(te,te+3)-te; if(cnt<3) continue; it=ha.find(node(te[0],te[1],te[2])); if(it==ha.end()){ ha.insert(node(te[0],te[1],te[2])); ans++; } } } } printf("Case %d: %d ",i,ans); s[len]=s[len-1]=0; } return 0; }*/
T3代码：
#include<cstdio> #include<cstring> using namespace std; const int N=11; const int M=110; const int mod=1000000007; int T,n,ans,a[N][M]; int f[M][M*10]; bool vis[M]; /*void dfs(int dep){ if(dep>n){ ans++; if(ans>=mod) ans-=mod; return ; } for(int i=1;i<=a[dep][0];i++){ if(!vis[a[dep][i]]){ vis[a[dep][i]]=1; dfs(dep+1); vis[a[dep][i]]=0; } } }*/ void dp(){ memset(f,0,sizeof f); f[0][0]=1; for(int i=1;i<=100;i++){ for(int j=0;j<(1<<n);j++){ f[i][j]=f[i-1][j]; } for(int j=1;j<=n;j++){ if(!a[j][i]) continue; for(int k=0;k<(1<<n);k++){ if(k&(1<<j-1)) continue; f[i][k+(1<<j-1)]=(f[i][k+(1<<j-1)]+f[i-1][k])%mod; } } } printf("%d ",f[100][(1<<n)-1]); } #define name "shirt" int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); scanf("%d",&T); while(T--){ //ans=0; memset(a,0,sizeof a); scanf("%d",&n);getchar(); for(int i=1,x;i<=n;i++){ do{ scanf("%d",&x); a[i][x]=1; }while(getchar()!=' '); } dp(); //dfs(1); //printf("%d ",ans); } return 0; }