A. Salem and Sticks

Description:

Salem gave you $n$n sticks with integer positive lengths $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​.
For every stick, you can change its length to any other positive integer length (that is, either shrink or stretch it). The cost of changing the stick’s length from $a$a to $b$b is $\mid a-b\mid$∣a−b∣, where $\mid x\mid$∣x∣ means the absolute value of $x$x.
A stick length $a_i$ai​ is called almost good for some integer $t$t if $\mid a_i-t\mid \le 1$∣ai​−t∣≤1.
Salem asks you to change the lengths of some sticks (possibly all or none), such that all sticks’ lengths are almost good for some positive integer $t$t and the total cost of changing is minimum possible. The value of $t$t is not fixed in advance and you can choose it as any positive integer.
As an answer, print the value of $t$t and the minimum cost. If there are multiple optimal choices for $t$t, print any of them.

Input:

The first line contains a single integer $n$n ( $1\le n\le 1000$1≤n≤1000) — the number of sticks.
The second line contains $n$n integers $a_i$ai​ ( $1\le a_i\le 100$1≤ai​≤100) — the lengths of the sticks.

Output

Print the value of $t$t and the minimum possible cost. If there are multiple optimal choices for $t$t, print any of them.

Sample Input:

3
10 1 4

Sample Output:

3 7

Sample Input:

5
1 1 2 2 3

Sample Output:

2 0

题目链接

对一个 $n$n 个元素的数列选择一个数 $t$t ，使得数列中所有元素变化到与 $t$t 差为 $1$1 或 $0$0 变化量之和的最小值

显然 $t$t 在数列中最小最大元素之内，因为数据范围很小所以直接枚举取最小值即可

AC代码:

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

int main(int argc, char *argv[]) {
    int n; cin >> n;
    vector<int> len(n);
    for (auto &it : len) cin >> it;
    sort(len.begin(), len.end());
    int ans(1e9), t(0);
    for (int i = len[0]; i <= len.back(); ++i) {
        int book(0);
        for (auto &it : len) book += it == i ? 0 : abs(it - i) - 1;
        if (book < ans) {
            ans = book;
            t = i;
        }
    }
    cout << t << " " << ans << endl;
    return 0;
}

B. Zuhair and Strings

Description:

Given a string $s$s of length $n$n and integer $k$k ( $1\le k\le n$1≤k≤n). The string $s$s has a level $x$x, if $x$x is largest non-negative integer, such that it’s possible to find in $s$s:

• $x$x non-intersecting (non-overlapping) substrings of length $k$k,
• all characters of these $x$x substrings are the same (i.e. each substring contains only one distinct character and this character is the same for all the substrings).

A substring is a sequence of consecutive (adjacent) characters, it is defined by two integers $i$i and $j$j ( $1\le i\le j\le n$1≤i≤j≤n), denoted as $s[i\dots j]$s[i…j] = “ $s_i{s}_{i+1}\dots s_j$si​si+1​…sj​”.
For example, if $k=2$k=2, then:

• the string “aabb” has level $1$1 (you can select substring “aa”),
• the strings “zzzz” and “zzbzz” has level $2$2 (you can select two non-intersecting substrings “zz” in each of them),
• the strings “abed” and “aca” have level $0$0 (you can’t find at least one substring of the length $k=2$k=2 containing the only distinct character).

Zuhair gave you the integer $k$k and the string $s$s of length $n$n. You need to find $x$x, the level of the string $s$s.

Input:

The first line contains two integers $n$n and $k$k ( $1\le k\le n\le 2\cdot 10^5$1≤k≤n≤2⋅105) — the length of the string and the value of $k$k.
The second line contains the string $s$s of length $n$n consisting only of lowercase Latin letters.

Output

Print a single integer $x$x — the level of the string.

Sample Input:

8 2
aaacaabb

Sample Output:

2

Sample Input:

2 1
ab

Sample Output:

1

