第四届（2025）青少年编程挑战赛C++入门组题解

#include <bits/stdc++.h>
using namespace std;

int main() {
	long long n, a, m;
	cin >> n >> a;
	m = n * a;
	cout << m;
	return 0;
}

#include <bits/stdc++.h>
#define R register
#define us unsigned
#define ll long long
using namespace std;

bool solve(ll n) { //判断是否为质数
	if (n <= 1)
		return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)
			return false;
	}
	return true;
}

int main() {
	ll l, r;
	cin >> l >> r;
	ll b = sqrtl(l), e = sqrtl(r); //l和r之间的平方数的平方根
	bool flag = false;
	for (ll i = b; i <= e; i++) {
		if (i * i < l)
			continue;
		if (i * i > r)
			break;
		ll t = i * i, sum = 0;
		while (t) { //数位分解
			sum += t % 10;
			t /= 10;
		}
		if (solve(sum)) {
			cout << i *i << " "; //答案
			flag = true;
		}
	}
	if (!flag)
		cout << 0; //无解

	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long //记得开long long
ll a[200005]; //记得开long long
ll b[200005]; //记得开long long
ll c[500005]; //记得开long long
ll d[500005]; //记得开long long

int main() {
	int n, m, q, k;
	cin >> n >> m >> q >> k;

	int op, x;
	for (int i = 1; i <= q; i++) {
		cin >> op >> x;
		if (op == 1) {
			a[x]++;
			if (a[x] == k)
				a[x] = 0;
		} //去除重复在k次以上的部分
		else {
			b[x]++;
			if (b[x] == k)
				b[x] = 0;
		} //去除重复在k次以上的部分
	}
	ll ans1 = 0, ans2 = 0, ans;
	for (int i = 1; i <= n; i++)
		if (a[i] > 0) {
			ans1++; //统计去除后有多少被涂色的行
			c[a[i]]++; //用桶存储被涂色过a[i]次的行
		}
	for (int i = 1; i <= m; i++)
		if (b[i] > 0) {
			ans2++; //统计去除后有多少被涂色的列
			d[b[i]]++; //用桶存储被涂色过b[i]次的列
		}
	ans = ans1 * m + ans2 * n - ans1 * ans2; //公式计算
	for (int i = 1, j = k - 1; i <= k - 1, j >= 1; i++, j--)
		ans -= c[i] * d[j]; //去除涂色次数加和为k的交叉格
	cout << ans << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1003;


//face= 0-西 1-东 2-北 3-南
//根据当前朝向 face，计算下一步的坐标变化。
const int dx[] = {0, 0, -1, 1}; //face=0,1,2,3时的方向值,左右和上下
const int dy[] = {-1, 1, 0, 0};


//转向后的新方向
const int turnLeft[] = {3, 2, 0, 1}; //face=0,1,2,3时
const int turnRight[] = {2, 3, 1, 0};

struct node {
	int x, y, face, step; //位置 面对的方向，步数
} st, en, now, nx; //起点 终点 当前点 下一点

int maze[N][N], vis[N][N][4]; //迷宫地图,状态标记数组(位置和面对的方向)
int n, m, ans = -1;

void bfs() {
	queue<node> q;
	st.step = 0;
	vis[st.x][st.y][st.face] = 1;
	q.push(st);
	while (!q.empty()) {
		now = q.front(), q.pop();
		if (now.x == en.x && now.y == en.y) {
			ans = now.step;
			return;
		}
		nx = now; //准备直走
		for (int i = 1; i <= 3; i++) { //沿着当前方向走i步
			nx.x += dx[now.face], nx.y += dy[now.face];
			//某处走不了时，不能再继续前行
			if (nx.x < 1 || nx.y < 1 || nx.x >= n || nx.y >= m || maze[nx.x][nx.y])
				break;//此路不通
			if (vis[nx.x][nx.y][nx.face])
				continue;//该状态扩展过了
			//注意此处，边界处不可走(0~n行 0~m列)
			vis[nx.x][nx.y][nx.face] = 1;
			nx.step = now.step + 1;//走一步
			q.push(nx);
		}
		nx = now, nx.step = now.step + 1; //准备转换方向
		nx.face = turnLeft[now.face];//左转
		if (!vis[nx.x][nx.y][nx.face]) {
			vis[nx.x][nx.y][nx.face] = 1;
			q.push(nx);
		}
		nx.face = turnRight[now.face];//右转
		if (!vis[nx.x][nx.y][nx.face]) {
			vis[nx.x][nx.y][nx.face] = 1;
			q.push(nx);
		}

	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) //读入格子的值
		for (int j = 1; j <= m; j++) {
			int a;
			scanf("%d", &a);
			if (a) { //该格子为障碍(i,j视为格子右下角坐标)，则障碍的四个点均不可走
				maze[i][j] = maze[i - 1][j - 1] = maze[i - 1][j] = maze[i][j - 1] = 1;
			}
		}
	scanf("%d%d%d%d %c", &st.x, &st.y, &en.x, &en.y, &st.face);
	st.face = (st.face == 'W' ? 0 : (st.face == 'E' ? 1 : (st.face == 'N' ? 2 : 3))); //w-0 E-1 N-2 S-3
	bfs();
	if (ans == -1)
		printf("-1\n");
	else
		printf("%d\n", ans);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct node {
	int u, v;
	double w;
} a[5000000];
int n, f[5000000], cnt, k, l;
int x[5000000], y[5000000];

void add(int uu, int vv, double ww) { //uu到vv的距离为ww
	a[++cnt].u = uu;
	a[cnt].v = vv;
	a[cnt].w = ww;
}

bool cmp(node a1, node a2) {
	return a1.w < a2.w;
}

int find(int u) { //并查集
	if (f[u] == u)
		return u;
	else
		return f[u] = find(f[u]);
}

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		f[i] = i;
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &x[i], &y[i]);
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++) { //把任意两个野人的距离存起来
			double s = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
			add(i, j, s);
		}
	sort(a + 1, a + cnt + 1, cmp); //排序
	for (int i = 1; i <= cnt; i++) {
		int uu = find(a[i].u);
		int vv = find(a[i].v);
		if (uu == vv)
			continue;   //边连的两点在同一个部落，跳过
		f[uu] = vv;            //连起来
		l++;
		if (l == n - k + 1) {  //第n-k+1条边为答案
			printf("%.2lf", a[i].w);
			return 0;
		}
	}
	return 0;
}