liuchuo – 第235页 – 我不管，反正我最萌～

蓝桥杯 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;

}

蓝桥杯 ALGO-8 算法训练操作格子（线段树）

问题描述
有n个格子，从左到右放成一排，编号为1-n。
共有m次操作，有3种操作类型：
1.修改一个格子的权值，
2.求连续一段格子权值和，
3.求连续一段格子的最大值。
对于每个2、3操作输出你所求出的结果。
输入格式
第一行2个整数n，m。
接下来一行n个整数表示n个格子的初始权值。
接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。
输出格式
有若干行，行数等于p=2或3的操作总数。
每行1个整数，对应了每个p=2或3操作的结果。
样例输入
4 3
1 2 3 4
2 1 3
1 4 3
3 1 4
样例输出
6
3
数据规模与约定
对于20%的数据n <= 100，m <= 200。
对于50%的数据n <= 5000，m <= 5000。
对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。
分析：用结构体数组建立一棵线段树~当p==1时从上到下更新这个线段树的值，当p==2的时候搜索对应区间内的总和~当p==3的时候搜索对应区间的最大值~

#include <iostream>
#define max(a, b) a > b ? a : b;
using namespace std;

struct node {
    int l;
    int r;
    int maxvalue;
    int sum;
} a[1000000];

void init(int left, int right, int i) {
    a[i].l = left;
    a[i].r = right;
    a[i].maxvalue = 0;
    a[i].sum = 0;
    if(left != right) {
        int mid = (left + right) / 2;
        init(left, mid, 2 * i);
        init(mid + 1, right, 2*i+1);
    }
}

void insert(int i, int j, int value) {
    if(a[i].l == a[i].r) {
        a[i].maxvalue = value;
        a[i].sum = value;
        return ;
    }
    int mid = (a[i].l + a[i].r) / 2;
    if(j <= mid)
        insert(2 * i, j, value);
    else
        insert(2 * i + 1, j, value);
    a[i].maxvalue = max(a[2*i].maxvalue, a[2*i+1].maxvalue);
    a[i].sum = a[2*i].sum + a[2*i+1].sum;
}

int find_sum(int i, int x, int y) {
    if(x == a[i].l && y == a[i].r) {
        return a[i].sum;
    }
    int mid = (a[i].l + a[i].r) / 2;
    if(y <= mid)
        return find_sum(2*i, x, y);
    else if(x > mid)
        return find_sum(2*i+1, x, y);
    else
        return find_sum(2*i, x, mid)+ find_sum(2*i+1, mid+1, y);
}

int find_max(int i, int x, int y) {
    if(x == a[i].l && y == a[i].r) {
        return a[i].maxvalue;
    }
    int mid = (a[i].l + a[i].r) / 2;
    if(y <= mid)
        return find_max(2*i, x, y);
    else if(x > mid)
        return find_max(2*i+1, x, y);
    else
        return max(find_max(2*i, x, mid), find_max(2*i+1, mid+1, y));
}


int main() {
    int n, m;
    cin >> n >> m;
    init(1, n, 1);
    int value;
    for(int j = 1; j <= n; j++) {
        cin >> value;
        insert(1, j, value);
    }
    for(int k = 0; k < m; k++) {
        int p, x, y;
        cin >> p >> x >> y;
        if(p == 1)
            insert(1, x, y);
        if(p == 2)
            cout << find_sum(1, x, y) << endl;
        if(p == 3)
            cout << find_max(1, x, y) << endl;
    }
    return 0;
}

#include <iostream>

#define max(a, b) a > b ? a : b;

using namespace std;

struct node {

int l;

int r;

int maxvalue;

int sum;

} a[1000000];

void init(int left, int right, int i) {

a[i].l = left;

a[i].r = right;

a[i].maxvalue = 0;

a[i].sum = 0;

if(left != right) {

int mid = (left + right) / 2;

init(left, mid, 2 * i);

init(mid + 1, right, 2*i+1);

}

void insert(int i, int j, int value) {

if(a[i].l == a[i].r) {

a[i].maxvalue = value;

a[i].sum = value;

return ;

}

int mid = (a[i].l + a[i].r) / 2;

if(j <= mid)

insert(2 * i, j, value);

else

insert(2 * i + 1, j, value);

a[i].maxvalue = max(a[2*i].maxvalue, a[2*i+1].maxvalue);

a[i].sum = a[2*i].sum + a[2*i+1].sum;

}

int find_sum(int i, int x, int y) {

if(x == a[i].l && y == a[i].r) {

return a[i].sum;

}

int mid = (a[i].l + a[i].r) / 2;

if(y <= mid)

return find_sum(2*i, x, y);

else if(x > mid)

return find_sum(2*i+1, x, y);

else

return find_sum(2*i, x, mid)+ find_sum(2*i+1, mid+1, y);

}

int find_max(int i, int x, int y) {

if(x == a[i].l && y == a[i].r) {

return a[i].maxvalue;

}

int mid = (a[i].l + a[i].r) / 2;

if(y <= mid)

return find_max(2*i, x, y);

else if(x > mid)

return find_max(2*i+1, x, y);

else

return max(find_max(2*i, x, mid), find_max(2*i+1, mid+1, y));

}

int main() {

int n, m;

cin >> n >> m;

init(1, n, 1);

int value;

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

cin >> value;

insert(1, j, value);

}

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

int p, x, y;

cin >> p >> x >> y;

if(p == 1)

insert(1, x, y);

if(p == 2)

cout << find_sum(1, x, y) << endl;

if(p == 3)

cout << find_max(1, x, y) << endl;

}

return 0;

}

蓝桥杯ALGO-125算法训练王、后传说(回溯、递归)

