正文
10.18 noip模拟试题
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
分火腿
（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。
/*数论题 似乎搞麻烦了 可以化简*/
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll T,n,m,lcm,gcd;
ll Gcd(ll x,ll y){
return y?Gcd(y,x%y):x;
}
ll Lcm(ll x,ll y){
return x/Gcd(x,y)*y;
}
int main()
{
freopen("hdogs.in","r",stdin);
freopen("hdogs.out","w",stdout);
cin>>T;
while(T--){
cin>>n>>m;
gcd=Gcd(n,m);
n/=gcd;m/=gcd;
lcm=Lcm(n,m);
ll x=(lcm-n)/n*gcd;
cout<<x<<endl;
}
return ;
}
无聊的会议
（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
/*
n*n*n暴力40 开始傻逼的写x==y==z....
正解比较神奇 看不懂....又没有注释
于是弃疗了QAQ
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 2000010
using namespace std;
int T,n,ans,sum,cas,x,y,z;
char s[maxn];
int main()
{
//freopen("meeting.in","r",stdin);
//freopen("meeting.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%s",s);
n=strlen(s);ans=;sum=
for(int i=;i<n;i++)
s[i+n]=s[i];
for(int i=;i<n;i++)
for(int j=i+;j<n+i;j++)
for(int k=j+;k<n+i;k++)
if(s[i]==s[j]&&s[j]==s[k]){
x=j-i;y=k-j;z=n*-k+i-n;
if(x==y&&y==z)sum++;
else if(x==y||y==z||x==z)ans++;
}
ans/=;
if(n%==)ans+=sum/;
printf("Case %d: %d\n",++cas,ans);
}
return ;
}
班服
(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种。
/*简单的状丫 考试没时间了 打了50的暴力*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 3010
#define mod 1000000007
using namespace std;
int T,n,c[][],f[][maxn],ans,x;
char s;
void Solve(){
f[][]=;//f[i][j]表示前i种服装 选不选的状态集合为j的方案数
for(int i=;i<=;i++)
for(int j=;j<(<<n);j++){
f[i][j]+=f[i-][j];
for(int k=;k<=c[i][];k++)
if(j&(<<c[i][k]-)){
f[i][j]+=f[i-][j-(<<c[i][k]-)];
if(f[i][j]>mod)f[i][j]%=mod;
}
}
}
int main()
{
freopen("shirt.in","r",stdin);
freopen("shirt.out","w",stdout);
scanf("%d",&T);
while(T--){
ans=;scanf("%d",&n);
memset(c,,sizeof(c));
memset(f,,sizeof(f));
for(int i=;i<=n;i++){
while(){
scanf("%d",&x);
c[x][++c[x][]]=i;
s=getchar();
if(s=='\n')break;
}
}
Solve();
printf("%d\n",f[][(<<n)-]);
}
return ;
}
conclusion
今天170
题目比较水 不是很高 而且 暴力分 没 的 全
QAQ
T1 数论啊 找找规律就水过了
T2 不会正解啊 想了好久也没想出来....
最后还是暴力
%的数据保证n<=
%的数据保证 n<=^
被数据坑了又
上次以为会有几个在这范围之间的
然后出了%40剩下都是最大的数据 还浪费了好久
这次长记性了 反正慢了 n*n*n和n*n区别不大
然而一个40 一个50
而且40的还打wa了 x==y==z.....
暴力wa了就很蛋疼了 又不能排...
T3 时间不多了 10分钟暴力...
正解简单状丫dp
应该能想出来的 可是吧
QAQ
总之还是能打快的就打快的 特别是数据范围不清楚的时候
还有就是 不要一个题卡太久 有时候说不定T3比T2好想
