2014-10-24 NOIP欢乐赛
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==)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\n",m-gcd(n,m));
}
}
100分 数学推理
无聊的会议
(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[]; ll calcu(){
ll ans=;
ans=(ll)n*((n-)/);
if(n%==)ans-=n/*;
return ans;
}
ll del(){
ll ans;
if(n%==){
int s1=,i,s0=;
for(i=;i<n;i++){
if(a[i]=='')s0++;
else s1++;
}
ans=(ll)s1*s0*;
if(n%==){
s1=n/;s0=n/*;
for(i=;i<n;i++){
if(a[i]!=a[(i+s1)%n])ans--;
if(a[i]!=a[(i+s0)%n])ans--;
}
}
return ans/;
}
else {
int i,s00=,s01=,s10=,s11=;
for(i=;i<n;i+=){
if(a[i]=='')s00++;
else s01++;
}
for(i=;i<n;i+=){
if(a[i]=='')s10++;
else s11++;
}
ans=(ll)s00*s11*;ans+=(ll)s01*s10*;
ans+=(ll)s00*s01*;ans+=(ll)s10*s11*;
int n1,n2;
n1=n/;
for(i=;i<n;i++)
if(a[i]!=a[(i+n1)%n])ans--;
if(n%==){
int s1=n/,s0=n/*;
for(i=;i<n;i++){
if(a[i]!=a[(i+s1)%n])ans--;
if(a[i]!=a[(i+s0)%n])ans--;
}
}
return ans/;
}
}
int main(){
freopen("meeting.in","r",stdin);
freopen("meeting.out","w",stdout);
scanf("%d",&T);
int Case=;
while(T--){
Case++;
scanf("%s",&a);
n=strlen(a);
printf("Case %d: %I64d\n",Case,calcu()-del());
}
return ;
}
100分
班服
(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[],a[][],f[][];
bool flag;
int qread(){
int i=;
char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch<=''&&ch>=''){i=i*+ch-'';ch=getchar();}
if(ch=='\n')flag=;
return i;
}
int main(){
freopen("shirt.in","r",stdin);
freopen("shirt.out","w",stdout);
scanf("%d",&T);
for(int i=;i<=;i++)bin[i]=<<i;
while(T--){
memset(a,,sizeof(a));
memset(f,,sizeof(f));
scanf("%d",&n);
for(int i=;i<=n;i++){
flag=;
while(){
int s=qread();
a[i][s]=;
if(flag==)break;
}
}
f[][]=;
int tot=(<<n)-;
for(int i=;i<=;i++){
for(int j=;j<=tot;j++){
f[i][j]=f[i-][j];
for(int k=;k<=n;k++)
if(a[k][i]&&(j&(<<k-)))
f[i][j]=(f[i][j]+f[i-][j^(<<k-)])%mod;
}
}
printf("%d\n",f[][tot]);
}
}
100分 状压dp
最新文章
- iOS适配 旧项目工程在iOS9下不能正常显示
- AutoMapper完成Dto与Model的转换
- class的继承,从基类开始
- 23.跳台阶问题[Fib]
- (四)802.1Q VLAN
- php上传文件时出现错误:failed to open stream: Permission denied
- JS中多个onload冲突解决办法
- angularjs 资源集合
- 小心DriveInfo类IsReady属性的较大延迟问题
- 20151225--easyUI
- CSDN个人空间能再烂吗?
- 点聚weboffice隐藏自带工具栏
- iview-admin安装
- 99%的Linux运维工程师必须要掌握的命令及运用
- 干货 | SSMS客户端连接京东云RDS SQL Server配置方法
- 【译】为什么BERT有3个嵌入层,它们都是如何实现的
- [UOJ86]mx的组合数——NTT+数位DP+原根与指标+卢卡斯定理
- JS的document.links函数使用示例
- 06-java学习-方法的学习
- 利用函数或映射进行数据转换 (map)
热门文章
- (转)Ubuntu10.04编译FFmpeg
- 【docker】开启remote api访问,并使用TLS加密
- 2016WWDC详解
- hihocoder #1052 : 基因工程(字符串处理 + 找规律 )
- macd背离的级别
- python根据圆的参数方程求圆上任意一点的坐标
- tensorflow knn 预测房价 注意有 Min-Max Scaling
- 前端多媒体(4)—— video标签全面分析
- Linux下安装二进制版mysql-8.0.15
- MySQL活动期间订单满600元并且在活动日期之前超过30天没有下过单_20161030