Code – 第232页

使用setprecision控制输出流显示浮点数的有效数字个数（C++）

setprecision的头文件为：#include <iomanip>
会自动四舍五入
setprecision(n)表示显示n个有效数字
和fixed连用可以控制小数点后面输出的位数

cout << setprecision(2) << 1.251 << endl;//输出为1.3
cout << fixed << setprecision(2) << 1.236 << endl;//输出为1.24

1 2	cout << setprecision(2) << 1.251 << endl;//输出为1.3 cout << fixed << setprecision(2) << 1.236 << endl;//输出为1.24

蓝桥杯 ADV-193 算法提高盾神与条状项链

问题描述
　　有一天，盾神捡到了好多好多五颜六色的珠子！他心想这些珠子这么漂亮，可以做成一条项链然后送给他心仪的女生~于是他用其中一些珠子做成了长度为n的项链。当他准备把项链首尾相接的时候，土方进来了。
　　“哇这么恶心的项链你也做得出来！！！”
　　盾神自知审美不是他的长项，于是他很谦虚地请教土方，怎么才能把项链做得漂亮。
　　“这个嘛~首先你要在这里加上一个这种颜色的珠子，然后在这里去掉这个珠子，然后……，最后你看看是不是漂亮很多咧~”土方一下子说出了m个修改步骤。
　　盾神觉得这个用人工做太麻烦了，于是交给了你。
输入格式
　　第一行两个数，分别为n，m。
　　第二行n个数，表示盾神一开始的项链。第i个数表示第i颗珠子的颜色。
　　接下来m行，为以下形式之一：
　　ADD P Q：表示在颜色为P的珠子前面加上一个颜色为Q的珠子。
　　DEL P：表示把颜色为P的珠子去掉，如果它不在端点处，则需要把它旁边的两颗珠子连起来。例如某时刻项链状态为1 4 5 8，则执行DEL 4会变成1 5 8，执行DEL 1会变成4 5 8。
　　输入保证在每次操作之前，项链有颜色为P的珠子，且任意时刻珠子颜色互不相同。
输出格式
　　第一行为一个数len，为做完所有操作后，项链的长度。
　　第二行len个数，表示此时项链的状态。第i个数表示第i颗珠子的颜色。
样例输入
10 5
1 2 3 4 5 6 7 8 9 10
DEL 5
ADD 7 5
DEL 10
ADD 4 20
ADD 20 12
样例输出
11
1 2 3 12 20 4 6 5 7 8 9
数据规模和约定
　　表示颜色的数字不超过10^5的正数，1<=n<=10^4，1<=m<=10^4。

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for(int i = 0; i < m; i++) {
        string s;
        cin >> s;
        if(s == "DEL") {
            int p;
            cin >> p;
            for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {
                if(*it == p) {
                    v.erase(it);
                    break;
                }
            }
        }
        if(s == "ADD") {
            int p, q;
            cin >> p >> q;
            for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {
                if(*it == p) {
                    v.insert(it, q);
                    break;
                }
            }
        }
    }
    cout << v.size() << endl;
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

vector<int> v(n);

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

cin >> v[i];

}

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

string s;

cin >> s;

