算法上机考试复习

前言

最近要上机考试,因此还是对以前做过的题目做一个复习回顾,自己重新手写一遍,纯属回顾,代码风格不好请海涵,考完试以后我把考了的点都标记了一下方便以后学弟学妹们复习了,2333

迭代递归

汽水瓶(考试考了类似的)

题目描述

有这样一道智力题:“某商店规定:三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶,她最多可以换多少瓶汽水喝?”答案是5瓶,方法如下:先用9个空瓶子换3瓶汽水,喝掉3瓶满的,喝完以后4个空瓶子,用3个再换一瓶,喝掉这瓶满的,这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水,喝掉这瓶满的,喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有n个空汽水瓶,最多可以换多少瓶汽水喝?

输入

输入文件最多包含10组测试数据,每个数据占一行,仅包含一个正整数n(1≤n≤100),表示小张手上的空汽水瓶数。n=0表示输入结束,你的程序不应当处理这一行。

输出

对于每组测试数据,输出一行,表示最多可以喝的汽水瓶数。如果一瓶也喝不到,输出 0

样例输入
1
2
3
4
3
10
81
0
样例输出
1
2
3
1
5
40
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;

int main(){
int n;
while(cin>>n){
if(n == 0 )break;
int a,b;
int result = 0;
while(n >= 3){
a = n/3;
b = n%3;
result += a;
n = a+b;
}
if( n ==2) result += 1;
printf("%d",result);

}
return 0;
}

跳台阶(考试考了类似的)

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

输入

多组测试样例。每组测试样例包含一个整数n。(1<=n<=100)

输出

每组测试样例输出一行,表示青蛙跳上n级台阶的跳法数量.

所得到的结果模1000000007

样例输入
1
2
3
4
样例输出
1
2
3
5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
const int l=1000000007;
long long dp[205]={0};


unsigned long long solve_1(int n ){
static long long count[205] = {0};
if(count[n] != 0 ) return count[n]; //这里有点像备忘录方法,不然直接递归这题会超时
if(n<=0) return 0;
else if( 1 == n) return 1;
else if( 2 == n) return 2;
count[n] = solve_1(n-1)+solve_1(n-2)%l;
return count[n];
}



void solve_2(int n){
dp[0] = 1;
dp[1] = 1;
for(int i =2 ; i <= n; i++){
dp[i] = (dp[i-1]+dp[i-2])%l; //关键是这个递推式
}
cout<<dp[n]<<endl;
}

int main(){
int n;
while(cin>>n){
cout<<solve_1(n)<<endl;//递归
solve_2(n); //动态规划
}
return 0;
}

进制转换(考试考了类似的)

题目描述

输入一个十进制正整数,然后输出它所对应的八进制数。

输入

输入一个十进制正整数n(1≤n≤106) 。

输出

输出n对应的八进制数,输出在一行。

样例输入
1
10
样例输出
1
12
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
void solve(int num){
int s[100];
int i=0;
int tmp=0;
while(num!=0){
tmp = num%8;
num = num/8;
s[i++] = tmp;
}
for(int j=i-1;j>=0;j--){
cout<<s[j];

}
cout<<endl;

}


/*这个题目也可以用栈去模拟,几进制自己灵活变通*/

int main(){
int a;
cin>>a;
solve(a);
return 0;


}

排列问题

题目描述

输入一个可能含有重复字符的字符串,打印出该字符串中所有字符的全排列。

输入

单组测试数据,输入数据是一个长度不超过10个字符的字符串,以逗号结尾。

输出

打印出该字符串中所有字符的全排列。以字典序顺序输出,用空格分隔。

样例输入
1
abc,
样例输出
1
abc acb bac bca cab cba
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

char a[200];
int main(){

cin>>a;
int lena = strlen(a);

do
{
for( int i = 0; i < lena-1; i++ ) { cout << a[i]; } cout << " ";
} while( next_permutation(a, a+lena-1) ); //关键是这个函数

return 0;
}

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>

using namespace std;
char a[100];

void Perm(char *list,int k,int m){
if( k == m){
for(int i=0 ;i <= m; i++) cout<<list[i];
cout<<" ";
}else{
for(int i=k; i<=m; i++){
swap(list[k],list[i]);
Perm(list,k+1,m);
swap(list[k],list[i]); //关键是换位之后记得还原现场
}
}
}




