题目链接：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 ;
}