周报"/>
这学期的可能是倒数第二篇周报
写在前面
这周学啥新的了嘛？没有。那这周干什么了？完成任务+复习。 真是时间不等人，转眼又到了学期末，但求期末不挂吧。为了给我下周留点时间，我拖拖拉拉的终于完成了会长布置的任务，但是第三章的题这么没有题单，所以就做了第四章的题。
周报的主要内容
only洛谷算法题解析
正文
P1093 【奖学金】（表示我想要）
这道题我是想不明白的，为何会是一个普及题目，这比有的入门题目还简单，不久是个结构体排序么
先定义一个结构体
struct date{int chinese;int math;int english;int sum;int num;
};
这是我第一次定义的，写道程序中心的时候我突然发现数学和英语这两个数据完全没有任何用在结构体里面，定义到主函数就行了
typedef struct Grade{int number;int yu;int sum;
}grade;
这就是第二版；
主程序特别简单就是一个排序，然后输出结构体数组的前五项就行了
#include <stdio.h>
typedef struct Grade{int number;int yu;int sum;
}grade;
int main()
{grade student[301],temp;int num,i,shu,ying,j;scanf("%d",&num);for(i=1;i<=num;i++){scanf("%d%d%d",&student[i].yu,&shu,&ying);student[i].sum=student[i].yu+shu+ying;student[i].number=i;}for(i=1;i<num;i++){for(j=1;j<=num-i;j++){if(student[j].sum<student[j+1].sum){temp=student[j];student[j]=student[j+1];student[j+1]=temp;}if(student[j].sum==student[j+1].sum){if(student[j].yu<student[j+1].yu){temp=student[j];student[j]=student[j+1];student[j+1]=temp;}}}}for(i=1;i<=5;i++){printf("%d %d\n",student[i].number,student[i].sum);}return 0;
}
P1718【宇宙总统】
很疑惑为啥排序提单里面的普及题这么水，与后面的暴力枚举和搜索里面的普及题格格不入，而且这个题完全用可以不用排序，就是不知道其他的语言里面有没有strcmp这么一个函数了，要是没有可以自己写嘛（手动滑稽）
将每一个字符串比较谁大就把谁留下，然后再输出最大的那个字符串和号数就行
但是这里用字符串判断数字大小并不是谁比谁大就行，因为strcmp比的是每个字符的ascill码比如9>10000,就是因为他比第一位的时候9比一大他就想当然了
if((strcmp(s2,s)>0&&strlen(s2)>=strlen(s))||strlen(s2)>strlen(s))
判断条件这样写就可以过了
#include <stdio.h>
#include <string.h>
//typedef struct P{
// int num;
// char s[200];
//}p;
int main()
{//p piao[30];int i,j,num,people=1;char s[200],s2[200];scanf("%d",&num);scanf("%s",s);for(i=2;i<=num;i++){scanf("%s",s2);if((strcmp(s2,s)>0&&strlen(s2)>=strlen(s))||strlen(s2)>strlen(s)){strcpy(s,s2);people=i;}}printf("%d\n%s",people,s);return 0;
}
接下来说两道暴力枚举的题
这些题都过于暴力，，，，完全就是扭曲人性
P2098【烤鸡】
其实吧这道题用dfs也可以做，但是我把代码搞丢了。。。。也是很懵逼
枚举的话直接枚举各种类型，因为只有十种调料，所以套十层循环就行了，最牛的的是这题枚举的话要先输出方法总个数然后才能输出方法，不然枚举也不需要这么长了
#include "stdio.h"
int main()
{ int a,b,c,d,e,f,g,h,i,j,num,sum=0; scanf("%d",&num); for (a=1;a<=3;a++) { for (b=1;b<=3;b++) { for (c=1;c<=3;c++) { for (d=1;d<=3;d++) { for (e=1;e<=3;e++) { for (f=1;f<=3;f++) { for (g=1;g<=3;g++) { for(h=1;h<=3;h++) { for (i=1;i<=3;i++) { for (j=1;j<=3;j++) { if (a+b+c+d+e+f+g+h+i+j==num) { sum++; } } } } } } } } } } } printf("%d\n",sum); for (a=1;a<=3;a++) { for (b=1;b<=3;b++) { for (c=1;c<=3;c++) { for (d=1;d<=3;d++) { for (e=1;e<=3;e++) { for (f=1;f<=3;f++) { for (g=1;g<=3;g++) { for(h=1;h<=3;h++) { for (i=1;i<=3;i++) { for (j=1;j<=3;j++) { if (a+b+c+d+e+f+g+h+i+j==num) { printf("%d %d %d %d %d ",a,b,c,d,e);printf("%d %d %d %d %d\n",f,g,h,i,j); } } } } } } } } } } }
}
P1036【选数】这道搜索题为什么会放在枚举题单里面我很是困惑。
按照题目要求先写一个判断素数的函数
int priem(int n)
{int i;for(i=2;i<=sqrt(n);i++){if(n%i==0){return 0;}}return 1;
}
这个很随意就能写出来
然后dfs经典格式
//判断边界条件
。。。。
//枚举所有可能
这里的边界条件就是有多少个数，每种可能就是把任意数字加起来
#include <stdio.h>
#include <math.h>
int arr[30],book[30],flag[30],k,n,cnt=0,l=0;
int priem(int n)
{int i;for(i=2;i<=sqrt(n);i++){if(n%i==0){return 0;}}return 1;
}
void dfs(int step,int start)
{int i,sum=0;//判断边界条件 if(step==k){for(i=0;i<k;i++){sum+=book[i];}if(priem(sum)){cnt++;}return;}//尝试所有可能for(i=start;i<n;i++){if(flag[i]==0){flag[i]=1;book[step]=arr[i];dfs(step+1,i+1);flag[i]=0;}} return;
}
int main()
{int i;scanf("%d%d",&n,&k);for(i=0;i<n;i++){scanf("%d",&arr[i]);}dfs(0,0);printf("%d",cnt);return 0;
}
P2404【自然数的拆分】
这道题可真的是苦了我了，
这道题我在尝试每种可能的点子上真的受到了挫折，确实我把每种可能都尝试了，但是呢？1+1+2和1+2+1有什么区别？这就是写的算法的问题
//尝试所有可能for(i=start;i<num;i++){if(sum+i<=num){book[n]=i;dfs(sum+i,n+1,i);}elsebreak;}
改了之后只需要在dfs函数里面多加一个strat变量，让尝试的开始从start开始而不是1就行了，格式一模一样，模板一模一样，生搬硬套，是个学了两天搜索的都可以过。
#include <stdio.h>
int num,book[10];
void dfs(int sum,int n,int start)
{int i,temp,a[10];//判断边界条件if(sum==num){for(i=0;i<n;i++){if(i==0){printf("%d",book[i]);}else{printf("+%d",book[i]);}} printf("\n");return;}//尝试所有可能for(i=start;i<num;i++){if(sum+i<=num){book[n]=i;dfs(sum+i,n+1,i);}elsebreak;}return;
}
int main()
{scanf("%d",&num);dfs(0,0,1);return 0;
}
写在最后
其实还有几道题可以写的，但是我要是这周都写完了，下周发啥？下周也没有时间做题了，要求不高一天一道就行。那剩下的题就下周发吧。
更多推荐
这学期的可能是倒数第二篇周报
发布评论