int main(){
cin>>a;
int lena = strlen(a);
a[lena-1] = '\0';
lena = strlen(a);
sort(a,a+lena);
Perm(a,0,lena-1);

return 0;
}

矩形滑雪场

题目描述

zcb喜欢滑雪。他来到了一个滑雪场,这个滑雪场是一个矩形,为了简便,我们用r行c列的矩阵来表示每块地形。为了得到更快的速度,滑行的路线必须向下倾斜。 例如样例中的那个矩形,可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1,其实25-24-23…3-2-1更长,事实上这是最长的一条。

输入

第1行:两个数字r,c(1 ≤ r, c ≤ 100),表示矩阵的行列。第2..r+1行:每行c个数,表示这个矩阵。

输出

仅一行:输出1个整数,表示可以滑行的最大长度。

样例输入
1
2
3
4
5
6
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
样例输出
1
25
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
int r,c;
int m[105][105];
int record[105][105]={0};
int m_x[4] = {0,0,1,-1};
int m_y[4] = {1,-1,0,0};

int dfs(int x, int y){
if(record[x][y]) return record[x][y];
for(int i =0 i< 4 ;i++){ //往四个方向深搜
int wx = x+ m_x[i];
int wy = y+ m_y[i];
if(wx >= 1 && wx <= r && wy >=1 && wy<= c && m[x][y] > m[wx][wy]){
record[x][y] = max(record[x][y], dfs(wx,wy)+1);
}
}
return record[x][y];
}



int main(){
cin>>r>>c;
for(int i =1;i <=r ;i++){
for(int j = 1; j<=c;j++){
cin>>m[i][j];
}
}
int result =-1;
for(int i =1;i < = r; i++){
for(int j =1 ; j<=c;j++){
record[i][j] = dfs(i,j);
result = max(record[i][j],result);
}
}
cout<<result + 1<<endl;
retrun 0;
}

动态规划

这种题目关键记住dp公式就好书上都有不多说

最长公共子序列

题目描述

给你一个序列X和另一个序列Z,当Z中的所有元素都在X中存在,并且在X中的下标顺序是严格递增的,那么就把Z叫做X的子序列。
例如:Z=<a,b,f,c>是序列X=<a,b,c,f,b,c>的一个子序列,Z中的元素在X中的下标序列为<1,2,4,6>。
现给你两个序列X和Y,请问它们的最长公共子序列的长度是多少?

输入

输入包含多组测试数据。每组输入占一行,为两个字符串,由若干个空格分隔。每个字符串的长度不超过100。

输出

对于每组输入,输出两个字符串的最长公共子序列的长度。

样例输入
1
2
3
abcfbc abfcab
programming contest
abcd mnp
样例输出
1
2
3
4
2
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;

int c[2005][2005];
int m[2005][2005];
char a[2005],b[2005];

/*构造最优解*/
void LCS(int i,int j){
if(i ==0|| j==0) return;
if(m[i][j] == 1){
LCS(i-1,j-1);
cout<<a[i-1];
}else if(m[i][j] == 2){
LCS(i-1,j);
}else{
LCS(i,j-1);
}

}


void solve(int lena,int lenb){
for(int i=0;i <=lena ;i++){
c[i][0] = 0;
}
for(int j =0;j<=lenb;j++){
c[0][j] = 0;
}
for(int i=1;i<=lena;i++){
for(int j=1;j<=lenb;j++){
if(a[i-1] == b[j-1]) {
c[i][j] = c[i-1][j-1]+1;
m[i][j] = 1;
}
else if(c[i-1][j] >= c[i][j-1]){
c[i][j] = c[i-1][j];
m[i][j] =2;
}else{
c[i][j] = c[i][j-1];
m[i][j] = 3;
}
}

}
cout << c[lena][lenb]<<endl;
// LCS(lena,lenb);

}


int main(){
cin>>a;
cin>>b;
int lena = strlen(a);
int lenb = strlen(b);
solve(lena,lenb);
return 0;
}

矩阵连乘

题目描述

给定n个矩阵{A1,A2,…,An},及m个矩阵连乘的表达式,判断每个矩阵连乘表达式是否满足矩阵乘法法则,如果满足,则计算矩阵的最小连乘次数,如果不满足输出“MengMengDa“。

输入

