模拟赛SXJ202507270900比赛记录&题解

字母哥大脚王

题目请看

T1

贪心：主要考察\(<50\%\)时\(差值\ mod \ 2 \neq 0\)与\(>50\%\)时\(差值\ mod \ 3 \neq 0\)的情况

\(\begin{cases} \text{计算 } cha = 50 - n \\ \text{如果 } cha \bmod 2 \neq 0 \text{ 则} \\ \quad \text{输出 } \left\lceil \dfrac{cha}{2} \right\rceil + 1 \\ \text{否则} \\ \quad \text{输出 } \dfrac{cha}{2} \\ \end{cases}\)

\( \begin{cases} \quad \text{计算 } cha = n - 50 \\\quad \begin{cases} \text{如果 } cha \bmod 3 = 1 \text{ 则} & \text{输出 } \dfrac{cha - 1}{3} + 2 \\ \text{如果 } cha \bmod 3 = 2 \text{ 则} & \text{输出 } \dfrac{cha - 2}{3} + 4 \\ \text{如果 } cha \bmod 3 = 0 \text{ 则} & \text{输出 } \dfrac{cha}{3} \\ \end{cases} \\ \end{cases} \)

贴一下代码

#include <bits/stdc++.h>
using namespace std;
#define fre(c) freopen(c".in","r",stdin);freopen(c".out","w",stdout);
#define ll long long
#define endl "\n"
#define ios ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define cst const
int t, jia = 2, jian = 3;
ll read() {
	char c;
	ll sum = 0;
	int f = 1;
	c = getchar();
	while (!isdigit(c)) {
		if (c == '-')
			f *= -1;
		c = getchar();
	}
	while (isdigit(c)) {
		sum = sum * 10 + (c - '0');
		c = getchar();
	}
	return sum * f;
}
void fun() {
	int n;
	cin >> n;
	if (n == 50) {
		cout << "0" << endl;
	}
	if (n < 50) {
		int cha = 50 - n;
		if (cha % jia != 0) {
			cha += jian;
			cout << cha / 2 + 1 << endl;
		} else {
			cout << cha / 2 << endl;
		}
	}
	if (n > 50) {
		int cha = n - 50;
		if (cha % jian == 1) {
			cout << (cha - 1) / jian + 2 << endl;
		}
		if (cha % jian == 2) {
			cout << (cha - 2) / jian + 4 << endl;
		}
		if (cha % jian == 0) {
			cout << cha / jian << endl;
		}
	}
}
int main() {
	ios
//	fre("3")
	fre("light")
	cin >> t;
	while (t --) {
		fun();
	}
	return 0;
}

赛时：100point

赛后：无

T2

一道大模拟题目，主在于找到\(max\)并分配给下一位

漏了情况qwq

贴一下代码

#include <bits/stdc++.h>
using namespace std;
#define fre(c) freopen(c".in","r",stdin);freopen(c".out","w",stdout);
#define ll long long
#define endl "\n"
#define ios ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define cst const
cst int N = 1e3 + 5;
int n, t, music[N], mid, y = 0, x = 0, ma, ans;
int main(){
	ios
	fre("music")
	cin >> n >> t;	
	for (int i = 1; i <= n; i ++) {
		cin >> music;
	}
	while (t --) {
		for (int i = 1; i <= n; i ++) {
			if(i == ans){
				music = 0;
			} else {
				music += mid;
				if(i <= y) 
					music ++;
			}
			if(music > ma){
				ma = music;
				x = i;
			}
		}
		ans = x;
		mid = ma / (n - 1);
		y = ma % (n - 1);
		if(ans <= y) y ++;
		ma = 0;
		cout << ans << endl;	
	}
	return 0;
}

赛时：50point

赛后：100point

T3

有三种可能：

