模拟赛SXJ202507270900比赛记录&题解
<h1 id="题目请看"><mark>题目请看</mark></h1><h2 id="t1">T1</h2>
<p>贪心：主要考察<span class="math inline">\(<50\%\)</span>时<span class="math inline">\(差值\ mod \ 2 \neq 0\)</span>与<span class="math inline">\(>50\%\)</span>时<span class="math inline">\(差值\ mod \ 3 \neq 0\)</span>的情况</p>
<p><span class="math inline">\(\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}\)</span></p>
<p><span class="math inline">\(
\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}
\)</span></p>
<details>
<summary>贴一下代码</summary>
<pre><code>#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;
}
</code></pre>
</details>
<blockquote>
<p>赛时：100point</p>
<p>赛后：无</p>
</blockquote>
<h2 id="t2">T2</h2>
<p>一道大模拟题目，主在于找到<span class="math inline">\(max\)</span>并分配给下一位</p>
<blockquote>
<p>漏了情况<mark>qwq</mark></p>
</blockquote>
<details>
<summary>贴一下代码</summary>
<pre><code>#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, 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;
}
</code></pre>
</details>
<blockquote>
<p>赛时：50point</p>
<p>赛后：100point</p>
</blockquote>
<h2 id="t3">T3</h2>
<p>有三种可能：</p>
<p><span class="math inline">\(
\left\{
\begin{aligned}
&1在依赖链：依赖链往前排放 \\
&1固定位置：输出固定的位置编号\\&1无约束：依赖链往后排放
\end{aligned}
\right.
\)</span></p>
<blockquote>
<p>以后要多做这类题目</p>
</blockquote>
<details>
<summary>贴一下代码（有点乱，大佬别在意）</summary>
<pre><code>#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, prefix, c, p, a, t, 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] = c;
t] = 1;
if (c == 1) {
cout << p;
return 0;
}
}
if (flag) {
for (int i = 1; i <= n; i ++) {
if (a == yilai)l ++;
else if (!a && !t]) {
l ++;
a = yilai;
if (yilai == 1) {
cout << i;
return 0;
}
}
}
} else {
for (int i = n; i > 0 ;i --) {
if (a == yilai) {
m --;
} else if (!a && m > 0 && !t]) {
a = yilai;
}
}
for (int i = 1; i <= n; i ++) {
if (!a) {
cout << i;
return 0;
}
}
}
return 0;
}
</code></pre>
</details>
<blockquote>
<p>赛时：60point</p>
<p>赛后：100point</p>
</blockquote>
<h2 id="t4">T4</h2>
<p>一道数据结构的题目，题目要求我们用链式前向星建一棵树，接着对每次充能进行搜索。</p>
<p>这里要<mark>注意</mark>的是：</p>
<p>朴素做法就是每次输入进行一次dfs，但时间超限，代码如下：</p>
<pre><code class="language-cpp">while (q --) {
int p;
ll x;
cin >> p >> x;
dfs(p, fa, x);
}
</code></pre>
<p><span style="color: rgba(255, 165, 0, 1)">可惜：TLE 40point</span></p>
<p>正确做法就是每次把充能值在根节点相加，那么根节点的叶子节点都会有<span class="math inline">\(父亲节点+自己单独的充能\)</span></p>
<details>
<summary>贴一下代码</summary>
<pre><code>#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, tot = 0, fa;
ll val;
struct Edge {
int to, nxt;
} tree;
void link(int x, int y) {
tot ++;
tree.to = y;
tree.nxt = head;
head = tot;
}
void dfs(int u, int root) {
for (int i = head; i; i = tree.nxt) {
int v = tree.to;
if (v == root) {
continue ;
}
val += 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 = u;
}
while (q --) {
int p;
ll x;
cin >> p >> x;
val += x;
// dfs(p, fa, x);
}
dfs(1, -1);
for (int i = 1; i <= n; i ++) {
cout << val << " ";
}
return 0;
}
</code></pre>
</details>
<p><span style="color: rgba(0, 128, 0, 1)">喜获AC</span></p>
<blockquote>
<p>赛时：40point</p>
<p>赛后：100point</p>
</blockquote>
<h2 id="t5">T5</h2>
<p>一道dp版题，背包问题</p>
<details>
<summary>贴一下代码，题目不是我出的，这只是标程</summary>
<pre><code>#include<bits/stdc++.h>
using namespace std;
int dp;
struct choose {
int w6, w9;
} w;
int main() {
freopen("bank.in", "r", stdin);
freopen("bank.out", "w", stdout);
int n;
cin >> n;
w.w6 = w.w9 = 1;
memset(dp, 127, sizeof(dp));
dp = 0;
int cnt = 0;
while (pow(6, ++cnt) <= n) w.w6 = pow(6, cnt);
w.w6 = pow(6, cnt);
cnt = 0;
while (pow(9, ++cnt) <= n) w.w9 = pow(9, cnt);
w.w9 = pow(9, cnt);
for (int i = 1; i <= n; i++) {
for (int j = 0; w.w6 <= i; j++)
dp = min(dp, dp.w6] + 1);
for (int j = 0; w.w9 <= i; j++)
dp = min(dp, dp.w9] + 1);
}
cout << dp;
}
</code></pre>
</details>
<blockquote>
<p>赛时：10point</p>
<p>赛后：100point</p>
</blockquote><br><br>
来源：https://www.cnblogs.com/KevinSystemOlineJudge/p/19013279
頁:
[1]