if(s == "DEL") {

int p;

cin >> p;

for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {

if(*it == p) {

v.erase(it);

break;

}

if(s == "ADD") {

int p, q;

cin >> p >> q;

for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {

if(*it == p) {

v.insert(it, q);

break;

}

cout << v.size() << endl;

for(int i = 0; i < v.size(); i++) {

cout << v[i] << " ";

}

return 0;

}

蓝桥杯 ALGO-29 算法训练校门外的树（区间处理）

问题描述
　　某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
　　由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入格式
　　输入文件的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出格式
　　输出文件包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
样例输入
500 3
150 300
100 200
470 471
样例输出
298
数据规模和约定
　　对于20%的数据，区域之间没有重合的部分；
　　对于其它的数据，区域之间有重合的情况。

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int l, m;
	cin >> l >> m;
	vector<int> v(l+1, 1);
	for(int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		for(int j = a; j <= b; j++) {
			v[j] = 0;
		}
	}
	int cnt = 0;
	for(int i = 0; i < l+1; i++) {
		if(v[i] == 1)
			cnt++;
	}
	cout << cnt;
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int l, m;

cin >> l >> m;

vector<int> v(l+1, 1);

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

int a, b;

cin >> a >> b;

for(int j = a; j <= b; j++) {

v[j] = 0;

}

int cnt = 0;

for(int i = 0; i < l+1; i++) {

if(v[i] == 1)

cnt++;

}

cout << cnt;

return 0;

}

蓝桥杯 ALGO-11 算法训练瓷砖铺放（递归/动态规划）

问题描述
　　有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？
　　例如，长度为4的地面一共有如下5种铺法：
　　4=1+1+1+1
　　4=2+1+1
　　4=1+2+1
　　4=1+1+2
　　4=2+2
　　编程用递归的方法求解上述问题。
输入格式
　　只有一个数N，代表地板的长度
输出格式
　　输出一个数，代表所有不同的瓷砖铺放方法的总数
样例输入
4
样例输出
5

分析：用动态规划的方法解：

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> v(n+1);
	v[0] = 1, v[1] = 1;
	for(int i = 2; i <= n; i++) {
		v[i] = v[i-1] + v[i-2];
	}
	cout << v[n];
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n;

cin >> n;

vector<int> v(n+1);

v[0] = 1, v[1] = 1;

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

v[i] = v[i-1] + v[i-2];

}

cout << v[n];

return 0;

}

蓝桥杯ADV-17算法提高统计单词数

问题描述
　　统计输入英文文章段落中不同单词（单词有大小写之分,　　但统计时忽略大小写）各自出现的次数。输入段落中所含单词的总数不超过100，最长单词的长度不超过20个字母.
输入格式
　　一个包含若干句子的段落, 每个句子由若干英文单词组成. 除空格,　　逗号和句号外, 这些输入的句子中不含其他非字母字符, 并且, 逗号和句号紧跟在它前面的英文单词后面, 中间没有空格. 段落最后一个字符是回车符,　　表示输入结束.
输出格式
　　若段落中共有M个不同的英文单词，则按照其在段落中出现的先后顺序输出M行，各行的格式为:　　单词中所有字母均用大写形式输出（最长的单词顶格输出，它前面没有多余的空格;　　其余单词与其右对齐）+冒号+N个*号+该单词在段落中的出现次数N
样例输入
This is a test. This test is easy. This is a test. This test is easy.

样例输出
THIS:****4
IS:****4
A:**2
TEST:****4
EASY:**2
分析：本来想用map映射做的，结果发现必须要根据单词出现的次序排列，而不是按照字典序排列。。所以不能用map了。。所以用了pair类型的vector存储~~虽然题目中说保证逗号和句号之后紧跟空格，结果测试用例骗人。。逗号和句号后面还是有一个空格的。。所以要多加个continue的判断，防止把空格记入单词数里面~还有就是输出的时候是大写字符，要把小写转换成大写再存储进去呢~~

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef pair<string, int> p;
int main() {
    string str;
    vector<p> v;
    getline(cin, str);
    string s;
    int flag2 = 0;
    int maxlen = 0;
    for(int i = 0; i < str.length(); i++) {
        if(flag2 == 1 && str[i] == ' ')
            continue;
        if(str[i] == '.' || str[i] == ' ' || str[i] == ',' ) {
            flag2 = 1;
            int len = s.length();
            maxlen = maxlen > len ? maxlen : len;
            for(int j = 0; j < len; j++) {
                if(s[j] >= 'a' && s[j] <= 'z') {
                    s[j] = s[j] - 32;
                }
            }
            int flag = 0;
            for(int i = 0; i < v.size(); i++) {
                if(v[i].first == s) {
                    v[i].second++;
                    flag = 1;
                }
            }
            if(flag == 0) {
                p temp = make_pair(s, 1);
                v.push_back(temp);
            }
            s = "";
        } else {
            flag2 = 0;
            s += str[i];
        }
    }
    for(int i = 0; i < v.size(); i++) {
        string temp = v[i].first;
        int len = maxlen - temp.length();
        for(int k = 0; k < len; k++) {
            cout << " ";
        }
        cout << v[i].first << ":";
        for(int j = 0; j < v[i].second; j++) {
            cout << "*";
        }
        cout << v[i].second << endl;
    }
    return 0;
}

