题目链接:http://dluacm.cn/wp-content/uploads/2023/11/202311zhengshi.pdf
补题链接:https://ac.nowcoder.com/acm/contest/69510
难度预测
Check-in:C
Easy:A,M
Easy-Medium:I,K
Medium:B,L,E
Medium-Hard:D,H,J
Hard:G,F
统计
A:43/74
B:5/63
C:48/3
D:2/40
E:4/51
F:5/11
G:0/21
H:0/57
I:17/22
J:3/49
K:10/61
L:4/9
M:35/196
problem A 加训时间!
根据题意可知,答案为数组最大值*n。
problem B 爆wa种子!
对于形如\space y=ax^2+bx+c\space的函数方程只可能有三种情况:
- 抛物线,由于数据保证a\ge 0,所以必定开口向上,那么此时最低点x坐标可以由\Large\frac{-b}{2a}得到再代入方程\space y=ax^2+bx+c\space即可得到最小值
- 一条平行于x轴的直线
- 一条既不平行于y轴也不平行于x轴的直线
如果出现情况3,答案只能是负无穷。
如果没出现过情况3,则对情况1以及情况2求出的最低点取min即可。
problem C 晚上不睡觉
输出a\cdot b的错误答案即可。例如可以直接输出-1或a\cdot b+1。
problem D 书生的负数
当将所有数字相加,数字之和大于-n时将除最后一个数之外的所有数改为-1,最后一个数为非负数,输出n-1;
否则所有的数都可以改为负数,输出n。
problem E 明天
把tomorrow的子串全部提取出来,存到map中,每次判断即可。
#include <bits/stdc++.h>
using namespace std ;
int main()
{
ios::sync_with_stdio(false) ;
cin.tie(nullptr) ;
map<string, bool> mp ;
string T = "tomorrow" ;
for(int i = 0; i < 8; ++ i)
for(int j = i; j < (!i ? 7 : 8); ++ j)
mp[T.substr(i, j - i + 1)] = 1 ;
int Q ; cin >> Q ;
while(Q --)
{
string s ; cin >> s ;
cout << (mp.count(s) ? "yes" : "no") << '\n' ;
}
return 0 ;
}
problem F 跳棋
观察到如果有任意两个棋子相邻,整个棋盘的位置都能被跳到,枚举一下判断是否有棋子相邻即可。
#include <bits/stdc++.h>
using namespace std ;
using ll = long long ;
int main()
{
ios::sync_with_stdio(false) ;
cin.tie(nullptr) ;
int n ; string s ; cin >> n >> s ;
for(int i = 0; i < n - 1; ++ i)
if(s[i] == 'X' && s[i + 1] == 'X')
return cout << n << '\n', 0 ;
int ans = 0 ;
for(int i = 0; i < n; ++ i) ans += s[i] == 'X' ;
cout << ans << '\n' ;
return 0 ;
}
problem G 河流管理
并查集。
每一次打开挡板,便将当前的河段与下一段河流合并,然后跳到下一段尚未与当前河段合并的河流继续合并。
#include <bits/stdc++.h>
using namespace std ;
const int N = 5e5 + 5 ;
int n, q ;
int a[N], fa[N], nxt[N] ;
int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]) ; }
int main()
{
ios::sync_with_stdio(false) ;
cin.tie(nullptr) ;
cin >> n >> q ;
for(int i = 1; i <= n; ++ i) cin >> a[i] ;
for(int i = 1; i <= n; ++ i) fa[i] = i, nxt[i] = i + 1 ;
while(q --)
{
int opt ; cin >> opt ;
if(opt == 1)
{
int l, r, g ; cin >> l >> r ;
while((g = nxt[get(l)]) <= r)
{
int fl = get(l), fr = get(g) ;
fa[fl] = fr ;
a[fr] = max(a[fr], a[fl]) ;
l = g ;
}
}
else
{
int x ; cin >> x ;
cout << a[get(x)] << '\n' ;
}
}
return 0 ;
}
problem H 冒险
观察到背包内物品体积成指数级增长,所以背包内物品个数在log\ k级别。
假设背包内要放入x个物品,显然那么一定是放入前x小的物品,且优先放体积较小的物品。
排序后暴力枚举选多少个物品即可。
#include <bits/stdc++.h>
using namespace std ;
#define ll long long
const int N = 1e6 + 5, M = 20 ;
const ll INF = 1e18 ;
int n, k, a[N] ;
ll f[M] ;
int main()
{
ios::sync_with_stdio(false) ;
cin >> n >> k ;
for(int i = 1; i <= n; ++ i) cin >> a[i] ;
sort(a + 1, a + n + 1) ;
int ans = 0 ;
for(int i = 0; i <= min(M - 1, n); ++ i)
{
ll t = 0 ;
for(int j = 1; j <= i; ++ j)
t += a[j] * (1ll << (i - j)) ;
if(t <= k) ans = i ;
}
cout << ans << '\n' ;
return 0 ;
}
problem I 妙wa种子!
由于每段对于答案的贡献是该段中的最大值,那么最优方案就是选出这些数中前k大的数求和。
我们先选出前k大的数,以这些前k大的数为起点不断往左、右扩张,直到这些前k个数所在段能覆盖整个数组,就划分出了每段。
problem J 货币系统
由裴蜀定理可得a, b, c能凑出的最小正整数为gcd(a,b,c),所以判断gcd(a, b, c)是否为1即可。
problem K 从南到北II
读入字符串,从0到n-3逐个比对,每一位和后面两位是否是“hui”和“hen”,如果为“hui”和“hen”则将这三位改为0,最后输出非0的字符即可。
problem L 选拔
找到每个数组的最大值,然后把剩下的放进一个数组a里。由于之前已经选了n个数组的最大值,所以还需选出m-n个,将数组a按降序排序后选出前m-n个即可。
problem M 远方
如果所有的建筑物都不会挡住enterdawn的视线,即x > \max_{i=1}^n y时,输出yes,否则输出no。
#include <bits/stdc++.h>
using namespace std ;
int main()
{
ios::sync_with_stdio(false) ;
cin.tie(nullptr) ;
int n, x, y, maxv = -1 ; cin >> n >> x ;
for(int i = 1; i <= n; ++ i)
{
cin >> y ;
maxv = max(maxv, y) ;
}
cout << (x > maxv ? "yes" : "no") << '\n' ;
return 0 ;
}