Sample Input:

4 2
abab

Sample Output:

0

题目链接

求字符串 $s$s 中不重叠长度为 $k$k 且元素相同（各子序列以及序列内各元素）的连续子序列最大数量

处理每段连续区间，用 $26$26 个变量统计每段区间内符合要求的子序列，取最大值即可

AC代码:

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

int main(int argc, char *argv[]) {
    int n, k; cin >> n >> k;
    string s; cin >> s;
    vector<pair<int, int>> seg;
    for (int l = 0, r = 0; l < n; l = r) {
        while (s[l] == s[r] && r < n) r++;
        seg.push_back(make_pair(l, r));
    }
    vector<int> ans(26, 0);
    for (auto &it : seg) ans[s[it.first] - 'a'] += (it.second - it.first) / k;
    sort(ans.begin(), ans.end());
    cout << ans.back() << endl;
    return 0;
}

C. Ayoub and Lost Array

Description:

Ayoub had an array $a$a of integers of size $n$n and this array had two interesting properties:

• All the integers in the array were between $l$l and $r$r (inclusive).
• The sum of all the elements was divisible by $3$3.

Unfortunately, Ayoub has lost his array, but he remembers the size of the array $n$n and the numbers $l$l and $r$r, so he asked you to find the number of ways to restore the array.
Since the answer could be very large, print it modulo $10^9+7$109+7 (i.e. the remainder when dividing by $10^9+7$109+7). In case there are no satisfying arrays (Ayoub has a wrong memory), print $0$0.

Input:

The first and only line contains three integers $n$n, $l$l and $r$r ( $1\le n\le 2\cdot 10^5,1\le l\le r\le 10^9$1≤n≤2⋅105,1≤l≤r≤109) — the size of the lost array and the range of numbers in the array.

Output

Print the remainder when dividing by $10^9+7$109+7 the number of ways to restore the array.

Sample Input:

2 1 3

Sample Output:

3

Sample Input:

3 2 2

Sample Output:

1

Sample Input:

9 9 99

Sample Output:

711426616

题目链接

对于 $n$n 个数的数列，其中每个元素均可取 $[l,r]$[l,r] 中任意一值，求数列之和为 $3$3 的倍数的方案数

考虑动态规划， $dp\left[i\right]\left[j\right]$dp[i][j] 为前 $i$i 个数之和 mod3=j 的方案数

所以状态转移为 dp[i][j]=k=l∑r​dp[i−1][(j−k)mod3]

但是这样每次转移枚举 $[l,r]$[l,r] 显然会 $TLE$TLE ，所以我们可以预处理出 $[l,r]$[l,r] 中 mod3=(0、1、2) 分别的数量，这样状态转移就可以优化为 dp[i][j]=k=0∑2​dp[i−1][(j−k)mod3]×cnt[k]

AC代码:

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

int main(int argc, char *argv[]) {
    const int mod(1e9 + 7);
    int n, l, r; cin >> n >> l >> r;
    auto __mod = [&] (int key1, int key2) {
        int ans(key1 - key2);
        while (ans < 0) ans += 3;
        return ans % 3;
    };
    vector<long long> cnt(3, 0);
    cnt[0] = (r / 3) - ((l - 1) / 3);
    cnt[1] = ((r + 2) / 3) - ((l + 1) / 3);
    cnt[2] = ((r + 1) / 3) - (l / 3);
    vector<vector<long long>> dp(n, vector<long long>(3, 0));
    dp[0][0] = cnt[0]; dp[0][1] = cnt[1]; dp[0][2] = cnt[2];
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                dp[i][j] = (dp[i][j] + dp[i - 1][__mod(j, k)] * cnt[k] % mod) % mod;
            }
        }
    }
    cout << dp[n - 1][0] << endl;
    return 0;
}

D. Kilani and the Game

Description:

