首页 > 代码库 > 9.7noip模拟试题
9.7noip模拟试题
题目名称 | 日历游戏 | 最大公约数 | 密码 |
英文代号 | calendar | gcd | pasuwado |
输入文件名 | calendar.in | gcd.in | pasuwado.in |
输出文件名 | calendar.out | gcd.out | pasuwado.out |
时限 | 1秒 | 1秒 | 1秒 |
空间限制 | 128M | 256M | 256M |
测试点数目 | 20 | 10 | 10 |
测试点分值 | 5 | 10 | 10 |
是否有部分分 | 无 | 无 | 无 |
附加文件 | 无 | 无 | 无 |
题目类型 | 传统 | 传统 | 传统 |
是否有SPJ | 无 | 无 | 无 |
注意：最终测试时，所有编译命令均不打开任何优化开关。
请独立完成题目，不要讨论，不得使用搜索引擎。
- 1. 日历游戏
【问题描述】
moreD和moreD的宠物CD正在玩一个日历游戏，开始时，他们从1900年1月1日到2012年12月22日（你懂的……）选一个日期开始，依次按照如下规则之一向后跳日期：
- 跳到日历上的下一天。
- 跳到日历上的下个月的同一天（如果不存在，则不能这么做）。
要是谁正好到达2012年12月22日那么他就赢了，如果到达这天之后的日期那他就输了——原因你也懂的。
每次都是moreD先走的。
现在，给你一个日期，请问moreD一定能赢吗？
【输入】
输入共T行，每行三个整数，Y、M、D，分别表示年、月、日。日期在1900年1月1日到2012年12月22日之间（包含两端）。
T并不在输入数据当中。
【输出】
要是moreD一定能赢，输出一行YES，否则输出NO。
【输入输出样例一】
calendar.in | calendar.out |
2012 12 20 | NO |
1956 3 26
【输入输出样例二】
calendar.in | calendar.out |
2012 12 21 | YES |
【数据描述】
对于50%的数据，是1949年1月1日后的日期。 T <= 5
对于100%的数据，是1900年1月1日后的日期。T <= 10
/*一看题目是博弈就懵了....其实可以转化成好理解的每个状态获胜的条件是后面的某一个状态不合法 而失败则是后面的每个状态都合法 然后搜一下就好了 */#include<iostream>#include<cstdio>#include<cstring>using namespace std;int n,f[2015][15][35];int M[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};int Judge(int x){ return x%400==0||(x%4==0&&x%100);}void Get1(int &a,int &b,int &c){ int sum=M[b]; if(b==2)sum+=Judge(a); if(c>sum){ c=1;b++; } if(b>12){ b=1;a++; }}void Get2(int &a,int &b,int &c){ if(b>12){ b=1;a++; } int sum=M[b]; if(b==2)sum+=Judge(a); if(c>sum){ a=2013;return; }}int Canot(int a,int b,int c){ if(a==2012&&b==12&&c>22)return 1; if(a>2012)return 1; return 0;}int Dfs(int a,int b,int c){ if(a==2012&&b==12&&c==22)return f[a][b][c]=0; if(f[a][b][c]!=-1)return f[a][b][c]; if(Canot(a,b,c))return f[a][b][c]=1; int x,y,z; x=a,y=b,z=c; z++;Get1(x,y,z); if(!Dfs(x,y,z))return f[a][b][c]=1; x=a,y=b,z=c; y++;Get2(x,y,z); if(!Dfs(x,y,z))return f[a][b][c]=1; return f[a][b][c]=0;}int main(){ freopen("calendar.in","r",stdin); freopen("calendar.out","w",stdout); int a,b,c; memset(f,-1,sizeof(f)); while(~scanf("%d%d%d",&a,&b,&c)){ if(Dfs(a,b,c))printf("YES\n"); else printf("NO\n"); } return 0;}
2.最大公约数
【问题描述】
话说CD比较欠扁，他表示在课室的日子没有教主在旁边打他的日子太寂寞了，所以这一晚，他终于来到了电脑室被打。由于CD是大家的宠物，于是大家都来打CD了。电脑室里有n个人，第i个人希望打CD ai下。但是太多人打CD，他又会不爽，于是他规定只能有K个人打到他，并且为了公平起见，最终K个人打他的次数都必须是相同的，CD规定这个次数就是这K个人希望打他的次数的最大公约数。为什么是最大公约数呢？因为他觉得被打的次数是GCD的话他才会变成Glad CD。之前说了，CD比较欠扁，于是CD希望，K个人打他的次数的和最大。你能告诉他他最后总共会被打多少下么？
【输入格式】
第一行两个正整数n，k。
第二行n个正整数，表示每个人希望打CD多少下。
【输出格式】
输出一个正整数表示CD会被打多少下。
【样例输入输出】
gcd.in | gcd.out |
3 1 1 2 3
| 3
|
【数据说明】
对于30%的数据，保证k≤n≤20。
对于50%的数据，保证输入中所有数小于5000。
对于100%的数据，保证输入中所有数小于500000，k≤n。
暴力30：
/*简单的做法没想到....暴力n*n*ndp */#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 5210using namespace std;int n,m,a[maxn],f[maxn][maxn],ans;int Gcd(int x,int y){ return !y?x:Gcd(y,x%y);}int main(){ freopen("gcd.in","r",stdin); freopen("gcd.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); for(int i=1;i<=n;i++) for(int j=1;j<=i;j++){ for(int k=j-1;k<i;k++) f[i][j]=max(f[i][j],Gcd(f[k][j-1],a[i])); if(j==m)ans=max(ans,f[i][j]); } printf("%d\n",ans*m); return 0;}
正解nlnn：
/*正解直接枚举答案然后扫一遍这个的倍数有几个 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 500010#define ll long longusing namespace std;int n,m,x,c[maxn],ans;int init(){ int x=0;char s=getchar(); while(s<‘0‘||s>‘9‘)s=getchar(); while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x;}int main(){ freopen("gcd.in","r",stdin); freopen("gcd.out","w",stdout); n=init();m=init(); for(int i=1;i<=n;i++){ x=init(); c[x]++; } for(int i=500000;i>=1;i--){ int s=0; for(int j=i;j<=500000;j+=i) s+=c[j]; if(s>=m){ ans=i;break; } } cout<<(ll)ans*m; return 0;}
3.密码
【问题描述】
哪里有压迫，哪里就有反抗。
moreD的宠物在法庭的帮助下终于反抗了。作为一只聪明的宠物，他打算把魔法使moreD的魔法书盗去，夺取moreD的魔法能力。但moreD怎么会让自己的魔法书轻易地被盗取？moreD在魔法书上设置了一个密码锁，密码锁上有一个问题。
施以斯卧铺魔法吧，你有M次机会，如此将得完美密码。
然后是一串小写字母串。
moreD的宠物斯卧铺魔法就是施法时的字符串其中相邻两位交换。
而moreD对于完美密码的定义自然是最小字典序了。
请帮助moreD的宠物，想出密码吧。
【输入格式】
第一行一个整数M，表示操作次数。
第二行一串小写字母组成的字符串S，如题目所示。
【输出格式】
输出完美密码。
【输入样例】
3
dcba
【输出样例】
adcb
【数据范围】
对于30%的数据|S|≤10
对于60%的数据|S|≤3,000
对于100%的数据8≤|S|≤100,000 M≤(|S|-8)^2+2
【后记】
宠物最终战胜了moreD,和自己的宠物快乐地生活着。
【样例解释】
先对第3，4两位施法，字符串变成dcab，然后对第2，3两位施法，字符串变成dacb，最后对第1，2两位施法，字符串变成adcb。
/*贪心 枚举每个位置最小的字母 如果步数还够 就过来不够的话就放过暴力的话n*n 用数据结构优化 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 100010#define ll long longusing namespace std;ll n,len,fir[210],nex[maxn],t[maxn];char s[maxn];void Add(ll pos,ll data){ while(pos<len){ t[pos]+=data; pos+=pos&(-pos); }}ll find(ll pos){ ll r=0; while(pos){ r+=t[pos]; pos-=pos&(-pos); } return r;}int main(){ freopen("pasuwado.in","r",stdin); freopen("pasuwado.out","w",stdout); scanf("%lld%s",&n,s+1); len=strlen(s+1); for(int i=1;i<=len;i++)Add(i,1); for(int i=len;i>=1;i--){ nex[i]=fir[s[i]-‘a‘+1]; fir[s[i]-‘a‘+1]=i; } for(int i=1;i<=len;i++){ for(int j=1;j<=26;j++){ ll pos=fir[j]; if(pos==0)continue; ll sum=find(pos-1); if(n>=sum){ n-=sum; Add(pos,-1); printf("%c",j+‘a‘-1); fir[j]=nex[pos]; break; } } } return 0;}
9.7noip模拟试题