蓝桥杯刷题第二十二天

第一题：受伤的皇后

题目描述
有一个 n×n 的国际象棋棋盘（n 行 n 列的方格图），请在棋盘中摆放 n 个受伤的国际象棋皇后，要求：
任何两个皇后不在同一行。
任何两个皇后不在同一列。
如果两个皇后在同一条 45 度角的斜线上，这两个皇后之间行号的差值至少为 3 。
请问一共有多少种摆放方案。
输入描述
输入的第一行包含一个整数 n。
其中，1≤n≤10。
输出描述
输出一个整数，表示答案。

输入

4

输出

2

深搜，对于每一行进行选择

check判断，列是否有

对角线是否有， 如果有，则行差值大于等于三

正对角线 行 + 列 == 该点 行 + 列

反对角线 行- 该点行 == 列 - 该点列

如果是dg,udg数组来表示

dg[x + y], udg[n - x + y]来判断，但是这种是正规皇后

#include<iostream>
using namespace std;const int N = 12;
int a[12];  //表示第i行元素在第几列
int n, ans;bool check(int row, int y){for(int i = 0 ; i < row; i++){if(a[i] == y) return false;if(a[i] + i == row + y && row - i < 3) return false;if(row - i == y - a[i] && row - i < 3) return false;}return true;
}void dfs(int u){if(u == n){ans++;return ;}for(int i = 0; i < n; i++){if(check(u, i)){a[u] = i;dfs(u + 1);a[u] = 0;}  }
}int main(){cin>>n;dfs(0);cout<<ans<<endl;return 0;
}

第二题：完全平方数

问题描述
一个整数 a 是一个完全平方数, 是指它是某一个整数的平方, 即存在一个 整数 b, 使得a=b2 。
给定一个正整数 n, 请找到最小的正整数 x, 使得它们的乘积是一个完全平 方数。
输入格式
输入一行包含一个正整数 n 。
输出格式
输出找到的最小的正整数 x 。
样例输入 1
12
样例输出 1
3
样例输入 2
15
样例输出 2
15
评测用例规模与约定
对于 30 的评测用例, 1≤n≤1000, 答案不超过 1000 。
对于 60 的评测用例, 1≤n≤108, 答案不超过 108 。
对于所有评测用例,1≤n≤1012, 答案不超过 1012 。

一个数是完全平方数，一定有他分解得质因数得指数一定是偶数

所以我们找到指数非偶数的质因数，然后再乘到res里面就得到的最小要乘的数

考察分解质因数

#include <iostream>
using namespace std;typedef long long LL;int main()
{long long n;cin>>n;LL res = 1;for(LL i = 2; i <= n / i; i++)if(n % i == 0){LL s = 0;while( n % i == 0) s ++ , n /= i;if(s % 2) res *= i;}if(n > 1) res *= n;cout<<res<<endl;return 0;
}