国赛2021-纯质数
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如果一个正整数只有 1 和它本身两个约数，则称为一个质数（又称素数）。
前几个质数是：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, · · ·。
如果一个质数的所有十进制数位都是质数，我们称它为纯质数。例如2,3,5,7,23,37 都是纯质数，而 11, 13, 17, 19, 29, 31不是纯质数。当然 1, 4, 35也不是纯质数。
请问，在 11 到 20210605中，有多少个纯质数？
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
这是一个填空题，直接输出答案 1903 就行，直接暴力解决。下面是计算的代码。
#include <iostream>
using namespace std;
const int N = 20210605;
bool prime[N + 10];
bool isprime(int x) {
if (x < 2) return false;
for (int i = 2; i * i <= x; i++)
if (x % i == 0) return false;
return true;
}
bool ischun(int n) {
while (n) {
int t = n % 10;
if (t == 1 || t == 4 || t == 6 || t == 8 || t == 9 || t == 0)
return false;
n /= 10;
}
return true;
}
int main() {
int res = 0;
for (int i = 2; i < N; i++) {
if (isprime(i) && ischun(i)) {
res++;
}
}
cout << res << endl;
return 0;
}
2021省赛-最小筹码
问题描述
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意 小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。
输入格式
输入包含一个正整数 N。
输出格式
输出一个整数代表答案。
样例输入
7
样例输出
3
样例说明
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4(天平一边放 6 ，另一边放 4 ）；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。
评测用例规模与约定
对于所有评测用例，1 ≤ N ≤ 1000000000。
似乎是比较简单的贪心，为啥我是看了题解才勉强会写呢...
贪心思路：
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
LL cnt;
LL sum;
LL res;
int main() {
LL n;
cin >> n;
for (int i = 0; i < 0x3f3f3f; i++) {
sum += pow(3, i);
if (sum >= n) {
res = i;
break;
}
}
cout << res + 1 << endl;
return 0;
}
2021模拟赛-灌溉
题目描述
小蓝负责花园的灌溉工作。
花园可以看成一个 n 行 m 列的方格图形。中间有一部分位置上安装有出水管。
小蓝可以控制一个按钮同时打开所有的出水管，打开时，有出水管的位置可以被认为已经灌溉好。
每经过一分钟，水就会向四面扩展一个方格，被扩展到的方格可以被认为已经灌溉好。即如果前一分钟某一个方格被灌溉好，则下一分钟它上下左右的四个方格也被灌溉好。
给定花园水管的位置，请问 k 分钟后，有多少个方格被灌溉好？
输入描述
输入的第一行包含两个整数 n, m。
第二行包含一个整数 t ，表示出水管的数量。
接下来 t 行描述出水管的位置，其中第 i 行包含两个数 r, c 表示第 r 行第 c 列有一个排水管。
接下来一行包含一个整数 k。
其中，1 \leq n, m \leq 100, 1 \leq t \leq 10, 1 \leq k \leq 1001≤n,m≤100,1≤t≤10,1≤k≤100。
输出描述
输出一个整数，表示答案。
输入输出样例
示例 1
输入
3 6
2
2 2
3 4
1
输出
9
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;
const int N = 110;
// 偏移量
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
// 队列
typedef pair<int, int> PII;
queue<PII> q;
bool watered[N][N];
int n, m, t, k;
int cnt;
void water() {
// 第一个元素
auto sign = q.front();
q.push(q.front());
do {
auto t = q.front();
for (int i = 0; i < 4; i++) {
int x = t.x + dx[i];
int y = t.y + dy[i];
// 如果越界
if (x < 0 || x > n || y < 0 || y > m) continue;
// 如果已经灌溉过了
if (watered[x][y]) continue;
// 如果没有
watered[x][y] = true;
cnt++;
q.push({x, y});
}
q.pop();
} while (q.front() != sign);
}
int main() {
scanf("%d%d%d", &n, &m, &t);
while (t--) {
int r, c;
scanf("%d%d", &r, &c);
watered[r][c] = true;
q.push({r, c});
cnt++;
}
scanf("%d", &k);
// 每一个 k 就是一次灌溉的过程
while (k--) {
water();
}
printf("%d", cnt);
return 0;
}