输入数据由多组数据组成(不超过10组样例)。每组数据格式如下:
第一行是2个整数n (1≤n≤26)和m(1≤m≤3),表示矩阵的个数。
接下来n行,每行有一个大写字母,表示矩阵的名字,后面有两个整数r和c,分别表示该矩阵的行数和列数,其中1 < r, c
第n+1行到第n+m行,每行是一个矩阵连乘的表达式(2<=矩阵个数<=100)。

输出

对于每个矩阵连乘表达式,如果运算不满足矩阵乘法法则的情况(即左矩阵列数与右矩阵的行数不同),则输出“MengMengDa”,否则输出最小矩阵连乘次数。

数据保证结果不超过1e9。

样例输入
1
2
3
4
5
6
3 2
A 10 100
B 5 50
C 100 5
ACB
ABC
样例输出
1
2
7500
MengMengDa
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>


using namespace std;
int m[26][26];

struct Matrix{
int r,c;
};


void solve(int p[],int len){
for(int i =1; i<=len;i++) m[i][i] = 0;
for(int r =2; r<=len;r++){
for(int i = 1; i <= len-r+1; i++){
int j = i + r-1;
m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];
for(int k =i+1 ;k < j; k++){
m[i][j] = min(m[i][j],m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]);
}
}
}
cout<<m[1][len]<<endl;

}

int main(){
int n,l;
while(cin>>n>>l){
map<char,Matrix>my_map;
int p[105];
for(int i =1;i <= n;i++){
char a;
int j,k;
cin>>a>>j>>k;
Matrix tmp ;
tmp.r = j;
tmp.c = k;
my_map[a] = tmp;
}
char words[101];

for(int i =0; i < l; i++){
cin>>words;
int lenw = strlen(words);
int flag = 0;
p[0] = my_map[words[0]].r;
p[1] = my_map[words[0]].c;
for(int j =1; j < lenw;j++){ //注意
if(my_map[words[j]].r != my_map[words[j-1]].c){
flag =1;
break;
}
p[j+1] = my_map[words[j]].c;
}
if(flag == 1) puts("MengMengDa");
else solve(p,lenw);
}

}
return 0;
}

01背包(考试考了类似的)

题目描述

已知有N种物品和一个可容纳C重量的背包。每种物品i的重量为Wi,价值为Pi。那么,采用怎样的装包方法才会使装入背包物品的总价值最大。

输入

包含多组测试数据。第一行为一个整数T(1<=T<=10),代表测试数据个数。

接下来有T组测试数据。每组测试数据第一行为背包的重量C(C<10000)和物品个数N(N<1000)。接下来的N行分别为物品的重量cost(1<=cost<=100)和价值val(1<=val<=3000000)。(注意:结果可能超过int范围)

输出

对每组测试数据,输出其对应的所装物品的最大价值。

样例输入
1
2
3
4
5
6
7
1
10 5
2 6
2 3
6 5
5 4
4 6
样例输出
1
15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>

using namespace std;
int w[1005]={0},v[1005]={0};
int m[1005][10005]={0};
int x[1005]={0};//标记作用

/*构造最优解*/
void output(int n,int cost){
for(int i = n; i>1; i--){ //注意这里可能会出错
if( m[i][cost] == m[i-1][cost] ) x[i] = 0;
else{
x[i]= 1;
cost -=w[i];
}
}
//cout<<1<<endl;
x[1] = m[1][cost]?1:0;
for(int i = 1; i<=n; i++){
cout<<x[i]<<" ";
}
cout<<endl;
}



int main(){
int T;
cin>>T;
while(T--){
int c,n;
cin>>c>>n;
for(int i =1 ; i<= n;i++){
cin>>w[i]>>v[i];
}
for(int i = 1;i <= n; i++){
for(int j =1;j<= c;j++){
if(j >= w[i]) m[i][j] = max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
else m[i][j] = m[i-1][j];
}
}
cout<<m[n][c]<<endl;
// output(n,c);
}
return 0;
}

最大子段和

题目描述

给定n个整数组成的序列a1,a2,…an, 求子段和ai+ai+1+…+aj(子段可为空集)的最大值。

输入

包含多组测试数据。第一行为一个整数T(1<=T<=20),代表测试数据个数。

每组测试数据第一行为一个整数n,代表有n个整数(1<=n<=10000)。

接下来一行有n个数x(-1000<=x<=1000)。