Kilani is playing a game with his friends. This game can be represented as a grid of size $n\times m$n×m, where each cell is either empty or blocked, and every player has one or more castles in some cells (there are no two castles in one cell).
The game is played in rounds. In each round players expand turn by turn: firstly, the first player expands, then the second player expands and so on. The expansion happens as follows: for each castle the player owns now, he tries to expand into the empty cells nearby. The player $i$i can expand from a cell with his castle to the empty cell if it’s possible to reach it in at most $s_i$si​ (where $s_i$si​ is player’s expansion speed) moves to the left, up, right or down without going through blocked cells or cells occupied by some other player’s castle. The player examines the set of cells he can expand to and builds a castle in each of them at once. The turned is passed to the next player after that.
The game ends when no player can make a move. You are given the game field and speed of the expansion for each player. Kilani wants to know for each player how many cells he will control (have a castle their) after the game ends.

Input:

The first line contains three integers $n$n, $m$m and $p$p ( $1\le n,m\le 1000$1≤n,m≤1000, $1\le p\le 9$1≤p≤9) — the size of the grid and the number of players.
The second line contains $p$p integers $s_i$si​ ( $1\le s\le 10^9$1≤s≤109) — the speed of the expansion for every player.
The following $n$n lines describe the game grid. Each of them consists of $m$m symbols, where ‘.’ denotes an empty cell, ‘#’ denotes a blocked cell and digit $x$x ( $1\le x\le p$1≤x≤p) denotes the castle owned by player $x$x.
It is guaranteed, that each player has at least one castle on the grid.

Output

Print $p$p integers — the number of cells controlled by each player after the game ends.

Sample Input:

3 3 2
1 1
1…
…
…2

Sample Output:

6 3

Sample Input:

3 4 4
1 1 1 1
…
#…
1234

Sample Output:

1 4 3 3

题目链接

在一张地图上 $p$p 个人每个人有一些城堡，每一轮每个人从其所有拥有的城堡开始扩张（其他人已占领城堡不可扩张，’#'障碍物不可扩张），最远曼哈顿距离不能超过 $s_i$si​ ，直到所有人均不可继续扩张游戏结束，求游戏结束时每个人所占领的城堡数

每轮对 $p$p 个人依次进行 $bfs$bfs 搜索扩张城堡（注意剪枝），直至所有人不能扩张为止

扩张时统计计数即可

AC代码:

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

int main(int argc, char *argv[]) {
    int n, m, p; cin >> n >> m >> p;
    vector<int> s(p);
    for (auto &it : s) cin >> it;
    vector<queue<pair<int, int>>> que(p);
    vector<int> ans(p, 0);
    vector<vector<char>> maze(n, vector<char>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> maze[i][j];
            if (isdigit(maze[i][j])) {
                que[maze[i][j] - '0' - 1].push(make_pair(i, j));
                ans[maze[i][j] - '0' - 1]++;
            }
        }
    }
    auto check = [&](int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == '.';
    };
    auto bfs = [&](int key) {
        int speed = s[key];
        while (speed--) {
            if (que[key].empty()) break;
            int size = que[key].size();
            for (int k = 0; k < size; ++k) {
                if (que[key].empty()) continue;
                pair<int, int> cur = que[key].front(); que[key].pop();
                for (int i = -1; i < 2; ++i) {
                    for (int j = -1; j < 2; ++j) {
                        if (abs(i) == abs(j)) continue;
                        int nx(cur.first + i), ny(cur.second + j);
                        if (check(nx, ny)) {
                            maze[nx][ny] = key + '0';
                            ans[key]++;
                            que[key].push(make_pair(nx, ny));
                        }
                    }
                }
            }
        }
    };
    bool flag(true);
    while (flag) {
        flag = false;
        for (int i = 0; i < p; ++i) {
            if (que[i].empty()) continue;
            flag = true;
            bfs(i);
        }
    }
    for (auto &it : ans) cout << it << " ";
    cout << endl;
    return 0;
}