问题描述
　　地球人都知道，在国际象棋中，后如同太阳，光芒四射，威风八面，它能控制横、坚、斜线位置。
看过清宫戏的中国人都知道，后宫乃步步惊心的险恶之地。各皇后都有自己的势力范围，但也总能找到相安无事的办法。
所有中国人都知道，皇权神圣，伴君如伴虎，触龙颜者死……
现在有一个n*n的皇宫，国王占据他所在位置及周围的共9个格子，这些格子皇后不能使用（如果国王在王宫的边上，占用的格子可能不到9个）。当然，皇后也不会攻击国王。
现在知道了国王的位置（x,y）（国王位于第x行第y列，x,y的起始行和列为1），请问，有多少种方案放置n个皇后，使她们不能互相攻击。
输入格式
　　一行，三个整数，皇宫的规模及表示国王的位置
输出格式
　　一个整数，表示放置n个皇后的方案数
样例输入
8 2 2
样例输出
10
数据规模和约定
　　n<=12

分析：和n皇后问题一样，一样的套路…..加一个判定当前是否为国王的领地就可以~
pos[i]存放的是第i行的皇后所在的位置
递归以行的形式递归，每次放置的皇后要判断是否与前面已经放置的皇后冲突
从pos[row] = 0开始一直到n-1，判断是否安全如果安全就进行下一行的摆放
每次递归到row==n的时候表示当前所有n个皇后已经摆放完成
这是一个深度优先的过程，从在第一行放在第一个位置开始，摆放第二行、第三行…直到最后一行。
然后pos[row]++,表示将第一行放在第二个位置…然后摆放第二行、第三行…直到最后一行……
直到所有的情况深度优先搜索完成。

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int n, x, y;
int cnt = 0;

bool issafe(vector<int> &pos, int row) {
    for(int i = 0; i < row; i++) {
        if(pos[i] == pos[row] || abs(pos[i] - pos[row]) == abs(i - row)) {
            return false;
        }
    }
    return true;
}

void dfs(vector<int> &pos, int row) {
    if(row == n) {
        cnt++;
        return ;
    }
    for(pos[row] = 0; pos[row] < n; pos[row]++) {
        if((pos[row] == y-2 || pos[row] == y-1 || pos[row] == y) && (row == x-2 || row == x-1 || row == x))
            continue;
        if(issafe(pos, row)) {
            dfs(pos, row + 1);
        }
    }
}

int main(){
    cin >> n >> x >> y;
    vector<int> pos(n);
    dfs(pos, 0);
    cout << cnt;
    return 0;
}

#include <iostream>

#include <cmath>

#include <vector>

using namespace std;

int n, x, y;

int cnt = 0;

bool issafe(vector<int> &pos, int row) {

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

if(pos[i] == pos[row] || abs(pos[i] - pos[row]) == abs(i - row)) {

return false;

}

return true;

}

void dfs(vector<int> &pos, int row) {

if(row == n) {

cnt++;

return ;

}

for(pos[row] = 0; pos[row] < n; pos[row]++) {

if((pos[row] == y-2 || pos[row] == y-1 || pos[row] == y) && (row == x-2 || row == x-1 || row == x))

continue;

if(issafe(pos, row)) {

dfs(pos, row + 1);

}

int main(){

cin >> n >> x >> y;

vector<int> pos(n);

dfs(pos, 0);

cout << cnt;

return 0;

}

蓝桥杯 ALGO-116 算法训练最大的算式

问题描述
题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：
N=5，K=2，5个数字分别为1、2、3、4、5，可以加成：
1*2*(3+4+5)=24
1*(2+3)*(4+5)=45
(1*2+3)*(4+5)=45
……
输入格式
输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中（2<=N<=15, 0<=K<=N-1）。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。
输出格式
输出文件仅一行包含一个整数，表示要求的最大的结果
样例输入
5 2
1 2 3 4 5
样例输出
120
样例说明
(1+2+3)*4*5=120
分析：用动态规划解决。设sum[i]为前i个数的总和，那么从j到k的总和为sum[k]-sum[j-1]。设dp[i][j]表示前i个数中有j个乘号的最大的结果。则要想知道dp[i][j]，可以尝试从第二个数的前面一直到最后一个数的前面依次添加乘号，将最大的结果保存至dp[i][j]中。就可以得到状态转移方程为：dp[i][j] = max(dp[i][j], dp[l-1][j-1] * (sum[i] – sum[l-1]));l为插入相乘的两个数的后一个数字的坐标。

#include <iostream>
using namespace std;
#define max(a, b) a > b ? a : b;
long long int dp[16][16];
int sum[16];

int main() {
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        int temp;
        cin >> temp;
        sum[i] =  sum[i-1] + temp;
    }
    for(int i = 1; i <= n; i++) {
        dp[i][0] = sum[i];
    }
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j <= i-1 && j <= k; j++) {
            for(int l = 2; l <= n; l++) {
                dp[i][j] = max(dp[i][j], dp[l-1][j-1] * (sum[i] - sum[l-1]));
            }
        }
    }
    cout << dp[n][k];
    return 0;
}

#include <iostream>

using namespace std;

#define max(a, b) a > b ? a : b;

long long int dp[16][16];

int sum[16];

int main() {

int n, k;

cin >> n >> k;

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

int temp;

cin >> temp;

sum[i] = sum[i-1] + temp;

}

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

dp[i][0] = sum[i];

}

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

for(int j = 1; j <= i-1 && j <= k; j++) {

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

dp[i][j] = max(dp[i][j], dp[l-1][j-1] * (sum[i] - sum[l-1]));

}

cout << dp[n][k];

return 0;

}