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

蓝桥杯 ADV-203 算法提高 8皇后·改(八皇后问题)

问题描述
规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。
输入格式
一个8*8的棋盘。
输出格式
所能得到的最大数字和
样例输入
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
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
样例输出
260
数据规模和约定
棋盘上的数字范围0~99

#include <iostream>
#include <cmath>
using namespace std;
int maxvalue = 0;
int pic[8][8];

bool issafe(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 dfs(int pos[], int row) {
    if(row == 8) {
        int sum = 0;
        for(int i = 0; i < 8; i++) {
            sum += pic[i][pos[i]];
        }
        maxvalue = sum > maxvalue ? sum : maxvalue;
        return ;
    }
    for(pos[row] = 0; pos[row] < 8; pos[row]++) {
        if(issafe(pos, row)) {
            dfs(pos, row + 1);
        }
    }
}

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

#include <iostream>

#include <cmath>

using namespace std;

int maxvalue = 0;

int pic[8][8];

bool issafe(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 dfs(int pos[], int row) {

if(row == 8) {

int sum = 0;

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

sum += pic[i][pos[i]];

}

maxvalue = sum > maxvalue ? sum : maxvalue;

return ;

}

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

if(issafe(pos, row)) {

dfs(pos, row + 1);

}

int main() {

int pos[8];

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

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

cin >> pic[i][j];

}

dfs(pos, 0);

cout << maxvalue;

return 0;

}

蓝桥杯 BASIC-19 基础练习完美的代价

问题描述
回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是：交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文！完美！)
输入格式
第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
第二行是一个字符串，长度为N.只包含小写字母
输出格式
如果可能，输出最少的交换次数。
否则输出Impossible
样例输入
5
mamad
样例输出
3
分析：过程见代码注释部分。其中有两个注意点：
1.impossible的情况：如果有一个字符出现的次数是奇数次数，而且n是偶数，那么不可能构成回文
如果n是奇数，但是已经有一个字符出现的次数是奇数次数了，那么如果又有一个字符是奇数次数，就不可能构成回文。
2.如果n是奇数，计算中间那个字符交换的次数的时候，不需要模拟把这个数移动到中间去，因为移动到中间的话假设有一对数都在左边或者都在右边，
那么交换成回文的时候就要经过中间，就会每次把cnt多加了1，而这个1是没有必要的，因为可以所有的回文移动完了之后再把这个独立的奇数移动过去，才能保证交换次数最少。

#include <iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int j = n - 1;
	int cnt = 0;//cnt用来统计交换的次数
	int flag = 0;//flag判断是否已经有一个单独的奇个数的字符了
	for(int i = 0; i < j; i++) {//i指针从头遍历到倒数第二个字符
		for(int k = j; k >= i; k--) {//k指针从后面往前一直到i寻找和s[i]相同的s[k]
			if(k == i) {//如果找不到相同的
				if(n % 2 == 0 || flag == 1) {//impossible的两种情况
					cout << "Impossible";
					return 0;
				}
				flag = 1;
				cnt += n / 2 - i;
			} else if(s[k] == s[i]) {
				for(int l = k; l < j; l++) {
					swap(s[l], s[l+1]);//把s[k]换到s[j]处
					cnt++;//统计交换次数
				}
				j--;
				break;
			}
		}
	}
	cout << cnt;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

string s;

cin >> s;

int j = n - 1;

int cnt = 0;//cnt用来统计交换的次数

int flag = 0;//flag判断是否已经有一个单独的奇个数的字符了

for(int i = 0; i < j; i++) {//i指针从头遍历到倒数第二个字符

for(int k = j; k >= i; k--) {//k指针从后面往前一直到i寻找和s[i]相同的s[k]

if(k == i) {//如果找不到相同的

if(n % 2 == 0 || flag == 1) {//impossible的两种情况

cout << "Impossible";

return 0;

}

flag = 1;

cnt += n / 2 - i;

} else if(s[k] == s[i]) {

for(int l = k; l < j; l++) {

swap(s[l], s[l+1]);//把s[k]换到s[j]处

cnt++;//统计交换次数

}

j--;

break;

}

cout << cnt;

return 0;

}

蓝桥杯 ALGO-126 算法训练水仙花

问题描述
判断给定的三位数是否水仙花数。所谓水仙花数是指其值等于它本身每位数字立方和的数。例 153 就是一个水仙花数。 153=13+53+33
输入格式
一个整数。
输出格式
是水仙花数,输出”YES”,否则输出”NO”(不包括引号)
样例输入
123
样例输出
NO
数据规模和约定
一个三位的整数,否则输出”NO”

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    int a = 0;
    int sum = 0;
    for(int i = 0; i < s.length(); i++) {
        int temp = s[i] - '0';
        a = a * 10 + temp;
        sum += (temp * temp * temp);
    }
    if(sum == a) {
        cout << "YES";
    } else {
        cout << "NO";
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

cin >> s;

int a = 0;

int sum = 0;

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

int temp = s[i] - '0';

a = a * 10 + temp;

sum += (temp * temp * temp);

}

if(sum == a) {

cout << "YES";

} else {

cout << "NO";

}

return 0;

}

蓝桥杯 BASIC-18 基础练习矩形面积交