\( \left\{ \begin{aligned} &1在依赖链：依赖链往前排放 \\ &1固定位置：输出固定的位置编号\\&1无约束：依赖链往后排放 \end{aligned} \right. \)

以后要多做这类题目

贴一下代码（有点乱，大佬别在意）

#include <bits/stdc++.h>
using namespace std;
#define fre(c) freopen(c".in","r",stdin);freopen(c".out","w",stdout);
#define ll long long
#define endl "\n"
#define ios ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define cst const
cst int N = 1e2 + 5;
int n, m, k, yilai[N], prefix[N], c[N], p[N], a[N], t[N], cnt = 0, l = 0;
bool flag = false;
ll read() {
	char c;
	ll sum = 0;
	int f = 1;
	c = getchar();
	while (!isdigit(c)) {
		if (c == '-')
			f *= -1;
		c = getchar();
	}
	while (isdigit(c)) {
		sum = sum * 10 + (c - '0');
		c = getchar();
	}
	return sum * f;
}
int main() {
	ios
	fre("task")
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i ++) {
		a = t = 0;
	}
	for (int i = 1; i <= m; i ++) {
		cin >> yilai;
		if (yilai == 1) {
			flag = true;
		}
	}
	for (int i = 1; i <= k; i ++) {
		cin >> c >> p;
		a[p] = c;
		t[c] = 1;
		if (c == 1) {
			cout << p;
			return 0;
		}
	}
	if (flag) {
		for (int i = 1; i <= n; i ++) {
			if (a == yilai[l + 1])l ++;
			else if (!a && !t[yilai[l + 1]]) {
				l ++;
				a = yilai[l];
				if (yilai[l] == 1) {
					cout << i;
					return 0;
				}
			}
		}
	} else {
		for (int i = n; i > 0 ;i --) {
			if (a == yilai[m]) {
				m --;
			} else if (!a && m > 0 && !t[yilai[m]]) {
				a = yilai[m --];
			}
		}
		for (int i = 1; i <= n; i ++) {
			if (!a) {
				cout << i;
				return 0;
			}
		}
	}
	return 0;
}

赛时：60point

赛后：100point

T4

一道数据结构的题目，题目要求我们用链式前向星建一棵树，接着对每次充能进行搜索。

这里要注意的是：

朴素做法就是每次输入进行一次dfs，但时间超限，代码如下：

while (q --) {
	int p;
	ll x;
	cin >> p >> x;
	dfs(p, fa[p], x);
}

可惜：TLE 40point

正确做法就是每次把充能值在根节点相加，那么根节点的叶子节点都会有\(父亲节点+自己单独的充能\)

贴一下代码

#include <bits/stdc++.h>
using namespace std;
#define fre(c) freopen(c".in","r",stdin);freopen(c".out","w",stdout);
#define ll long long
#define endl "\n"
#define ios ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define cst const
cst int N = 2 * 1e5 + 5;
int n, q, head[N], tot = 0, fa[N];
ll val[N];
struct Edge {
	int to, nxt;
} tree[N * 2];
void link(int x, int y) {
	tot ++;
	tree[tot].to = y;
	tree[tot].nxt = head[x];
	head[x] = tot;
}
void dfs(int u, int root) {
	for (int i = head; i; i = tree.nxt) {
		int v = tree.to;
		if (v == root) {
			continue ;
		}
		val[v] += val;
		dfs(v, u);
	}
}
int main() {
	ios
	fre("tree")
	cin >> n >> q;
	for (int i = 1; i <= n - 1; i ++) {
		int u, v;
		cin >> u >> v;
		link(u, v);
		link(v, u);
		fa[v] = u;
	}
	while (q --) {
		int p;
		ll x;
		cin >> p >> x;
		val[p] += x;
//		dfs(p, fa[p], x);
	}
	dfs(1, -1);
	for (int i = 1; i <= n; i ++) {
		cout << val << " ";
	}
	return 0;
}

喜获AC

赛时：40point

赛后：100point

T5

一道dp版题，背包问题

贴一下代码，题目不是我出的，这只是标程

#include<bits/stdc++.h>
using namespace std;
int dp[1000005];
struct choose {
	int w6, w9;
} w[100005];
int main() {
	freopen("bank.in", "r", stdin);
	freopen("bank.out", "w", stdout);
	int n;
	cin >> n;
	w[0].w6 = w[0].w9 = 1;
	memset(dp, 127, sizeof(dp));
	dp[0] = 0;
	int cnt = 0;
	while (pow(6, ++cnt) <= n) w[cnt].w6 = pow(6, cnt);
	w[cnt].w6 = pow(6, cnt);
	cnt = 0;
	while (pow(9, ++cnt) <= n) w[cnt].w9 = pow(9, cnt);
	w[cnt].w9 = pow(9, cnt);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; w[j].w6 <= i; j++)
			dp = min(dp, dp[i - w[j].w6] + 1);
		for (int j = 0; w[j].w9 <= i; j++)
			dp = min(dp, dp[i - w[j].w9] + 1);
	}
	cout << dp[n];
}

赛时：10point

赛后：100point

来源：https://www.cnblogs.com/KevinSystemOlineJudge/p/19013279