输出

输出其对应的最大子段和。

样例输入
1
2
3
1
6
2 -11 4 13 -1 2
样例输出
1
18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
int a[10005]={0};

void solve(int len){
int sum = 0;
int k = 0;
for(int i =0 ; i< len ;i++){
if(k > 0){
k += a[i];
}else{
k = a[i];
}
if(k > sum) sum = k;
}
cout<<sum<<endl;
}


int main(){
int T;
cin>>T;
while(T--){
int n ;
cin>>n;
for(int i = 0; i<n;i++) cin>>a[i];
solve(n);
}
return 0;
}

求数组的最长递减子序列

题目描述

给定一个整数序列,输出它的最长递减(注意不是“不递增”)子序列。

输入

输入包括两行,第一行包括一个正整数N(N<=1000),表示输入的整数序列的长度。第二行包括用空格分隔开的N个整数,整数范围区间为[-30000,30000]。

输出

输出最长递减子序列,数字之间有一个空格。

样例输入
1
2
8
9 4 3 2 5 4 3 2
样例输出
1
9 5 4 3 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;
int num[205];
int dp[205];
int roud[205];
int maxc;
int N;

void output(int x) {
if(x){
output(roud[x]);
if(maxc != x) cout<<num[x]<<" ";
else cout<<num[x]<<endl;
}
}



int main(){
cin>>N;
for(int i= 1 ; i<= N; i++) cin>>num[i];
for(int i = 1 ; i <= N ; i++){
dp[i] = 1;
roud[i] = 0;
for(int j = 1 ; j < i; j++){
if(num[j] > num[i] && dp[i] < dp[j] +1 ){
dp[i] = dp[j] +1 ;
roud[i] = j;
}
}
if(dp[i] > dp[maxc]){
maxc = i;
}

}
output(maxc);
return 0;
}

沙子的质量

题目描述
设有N堆沙子排成一排,其编号为1,2,3,…,N(N< =300)。每堆沙子有一定的数量,可以用一个整数来描述,现在要将N堆沙子合并成为一堆,每次只能合并相邻的两堆,合并的代价为这两堆沙子的数量之和,合并后与这两堆沙子相邻的沙子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同,如有4堆沙子分别为1 3 5 2我们可以先合并1、2堆,代价为4,得到4 5 2又合并1,2堆,代价为9,得到9 2,再合并得到11,总代价为4+9+11=24,如果第二步是先合并2,3堆,则代价为7,得到4 7,最后一次合并代价为11,总代价为4+7+11=22;问题是:找出一种合理的方法,使总的代价最小。输出最小代价。

输入

第一行一个数N表示沙子的堆数N。 第二行N个数,表示每堆沙子的质量。 a[i]< =1000。

输出

合并的最小代价。

样例输入
1
2
4
1 3 5 2
样例输出
1
22
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>

using namespace std;
int a[105]={0};
int m[305][305];


/*这个题目就是另类的矩阵连乘*/
int main(){
int n;
cin>>n;
for(int i= 1; i <= n;i++) {
cin>>a[i];
a[i] += a[i-1];
m[i][i] = 0;
}
for(int r =2; r<=n;r++){
for(int i=1; i<=n-r+1; i++ ){
int j = i+r-1;
m[i][j] = m[i+1][j]+a[j]-a[i-1];
for(int k = i+1; k<j; k++){
m[i][j] = min(m[i][j],m[i][k]+m[k+1][j]+a[j]-a[i-1]);
}
}
}
cout<<m[1][n]<<endl;

return 0;
}

节食的限制

题目描述

Bessie像她的诸多姊妹一样,因為从Farmer John的草地吃了太多美味的草而长出了太多的赘肉。所以FJ将她置於一个及其严格的节食计划之中。她每天不能吃多过H(5<=H<=45000)公斤的乾草。Bessie只能吃一整綑乾草;当她开始吃一綑乾草的之后就再也停不下来了。她有一个完整的N(1<=n<=50)綑可以给她当作晚餐的乾草的清单。她自然想要尽量吃到更多的乾草。很自然地,每綑乾草只能被吃一次(即使在列表中相同的重量可能出现2次,但是这表示的是两綑乾草,其中每綑乾草最多只能被吃掉一次)。 给定一个列表表示每綑乾草的重量Si(1<=Si<=H),求Bessie不超过节食的限制的前提下可以吃掉多少乾草(注意一旦她开始吃一綑乾草就会把那一綑乾草全部吃完)。

