|
目录
A XP的素数
B XP的点滴
C 今年暑假不AC
D 最优装载
E XP的小视频
F 最小生成树（Prim）
A XP的素数
题目描述
XP最近对素数很痴迷，特别是那些特殊的素数，其中有一类素数被称为孪生素数。其定义如下：如果一个数k是素数，k+2也是素数，那么k和k+2成为一对孪生素数。请计算一个给定区间m和n（0<m<n）中孪生素数对的个数。
输入
单组输入数据
m n
(0<m<n<1000)
输出
请输出一行结果:区间[m,n]中孪生素数对的个数
样例输入?Copy
1 999
样例输出?Copy
35
分析：这个题很简单，就是一个素数的判定ok，
看代码就懂了。
代码实现：c语言
#include <stdio.h>
#include <stdlib.h>
int main (){
int m;
int n;
while(~scanf("%d %d",&m,&n)){
????????int count=0;
????for(int i=m;i<=n;i++)
?????if(sushu(i)==1&&sushu(i+2)==1)
?????????count++;
??printf("%d",count);
??printf("\n");
}
return 0;
}
int sushu (int n){
????if(n==1) return 0;
for(int i=2;i<=sqrt(n);i++)
????if(n%i==0) return 0;
????return 1;
}
B XP的点滴
题目描述
XP一不留神感冒了，于是跑到校医院打点滴。打点滴真是无聊啊，他看到盐水一滴一滴地滴下来，突然想到一个问题：如果盐水有规律地滴下，先滴一滴，停一下；然后滴二滴，停一下；再滴三滴，停一下...，假设这瓶盐水一共有n毫升，每一滴是y毫升，每一滴需要的时间是一秒（假设最后一滴不到y毫升，需花费的时间也算一秒），停一下的时间也是一秒。请问XP多久能挂完这瓶盐水呢？
输入
单组输入数据?
n y (0<n,y<=1000)
输出
输出一行结果
样例输入?Copy
10 1
样例输出?Copy
13
分析：这个题就看你基本功了，就是一个凑凑的问题。
代码实现：c语言
#include <stdio.h>
#include <stdlib.h>
int main (){
int n;
int y;
while(~scanf("%d %d",&n,&y)){
int d=n/y;
int dy=n%y;
if(dy!=0) d++;
int z=solve(d);
printf("%d",z);
printf("\n");
}
return 0;
}
int solve (int d){
int sum=0;
int i=1;
while(sum<d)
{
????sum+=i;
????i++;
}
int count=d+i-2;
return count;
}
C 今年暑假不AC
题目描述
“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%...”
确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）
输入
输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。
输出
对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。
样例输入?Copy
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0
样例输出?Copy
5
分析：先按照节目的结束时间从小到大排序。
然后进行贪心算法，只要这个 节目的 开始时间大于上一个节目的结束时间就可以计数+1；
具体看代码分析：
代码实现：c语言
#include <stdio.h>
#include <stdlib.h>
struct jiemu {
int stime;
int ftime;
};
int cmp (const void *a,const void *b){
struct jiemu *c=(struct jiemu *)a;
struct jiemu *d=(struct jiemu *)b;
return c->ftime-d->ftime;
}
int main (){
int n;
while(~scanf("%d",&n)){
????????if(n==0) break;
????struct jiemu b[n];
????for(int i=0;i<n;i++)
????????scanf("%d %d",&b[i].stime,&b[i].ftime);
qsort(b,n,sizeof(b[0]),cmp);
int j=0;
int count=1;
for(int i=1;i<n;i++)
{
?????if(b[i].stime>=b[j].ftime)
????????{
????????count++;
????????j=i;
????????}
}
????printf("%d",count);
????printf("\n");
}
return 0;
}
D 最优装载
题目描述
使用贪心算法求解最优装载问题。
输入
每组输入包括两部分，?
第一行包括集装箱个数n，以及船的装载量C。?
接下来n行每行则输入集装箱编号以及其重量。
输出
输出包括两行，第一行为最多可装载的集装箱数量?。
第二行则为最优装载方案对应的所有集装箱编号（按照装载次序输出，用空格隔开）?。
样例输入?Copy
5 10
1 1
2 2
3 3
4 4
5 5
样例输出?Copy
4
1 2 3 4
分析：贪心算法，先将货物按照重量 从轻到重? 进行排序，然后一个一个装进去，直到装不了为止。
代码实现：c语言
#include <stdio.h>
#include <stdlib.h>
struct huowu{
int sno;
int w;
};
int cmp(const void *a,const void *b){
????struct huowu *c=(struct huowu *)a;
????struct huowu *d=(struct huowu *)b;
????return c->w-d->w;
}
int main (){
int n;
int c;
while(~scanf("%d %d",&n,&c)){
????struct huowu b[n];
????for(int i=0;i<n;i++)
????????scanf("%d %d",&b[i].sno,&b[i].w);
????qsort(b,n,sizeof(b[0]),cmp);
????int sum=0;
????int count=0;
????for(int i=0;i<n;i++)
????{
?????????sum+=b[i].w;
?????????count++;
?????????if(sum>c){
????????????count--;
????????????break;
?????????}
????}
????printf("%d",count);
????printf("\n");
????for(int i=0;i<count;i++)
????????printf("%d ",b[i].sno);
????printf("\n");
}
return 0;
}
E XP的小视频
题目描述
XP的表哥为他推荐了一些学习计算机编程的小视频，这些视频的播放时间长短不完全相同。现在给定一段时间，你能告诉XP他最多可以看多少个视频吗？每个视频的播放时间和给定的总时间均用分钟为单位。
输入
单组输入数据
第一行为m n
m为给定时间长度（分钟）(0<n,m<=1000)
n表示视频个数
接下来是n个整数代表每个视频的播放时间(每个视频播放时间为不超过1000的正整数)
输出
输出一个整数代表XP最多可以看的视频数。
样例输入?Copy
84 6
65 46 18 76 79 3
样例输出?Copy
3
分析：此题更加简单，就是将 视频时间排个序，然后累加即可，直到达到指定时间。
直接来代码吧
代码实现：c语言
#include <stdio.h>
#include <stdio.h>
int main (){
int n;
int m;
int a[2000];
while(~scanf("%d %d",&m,&n)){
????for(int i=0;i<n;i++)
????????scanf("%d",&a[i]);
????sort(a,0,n-1);
????int sum=0;
????int count=0;
????for(int i=0;i<n;i++)
????????{
????????????sum+=a[i];
????????????count++;
????????????if(sum>m)
????????????{
????????????????count--;
????????????????break;
????????????}
????????}
????????printf("%d",count);
????????printf("\n");
}
return 0;
}
int patition (int a[],int p,int q){
int j,i=p;
int x=a[p];
for(j=p+1;j<=q;j++)
{
????if(x>a[j]){
????????i++;
????????swap(a,i,j);
????}
}
swap(a,p,i);
return i;
}
void sort(int a[],int p,int q){
????if(p<q){
int i=patition(a,p,q);
sort(a,p,i-1);
sort(a,i+1,q);
????}
}
void swap(int a[],int i,int j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
F 最小生成树（Prim）
题目描述
使用Prim算法求图的最小生成树(MST)
输入
每组数据分为两个部分，第一部分为图的点数n，和边数m,
第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。
输出
最小生成树，输出时按照边的两个端点的升序输出。（先看左端点，再看右端点，端点不换位置）
样例输入?Copy
3 3
0 1 10
0 2 15
1 2 50
样例输出?Copy
0 1 10
0 2 15
分析：很显然，prim算法，是根据 ‘点’ 来的。时隔多年，有点忘记了，嘿嘿嘿。
分别用一个数组来记录 一个点是否加入 s点集。
? ? ? ? ?一个数组来记录一个不在s 的 点到邻近s点集 的最短距离。?（这个表示 最近邻接点的权值）
? ? ? ? 一个数组来记录一个不在s 的 点 在s点集? 的最近邻点。 （这个是表示 最近邻接点）
然后，我们就先让 0点 为 s点集 ，即此时 s点集中 只有? 0点。
然后我们就在不是 0 点里面 找一个 与 0点距离最近的点 ，分别 用数组记录。
找到点之后，我们就把这个邻接点 加入 s点集，并开始更新 与s点集 的 邻接点 及其权值。
分析到此为止，这个只靠我的分析 不是很清楚。
看我代码加注释吧，容易理解一点。但是要肯定的是，基本思路 已经在上面说明了，尽管你现在可能不懂。
代码实现：c语言
#include <stdio.h>
#include <stdlib.h>
struct shu{
int d1;
int d2;
int bian;
};
struct shu s[200];
struct M{
????int x;
????int y;
????int v;
};
struct M mp[200];
int cmp(const void *a,const void *b){
struct shu *c=(struct shu *)a;
struct shu *d=(struct shu *)b;
if(c->d1!=d->d1) return c->d1-d->d1;
return c->d2-d->d2;
}
int img[200][200];// 表示用 点和边 连起来的图。
int n,m;// n是点的数量，m是边的数量
int INF=10000;
int flag=0;
void init (){
for(int i=0;i<n;i++)
????for(int j=0;j<n;j++)
????img[i][j]=INF;
}// 初始化这个图，两点之间的距离都是无穷大.
void prim(){
int closeset[200];//记录该点的（不在s）最近邻接点（在s）
int lowcost[200];//记录该点 （不在s）到 最近邻接点（在s）的权值
int used[200];//记录该点是否加入s点集
for(int i=0;i<n;i++)
{
????closeset[i]=0;//刚开始，所有点的最近邻接点都是 第一个点（包括第一点）。
????lowcost[i]=img[0][i];//刚开始，所有点到最近邻接点的距离都是到第一点的距离（包括第一点）。
????used[i]=0;//刚开始，所有点都不在s中。
}
//开始。
used[0]=1;//把第一点加入 s中。
for(int i=1;i<n;i++)
{
????int j=0;
????for(int k=0;k<n;k++)
????????if((!used[k])&&(lowcost[k]<lowcost[j])) j=k; //找到 最近的一点也就是权值最小的点。
????s[flag].d1=closeset[j];//保存起来
????s[flag].d2=j;//保存起来
????s[flag].bian=lowcost[j];//保存起来
????flag++;
????used[j]=1;//找到该点后，就可以把它加入s点集 中。
????//开始更新
????for(int k=0;k<n;k++)
????{
????????if((!used[k])&&(img[k][j]<lowcost[k])){
????????????lowcost[k]=img[k][j];
????????????closeset[k]=j;
????????}
????}
}
}
int main (){
int d1;
int d2;
int bian;
??while(~scanf("%d %d",&n,&m)){
????????????init();
????????????for(int i=0;i<m;i++)
????????????{
????????????????scanf("%d %d %d",&d1,&d2,&bian);
????????????????img[d1][d2]=bian;
????????????????img[d2][d1]=bian;
??????????????????mp[i].x=d1;
??????????????????mp[i].y=d2;
??????????????????mp[i].v=bian;
????????????}
????????????prim();
????????????qsort(s,flag,sizeof(s[0]),cmp);
????????????
?????????????for(int k=0;k<flag;k++){
????????????????int temp=0;
????????????????for(int i=0;i<n;i++){
???????????????????????if( s[k].d1==mp[i].x&&s[k].d2==mp[i].y){
???????????????????????????temp=1;
???????????????????????????break;
??????????????????????????}
????????????????}
????????????????if(temp){
????????????????????printf("%d %d %d\n",s[k].d1,s[k].d2,s[k].bian);
????????????????}else{
??????????????????printf("%d %d %d\n",s[k].d2,s[k].d1,s[k].bian);
????????????????}
???????????}
?????????????????flag=0;
????????}
return 0;
}
|