视频题解

• A、下雨 0:47--2:08
• B、川超 2:21--7:23
• C、涂色 7:39--13:47
• D、报数 14:03--19:51
• E、分组 20:20--34:03
• F、偶数 34:20--54:43

---

A. 下雨

按照题意判断即可

#include <bits/stdc++.h>
using namespace std;

int main() {
	int a, b; cin >> a >> b;
    if(a + b == 0) {
        cout << "No";
        return 0;
    }
    cout << (a * 3 <= b? "Yes" : "No");
}

B. 川超

不可能的情况：$n < 4 || m < 4 ||n + m < 11$

否则对两个数组从大到小排序，各自的前 $4$ 位必选，接下来的 $3$ 位存在于 $a_5\sim a_7$（如有） 与 $b_5\sim b_7$（如有），再排序选最大的 $3$ 个即可。

#include <bits/stdc++.h>
using namespace std;
int a[100005], b[100005];
int main() {
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];
    if(n < 4 || m < 4 || n + m < 11) {
        cout << -1 << endl;
        return 0;
    }
    sort(a + 1, a + 1 + n, greater<int>());
    sort(b + 1, b + 1 + m, greater<int>());
    long long ans = 0;
    for(int i = 1; i <= 4; i++) ans += a[i] + b[i];
    int k[10] = {}, cnt = 0;
    for(int i = 5; i <= min(n, 7); i++) k[++cnt] = a[i];
    for(int i = 5; i <= min(m, 7); i++) k[++cnt] = b[i];
    sort(k + 1, k + 1 + cnt, greater<int>());
    for(int i = 1; i <= 3; i++) ans += k[i];
    cout << ans << endl;
}

C. 涂色

题意是说每次都必须涂连续的 $3$ 个长度。

因此找到字符串中所有 $1$ 所在的段，若其长度 $<3$ 则说明不可能。

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t; cin >> t;
	while(t--) {
	    int n;
	    string s; cin >> n >> s;
	    int f = 1;
	    for(int i = 0; i < n; i++) {
	        if(s[i] == '0') continue;
	        int len = 1;
	        while(i + 1 < n && s[i + 1] == '1') {
	            i++;
	            len++;
	        }
	        if(len < 3) {
	            cout << "No" << endl;
	            f = 0;
	            break;
	        }
	    }
	    if(f)
	        cout << "Yes" << endl;
	}

}

D. 报数

- 30pts:

枚举即可

- 100pts:

写下前几组数字观察规律，每 $8$ 个为一组，分别以 $15$ 递增

#include <iostream>
using namespace std;

int main()
{
    long long n; cin >> n;
    long long a[10] = {0, 1, 2, 4, 7, 8, 11, 13, 14};
    // 16 17 19 22 23 26 28 29
    if(n % 8 == 0) cout << n / 8 * 15 - 1;
    else cout << n / 8 * 15 + a[n % 8];
    return 0;
}

E. 分组

对原数据进行奇偶分组，奇数可以合并为偶数，反之则不能。当奇偶数量越平衡时分组越多，否则就以奇数组为限。

#include <iostream>
using namespace std;
int main()
{
	int n;
    cin >> n; int a[2] = {};
	for(int i = 0; i < n; i ++ ){
		int x;cin >> x;
		a[x & 1] ++ ;
	}
	while(a[0] < a[1])
	{
		a[1] -= 2;
		a[0] ++ ;
	}
	if(a[0] == a[1]) cout << a[0] + a[1] << endl;
	else if(a[0] > a[1]) cout << a[1] * 2 + 1 << endl;
    return 0;
}

F. 偶数

- 30pts:

注意到要做修改也一定是将奇数改为偶数。预处理 $1\sim i$ 每个前缀子段的偶数个数 $b[i]$ ，再枚举每个奇数位置，遍历所有子数组统计个数。

- 100pts:

先计算出不做操作时的答案：注意到只有连续奇数的一段不会对答案产生任何贡献，所以可以从总数 $\frac{n\times(n+1)}2$ 中减去连续奇数段对应的子数组的数量。同时统计出最长的连续奇数段长度 $k$。

再考虑进行一次操作，那一定是在最长的连续奇数段的中间位置进行修改，依照长度分为奇偶两种情况。

• 当 $k$ 为奇数时，将最中间的奇数修改为偶数，则从长度为 $k$ 的奇数段变为 $[\frac{k}2$ 的奇数，偶数，$\frac{k}2$ 的奇数$]$，此时增加的段数：$\frac{k\times(k+1)}2-\frac{\frac{k}2\times(\frac{k}2+1)}2\times 2$
• 当 $k$ 为偶数时，将中间的奇数修改为偶数，则从长度为 $k$ 的奇数段变为 $[\frac{k}2-1$ 的奇数，偶数，$\frac{k}2$ 的奇数$]$，此时增加的段数：$\frac{k\times(k+1)}2-\frac{\frac{k}2\times(\frac{k}2+1)}2-\frac{(\frac{k}2-1)\times(\frac{k}2)}2$

#include <bits/stdc++.h>

using namespace std;
#define ll long long
ll A[200005];

int main() {

    ll t;
    cin >> t;

    while (t--) {
        ll n;
        cin >> n;
        ll oddCount = 0;

        for (ll i = 0; i < n; i++) {
            cin >> A[i];
            if (A[i] % 2 != 0) {
                ++oddCount;
            }
        }
        
        ll ans = (n * (n + 1)) / 2;
        ll k = 0;

        if (oddCount <= 1) {
            cout << ans << endl;
            continue;
        } else {

            ll c = 0;
            for (ll i = 0; i < n; i++) {
                if (A[i] % 2 != 0) {
                    c++;
                    k = max(k, c);
                } else {
                    ans -= (c * (c + 1)) / 2;
                    c = 0;
                }
            }
            ans -= (c * (c + 1)) / 2;
        }
        if(k & 1) 
            ans += k * (k + 1) / 2 -  (k / 2) * (k / 2 + 1);
        
        else 
            ans += k * (k + 1) / 2 -
            (k / 2) * (k / 2 + 1) / 2 -
            (k / 2 - 1) * (k / 2) / 2;
        cout << ans << endl;
    }
}