ZZJC新生训练赛第四场题解
ZZJCACM新生训练赛 - 2024.10.16
题目难度
- Easy(简单): B, C, D, G
- Medium(中等): A, E
- Anti-AK(防AK): E
C题解题思路
A页既可以是彩印也可以是黑白印，B页只能是彩印，所以只要比较A页彩印和A页黑白印的价格高低就好。
因为 a, b, x, y 最大都是 1e9，用 int 直接相乘的话会爆掉，所以要开 long long。
C题代码
#include<bits/stdc++.h>
#define int long long
const int N = 1e6 + 10;
using namespace std;
void matt(){
int a, b, x, y;
cin >> a >> b >> x >> y;
cout << min((a + b) * y, a * x + b * y) << '\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0); // 加快 cin, cout 输入输出速度
int T = 1;
cin >> T;
while (T--)
{
matt();
}
return 0;
}
D题解题思路
有一部分人一道题都没对的情况下 AK 的人最多。
D题代码
#include<bits/stdc++.h>
#define int long long
const int N = 1e6 + 10;
using namespace std;
void matt(){
int a, b, c;
cin >> a >> b >> c;
cout << c / a;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
matt();
}
return 0;
}
B题解题思路
根据题意，要让怪兽血量扣得最多，伤害越高的药水最先使用。注意怪兽血量要向下取整。
B题代码
#include<bits/stdc++.h>
#define int long long
const int N = 1e6 + 10;
using namespace std;
int a[10];
void matt(){
int n, ans;
cin >> n >> a[0] >> a[1] >> a[2];
sort(a, a + 3);
ans = n;
for (int i = 2; i >= 0; i--)
{
int x = ans - ans * 0.01 * a[i]; // int 自动会向下取整
ans = x;
}
cout << n - ans;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
matt();
}
return 0;
}
G题解题思路
根据题意直接对 l 和 r 开根号，数一下两者之间有几个数字。注意 x 要向上取整，y 要向下取整。
G题代码
#include<bits/stdc++.h>
// #define int long long
const int N = 1e5 + 10;
using namespace std;
void matt(){
int l, r;
cin >> l >> r;
int x = ceil(sqrt(l));
int y = sqrt(r);
cout << y - x + 1 << '\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while (T--)
{
matt();
}
return 0;
}
A题解题思路
如果直接暴力枚举的话肯定会超时。
所以我们记录前面没被删除的字符串，碰到 'c' 和 'b'，去寻找前面那个没被删除的字符，判断是否需要删除。
A题代码
#include<bits/stdc++.h>
#define int long long
const int N = 1e6 + 10;
using namespace std;
int a[N] = {0}; // 数组 a 用来记录前面没被删除的字符的下标位置
void matt(){
int n, ans = 1; // ans 是数组 a 存放字符的个数
string s;
cin >> n >> s;
for (int i = 1; i < n; i++)
{
if (s[i] == 'c' && s[a[ans - 1]] == 'f' || s[i] == 'b' && s[a[ans - 1]] == 't') ans--; // 判断是否需要删除，如果需要 ans 减一
else a[ans++] = i; // 如果不需要，将 s[i] 字符的下标添加到 a 中
}
cout << ans;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
matt();
}
return 0;
}
F题解题思路
当找到右括号的时候寻找左括号个数，其中任意一个都可以和当前右括号匹配。注意取余。
F题代码
#include<bits/stdc++.h>
#define int long long
const int N = 1e6 + 10, mod = 1e9 + 7;
using namespace std;
void matt(){
string s;
cin >> s;
int n = s.size(), ans = 0, sum = 1;
for (int i = 0; i < n; i++)
{
if (s[i] == '(') ans++;
else{
sum *= ans;
sum %= mod;
ans--;
}
}
cout << sum;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
matt();
}
return 0;
}
E题解题思路
经典模拟题，根据题意用结构体 CPU 存储进程号，到达时间等信息，用优先队列 priority_queue 存储已经到达的进程号。每当一个进程号到达的时候，去判断前面到达的进程号的完成情况。
E题代码
#include<bits/stdc++.h>
#define int long long
const int N = 2e4 + 10;
using namespace std;
struct CPU
{
int cjh, ddsj, zxsj, yxj;
bool operator<(const CPU &x) const
{
if (x.yxj == yxj) return ddsj > x.ddsj;
else return yxj < x.yxj;
}
}; // 创建一个结构体，存储进程号等信息，并且在优先队列里面根据题意排序
void matt(){
int a, b, c, d;
priority_queue<CPU> qe; // 创建一个优先队列 qe
int t = 0;
while (cin >> a >> b >> c >> d) // 输入数据
{
while (!qe.empty() && b >= t + qe.top().zxsj){
t += qe.top().zxsj;
cout << qe.top().cjh << ' ' << t << '\n';
qe.pop();
} // 当队列非空情况下，将在此进程号到达之前的已经完成的进程号输出
if (qe.empty()){
qe.push({a, b, c, d});
t = b;
} // 当队列为空的情况下，将数据输入 qe
else {
if (d > qe.top().yxj){
CPU tmp = qe.top();
tmp.zxsj -= b - t;
qe.pop();
qe.push(tmp);
qe.push({a, b, c, d});
t = b;
} // 当输入的进程号的优先级大于当前正在进行的进程号时，优先进行操作
else qe.push({a, b, c, d}); // 否则直接将数据输入 qe
}
}
while (!qe.empty())
{
t += qe.top().zxsj;
cout << qe.top().cjh << ' ' << t << '\n';
qe.pop();
} // 将队列中剩余数据输出
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
matt();
}
return 0;
}