A. Odd Eraser

Problem: A. Odd Eraser

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

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

Memory Limit: 256 MB

Time Limit: 1000 ms

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

解题思路

最开始的想法是直接模拟删除奇数，后来发现首位和末尾的数是永远不会被删除的，所以直计算首尾两个数的最大公约数即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        cout << __gcd(a[0], a[n - 1]) << '\n';
    }
    return 0;
}

时间：O(n)需要读取数组 空间：O(n)线性存储空间

B1. Carrot Chopdown (Easy Version)

Problem: B1. Carrot Chopdown (Easy Version)

Contest: Codeforces - Codeforces Round 1118 (Div. 2)

URL: https://codeforces.com/contest/2258/problem/B1

Memory Limit: 256 MB

Time Limit: 1000 ms

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

解题思路

题目要求对胡萝卜只进行一次切分操作，将长度大于x的胡萝卜切成l-x和x,由此可以看出，本题可以通过枚举所有可能目标长度，例如：目标长度$l$来自于两种方式：目标长度胡萝卜总数 = 原本长度$≥l$的胡萝卜数量+原本长度恰好为$2l$的胡萝卜数量。前者在切割次数为一的情况下贡献度为1，后者为2。 计算总数时，采取后缀和的形式计算，节省重复计算长度>=l的胡萝卜数量

代码如下：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n,m;
        cin >> n>>m;
        vector<int> a(m+1,0);
        int res=0;
        for (int i = 0; i < n; i++){
			int x;
			cin>>x;
        	a[x]++;
        }
        int te = 0;          // 后缀和：长度 >= l 的胡萝卜总数
        for (int l = m; l >= 1; l--) {
            te += a[l];      // 累加长度恰好为 l 的数量
            int e = 0;
            if (2*l <= m) e = a[2*l];  // 长度为 2l 的额外贡献
            res = max(res, e + te);    // 更新答案
        }
        cout<<res<<'\n';
    }
    return 0;
}

时间：O(n + m)，每个测试用例线性扫描 空间：O(m)，频次数组