A.Soccer（思维）

题意：

迪马喜欢看足球比赛。在这样一场比赛中，记分牌上的比分表示为$x$:$y$，其中$x$是第一队的进球数，$y$是第二队的进球数。在任何时候，只有一支球队可以进球，因此比分$x$:$y$可以变为$(x+1)$:$y$，或者$x$:$(y+1)$。

在观看足球比赛时，迪马被一些非常重要的事情分散了注意力，过了一段时间，他又重新开始观看比赛。迪马记得他走神前的比分和他回来后的比分。鉴于这两个比分，他想知道以下问题。有没有可能在迪马没有看比赛的时候，两队的比分从来没有相同过？

可以肯定的是，在迪马记得的两个时间点上，两队的比分都不相等。不过，也有可能在他不在的时候，比分并没有发生变化。

请帮助迪马回答问题！

分析：

我们将之前的比分表示为$[x_1,y_1]$，之后的比分表示为$[x_2,y_2]$。二者不相交则不可能出现相同的分数。

代码：

#include<bits/stdc++.h>

using namespace std;

void solve() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    if (x1 < y1) {
        if (x2 >= y2) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
        }
    } else if (x1 > y1) {
        if (x2 <= y2) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
        }
    } else {
        cout << "YES" << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

B.Collatz Conjecture（思维、数学）

题意：

最近，一年级学生马克西姆学习了科拉兹猜想，但他在讲课时没有太注意，所以他认为猜想中提到了以下过程：

有一个变量$x$和一个常数$y$。下面的操作进行了$k$次：

• 将$x$增加$1$，然后
• 当数字$x$能被$y$整除时，再除以$y$。

请注意，这两个操作都是在一次操作中依次进行的。

例如，如果数字$x=16$、$y=3$和$k=2$，那么经过一次运算后，$x$就变成了$17$，而经过另一次运算后，$x$就变成了$2$，因为加一后，$x=18$就能被$3$整除两次。

鉴于初始值为$x$、$y$和$k$，马克西姆想知道$x$的最终值是多少。

分析：

直接模拟会超时。考虑如果$x$等于$1$，可以直接跳出循环，用数学方法解决，因为这时$x$就一直会在$[1,y]$之间。

代码：

#include<bits/stdc++.h>

using namespace std;

void solve() {
    int x, y, k;
    cin >> x >> y >> k;
    while (k != 0 && x != 1) {
        int t = min(k, y - x % y);
        x += t;
        k -= t;
        while (x % y == 0) {
            x /= y;
        }
    }
    k %= (y - 1);
    x = x + k;
    cout << x << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C.Boring Day（贪心）

题意：

又是无聊的一天，埃戈尔觉得无聊，决定做点什么。但因为没有朋友，他就想出了一个游戏。

埃戈尔有一副$n$张扑克牌，最上面的$i$张牌上写着数字$a_i$。埃戈想玩一定轮数的游戏，直到牌用完为止。在每一轮中，他都会从牌面顶端抽取一张非零数的牌，然后结束这一轮。如果在这一轮中收集到的纸牌上的数字之和在$l$和$r$（包括首尾数字）之间，则这一轮获胜；否则，这一轮失败。

埃戈尔对纸牌的顺序了如指掌。请帮助埃戈尔确定他在这样的游戏中最多可以赢多少局。请注意，伊戈尔不需要连续赢得回合。

分析：

本题我们考虑贪心，使用双指针先一直往后加和（后面的指针往后走），当和不小于$l$时，将前指针也往后走，假如现所在位置为$l$。那么就将$sum-a_l$。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 1e6 + 5;
LL a[N];

void solve() {
    int n, L, R;
    cin >> n >> L >> R;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    LL cnt = 0;
    LL sum = 0;
    int l = 0;
    for (int r = 1; r <= n; r++) {
        sum += a[r];
        while (l + 1 <= r && sum > R) {
            sum -= a[++l];
        }
        if (sum >= L && sum <= R) {
            cnt++;
            sum = 0;
            l = r;
        }
    }
    cout << cnt << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

D.Beauty of the mountains（数学）

题意：

尼基塔喜欢山，终于决定去贝里安德山脉看看！这座山脉如此美丽，尼基塔决定用地图记录下来。地图是一个由$n$行和$m$列组成的表格，每个单元格都包含一个非负整数，代表山的高度。

他还注意到，山有两种类型：

• 有雪盖。
• 无雪帽。

尼基塔是一个非常务实的人。他希望有雪帽的山的高度总和等于没有雪帽的山的高度总和。他已经和贝里安德的市长波利卡普-波利卡波维奇达成了协议，允许他改造地貌。

尼基塔可以对大小为$k\times k$的子矩阵进行如下变换：他可以在该区域内的山峰高度上添加一个整数常数$c$，但山峰的类型保持不变。尼基塔可以为每次变换独立选择常数$c$。注意$c$可以是负数。

在进行变换之前，尼基塔会要求您找出是否有可能实现总和相等，或者是否不可能。即使山变成了峡谷，高度为负数，代价也无所谓。

如果地图上只有一种类型的山，那么另一种类型的山的高度之和将被视为零。

分析：

我们考虑到，如果要让这两部分分别相等（$0$部分的和为$su{m}_0$，$1$部分的和为$su{m}_1$），那么我们对于每一个$k\times k$的矩阵$m_i$，假设当前矩阵被选且其中有$nu{m}_{i,0}$个$0$，和$nu{m}_{i,1}$个$1$，且当前答案系数为$c_i$。

我们令$su{m}_0$加上$c_k\times nu{m}_{i,0}$，$su{m}_1$加上$c_k\times nu{m}_{i,1}$，那么$su{m}_0$会加上$\sum c_i\times nu{m}_{i,0}(i\in S)$，$su{m}_1$会加上$\sum c_i\times nu{m}_{i,1}(i\in S)$。这两部分加上原来的部分就是我们要求的相等的和，所以设原来两部分的差为$mn$，这样则有
$\sum c_i\times \mid nu{m}_{i,0}-nu{m}_{i,1}\mid =mn(i\in S)$。

而绝对值内的部分可以通过二维前缀和预处理，$c$为未知数，所以这是不定方程的形式，我们利用裴蜀定理，求出所有$\mid nu{m}_{i,0}-nu{m}_{i,1}\mid$的$gcd$（如果其中存在$0$则跳过），如果所有这些数都是$0$且$mn=0$，或者这个$gcd$整除$mn$则有方案，否则无方案。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 5e2 + 2;

LL gcd(int a, int b) {
    return b > 0 ? gcd(b, a % b) : a;
}

LL n, m, k, a[N][N], c[N][N];
string s[N];


LL cal1(int x1, int y1, int x2, int y2) {
    return c[x2][y2] - c[x1 - 1][y2] - c[x2][y1 - 1] + c[x1 - 1][y1 - 1];
}

LL cal2(int x1, int y1, int x2, int y2) {
    return a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
}

void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = " " + s[i];
        for (int j = 1; j <= m; j++) {
            if (s[i][j] == '0') {
                c[i][j] = -1;
                a[i][j] *= -1;
            } else {
                c[i][j] = 1;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            c[i][j] += c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1];
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }
    LL g = 0;
    for (int i = 1; i + k - 1 <= n; i++) {
        for (int j = 1; j + k - 1 <= m; j++) {
            LL sum = cal1(i, j, i + k - 1, j + k - 1);
            sum = abs(sum);
            g = gcd(g, sum);
        }
    }
    LL sum = cal2(1, 1, n, m);
    if ((g == 0 && sum == 0) || (g != 0 && sum % g == 0)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

E.Number of k-good subarrays（思维）

题意：

让$bit(x)$表示非负整数$x$的二进制表示中的$1$的个数。

如果一个数组的子数组只由二进制表示中的$1$数不超过$k$的数组成，那么这个数组被称为$k$（好）数组，对于数组$a$的子数组$(l,r)$，当满足条件$bit(a_i)\le k$对于所有$l\le i\le r$的$i$时，则该子数组是$k$好的。

给你一个长度为$n$的数组$a$，由从$0$开始的连续的非负整数组成，即$0\le i\le n-1$的$a_i=i$。你需要计算这个数组中$k$好的子数组的数量。

由于答案可能非常大，所以请输出对$10^9+7$取模的结果。

分析：

设$sol(n,k)$为答案。（注意，是$[0,n-1]$的）那么$sol(n,k)$可以通过$sol(mx,k)$和$sol(n-mx,k-1)$算出来，其中$mx$是小于$n$的最大$2$次幂。（大于等于$mx$的就会有一位固然是$1$，就会是$k-1$。）设$mx=2^c$。

除了内部的，还有一个端点在左边一个端点在右边的。官方题解是维护了三个值，较为复杂。

我们发现，如果$c>k$，那么左边最后一个就会有大于$k$个$1$，没有贡献，所以必须$c\le k$。这个时候左边所有的都满足，只需要计算右边的。右边的到了$2^k-1$也不行，因为这样也超过了（当然要和长度取最小值）。所以我们算出了右边的贡献$s=min(2^c-1,n-2^c)$。那么，答案就要多加上$s\times 2^c$。直接记忆化搜索即可。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const LL MOD = 1e9 + 7;
map<pair<LL, LL>, LL> mp;

LL sol(LL n, LL k) {
    if (k == 0 || n == 1) {
        return 1;
    }
    if (mp.count({n, k})) {
        return mp[{n, k}];
    }
    LL c = 0;
    while ((1ll << c + 1) < n) {
        c++;
    }
    LL l = sol(1ll << c, k);
    LL r = sol(n - (1ll << c), k - 1);
    LL ans = l + r;
    if (c <= k) {
        LL s = min((1ll << k) - 1, n - (1ll << c));
        ans += s % MOD * ((1ll << c) % MOD) % MOD;
    }
    mp[{n, k}] = ans % MOD;
    return ans % MOD;
}

void solve() {
    LL n, k;
    cin >> n >> k;
    cout << sol(n, k) << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

赛后交流

在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。

群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。