输入

第一行:两个由空格隔开的整数:H和N, 第2到N+1行:第i+1行是一个单独的整数,表示第i綑乾草的重量Si。

输出

一个单独的整数表示Bessie在限制范围内最多可以吃多少公斤的乾草。

样例输入
1
2
3
4
5
56 4
15
19
20
21
样例输出
1
56
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>


using namespace std;
int m[50][45000]={0};
int w[50];

/*本质就是01背包*/
int main(){
int h,n;
cin>>h>>n;
for(int i=1 ; i<= n; i++)cin>>w[i];
for(int i = 1; i<= n; i++){
for(int j = 1 ; j<=h; j++){
if(j >= w[i]) m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+w[i]);
else m[i][j] = m[i-1][j];
}
}
cout<<m[n][h]<<endl;


return 0;
}

贪心法

这类题目记得先排序,按怎样的顺序排,自己看清题目

homework

题目描述

临近开学了,大家都忙着收拾行李准 备返校,但 I_Love_C 却不为此担心! 因为他的心思全在暑假作业上:目前为止还未开动。

暑假作业是很多张试卷,我们这些从试卷里爬出来的人都知道,卷子上的题目有选择题、填空题、简答题、证明题等。而做选择题的好处就在于工作量很少,但又因为选择题题目都普遍很长。如果有 5 张试卷,其中 4 张是选择题,最后一张是填空题,很明显做最后一张所花的时间要比前 4 张长很多。但如果你只做了选择题,虽然工作量很少,但表面上看起来也已经做了4/5的作业了。

I_Love_C决定就用这样的方法来蒙混过关,他统计出了做完每一张试卷所需的时间以及它做完后能得到的价值(按上面的原理,选择题越多价值当然就越高咯)。

现在就请你帮他安排一下,用他仅剩的一点时间来做最有价值的作业。

输入

测试数据包括多组。每组测试数据以两个整数 M,N(1<M<20,1<N<10000) 开头,分别表示试卷的数目和 I_Love_C 剩下的时间。接下来有 M 行,每行包括两个整数 T,V(1<T<N,1<V<10000)分别表示做完这张试卷所需的时间以及做完后能得到的价值,输入以 0 0 结束。

输出

对应每组测试数据输出 I_Love_C 能获得的最大价值。保留小数点 2 位

提示:float 的精度可能不够,你应该使用 double 类型。

样例输入
1
2
3
4
5
6
4 20
4 10
5 22
10 3
1 2
0 0
样例输出
1
37.00
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
struct work{
double t,v;
double v_t;
};

bool cmp(work a, work b){
return a.v_t > b.v_t;
}



int main(){
int m,n;
work w[105];
while(cin>>m>>n && (m!=0 && n != 0)){
for(int i =0 ; i<m ;i++){
cin>>w[i].t>>w[i].v;
w[i].v_t = w[i].v/w[i].t;
}
sort(w,w+m,cmp);
double k =0,p_t =0;
for(int i =0; i<m ;i++){
if(p_t + w[i].t <= n){
p_t += w[i].t;
k += w[i].v;
}
else{
if(p_t < n){
k += (n - p_t)*w[i].v_t;
p_t = n;
break;
}
}
}
printf("%.2lf",k);
}


return 0;
}

区间包含问题

题目描述

已知 n 个左闭右开区间 [a,b),对其进行 m 次询问,求区间[l,r]最多可以包含 n 个区间中的多少个区间,并且被包含的所有区间都不相交。

输入

输入包含多组测试数据,对于每组测试数据:

第一行包含两个整数 n ,m (1≤n≤100000,1≤m≤100) 。

接下来 n 行每行包含两个整数 a ,b (0≤ a< b≤ 10^9) 。

接下来 m 行每行包含两个整数 l ,r (0≤ l< r≤ 10^9) 。

输出

对于每组测试数据,输出 m 行,每行包含一个整数。

样例输入
1
2
3
4
5
6
7
8
4 3
1 3
2 4
1 4
1 2
1 2
1 3
1 4
样例输出
1
2
3
1
1
2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>


using namespace std;

struct node{
int s,e;
};

bool cmp(node a,node b){
return a.e < b.e;
}


