题解_牛客博客

problem A 加训时间！

根据题意可知，答案为数组最大值 $*n$ 。

problem B 爆wa种子!

对于形如 $\space y=ax^2 bx c\space$ 的函数方程只可能有三种情况：

抛物线，由于数据保证 $a\ge 0$ ，所以必定开口向上，那么此时最低点 $x$ 坐标可以由 $\frac{-b}{2a}$ 得到再代入方程 $\space y=ax^2 bx c\space$ 即可得到最小值
一条平行于 $x$ 轴的直线
一条既不平行于 $y$ 轴也不平行于 $x$ 轴的直线

如果出现情况3，答案只能是负无穷。

如果没出现过情况3，则对情况1以及情况2求出的最低点取 $min$ 即可。

problem C 晚上不睡觉

输出 $a*b$ 的错误答案即可。例如可以直接输出 $-1$ 或 $a*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 ;
}