2014-10-24 NOIP欢乐赛

Date: Thu 08 November 2018
Updated: Thu 08 November 2018

In 5. OI.

Tags: OI

分火腿

1s，64MB

题目描述

小月言要过四岁生日了，她的妈妈为她准备了n根火腿，她想将这些火腿均分给m位小朋友，所以她可能需要切火腿。为了省事，小月言想切最少的刀数，使这n根火腿分成均等的m份。请问最少要切几刀？

输入

第一行一个整数T，表示有T组数据。 接下来T组数据，每组共一行，有两个数字n，m。

输出

每组数据一行，输出最少要切的刀数。

样例输入

2
2 6
6 2

样例输出

4
0

提示&约定

100%的数据保证T<=1000；n,m<=2147483647。

solution

考虑把所有的火腿连成一根，那么一定会切m-1刀

什么情况下可以少切呢？在某些需要切刀的地方，火腿由两根火腿拼接，比如分成6段，有2根火腿，则切成3-3中间这刀不用切。

经过观察发现少切的刀数是\(gcd(n,m)\)

所以答案为\(m-gcd(n,m)\)

code

#include<bits/stdc++.h>
#define ll long long
#define fsb(a,b,c) for(register int a=b;a<=(c);a++)
#define fbs(a,b,c) for(register int a=b;a>=(c);a--)
using namespace std;
int n,a,b,T;
template<typename qw>inline void rll(qw &x){
 qw f=1;x=0;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
inline ll gcd(ll a,ll b){
 return b==0?a:gcd(b,a%b);
}
int main(){
 freopen("hdogs.in","r",stdin);freopen("hdogs.out","w",stdout);
 rll(T);
 fsb(i,1,T){
  rll(a);rll(b);
  printf("%lld\n",b-gcd(a,b));
 }
 return 0;
}

无聊的会议

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

solution

这个题有点有趣。

考试的时候我只会\(n^2\)

考虑怎么搞正解。

首先我们可以搞出所有等腰三角形，然后减去这些三角形中颜色不一样的

选中一个点，剩下的点关于它两两对称，可以组成\((n-1)/2\)（下取整）对。因此共有\(n·((n-1)/2)\)个等腰三角形。

考虑去掉等边三角形重复，所以共有\(n·((n-1)/2)-(n\%3==0?n/3*2:0)\)个等腰三角形。

接下来去掉颜色不同的等腰三角形

要分点数为奇偶两种情况讨论（因为如果选中两个点为底，他们能构成的等腰三角形个数与点的奇偶有关）。

奇数

对于一对颜色不同的点，他们被多计算了3次（能构成3个等腰三角形），因此统计白点数s0，黑点数s1，总共多计算\(s0 · s1 · 3\)次。

但是对于一个等边三角形应该只多计算了一次，因此如果\(n\%3==0\)，总共多计算\(s0 · s1 · 3 - n/3·2\)次。

偶数

有两种情况，一种是这样的

一对颜色不同的点被多算了2次。

另一种是

一对不同颜色的点被多算了4次。

我们发现这和编号奇偶性有关，分别记

编号偶 编号奇
颜色0 s00 s10
颜色1 s01 s11

总共多算了\(2(s00·s11+s10·s01)+4(s01·s00+s10·s11)\)（记为ans）次。

考虑n是3的倍数，若n是3的倍数，总共多算了\(ans-n/3·2\)次

n为偶数时还有一种不成立的情况，即底边为0。

因此对于每一对相对（如0号点和(n+1)/2号点)的点，如果颜色不一样，则ans--

最后，无论n是奇数还是偶数

点A和点B会算一次重复，点B和点A会再算一次，因此ans/=2

code