#include <iostream>

#include <cstdio>

#include <vector>

using namespace std;

typedef pair<string, int> p;

int main() {

string str;

vector<p> v;

getline(cin, str);

string s;

int flag2 = 0;

int maxlen = 0;

for(int i = 0; i < str.length(); i++) {

if(flag2 == 1 && str[i] == ' ')

continue;

if(str[i] == '.' || str[i] == ' ' || str[i] == ',' ) {

flag2 = 1;

int len = s.length();

maxlen = maxlen > len ? maxlen : len;

for(int j = 0; j < len; j++) {

if(s[j] >= 'a' && s[j] <= 'z') {

s[j] = s[j] - 32;

}

int flag = 0;

for(int i = 0; i < v.size(); i++) {

if(v[i].first == s) {

v[i].second++;

flag = 1;

}

if(flag == 0) {

p temp = make_pair(s, 1);

v.push_back(temp);

}

s = "";

} else {

flag2 = 0;

s += str[i];

}

for(int i = 0; i < v.size(); i++) {

string temp = v[i].first;

int len = maxlen - temp.length();

for(int k = 0; k < len; k++) {

cout << " ";

}

cout << v[i].first << ":";

for(int j = 0; j < v[i].second; j++) {

cout << "*";

}

cout << v[i].second << endl;

}

return 0;

}

蓝桥杯 ADV-11 算法提高 Torry的困惑(提高型)

问题描述
　　Torry从小喜爱数学。一天，老师告诉他，像2、3、5、7……这样的数叫做质数。Torry突然想到一个问题，前10、100、1000、10000……个质数的乘积是多少呢？他把这个问题告诉老师。老师愣住了，一时回答不出来。于是Torry求助于会编程的你，请你算出前n个质数的乘积。不过，考虑到你才接触编程不久，Torry只要你算出这个数模上50000的值。
输入格式
　　仅包含一个正整数n，其中n<=100000。
输出格式
　　输出一行，即前n个质数的乘积模50000的值。
样例输入
1
样例输出
2

分析：和leetcode里面那道easy的题目-LeetCode 204. Count Primes方法一样~用v[i]数组标记当前是否为质数，先初始化为都为质数==0，然后只需去除从2到根号n的，从i*i开始的所有i的倍数即可~当然，当当前v[i]已经标记为不是质数的时候，就无需判断它的倍数了，因为例如16是4的倍数的同时，如果已知4是2的倍数，那么16一定是2的倍数~~

#include <iostream>
#define MOD 50000
using namespace std;
int v[2000000];
int main() {
    int n;
    cin >> n;
    for(int i = 2; i * i < 2000000; i++) {
        if(v[i] == 1)
            continue;
        for(int j = i * i; j < 2000000; j = j + i)
                v[j] = 1;
    }
    long long int ans = 1;
    int cnt = 0;
    for(int i = 2; i < 2000000; i++) {
        if(v[i] == 0) {
            ans = (ans * i) % MOD;
            cnt++;
        }
        if(cnt == n)
            break;
    }
    cout << ans;
    return 0;
}

#include <iostream>

#define MOD 50000

using namespace std;

int v[2000000];

int main() {

int n;

cin >> n;

for(int i = 2; i * i < 2000000; i++) {

if(v[i] == 1)

continue;

for(int j = i * i; j < 2000000; j = j + i)

v[j] = 1;

}

long long int ans = 1;

int cnt = 0;

for(int i = 2; i < 2000000; i++) {

if(v[i] == 0) {

ans = (ans * i) % MOD;

cnt++;

}

if(cnt == n)

break;

}

cout << ans;

return 0;

}