int main(){
int n ,m;
cin>>n>>m;
node a[105],b[105];
for(int i = 0; i< n;i++){
cin>>a[i].s>>a[i].e;
}
sort(a,a+n,cmp);
for(int j = 0; j< m;j++){
cin>>b[j].s>>b[j].e;
int sum = 0;
for(int k = 0 ;k < n;k ++){
if(a[k].s >= b[j].s){
if(a[k].e <= b[j].e){
sum++;
b[j].s = a[k].e;
}else break;

}

}
cout<<sum<<endl;
}

return 0;
}

法师康的工人

题目描述

三个法师康的工人每天早上6点到工厂开始到三条产品生产线上组装桔子手机。第一个工人在200时刻开始(从6点开始计时,以秒作为单位)在生产线上开始生产,一直到1000时刻。第二个工人,在700时刻开始,在1100时刻结束。第三个工人从1500时刻工作到2100时刻。期间最长至少有一个工人在生产线上工作的连续时间为900秒(从200时刻到1100时刻),而最长的无人生产的连续时间(从生产开始到生产结束)为400时刻(1100时刻到1500时刻)。

你的任务是用一个程序衡量N个工人在N条产品线上的工作时间列表(1≤N≤5000,以秒为单位)。

最长的至少有一个工人在工作的时间段

最长的无人工作的时间段(从有人工作开始计)

输入

输入第1行为一个整数N,第2-N+1行每行包括两个均小于1000000的非负整数数据,表示其中一个工人的生产开始时间与结束时间。

输出

输出为一行,用空格分隔开两个我们所求的数。

样例输入
1
2
3
4
3
200 1000
700 1100
1500 2100
样例输出
1
900 400
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>

using namespace std;

struct worker{
int s,e;
}w[105];

bool cmp(worker a, worker b){
if(a.s == b.s) return a.e<b.e;
else return a.s < b.s;
}

int main(){
int N ;
cin>>N;
for(int i =0; i < N ; i++) cin>>w[i].s>>w[i].e;
int sus = w[0].e -w[0].s,gap = 0,t1 = w[0].s,t2 = w[0].e;
for(int i = 0; i< N ;i++){
if(w[i].s > t2){
gap = max(gap,w[i].s-t2);
t1 = w[i].s;
}
t2 = max(t2,w[i].e);
sus = max(sus,t2-t1);

}
cout<<sus<<" "<<gap<<endl;

return 0;
}

哈夫曼编码

题目描述

给定一只含有小写字母的字符串;输出其哈夫曼编码的长度

输入

第一行一个整数T,代表样例的个数,接下来T行,每行一个字符串,0<T<=2000,字符串长度0<L<=1500.

输出

对于每个字符串,输出其哈夫曼编码长度

样例输入
1
2
3
4
3
hrvsh
lcxeasexdphiopd
mntflolfbtbpplahqolqykrqdnwdoq
样例输出
1
2
3
10
51
115
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>

using namespace std;

int b[30];
char s[1005];
int ans=0;

struct cmp{
bool operator()(int x, int y){
return x>y;
}
};

/*会用优先队列事半功倍*/
priority_queue<int , vector<int>,cmp> q;


void solve() {
for(int i = 0 ;i<26;i++){
if(b[i]) q.push(b[i]);
}
int sum = 0;
while(q.size()>1){
int a = q.top();
q.pop();
int c = q.top();
q.pop();
sum = a+c;
q.push(sum);

ans += sum ;
}
printf("%d\n",ans);
}




int main(){
int T;
cin>>T;
while(T--){
cin>>s;
int lens =strlen(s);
while(!q.empty()) q.pop();
ans = 0;
memset(b,0,sizeof(b));
for(int i =0; i < lens ; i++){
b[int(s[i]-'a')]++;
}
solve();

}
return 0;
}

