Code – 第227页

蓝桥杯 ALGO-2 算法训练最大最小公倍数（贪心算法）

问题描述
已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。

输入格式
输入一个正整数N。

输出格式
输出一个整数，表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定
1 <= N <= 10^6。

分析:
1.如果 n <= 2, 那么最小公倍数为 n
2.如果 n 是奇数，那么最小公倍数的最大值为末尾的三个数相乘
3.如果是偶数的话，如果同时出现两个偶数肯定会不能构成最大值了，因为会被除以2~~分两种情况：
(1)如果 n 是偶数且不是三的倍数，比如8，那么跳过n-2这个数而选择 8 7 5 能保证不会最小公倍数被除以2~~所以最小公倍数的最大值为n * (n – 1) * (n – 3)
(2)如果 n 是偶数且为三的倍数，比如6，如果还像上面那样选择的话，6和3相差3会被约去一个3，又不能构成最大值了。那么最小公倍数的最大值为(n – 1) * (n – 2) * (n – 3)

#include <iostream>  
using namespace std;  
int main() {  
    long long n, ans;  
    cin >> n;  
    if(n <= 2)  
        ans = n;  
    else if(n % 2 == 1)  
        ans = n * (n-1) * (n-2);  
    else if(n % 3 == 0)  
        ans = (n - 1) * (n - 2) * (n - 3);  
    else  
        ans = n * (n - 1) * (n - 3);    
    cout << ans;  
    return 0;  
}

#include <iostream>

using namespace std;

int main() {

long long n, ans;

cin >> n;

if(n <= 2)

ans = n;

else if(n % 2 == 1)

ans = n * (n-1) * (n-2);

else if(n % 3 == 0)

ans = (n - 1) * (n - 2) * (n - 3);

else

ans = n * (n - 1) * (n - 3);

cout << ans;

return 0;

}

蓝桥杯 PREV-5 历届试题错误票据

问题描述
某涉密单位下发了某种票据，并要在年终全部收回。
每张票据有唯一的ID号。全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。
因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。
你的任务是通过编程，找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。
输入格式
要求程序首先输入一个整数N(N<100)表示后面数据行数。
接着读入N行数据。
每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000），请注意行内和行末可能有多余的空格，你的程序需要能处理这些空格。
每个整数代表一个ID号。
输出格式
要求程序输出1行，含两个整数m n，用空格分隔。
其中，m表示断号ID，n表示重号ID

样例输入1
2
5 6 8 11 9
10 12 9
样例输出1
7 9
样例输入2
6
164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196
172 189 127 107 112 192 103 131 133 169 158
128 102 110 148 139 157 140 195 197
185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190
149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188
113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119
样例输出2
105 120

分析：把它们一个个放到集合里面，要是集合的容量不变说明是重复的数字~然后遍历集合，如果集合有一个数字不连续那就是这个数字是错误的~
用了while(cin >> a)后，发现第一个变量给不给都一样。。反正没什么用。。