问题描述
平面上有两个矩形，它们的边平行于直角坐标系的X轴或Y轴。对于每个矩形，我们给出它的一对相对顶点的坐标，请你编程算出两个矩形的交的面积。
输入格式
输入仅包含两行，每行描述一个矩形。
在每行中，给出矩形的一对相对顶点的坐标，每个点的坐标都用两个绝对值不超过10^7的实数表示。
输出格式
输出仅包含一个实数，为交的面积，保留到小数后两位。
样例输入
1 1 3 3
2 2 4 4
样例输出
1.00
分析：先把两个矩形的坐标都变成从左下角的到右上角的顺序~然后判断是否这两个矩形不重合~然后将所有的横坐标x排序，取中间两个的差值为重合面积的一条边的长度~然后将所有的纵坐标y排序，取中间两个的差值为重合面积的另一条边的长度~然后得重合面积的值~

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    double x1, y1, x2, y2, x3, y3, x4, y4;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    if(x1 > x2)
        swap(x1, x2);
    if(y1 > y2)
        swap(y1, y2);
    if(x3 > x4)
        swap(x3, x4);
    if(y3 > y4)
        swap(y3, y4);
    if((x2 < x3 && x1 < x3) || (y2 < y3 && y1 < y3) || (x4 < x1 && x3 > x1) || (y4 < y1 && y3 < y1)) {
        cout << "0.00";
        return 0;
    }
    double a[4] = {x1, x2, x3, x4};
    double b[4] = {y1, y2, y3, y4};
    sort(a, a+4);
    sort(b, b+4);
    double area = (a[2] - a[1]) * (b[2] - b[1]);
    printf("%.2f", area);
    return 0;
}

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int main() {

double x1, y1, x2, y2, x3, y3, x4, y4;

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

if(x1 > x2)

swap(x1, x2);

if(y1 > y2)

swap(y1, y2);

if(x3 > x4)

swap(x3, x4);

if(y3 > y4)

swap(y3, y4);

if((x2 < x3 && x1 < x3) || (y2 < y3 && y1 < y3) || (x4 < x1 && x3 > x1) || (y4 < y1 && y3 < y1)) {

cout << "0.00";

return 0;

}

double a[4] = {x1, x2, x3, x4};

double b[4] = {y1, y2, y3, y4};

sort(a, a+4);

sort(b, b+4);

double area = (a[2] - a[1]) * (b[2] - b[1]);

printf("%.2f", area);

return 0;

}

蓝桥杯 BASIC-17 基础练习矩阵乘法

问题描述
　　给定一个N阶矩阵A，输出A的M次幂（M是非负整数）
　　例如：
　　A =
　　1 2
　　3 4
　　A的2次幂
　　7 10
　　15 22
输入格式
　　第一行是一个正整数N、M（1<=N<=30, 0<=M<=5），表示矩阵A的阶数和要求的幂数
　　接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值
输出格式
　　输出共N行，每行N个整数，表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开
样例输入
2 2
1 2
3 4
样例输出
7 10
15 22

分析：竟然有一个！0次幂！矩阵的零次冥要输出单位矩阵！。。。（小柳柳卒，享年20）。。。

#include <iostream>
using namespace std;
long long int b[40][40];
int main() {
    int n, m;
    cin >> n >> m;
    long long int a[40][40];
    long long int t[40][40];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> a[i][j];
            t[i][j] = a[i][j];
        }
    }
    if(m == 0) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i != j) {
                    cout << 0 << " ";
                } else {
                    cout << 1 << " ";
                }
            }
            cout << endl;
        }
        return 0;
    }
    while(--m) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int k = n;
                while(k) {
                    b[i][j] += t[i][k-1] * a[k-1][j];
                    k--;
                }
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                t[i][j] = b[i][j];
                b[i][j] = 0;
            }
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cout << t[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

long long int b[40][40];

int main() {

int n, m;

cin >> n >> m;

long long int a[40][40];

long long int t[40][40];

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

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

cin >> a[i][j];

t[i][j] = a[i][j];

}

if(m == 0) {

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

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

if(i != j) {

cout << 0 << " ";

} else {

cout << 1 << " ";

}

cout << endl;

}

return 0;

}

while(--m) {

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

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

int k = n;

while(k) {

b[i][j] += t[i][k-1] * a[k-1][j];

k--;

}

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

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

t[i][j] = b[i][j];

b[i][j] = 0;

}

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

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

cout << t[i][j] << " ";

}

cout << endl;

}

return 0;

}

蓝桥杯 BASIC-16 基础练习分解质因数

问题描述
求出区间[a,b]中所有整数的质因数分解。
输入格式
输入两个整数a，b。
输出格式
每行输出一个数的分解，形如k=a1*a2*a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出
3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5
提示
先筛出所有素数，然后再分解。
数据规模和约定
2<=a<=b<=10000

#include <iostream>
using namespace std;
int isprime(int n) {
    if(n <= 1)
        return 0;
    else if(n == 2 || n == 3)
        return 1;
    else {
        for(int i = 2; i * i < n; i++) {
            if(n % i == 0) {
                return 0;
            }
        }
        return 1;
    }
}
int main() {
    int a, b;
    cin >> a >> b;
    for(int i = a; i <= b; i++) {
        int temp = i;
        cout << i << "=";
        int flag = 0;
        while(temp != 1) {
            for(int j = 2; j <= temp; j++) {
                if(isprime(j) && temp % j == 0) {
                    temp = temp / j;
                    if(flag == 1)
                        cout << "*";
                    cout << j;
                    flag = 1;
                    break;
                }
            }
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int isprime(int n) {

if(n <= 1)

return 0;

else if(n == 2 || n == 3)

return 1;

else {

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

if(n % i == 0) {

return 0;

}

return 1;

}

int main() {

int a, b;

cin >> a >> b;

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

int temp = i;

cout << i << "=";

int flag = 0;

while(temp != 1) {

for(int j = 2; j <= temp; j++) {

if(isprime(j) && temp % j == 0) {

temp = temp / j;

if(flag == 1)

cout << "*";

cout << j;

flag = 1;

break;

}

cout << endl;

}

return 0;

}