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
     
      #include
      
       #include
       
        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\n",m-__gcd(n,m));    }    fclose(stdin);    fclose(stdout);    return 0;}
       
      
     

 

T2代码：

#include
     
      #include
      
       #define ll long long#ifdef unix#define LL "%lld"#else#define LL "%I64d"#endifusing 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
       
        #include
        
         #include
         
          #include
          
           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
           
            ha;set
            
             ::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\n",i,0);continue;} s[++len]=s[1]; ans=0; for(int j=2;j
             
              =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\n",i,ans); s[len]=s[len-1]=0; } return 0;}*/
             
            
           
          
         
        
       
      
     

　

T3代码：

#include
     
      #include
      
       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<