A. Soccer

只有一种情况会导致两队的分持平，就是前后两队比分出现反超

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n;
int x1, yl, x2, y2;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> x1 >> yl >> x2 >> y2;
        
        if ((x1 - yl) * (x2 - y2) < 0) cout << "NO" << endl;
        else cout << "YES" << endl;
    }

    return 0;
}

B. Collatz Conjecture

模拟，当 \(x<y\) 并且接下来的操作产生了循环，跳出模拟过程，\(x\) 的最终取值可以直接计算出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int x, y, k;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> x >> y >> k;
        
        while (k)
        {
            int t = y - x % y;
            if (x == x / y + 1 && x < y)
            {
                x += k % t;
                break;
            }
            if (k >= t) 
            {
                k -= t, x += t;
                while (x % y == 0) x /= y;
            }
            else x += k, k = 0;
        }
        
        cout << x << endl;
    }

    return 0;
}

C. Boring Day

遍历数组，每遍历一个元素，序列就加上当前元素

当序列和大于 \(r\) 时，序列从前往后弹出元素，直到序列为空或者序列和小于等于 \(r\)

若弹出后此时和在 \([l,r]\) 之间，答案 \(+1\)，并清空序列

考虑用双指针或者队列来维护序列

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n, l, r;
int a[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n >> l >> r;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        int sum = 0, res = 0;
        queue<int> q;
        for (int i = 0; i < n; i++)
        {
            q.push(a[i]);
            sum += a[i];
            while (sum > r && q.size())
            {
                sum -= q.front();
                q.pop();
            }
            if (sum >= l && sum <= r)
            {
                res++;
                while (q.size())
                {
                    sum -= q.front();
                    q.pop();
                }
            }
        }
        
        cout << res << endl;
    }

    return 0;
}

D. Beauty of the mountains

对于每一个 \(k * k\) 的子矩阵，把有雪山的山峰数量和没雪山的山峰数量作差，结果为 \(x\)，若要把该子矩阵的山峰高度都增加 \(c\)，那么有雪山的山峰高度和与没雪山的山峰高度和之差的结果会增加 \(c*x\)

因此可以用矩阵前缀和统计出每一种 \(x\)，设 \(x\) 种类数为 \(l\)，两种山峰高度和之差为 \(s\)，为了将 \(s\) 变为 \(0\)，可以列出等式

\(x_1c_1+x_2c_2+x_3c_3+...+x_lc_l=s\)

其中 \(x\) 和 \(s\) 为定值，为了使 \(c\) 有整数解，需要满足 \(gcd(x_1,x_2,x_3,...,x_l)\) | s

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 510;

int T;
int n, m, k;
int g[N][N];
int s[N][N];

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

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n >> m >> k;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cin >> g[i][j];
                
        int sum = 0;
        for (int i = 1; i <= n; i++)
        {
            string t;
            cin >> t;
            t = ' ' + t;
            for (int j = 1; j <= m; j++)
            {
                s[i][j] = s[i - 1][j] +  s[i][j - 1] - s[i - 1][j - 1] + (t[j] == '1');
                if (t[j] == '1') sum += g[i][j];
                else sum -= g[i][j];
            }
        }
        
        int cnt = 0;
        for (int i = k; i <= n; i++)
            for (int j = k; j <= m; j++)
            {
                int x = s[i][j] - s[i - k][j] - s[i][j - k] + s[i - k][j - k];
                cnt = gcd(cnt, k * k - x * 2);
            }
            
        if (cnt && sum % cnt == 0 || !sum) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

E. Number of k-good subarrays

考虑 \(dp\)，设 \(dp(n,k)\) 为 \([0,n - 1]\) 中 \(k\) 好子数组的数量

令 \(c\) 为 \(n - 1\) 最高位 \(1\) 的位置，则可以把 \([0,n-1]\) 分割为 \([0,2^c-1]\) 和 \([2^c,n-1]\) 两部分，记为 \(L\) 和 \(R\)

对于 \(dp(n,k)\)，可以把它的答案分为两部分：

  1. \(k\) 好子数组的左右端点都在 \(L\) 中或 \(R\) 中
  2. \(k\) 好子数组的左端点在 \(L\) 中，右端点在 \(R\) 中

对于 \(1\)，可以写作 \(dp(2^c,k)+dp(n-2^c,k-1)\)

对于 \(2\)，可以写作 \(2^c*min(n-2^c,2^{k+1}-1-2^c)\)

  • 先看 \(L\) 区间，可以发现，当 \(c > k\) 时，\(2^c-1\) 中 \(1\) 的数量一定大于 \(k\)，因此只有 \(c <= k\) 时，\(L\) 区间才能取值，并且能够全部选取，个数为 \(2^c\)
  • 再看 \(R\) 区间，能取到的最大值是 \(2^k-1\) 能够取到的区间是 \([2^c,min(n-1,2^{k+1}-2))\)，转化成区间长度可表达为 \(min(n-2^c,2^{k+1}-1-2^c)\)

记忆化搜索比较好维护

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>

#define int long long

using namespace std;

typedef pair<int, int> PII;

const int mod = 1e9 + 7;

int T;
int n, k;
map<PII, int> p;

int dp(int x, int cnt)
{
    if (!cnt || x == 1) return 1;
    if (p.count({x, cnt})) return p[{x, cnt}];

    int c = 0;
    while (((int)1 << c + 1) < x) c++;

    int l = dp((int)1 << c, cnt), r = dp(x - ((int)1 << c), cnt - 1);
    int res = (l + r) % mod;
    if (c <= cnt)
    {
        int ll = (int)1 << c;
        int rr = (min(x - 1, ((int)1 << cnt + 1) - 2) - ll + 1)% mod;
        res = (res + ll % mod * rr % mod) % mod;
    }

    return p[{x, cnt}] = res;
}

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        
        cout << dp(n, k) << endl;
    }

    return 0;
}