CSP-J 2023 题解
T1 小苹果
这个题直接遍历枚举必定 TLE，这是 CCF 的出题风格，每题 T1 巨水无比，但是往往又需要一些思维。
这道题我们可以发现每一轮操作都会拿走 \(1 + (n - 1) / 3\) 个苹果，所以每次让 \(n\) 减去 \(1 + (n - 1) / 3\) 就可以了。
然后记录编号为 \(n\) 什么时候拿的即可。要注意加个 flag 防止重复选择。
#include <bits/stdc++.h>
#define rint register int
#define endl '\n'
#define int long long
int n;
int day, pos;
bool flag;
using namespace std;
signed main()
{
cin >> n;
while (n > 0)
{
day++;
if ((n - 1) % 3 == 0 && !flag)
{
flag = 1;
pos = day;
}
n -= (1 + (n - 1) / 3);
}
cout << day << ' ' << pos << endl;
return 0;
}
T2 公路
这个题难在于怎么想贪心。
到一个加油站的时候，先别加油，因为不知道后面需要多少油。
等到缺油的时候再从之前经过的最便宜的加油站加油。
加油量为 \(sum / d\),\(sum\) 表示还需要走的公里数
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 5;
int a[N];
int v[N];
int n, d;//变量名含义同题
int ans, sum;
signed main()
{
cin >> n >> d;
for (rint i = 1; i < n; i++)
{
cin >> v[i];
}//按题目要求读入
int minn = 1145141919810ll;//随便给一个特别大的数
for (rint i = 1; i < n; i++)
{
cin >> a[i];
sum += v[i];//记录和
minn = min(minn, a[i]);//记录价格最小值
ans += (sum + d - 1) / d * minn;//在向下取整的时候减一是好习惯
sum -= (sum + d - 1) / d * d;//在 CCF 考试题中，计算时无需考虑取整，因为自动向下取整
}
cout << ans << endl;
return 0;
}
T3 一元二次方程
直接按照题目模拟即可，没什么难的，然后有一个比赛小技巧，就是没事儿多看看部分分，有 50pts 的部分分有手就能拿：
针对特殊性质 C
int T;
scanf("%d%*d", &T);
const int N = 2e3;
while (T--)
{
int a, b, c, ans, flag = 0;
cin >> a >> b >> c;
for (rint i = -N; i <= N; i++)
{
if (a * i * i + b * i + c == 0)
{
ans = i;
flag = true;
}
}
if (flag)
{
cout << ans << endl;
}
else puts("NO");
}
有几个注意的要点：
- 1.不一定较大的解是 \(+sqrt(delta)\) 那个解，因为 \(a\) 可能是负数！！！
- 2.约分时注意细节
代码不写了，因为这个傻逼还没过。
T4 公路
个人认为本次 CSP 普及加提高中出的质量最高的一个题，没有之一！真的没想到分层图最短路可以这么考。
分层图问题，即图上每个点要拆分成 \(k\) 个状态，在建图的时候要微调。
在跑 dijkstra 的时候注意，对于原代码中的 \(dist[y] = dist[x] + z\) 更新的时候，要这么写：
z = 1;//不是 z = w[i]
if (dist[x] < w[i]) z += ((w[i] - dist[x] + k - 1) / k) * k;
为什么？当前的边需要的时间是 \(t_1\) 大于目前时间 \(t_2\)，让出发时间延后 \(ceil((t_1 - t_2) / k) * k\) 单位时间。
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e6 + 5;
const int M = 4e6 + 5;
int n, m, k;
int h[N], w[M], e[M], ne[M], idx, dist[M];
bool v[M];
priority_queue<pair<int, int> > q;
void add(int a, int b, int c)
{
e[++idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
q.push(make_pair(0, 1));
while (!q.empty())
{
int x = q.top().second;
q.pop();
if (v[x])
{
continue;
}
v[x] = 1;
for (rint i = h[x]; i; i = ne[i])
{
int y = e[i];
int z = 1;
if (dist[x] < w[i])
{
z += ((w[i] - dist[x] + k - 1) / k) * k;
}
if (dist[y] > dist[x] + z)
{
dist[y] = dist[x] + z;
q.push(make_pair(-dist[y], y));
}
}
}
}
signed main()
{
cin >> n >> m >> k;
for (rint i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
for (rint j = 0; j < k; j++)
{
add(a + j * n, b + ((j + 1) % k) * n, c);
}
}
dijkstra();
if (dist[n] >= 0x3f3f3f3f)
{
cout << -1 << endl;
return 0;
}
cout << dist[n] << endl;
return 0;
}