mxt.log
← 返回竞赛经历算法竞赛 / Codeforces

1119_div3

刷题

#算法竞赛

A. Moo Language School

Problem: A. Moo Language School

Contest: Codeforces - Codeforces Round 1119 (Div. 3)

URL: https://codeforces.com/contest/2259/problem/A

Memory Limit: 256 MB

Time Limit: 1000 ms

Powered by CP Editor (https://cpeditor.org)

解题思路

本题题面还是比较清晰的，总体目标是要求k个农场中，至少需要选择一块土地建立学校，如果土地属于Nhoj（字符为‘1’）需要支付代价，属于Jhon（字符为’0’）则不需要支付代价。

则我们只需要统计每个农场中是否存在’0’即可，有’0’则该块土地可建学校，不需要支付代价

因为1<=k<=n<=20数据规模不大，所以直接暴力枚举，遍历k个农场即可

代码如下：

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        string s;
        cin >> n >> k >> s;
        int ans = 0;
        for (int i = 0; i < n; i += k) {
            bool hasZero = false;
            for (int j = i; j < i + k; ++j) {
                if (s[j] == '0') {
                    hasZero = true;
                    break;
                }
            }
            if (!hasZero) ans++;
        }
        cout << ans << '\n';
    }
    return 0;
}

时间：O(n)需要遍历整个农场（最坏情况为每块土地均为Nhoj，则需遍历n）

空间：O(n)线性存储空间，存

Problem: B. Minus Two

Problem: B. Minus Two

Contest: Codeforces - Codeforces Round 1119 (Div. 3)

URL: https://codeforces.com/contest/2259/problem/B

Memory Limit: 256 MB

Time Limit: 2000 ms

Powered by CP Editor (https://cpeditor.org)

解题思路

题面说，可以对数组中的数进行任意次数操作，使得x=|x-2|，那么如果是奇数，不管操作多少次结果都为1；如果是偶数，如果是4的倍数，经过奇数次操作后结果为2，偶数次操作后结果为0；如果是2的倍数，经过奇数次操作后结果为0，偶数次操作后结果为2。

那么我们只需要比较三者中的数量，然后取最大值即可

代码如下：

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int odd = 0, mod4_0 = 0, mod4_2 = 0;
        for (int i = 0; i < n; ++i) {
            long long x;
            cin >> x;
            if (x & 1) {
                odd++;
            } else {
                if (x % 4 == 0) mod4_0++;
                else mod4_2++; 
            }
        }
        cout << max({odd, mod4_0, mod4_2}) << '\n';
    }
    return 0;
}

时间：O(n)，遍历每个数组

空间：O(n)，存储每一个数

Problem: C. 101

Problem: C. 101

Contest: Codeforces - Codeforces Round 1119 (Div. 3)

URL: https://codeforces.com/contest/2259/problem/C

Memory Limit: 256 MB

Time Limit: 2000 ms

Powered by CP Editor (https://cpeditor.org)

解题思路

题面说可以将数组中的-1变成0/1，使得数组子数组存在最长的a[l]=a[r]=1,a[l r]=0,r−l+1a[l]=a[r]=1,a[l~r]=0,r-l+1最长

那么我们需要考虑-1的位置，如果-1位于数组开头或结尾，且在首个-1左边，最后一个-1右边均无1存在，那么将此-1转为1，存在延长子数组的可能，如果-1在数组中间部分，左侧右侧有1，那么一旦将-1转为1，则会将原本数组分割，所以将1~1中间的-1转为0可以得到最优解

代码如下

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n;i++) cin >> a[i];
		int l=0,r=0;
		for(int i=0;i<n;i++){
			if(a[i]==1)l++;
			if(a[i]==-1&&l==0){
				a[i]=1;
				break;
			}
		}
		for(int i=n-1;i>-1;i--){
			if(a[i]==1)r++;
			if(a[i]==-1&&r==0){
				a[i]=1;
				break;
			}
		}
		for(auto i:a){
			cout<<max(i,0)<<' ';
		}
		cout<<'\n';
    }
    return 0;
}