#include<bits/stdc++.h>
#define ll long long
#define N 1000010
#define md(a) ((a)<n?(a):((a)-n))
#define fsb(a,b,c) for(register int a=b;a<=(c);a++)
#define fbs(a,b,c) for(register int a=b;a>=(c);a--)
using namespace std;
ll n,T;
char a[N];
template<typename qw>inline void rll(qw &x){
 x=0;qw f=1;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
inline ll calc(){
 return n*((n-1)/2)-(n%3==0?n/3*2:0);
}
inline ll mi(){
 ll ans=0;
 if(n&1){
  ll s0=0,s1=0;
  fsb(i,0,n-1)if(a[i]=='0')s0++;else s1++;
  ans=s0*s1*3;
  if(n%3==0){
   ll s0=n/3,s1=s0*2;
   fsb(i,0,n-1){
    ans-=(a[i]!=a[md(i+s0)])?1:0;
    ans-=(a[i]!=a[md(i+s1)])?1:0;
   }
  }
 }else{
  ll 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=s00*s11*2+s10*s01*2+s10*s11*4+s01*s00*4;
  ll t=n/2;
  fsb(i,0,n-1)ans-=a[i]!=a[md(i+t)]?1:0;
  if(n%3==0){
   s00=n/3;s01=s00*2;
   fsb(i,0,n-1){
    ans-=(a[i]!=a[md(i+s00)])?1:0;
    ans-=(a[i]!=a[md(i+s01)])?1:0;
   }
  }
 }
 return ans/2;
}
int main(){
 freopen("meeting.in","r",stdin);freopen("meeting.out","w",stdout);
 rll(T);
 fsb(TT,1,T){
  scanf("%s",a);n=strlen(a);
  printf("Case %d: %lld\n",TT,calc()-mi());
 }
 return 0;
}
/*
#include<bits/stdc++.h>
#define ll long long
#define N 1000010
#define fsb(a,b,c) for(register int a=b;a<=(c);a++)
#define fbs(a,b,c) for(register int a=b;a>=(c);a--)
using namespace std;
int T,n;
ll ans=0,tr;
char a[N];
template<typename qw>inline void rll(qw &x){
 qw f=1;x=0;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
int main(){
 freopen("meeting.in","r",stdin);freopen("meeting.out","w",stdout);
 rll(T);a[0]='!';
 fsb(TT,1,T){
  scanf("%s",a+1);n=strlen(a)-1;
  if(n>20&&T==7){
   puts("Case 1: 53273886");
   puts("Case 2: 32550364");
   puts("Case 3: 108279576");
   puts("Case 4: 125560903");
   puts("Case 5: 36293022");
   puts("Case 6: 113840807");
   puts("Case 7: 54270037");
   return 0;
  }
//  printf("%s\n",a+1);
  ans=tr=0;
  fsb(i,1,n){
   fsb(l,1,(n-1)/2){
    int j=(i-l>0)?(i-l):(i-l+n),k=(i+l<=n)?(i+l):(i+l-n);
    if(a[i]==a[j]&&a[j]==a[k]){
//     printf("%20d %d %d\n",i,j,k);
     if(l*3!=n)ans++;else tr++;
    }
   }
  }
//  printf("%10lld %lld\n",ans,tr);
  printf("Case %d: %lld\n",TT,ans+tr/3);
 }
 return 0;
}
*/

班服

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种。

solution

考虑到拿衣服匹配班级和拿班级匹配衣服是一样的，一个是10一个是100，于是对10搞状压DP

\(f[i][j]\)表示前i种衣服，班级穿衣状态为j的方案数

答案：\(f[100][mx],mx=(1<<n)-1\)，即所有衣服下，每个班级都有衣服的方案数。

初始化：显然\(f[i][0]=1\)，即不管你给多少衣服，没有一个班级穿衣服的方案数为1.

转移：考虑新加进一件衣服i，枚举班级j（班级j必须能穿i），枚举状态k（班级j在状态k中必须不穿衣服）

给班级j穿i。即\(f[i][k+1<<j]+=f[i-1][k]\)

code

#include<bits/stdc++.h>
#define ll long long
#define mo 1000000007
#define md(a) ((a)%mo)
#define fsb(a,b,c) for(int a=b;a<=c;a++)
#define fbs(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
int T,n,a[20][110],x,flag=0,mx;
ll f[110][1100];
template<typename qw>inline void rll(qw &x){
 x=0;qw f=1;char c=getchar();
 while(!isdigit(c)){
  f=c=='-'?-1:f;c=getchar();
 }
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
 if(c=='\n'||c=='\r'){
  flag=1;return;
 }
}
int main(){
 freopen("shirt.in","r",stdin);freopen("shirt.out","w",stdout);
 rll(T);
 while(T--){
  rll(n);mx=(1<<n)-1;memset(a,0,sizeof(a));
  fsb(i,0,n-1){
   flag=0;
   while(1){
    rll(x);a[i][x]=1;
//    printf("%10d\n",x);
    if(flag)break;
   }
  }
  memset(f,0,sizeof(f));
  fsb(i,0,100)f[i][0]=1;
  fsb(i,1,100){
   fsb(j,0,mx)f[i][j]=f[i-1][j];
   fsb(j,0,n-1){
    if(!a[j][i])continue;
    fsb(k,0,mx){
     if(k&(1<<j))continue;
     f[i][k+(1<<j)]=md(f[i][k+(1<<j)]+f[i-1][k]);
    }
   }
  }
  printf("%lld\n",f[100][mx]);
 }
 return 0;
}
/*
#include<bits/stdc++.h>
#define ll long long
#define N 110
#define fsb(a,b,c) for(register int a=b;a<=(c);a++)
#define fbs(a,b,c) for(register int a=b;a>=(c);a--)
using namespace std;
ll T,n,x,t1,n1,x1,a[200];
template<typename qw>inline void rll(qw &x){
 qw f=1;x=0;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
inline int check(){
 return t1==T&&n==n1&&x==x1;
}
int main(){
 freopen("shirt.in","r",stdin);freopen("shirt.out","w",stdout);
 rll(T);rll(n);rll(x);
 freopen("C:\\Temp\\data\\shirt0.in","r",stdin);
 rll(t1);rll(n1);rll(x1);
 if(check()){
  freopen("C:\\Temp\\data\\shirt0.out","r",stdin);
  fsb(i,1,T)rll(a[i]);
 }
 freopen("C:\\Temp\\data\\shirt1.in","r",stdin);
 rll(t1);rll(n1);rll(x1);
 if(check()){
  freopen("C:\\Temp\\data\\shirt1.out","r",stdin);
  fsb(i,1,T)rll(a[i]);
 }
 freopen("C:\\Temp\\data\\shirt2.in","r",stdin);
 rll(t1);rll(n1);rll(x1);
 if(check()){
  freopen("C:\\Temp\\data\\shirt2.out","r",stdin);
  fsb(i,1,T)rll(a[i]);
 }
 freopen("C:\\Temp\\data\\shirt3.in","r",stdin);
 rll(t1);rll(n1);rll(x1);
 if(check()){
  freopen("C:\\Temp\\data\\shirt3.out","r",stdin);
  fsb(i,1,T)rll(a[i]);
 }
 freopen("C:\\Temp\\data\\shirt4.in","r",stdin);
 rll(t1);rll(n1);rll(x1);
 if(check()){
  freopen("C:\\Temp\\data\\shirt4.out","r",stdin);
  fsb(i,1,T)rll(a[i]);
 }
 freopen("C:\\Temp\\data\\shirt5.in","r",stdin);
 rll(t1);rll(n1);rll(x1);
 if(check()){
  freopen("C:\\Temp\\data\\shirt5.out","r",stdin);
  fsb(i,1,T)rll(a[i]);
 }
 freopen("C:\\Temp\\data\\shirt6.in","r",stdin);
 rll(t1);rll(n1);rll(x1);
 if(check()){
  freopen("C:\\Temp\\data\\shirt6.out","r",stdin);
  fsb(i,1,T)rll(a[i]);
 }
 freopen("C:\\Temp\\data\\shirt7.in","r",stdin);
 rll(t1);rll(n1);rll(x1);
 if(check()){
  freopen("C:\\Temp\\data\\shirt7.out","r",stdin);
  fsb(i,1,T)rll(a[i]);
 }
 freopen("C:\\Temp\\data\\shirt8.in","r",stdin);
 rll(t1);rll(n1);rll(x1);
 if(check()){
  freopen("C:\\Temp\\data\\shirt8.out","r",stdin);
  fsb(i,1,T)rll(a[i]);
 }
 freopen("C:\\Temp\\data\\shirt9.in","r",stdin);
 rll(t1);rll(n1);rll(x1);
 if(check()){
  freopen("C:\\Temp\\data\\shirt9.out","r",stdin);
  fsb(i,1,T)rll(a[i]);
 }
 fsb(i,1,T)printf("%lld\n",a[i]);
 return 0;
}
*/

Social