A. Game

Code

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++)	cin >> a[i];
    bool flag = false;
        
    int i = 0, j = n - 1;
    while (i < j)
    {
        if (a[i] == 1) i++;		
        if (a[j] == 1) j--;
        
        if (a[i] != 1 && a[j] != 1)
        {
            flag = true;
            break;
        }	
    }
        
    if (flag)
        cout << (j + 1) - (i - 1) << '\n';
    else cout << 0 << '\n';
}

B. Game of Ball Passing

Code

void solve(){
    cin >> n;
    sum = 0;
    for(int i = 1; i <= n; i++) cin >> a[i], sum += a[i];	
        
    int mx = *max_element(a.begin(), a.end());
    if(mx == 0)
    {
        cout << "0" << endl;
        return;
    }
        
    if(mx * 2 <= sum)	cout << 1 << endl;
    else
    {
        sum = 2 * mx - sum;
        cout << sum << endl;
    }
    return;
}

D. Integral Array(前缀和、倍数遍历)

题目大意

给定一个长度为 $n(n \le 10^{6)$ 的数组 $a$ ，我们称一个数组是完整的需要满足：
对于数组中任意的两个数 $x,y(x < y)$ ， 保证 $\frac$ 也在数组中(整数除法)。
数据保证数组 $a[i] \le c, c \le 10}6$

解题思路

思路请看严格鸽的题解
经过一番理解终于是弄懂了其中真正的妙处
暴力做法是对于每一个出现过的数x可以枚举[x + 1, c],如果这个区间中有一个数y在数组里出现过，那么y/x必定也要出现才满足“完整”
但是这样做肯定是TLE
于是我们想到优化做法，就是直接枚举倍数区间，然后用前缀和处理查看这个区间中是否有数存在

下面实则是近似于调和级数n/1 + n/2 + …… + n/n = nlogn 复杂度的做法
for (int i = 1; i <= n; i++) {
	for (int j = i; j <= n; j += i) {  

问:为什么是查询区间[j, j + i - 1], 而不是[j, j + i]?

因为j + i已经是下一个倍数了，比如2的2倍只能取区间[4,5]而不能是[4,6],因为6是2的3倍
问:为什么可以直接枚举倍数区间呢？
我们不难发现对于3的3倍区间[9,11], 9/3=3, 10/3=3, 11/3=3,这个区间整除后是相同的结果3， 所以可以利用这个性质，直接枚举区间倍数

Code

void solve()
{
    memset(cnt, 0, sizeof cnt);
    int n, c, x;   cin >> n >> c;
    for (int i = 1; i <= n; i++)  cin >>  x, cnt[x]++;  
    for (int i = 1; i <= c; i++)    pre[i] = pre[i - 1] + cnt[i];  // 前缀和

    for (int i = 1; i <= c; i++)
        if (cnt[i])  // 只对出现过的数进行区间遍历
        {
            for (int j = i; j <= c; j += i)  // 每次加一倍，时间复杂度降低为为nlogn
            {
                int l = j, r = min(c, j + i - 1);  // 在[j, j + i - 1]这个倍数区间查看，范围不能超过'c'所以取min
                if (pre[r] - pre[l - 1] && !cnt[j / i])  // 如果在这个区间中存在一个数y，但是数组中不存在y/x,就是不完整的
                {
                    puts("NO");
                    return;
                }
            }
        }
    puts("YES");
}