最近要去PKU夏令营，所以将过去写过的机试题目的坑点总结在这里，以便查阅，复习。也希望能有所帮助，有所提高。
一、闰年问题
虽然闰年我们都知道，但是放到题目中还真不一定能快速准确的写出来。
一般来说，闰年的判别方法如下：
普通年:能被4整除但不能被100整除的年份为普通闰年，世纪年:能被400整除的为世纪闰年
(Year % 100 != 0 && Year % 4 ==0 )|| Year % 400 ==0
1，这类问题基本上复杂一些的就是要给定两个日期然后进行求解两个日期的差值。
解决这类问题我们使用如下方法：
可以进行预处理来解决，我定义三维数组分别表示年、月、日。并使用结构体定义方法。并在方法中判断月与年的进位。
image
image
image
之后用相减的方式进行计算即可。
image
2，之后还有星期问题
解决星期问题，我们可以同上问题。
image
我们得到两者之间的差，经过days加和后输出(days%7+7)%7。这里防止其有余数。
二、查找问题
对于查找问题，我们这里使用二分查找来解决。
当我们查找的对象为一个数组的时候，我们可以定义top=n-1，base=0
image.png
这里当top>=base的时候，我们就进入循环，定义mid为(top+base)/2的值，然后与目标值进行比对。当目标值小于mid值，我们从当前数组的左边开始寻找，既top=mid-1，否则从右边开始寻找。
三、贪心的活动安排问题
此问题比较简单，既将活动按照结束时间从小到大排序，然后依次取符合条件的活动。
内容比较简单，所以这里就不详细的写出来了。
四、数据结构题目--括号匹配问题
由于数据结构类型的题目熟练度不够，所以在这里我把括号匹配相应的内容写的清楚一些，方便之后进行查看。
题目的大致思想如下：定义str字符数组用来存储输入的字符串，定义ans字符数组用来保存最终结果。定义堆栈S用来匹配字符。具体的写法如下：
//
// Created by 陈平 on 2018/4/20.
//括号匹配
#include <stdio.h>
#include<iostream>
#include <stack>
using namespace std;
stack<int> S;
char str[110];
char ans[110];
int main(){
while (scanf("%s",str)!=EOF){
for (int i = 0; str[i]!=0; ++i) {
if (str[i]=='('){
S.push(i);
ans[i]=' ';
}
else if(str[i]==')'){
if(!S.empty()){
S.pop();
ans[i]=' ';
}
else{
ans[i]='?';
}
}
else ans[i]=' ';//当前字符为非括号时，保存空值
}
while (!S.empty()){
ans[S.top()]='$';
S.pop();
}
cout<<ans<<endl;
}
return 0;
}
在堆栈问题中，我们要注意下面几个语法格式：定义堆栈使用stack<int> S;不过记得加#include头。之后是S.top()、S.pop()、S.empty()。
四、哈弗曼树的题目
哈弗曼树属于理解起来比较简单的题目，做法比较有技巧性。这个题目要用到堆栈的使用方法。首先我们要定义一个小顶堆（每次取出来的值都是最小的）。
priority_queue<int, vector<int>, greater<int>> Q; //定义小顶堆
之后将输入的数据push进堆栈Q中。
之后统计Q.size()的数量，因为是提出两个数据，生成一个数据push进去。
//
// Created by 陈平 on 2018/7/11.
//
#include "iostream"
#include "stdio.h"
#include "queue"
using namespace std;
int main(){
priority_queue<int, vector<int>, greater<int>> Q; //定义小顶堆
//priority_queue<int> Q; //定义大顶堆
int n;
cin>>n;
//int num[1000];
while (!Q.empty()){
Q.pop();
}
int cut;
for (int i = 1; i <=n ; ++i) {
cin>>cut;
Q.push(cut);
}
int c;
int ans=0;
while (Q.size()>1){
int a,b;
a = Q.top();
Q.pop();
b = Q.top();
Q.pop();
c = a+b;
ans+=c;
Q.push(c);
}
cout<<ans<<endl;
}
五、数位拆解
数位拆解的问题要处理格式要注意一些。
将各个位保存到数组中。
while(a!=0){
buf[size++] = a%10;
a/=10;
}
之后将a的位数从大到小存进来。
六、进制转换
此类题目我们联系一道题目。我们熟练掌握将任意进制转换为任意进制即可。
题目大致如下：输入 15 Aab3 7表示将Aab3（15进制）转换为7进制的数。输出转换结果（此题结果为 210306）。
此类题目的思想如下：将n进制转换为10进制，然后由十进制转换为b进制。
下面我们说一下要注意的地方
//
// Created by 陈平 on 2018/7/14.
//
#include "iostream"
#include "string.h"
using namespace std;
int main(){
int m,n;
char a[40];
cin>>m>>a>>n;
int length = strlen(a);
int ans = 0;
int t = 1;
for (int i = length-1; i >=0 ; i--) {
int x;
if(a[i]>='0' && a[i]<='9') x = a[i] - '0';
if(a[i]>='A' && a[i]<='Z') x = a[i] - 'A' +10;
if(a[i]>='a' && a[i]<= 'z') x=a[i] -'a' + 10;
ans+=t*x;
t*=m;
}
//上述内容为将m进制的数转换为10进制
char fin[40];//用于保存转换进制后的结果
int save_flag = 0;
do{
int y = ans%n;
fin[save_flag++] = (y<10) ? y + '0' : y-10+'A';//注意这里是用char来保存的数字，所以注意ascii码
ans/=n;
}while (ans);
for (int j = save_flag-1; j >=0 ; j--) {
cout<<fin[j];
}
}
这里首先要注意我们转换为10进制的时候，由于使用的是char数组来存储的内容，所以提取各个位的时候我们要分下面三种情况：
if(a[i]>='0' && a[i]<='9') x = a[i] - '0';
if(a[i]>='A' && a[i]<='Z') x = a[i] - 'A' +10;
if(a[i]>='a' && a[i]<= 'z') x=a[i] -'a' + 10;
注意当我们这里若为字母的时候，我们要将每一位减去A或者a，然后要+10
之后用ans+=t*x; t*=m;ans用于存结果，而t是每一位的权值。
之后得到的ans就为10进制的数字了。
然后我们处理n进制转换问题。这里我们使用fin数组保存结果。这里我们要注意使用do while（为了防止给0的测试样例）这里我们要注意保存数组的时候要讲int类型的数字+'字符头'，这里要熟练使用int y = ans % n; ans /= n;而以这种方式存储的内容是由地位到高位的，所以我们要反过来输出。
七、最大公约数与最小公倍数
这个题目直接上代码。
#include "iostream"
using namespace std;
int gcd(int a,int b){
if(b==0) return a;
else return gcd(b, a%b);
}
int main(){
int a,b;
cin >> a>>b;
cout<<gcd(a,b);
}
下面是最小公倍数的求法。
#include "iostream"
using namespace std;
int gcd(int a,int b){
if(b==0) return a;
else return gcd(b, a%b);
}
int main(){
int n;
cin>>n;
int num[100];
for (int i = 0; i <n ; ++i) {
cin>>num[i];
}
int f1 = num[0];
int fin;
for (int j = 1; j <n ; ++j) {
int mul = f1*num[j];
fin = mul/gcd(f1,num[j]);
f1 = fin;
}
cout<<fin;
}
由于我们要求多组数的最小公倍数，所以我们用循环进行顺序多次求解。
八、素数问题（Prime）
这里使用math.h库来使用sqrt求解。
代码如下：
#include "iostream"
#include "math.h"
using namespace std;
int judge(int x){
if(x <= 1) return 0;//1不是素数，所以小于等于1都false
int bound = sqrt(x)+1;
for (int i = 2; i <bound ; ++i) {
if(x % i == 0) return 0;
}
return 1;
}
int main(){
int n;
cin>>n;
cout<<judge(n);
}
这里注意x若直接小于等于1，直接false，之后从2开始判断。
九、分解素因数
这种题目也是十分常见的类型，所以这里稍微写一下思路。
这里我们要获取某个范围内的所有素数。而我们不能使用上面的方法进行筛选，因为这样会导致我们的数据量过大。
#include "iostream"
#include "math.h"
using namespace std;
bool mark[100001];
int prime[100001];
int primeSize = 0;
int init(){
for (int i = 2; i <100001 ; ++i) {
if(mark[i]) continue;
prime[primeSize++] = i;
if(i>1000) continue;
for (int j = i*i; j <=100000 ; j+=i) {
mark[j] = true;
}
}
return 1;
}
int main(){
init();
for (int i = 0; i <10000 ; ++i) {
cout<<prime[i]<<" ";
}
}
这里要注意一些问题：if(mark[i]) continue;，这里标记为true为不是素数的意思。这里求解素数的方法是从2开始，找2的倍数然后标记为否。其余的就是素数。这里要注意 if(i>1000) continue;这句话要加上，不然会因为数太大而报错。之后我们要注意里面的循环for (int j = i*i; j <=100000 ; j+=i) {mark[j] = true; }这个从i*i开始，因为之前的内容已经由前面的数处理了，而且每次
j=j+i。得到这些素数之后的内容就容易求了。
下面我们求解因数分解的问题。
- 整数分解要求我们先求解1~100000的素数
- 之后我们要遍历这所有的素数，通过%求解判断是否==0
- 然后我们针对这个素数进行while循环，直到最后
具体代码如下：
#include "iostream"
#include "math.h"
using namespace std;
bool mark[100001];
int prime[100001];
int primeSize = 0;
int init(){
for (int i = 2; i <100001 ; ++i) {
if(mark[i]) continue;
prime[primeSize++] = i;
if(i>1000) continue;
for (int j = i*i; j <=100000 ; j+=i) {
mark[j] = true;
}
}
return 1;
}
int main(){
init();
int n;
cin>>n;
int ansPrime[40];//存因数的具体值
int ansSize=0;
int ansNum[40];//存因数出现的次数
for (int i = 0; i <primeSize ; ++i) {
if(n%prime[i] == 0) {
ansPrime[ansSize] = prime[i];
ansNum[ansSize] = 0;
while (n%prime[i]==0){
ansNum[ansSize]++;
n/=prime[i];
}
ansSize++;
if(n==1) break;
}
}
if(n!=1) {
ansPrime[ansSize] = n;
ansNum[ansSize++] = 1;
}
int ans = 0;
for (int j = 0; j <ansSize ; ++j) {
ans+=ansNum[j];
}
cout<<ans<<endl;
}
里面使用int ansPrime[40];//存因数的具体值 int ansSize=0; int ansNum[40];//存因数出现的次数
由init求出素数，之后进入循环，由if(n%prime[i] == 0)判断是否是因子，如果是则根据当前坐标存储值，之后算其因子的次数。使用while (n%prime[i]==0){ ansNum[ansSize]++; n/=prime[i]; }来保存出现的次数。并在最后ansSize++。
这里我们要注意当n==1的时候跳出循环，否则浪费时间。
在程序结束前，我们要记得if(n!=1) { ansPrime[ansSize] = n; ansNum[ansSize++] = 1; }当n！=1意味着剩余的n无法分解， 此时手动保存n。
十、快速幂
快速幂简单表示就是 a^b(mod n)。但是当其内容过大的时候，就爆掉了。。。
所以我们每一步都要进行取余数操作。
下面看代码：
#include "iostream"
using namespace std;
int main(){
int a,b,n;
cin>>a>>b>>n;
int ans = 1;
while (b!=0){
if(b%2==1){
ans = ans * a ;
ans = ans % n ;
}
a = a * a ;
b /= 2;
a = a % n;
}
cout<<ans;
}
- 这里首先定义ans用于保存最终结果
- 之后我们循环对b进行处理，当b%2==1，说明当前位为1.此时我们可以将ans*a。并且每一步都要对n进行取余。
- 在最后我们要注意，我们无论当前位数是1还是0，我们都要对a = a*a更新。然后对b取高一位。
高精度加法、乘法
这里放上加法与乘法的实现方法。加法简单一些，乘法难度较大。
/*
2 分析：
3
4 1.可能两个数的长度不同，那么就需要在一个数加完之后把另一个数的剩下的数全加上。
5
6 2.判断最高位，如果最高位有进位，那么还需要把进位位加上。
7 */
8 #include<stdio.h>
9 #include<string.h>
10 int main()
11 {
12 char a[200],b[200];//定义字符串数组
13 int c[500];
14 scanf("%s%s",a,b);//输入字符串数组
15 int i,j,k=0,r=0;
16 int lena,lenb;
17 lena = strlen(a);
18 lenb = strlen(b);
19 for(i=lena-1,j=lenb-1;i>=0&&j>=0;i--,j--){
20 int p=(a[i]-'0')+(b[j]-'0')+r;
21 r=p/10;//进位
22 c[k++]=p%10;//余数加到数组中
23 }
24 while(i>=0){ //如果b中的数加完了
25 int p=(a[i]-'0')+r;
26 r=p/10;
27 c[k++]=p%10;
28 i--;
29 }
30 while(j>=0){ //如果a中的数加完了
31 int p=(b[j]-'0')+r;
32 r=p/10;
33 c[k++]=p%10;
34 j--;
35 }
36 if(r){//判断最高位有没有进位
37 c[k++]=r;
38 }
39 for(int i=k-1;i>=0;i--){//输出结果
40 printf("%d",c[i]);
41 }
42 return 0;
43 }
对于乘法与加法相同，
length1 = s.length();
length2 = t.length();
for(i = 0;i < length1;i++){
a[i] = (int)(s[i] - '0');
}
for(i = 0;i < length2;i++){
b[i] = (int)(t[i] - '0');
}
for(i = 0;i < length1;i++){
start = i;
for(j = 0;j < length2;j++){
sum[start] += a[i]*b[j];
start ++;
}
}
for(i = 0;i < start;i++){
sum[i + 1] += sum[i] / 10;
sum[i] = sum[i] % 10;
十一、最小生成树
最小生成树应用并查集的知识，所以这里一并练习了。
下面放上题目要求：
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
输入描述:
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
输出描述:
对每个测试用例，在1行里输出最小的公路总长度。
输入
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
输入
3
5
#include "stdio.h"
#include "iostream"
#include "algorithm"
using namespace std;
int Tree[1000];
int findRoot(int x){
if(Tree[x]==-1) return x;
else{
int tmp = findRoot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
}
struct E{
int a,b;
int cost;
}edge[8000];
bool cmp(E a,E b){
return a.cost<b.cost;
}
int main(){
int n;
while (scanf("%d",&n)!=EOF && n!=0){
for (int i = 1; i <=n*(n-1)/2 ; ++i) {
cin>>edge[i].a>>edge[i].b>>edge[i].cost;
}
sort(edge+1,edge+n*(n-1)/2,cmp);
for (int j = 1; j <=n ; ++j) {
Tree[j] = -1;
}
int ans=0;
for (int i = 1; i <=n*(n-1)/2 ; ++i) {
int a = findRoot(edge[i].a);
int b = findRoot(edge[i].b);
if(a!=b){
Tree[a] = b;
ans += edge[i].cost;
}
}
cout<<ans<<endl;
}
}
十二、最短路径（Dj做法）
因为太菜了，所以这么简单的题目写了好久。。不过最后还是成功ac了。
下面方式代码：
#include "stdio.h"
#include "iostream"
using namespace std;
int map[1005][1005],dis[1005];
int cost[1005][1005],val[1005];
int visFlag[1005];
int dj(int start,int n){
for (int i = 1; i <=n ; ++i) {
dis[i] = map[start][i];
val[i] = cost[start][i];
}
visFlag[start] = 1;
val[start] = 0;
dis[start] = 0;
int k=start;
for (int j = 1; j <=n-1 ; ++j) {
int min = 99999;
for (int i = 1; i <=n ; ++i) {
if(visFlag[i]==0 && min >dis[i]){
min = dis[i];
k = i;
}
}
visFlag[k] = 1;
for (int l = 1; l <=n ; ++l) {
if(dis[l] > dis[k]+map[k][l]){
dis[l] = dis[k]+map[k][l];
val[l] = val[k]+cost[k][l];
}
else if(dis[l] == dis[k]+map[k][l] && val[l] > val[k]+cost[k][l]){
val[l] = val[k]+cost[k][l];
}
}
}
return 0;
}
int main(){
int n,m;
while (scanf("%d%d",&n,&m)!=EOF && n+m){
for (int i = 1; i <=n ; ++i) {
for (int j = 1; j <=n ; ++j) {
if(i==j) map[i][j] = 0;
else map[i][j] = 999999;
}
}
for (int k = 1; k <=n ; ++k) {
visFlag[k] = 0;
}
int a,b,d,p;
for (int l = 1; l <=m ; ++l) {
//cin>>a>>b>>d>>p;
scanf("%d%d%d%d",&a,&b,&d,&p);
if(map[a][b] > d){
map[a][b] = d;
map[b][a] = d;
cost[a][b] = p;
cost[b][a] = p;
}
}
int s,t;
cin>>s>>t;
dj(s,n);
//cout<<dis[t]<<" "<<val[t]<<endl;
printf("%d %d\n",dis[t],val[t]);
}
}
这道题目为
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
输入
输出 一行有两个数， 最短距离及其花费。
Sample Input
3 2
1 2 5 6
2 3 4 5
1 3
0 0
Sample Output
9 11
这道题目我使用了邻接矩阵去写，不过数据如果过大用链表会更好。这样也行，背一背这个模板就上路吧。。
下面放上我自己曾经写的一篇详细的介绍dj的博客。具体算法看里面吧！
https://www.cnblogs.com/Pinging/p/7911169.html
十三、广度搜索
今天把广度搜索内容也复习了一下，
- 注意剪枝的细节就好
- 注意使用队列存储
- 注意每次获得新的结点存储到队列中
- 注意剪枝的条件
//
// Created by 陈平 on 2018/7/15.
//
#include "iostream"
#include "stdio.h"
#include "queue"
using namespace std;
int maze[51][51][51];
int mark[51][51][51];
struct N{
int x,y,z;
int t;
};
queue<N> Q;
int go[][3]{
1,0,0,
-1,0,0,
0,1,0,
0,-1,0,
0,0,1,
0,0,-1
};
int BFS(int x,int y,int z){
while (!Q.empty()){
N now = Q.front();
Q.pop();
for (int i = 0; i <6 ; ++i) {
int nx = now.x + go[i][0];
int ny = now.y + go[i][1];
int nz = now.z + go[i][2];
if(mark[nx][ny][nz]) continue;
if(nx<0 || nx>=x || ny<0 ||ny>=y ||nz<0||nz>=z ) continue;
if(maze[nx][ny][nz]==1) continue;
mark[nx][ny][nz] = 1;
N tmp;
tmp.x = nx;
tmp.y = ny;
tmp.z = nz;
tmp.t = now.t +1 ;
Q.push(tmp);
if(nx==x-1 && ny==y-1 && nz==z-1) return tmp.t;
}
}
return 100000;
}
int main(){
int v;
cin>>v;
while(v--){
int a,b,c,t;
scanf("%d%d%d%d",&a,&b,&c,&t);
for (int i = 0; i <a ; ++i) {
for (int j = 0; j <b ; ++j) {
for (int k = 0; k <c ; ++k) {
scanf("%d",&maze[i][j][k]);
mark[i][j][k] = 0;
}
}
}
while (!Q.empty()) Q.pop();
N tmp;
tmp.x = tmp.y = tmp.z = tmp.t = 0;
Q.push(tmp);
int rec = BFS(a,b,c);
if(rec<=t) cout<<rec<<endl;
else cout<<"-1"<<endl;
}
}
十四、在大字符串中寻找小的字符串
#include<stdio.h>
#include<string.h>
//查找字符串函数
int strfind(char str[],char key[])
{
int l1,l2;
int i,j;
int flag;
l1=strlen(str);
l2=strlen(key);
for(i=0;i<=l1-l2;i++)
{
flag=1;
for(j=0;j<l2;j++)
{
if(str[i+j]!=key[j])
{
flag=0;
break;
}
}
if(flag)//意思是找到了就直接返回，没有就i++继续找下一个位置
return i;
}
return -1;
}
int main()
{
char str[]="I have a dream have";
char key[]="have";
int kk=strfind(str,key);
if(kk)
printf("字符串%s在字符串%s中首次出现的位置是%d\n",key,str,kk);
else
puts("查找失败！！！！！！");
}
十五、01背包问题
01背包问题难度不大，但是要理解相关算法精髓
https://www.cnblogs.com/Pinging/p/7899610.html
上面的连接解释了01背包的详细过程，然后我们用代码巩固一下
设：
int v[N]={0,8,10,6,3,7,2};
int w[N]={0,4,6,2,2,5,1};
即有6个物品，重量分别为：4、6、2、2、5、1.
价值分别为：8、10、6、3、7、2
而背包重量最大为12——求最多装的价值为多少
#include "iostream"
#include "fstream"
using namespace std;
int main(){
int v[15] = {0,8, 10, 6, 3, 7, 2};
int w[15] = {0,4, 6, 2, 2, 5, 1};
int dp[15][15];
for (int j = 0; j <15 ; ++j) {
for (int i = 0; i <15 ; ++i) {
dp[i][j] = 0;
}
}
int n = 6,c = 12;
for (int i = 1; i <=n ; ++i) {
for (int j = 1; j <=c ; ++j) {
if(j>=w[i]) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + v[i]);
else dp[i][j] = dp[i-1][j];
}
}//两层循环，从1到n，根据动态方程得到当前点的最大值（注意if，当当前j比当前第i个物体大的时候）
cout<<dp[n][c]<<endl;
int x[100];
for (int k = n; k >1 ; k--) {
if(dp[k][c] == dp[k-1][c]) x[k] = 0;
else {
c-=w[k];
x[k] = 1;
}
}
x[1] = (dp[1][c]>0)?1:0;
for (int l = 1; l <=n ; ++l) {
cout<<x[l]<<" ";
}
}
得到结果 111000代表编号1 2 3的物体均收下了
网友评论