#include <iostream>
#include <set>
using namespace std;
int main() {
    set<int> s;
    int row, a, m = 0, n = 0, size;
    cin >> row;
    while(cin >> a) {
        size = s.size();
        s.insert(a);
        if(s.size() == size) {
            n = a;
        }
    }
    set<int>::iterator it = s.begin();
    set<int>::iterator itt = it;
    for(it++ ; it != s.end(); it++, itt++) {
        
        if(*it != *itt + 1) {
            m = *itt + 1;
        }
    }
    cout << m << " " << n;
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

int main() {

set<int> s;

int row, a, m = 0, n = 0, size;

cin >> row;

while(cin >> a) {

size = s.size();

s.insert(a);

if(s.size() == size) {

n = a;

}

set<int>::iterator it = s.begin();

set<int>::iterator itt = it;

for(it++ ; it != s.end(); it++, itt++) {

if(*it != *itt + 1) {

m = *itt + 1;

}

cout << m << " " << n;

return 0;

}

蓝桥杯 ADV-144 算法提高 01背包

问题描述
　　给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
输入格式
　　输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。
　　以后N行每行两个数Wi和Vi,表示物品的重量和价值
输出格式
　　输出1行，包含一个整数，表示最大价值。
样例输入
3 5
2 3
3 5
4 7
样例输出
8
数据规模和约定
　　1<=N<=200,M<=5000.

分析：dp[i][j]表示前i件物品选择部分装入体积为j的背包后，背包当前的最大价值，
一共有n件物品，那么dp[n][m]就是前n件物品选择部分装入容量为m的背包后，背包内物品的最大价值
1.当当前输入的物品体积大于背包容量，则不装入背包，dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于背包容量，考虑装或者不装两种状态，取体积最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);

#include <iostream>
using namespace std;
int dp[201][5001];
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        int w, v;
        cin >> w >> v;
        for(int j = 1; j <= m; j++) {
            if (j >= w)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[n][m];
    return 0;
}

#include <iostream>

using namespace std;

int dp[201][5001];

int main() {

int n, m;

cin >> n >> m;

for(int i = 1; i <= n; i++) {

int w, v;

cin >> w >> v;

for(int j = 1; j <= m; j++) {

if (j >= w)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);

else

dp[i][j] = dp[i-1][j];

}

cout << dp[n][m];

return 0;

}

蓝桥杯 ALGO-30 算法训练入学考试（01背包，动态规划）

问题描述
　　辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
　　如果你是辰辰，你能完成这个任务吗？
输入格式
　　第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
　　包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入
70 3
71 100
69 1
1 2
样例输出
3
数据规模和约定
　　对于30%的数据，M <= 10；
　　对于全部的数据，M <= 100。

分析：01背包问题。对于每一个输入都有采和不采两种状态。
dp[i][j]表示对于前i个草药选择部分采且总时间不超过j小时后，草药的价值的最大值
可得dp[M][T]即是所求的解。
1.当当前输入的草药所需时间大于允许的最大时间j小时的时候，则不采，dp[i][j] = dp[i-1][j];
2.当当前输入的草药所需时间小于等于允许的最大时间小时的时候，考虑采或者不采两种状态，取能够使草药总价值最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b);

#include <iostream>
using namespace std;
int dp[101][1001];
int main() {
    int t, m;
    cin >> t >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        for(int j = 1; j <= t; j++) {
            if(j >= a)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[m][t];
    return 0;
}

#include <iostream>

using namespace std;

int dp[101][1001];

int main() {

int t, m;

cin >> t >> m;

for(int i = 1; i <= m; i++) {

int a, b;

cin >> a >> b;

for(int j = 1; j <= t; j++) {

if(j >= a)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b);

else

dp[i][j] = dp[i-1][j];

}

cout << dp[m][t];

return 0;

}

蓝桥杯 ALGO-31 算法训练开心的金明（01背包，动态规划）

问题描述
　　金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：
“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，
肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
　　设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为 j1，j2，……，jk，则所求的总和为：
　　v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）
　　请你帮助金明设计一个满足要求的购物单。
输入格式
　　输入文件的第1行，为两个正整数，用一个空格隔开：
　　N m
　　（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数。）
　　从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数
　　v p
　　（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）
输出格式
　　输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。
样例输入
1000 5
800 2
400 5
300 5
400 3
200 2
样例输出
3900
分析：01背包问题。对于每一个输入都有买和不买两种状态。
dp[i][j]表示对于前i件物品选择部分购买限定总价不超过j元后，物品的价格与重要程度乘积的总和的最大值
可得dp[m][n]即是所求的解。
1.当当前输入的物品价格大于允许的最大总价j元，则不买，dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于允许的最大总价j元，考虑买或者不买两种状态，取物品的价格与重要程度乘积的总和最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + t);

#include <iostream>
using namespace std;
int dp[25][30000];
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        for(int j = 1; j <= n; j++) {
            if(j >= a)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + a * b);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[m][n];
    return 0;
}

#include <iostream>

using namespace std;

int dp[25][30000];

int main() {

int n, m;

cin >> n >> m;

for(int i = 1; i <= m; i++) {

int a, b;

cin >> a >> b;

for(int j = 1; j <= n; j++) {

if(j >= a)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + a * b);

else

dp[i][j] = dp[i-1][j];

}

cout << dp[m][n];

return 0;

}

蓝桥杯 ALGO-21 算法训练装箱问题（动态规划，01背包）

问题描述
　　有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。
　　要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入格式
　　第一行为一个整数，表示箱子容量；
　　第二行为一个整数，表示有n个物品；
　　接下来n行，每行一个整数表示这n个物品的各自体积。
输出格式
　　一个整数，表示箱子剩余空间。
样例输入
24
6
8
3
12
7
9
7
样例输出
0

分析：dp[i][j]表示前i件物品选则部分装入体积为j的背包后，背包总共所占的最大体积，
一共有n件物品，那么dp[n][v]就是前n件物品选择部分装入体积为v的背包后，背包总共占有的最大体积
1.当当前输入的物品体积大于背包容量，则不装入背包，dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于背包容量，考虑装或者不装两种状态，取体积最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-t] + t);

#include <iostream>
using namespace std;
int dp[31][20001];
int main() {
    int v, n;
    cin >> v >> n;
    for(int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        for(int j = 1; j <= v; j++) {
            if (j >= t) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-t] + t);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << v - dp[n][v];
    return 0;
}

#include <iostream>

using namespace std;

int dp[31][20001];

int main() {

int v, n;

cin >> v >> n;

for(int i = 1; i <= n; i++) {

int t;

cin >> t;

for(int j = 1; j <= v; j++) {

if (j >= t) {

dp[i][j] = max(dp[i-1][j], dp[i-1][j-t] + t);

} else {

dp[i][j] = dp[i-1][j];

}

cout << v - dp[n][v];

return 0;

}