活动安排(考试考了类似的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>

using namespace std;

struct work{
int begin,end;

};

bool cmp(work a,work b){
return a.end < b.end;
}

work w[50];
int main(){
int n;
cin>>n;
for(int i =0; i< n; i++){
cin>>w[i].begin>>w[i].end;
}
sort(w,w+n,cmp);
int j = 0;
int ans = 1;
for(int i =1; i< n;i++){
if(w[i].begin >= w[j].end){
ans++;
j = i;
}
}
cout<<ans<<endl;
return 0;
}

听说,打赏我的人最后都成了大佬。



文章目录
  1. 1. 前言
  2. 2. 迭代递归
    1. 2.1. 汽水瓶(考试考了类似的)
      1. 2.1.1. 题目描述
        1. 2.1.1.1. 输入
        2. 2.1.1.2. 输出
        3. 2.1.1.3. 样例输入
        4. 2.1.1.4. 样例输出
    2. 2.2. 跳台阶(考试考了类似的)
      1. 2.2.1. 题目描述
        1. 2.2.1.1. 输入
        2. 2.2.1.2. 输出
        3. 2.2.1.3. 样例输入
        4. 2.2.1.4. 样例输出
    3. 2.3. 进制转换(考试考了类似的)
      1. 2.3.1. 题目描述
        1. 2.3.1.1. 输入
        2. 2.3.1.2. 输出
        3. 2.3.1.3. 样例输入
        4. 2.3.1.4. 样例输出
    4. 2.4. 排列问题
      1. 2.4.1. 题目描述
        1. 2.4.1.1. 输入
        2. 2.4.1.2. 输出
        3. 2.4.1.3. 样例输入
        4. 2.4.1.4. 样例输出
    5. 2.5. 全排列
    6. 2.6. 矩形滑雪场
      1. 2.6.1. 题目描述
        1. 2.6.1.1. 输入
        2. 2.6.1.2. 输出
        3. 2.6.1.3. 样例输入
        4. 2.6.1.4. 样例输出
  3. 3. 动态规划
    1. 3.1. 最长公共子序列
      1. 3.1.1. 题目描述
        1. 3.1.1.1. 输入
        2. 3.1.1.2. 输出
        3. 3.1.1.3. 样例输入
        4. 3.1.1.4. 样例输出
    2. 3.2. 矩阵连乘
      1. 3.2.1. 题目描述
        1. 3.2.1.1. 输入
        2. 3.2.1.2. 输出
        3. 3.2.1.3. 样例输入
        4. 3.2.1.4. 样例输出
    3. 3.3. 01背包(考试考了类似的)
      1. 3.3.1. 题目描述
        1. 3.3.1.1. 输入
        2. 3.3.1.2. 输出
        3. 3.3.1.3. 样例输入
        4. 3.3.1.4. 样例输出
    4. 3.4. 最大子段和
      1. 3.4.1. 题目描述
        1. 3.4.1.1. 输入
        2. 3.4.1.2. 输出
        3. 3.4.1.3. 样例输入
        4. 3.4.1.4. 样例输出
    5. 3.5. 求数组的最长递减子序列
      1. 3.5.1. 题目描述
        1. 3.5.1.1. 输入
        2. 3.5.1.2. 输出
        3. 3.5.1.3. 样例输入
        4. 3.5.1.4. 样例输出
    6. 3.6. 沙子的质量
      1. 3.6.0.1. 输入
      2. 3.6.0.2. 输出
      3. 3.6.0.3. 样例输入
      4. 3.6.0.4. 样例输出
  4. 3.7. 节食的限制
    1. 3.7.1. 题目描述
      1. 3.7.1.1. 输入
      2. 3.7.1.2. 输出
      3. 3.7.1.3. 样例输入
      4. 3.7.1.4. 样例输出
  • 4. 贪心法
    1. 4.1. homework
      1. 4.1.1. 题目描述
        1. 4.1.1.1. 输入
        2. 4.1.1.2. 输出
        3. 4.1.1.3. 样例输入
        4. 4.1.1.4. 样例输出
    2. 4.2. 区间包含问题
      1. 4.2.1. 题目描述
        1. 4.2.1.1. 输入
        2. 4.2.1.2. 输出
        3. 4.2.1.3. 样例输入
        4. 4.2.1.4. 样例输出
    3. 4.3. 法师康的工人
      1. 4.3.1. 题目描述
        1. 4.3.1.1. 输入
        2. 4.3.1.2. 输出
        3. 4.3.1.3. 样例输入
        4. 4.3.1.4. 样例输出
    4. 4.4. 哈夫曼编码
      1. 4.4.1. 题目描述
        1. 4.4.1.1. 输入
        2. 4.4.1.2. 输出
        3. 4.4.1.3. 样例输入
        4. 4.4.1.4. 样例输出
    5. 4.5. 活动安排(考试考了类似的)