蓝桥杯 – 第32页 – 柳婼の blog

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

}

蓝桥杯 ADV-206 算法提高不大的数

问题描述
在当今的大数据时代，超大数的高精度计算已经成为众多领域的热门研究之一。现在T校也想在此领域有所造诣已造福于全社会，然而由于时间有限，所以短时间内难以找出大数计算的通用算法，于是学校找到了同学中的“神霸”——你来帮忙，并仅要求你能在数并不算大的时候给出结果。又出于某种特殊需要，也并不要求你给出数的全部结果，而只是要求结果的前10位（注意不是后10位），并考虑到2的幂次的特殊性和典型性，所以要你计算的数均为2的幂次。
输入格式
一个自然数n。
输出格式
2的n次幂的前10位。
样例1 输入
60
样例1 输出
1152921504
样例2 输入
60000
样例2 输出
6305794870
数据规模和约定
0<=n<=10000000
注释
=。=
分析：本来想用位运算。。后来发现做不出来。。然后换了种方法做，AC了~
1.当乘以2的次数超过或者等于34次的时候，就会超过10位数字。用一个double型变量保存要求的数，然后再最后转为long long int 型。(至于为什么要用double型，因为第二步的除以1000相当于乘以1024，为了避免失去精度使得除法运算后的结果被转为int后不精准~~)为了防止超过10位数字，这个时候可以采取除法的方式让它位数控制在double的不溢出范围之内~~
2.已知2的10次方是1024，也就是说对于每一个是10的倍数i，就相当于给要求的数增加了1024倍，这个时候可以采取除以1000的方式保证它不溢出~
3.但是因为数据规模太大了，有一千万大小，所以每一个1024/1000=1.024，当乘以1.024的个数超过97次方的时候(1.024^97 = 9.979201547674)，就会等于让要求的数乘以了10.为了保证不溢出，可以在乘以了每970个2的时候，让要求的数除以10保证不会溢出~（如果想要更精准的可以用计算器得到：1.024^97.1 = 10.00289683498）就是每乘以971个2后除以10~
4.此时用上述办法得到的数如果在数据规模大的时候可能会有10位或者11位，这时候可以统计一下这个double型数字的位数，然后进行除以10的运算把它变为前面只有10位数。
5.此时转换为long long int型输出即可~

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    double t = 1.0;
    for(int i = 1; i <= n; i++) {
        t = t * 2;
        if(i >= 34 && i % 10 == 0) {
            t = t / 1000;
        }
        if(i % 971 == 0) {
            t = t / 10;
        }
    }
    long long int temp = t;
    int sum = 0;
    while(temp) {
        temp = temp / 10;
        sum++;
    }
    while(sum > 10) {
        t = t / 10;
        sum--;
    }
    long long int d = t;
    printf("%lld", d);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

double t = 1.0;

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

t = t * 2;

if(i >= 34 && i % 10 == 0) {

t = t / 1000;

}

if(i % 971 == 0) {

t = t / 10;

}

long long int temp = t;

int sum = 0;

while(temp) {

temp = temp / 10;

sum++;

}

while(sum > 10) {

t = t / 10;

sum--;

}

long long int d = t;

printf("%lld", d);

return 0;

}

蓝桥杯 BASIC-27 基础练习 2n皇后问题

问题描述
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0

分析：和n皇后问题一样，只不过2n皇后要用两个深度优先搜索。
调用放置白皇后的递归dfs，先放置白皇后，当每一个白皇后放置成功之后，在递归的return语句之前，
新建一个棋盘，复制原来的棋盘后并把放置了白皇后的位置置为0，调用摆放黑皇后的深度优先搜索。
当黑皇后也找到相应的解法后，cnt++; 最后输出cnt的值。

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int cnt = 0;

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

void blackdfs(vector<vector<int> > blackpic, vector<int> blackpos, int n, int blackrow) {
    if(blackrow == n) {
        cnt++;
        return ;
    }
    for(blackpos[blackrow] = 0; blackpos[blackrow] < n; blackpos[blackrow]++) {
        if(blackpic[blackrow][blackpos[blackrow]] == 1 && issafe(blackpic, blackpos, blackrow)) {
            blackdfs(blackpic, blackpos, n, blackrow + 1);
        }
    }
}


void dfs(vector<vector<int> > pic, vector<int> pos, int n, int row) {
    if(row == n) {
        vector<vector<int> > blackpic(n, vector<int>(n));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                blackpic[i][j] = pic[i][j];
            }
        }
        for(int i = 0; i < n; i++) {
            blackpic[i][pos[i]] = 0;
        }
        vector<int> blackpos(n);
        blackdfs(blackpic, blackpos, n, 0);
        return ;
    }
    for(pos[row] = 0; pos[row] < n; pos[row]++) {
        if(pic[row][pos[row]] == 1 && issafe(pic, pos, row)) {
            dfs(pic, pos, n, row + 1);
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<vector<int> > pic(n, vector<int>(n));
    vector<int> pos(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> pic[i][j];
        }
    }
    dfs(pic, pos, n, 0);
    cout << cnt;
    return 0;
}

#include <iostream>

#include <cmath>

#include <vector>

using namespace std;

int cnt = 0;

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

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

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

return false;

}

return true;

}

void blackdfs(vector<vector<int> > blackpic, vector<int> blackpos, int n, int blackrow) {

if(blackrow == n) {

cnt++;

return ;

}

for(blackpos[blackrow] = 0; blackpos[blackrow] < n; blackpos[blackrow]++) {

if(blackpic[blackrow][blackpos[blackrow]] == 1 && issafe(blackpic, blackpos, blackrow)) {

blackdfs(blackpic, blackpos, n, blackrow + 1);

}

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

if(row == n) {

vector<vector<int> > blackpic(n, vector<int>(n));

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

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

blackpic[i][j] = pic[i][j];

}

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

blackpic[i][pos[i]] = 0;

}

vector<int> blackpos(n);

blackdfs(blackpic, blackpos, n, 0);

return ;

}

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

if(pic[row][pos[row]] == 1 && issafe(pic, pos, row)) {

dfs(pic, pos, n, row + 1);

}

int main() {

int n;

cin >> n;

vector<vector<int> > pic(n, vector<int>(n));

vector<int> pos(n);

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

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

cin >> pic[i][j];

}

dfs(pic, pos, n, 0);

cout << cnt;

return 0;

}