A.Key races—签到

题意：两个人比赛打字速度，每个人获取任务和上交答案分别有个 t1，t2 秒的延迟，同时每个人打字的速度分别是 v1，v2 秒，求谁先将给定长度的字符串打完并上交答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int s, v1, v2, t1, t2;
    while (cin >> s >> v1 >> v2 >> t1 >> t2) {
        int cnt1 = 2 * t1 + v1 * s, cnt2 = 2 * t2 + s * v2;
        if (cnt1 < cnt2)
            cout << "First" << endl;
        else if (cnt1 > cnt2)
            cout << "Second" << endl;
        else
            cout << "Friendship" << endl;
    }
    // system("pause");
    return 0;
}

B.The number on the board—贪心

题意：有个数被写在了一块白板上，数的每个位置上的数和不小于 k 。有些人替换了其某些位置上的数使这个数变为了 n。已知数的长度并没有改变。请找出原先的数，满足上述条件的同时和 n 相同位置上数不同的个量尽量小

思路：首先如果改变了的数每个位置上的数和不小于 k，那么已经满足初始数的条件了，同时为了和 n 相同位置上数不同的个数尽量小我们输出 n 即可。如果小于 k，满足初始数的条件同时尽量少的增加和 n 相同位置上数不同的个数，贪心的选择的先用位置上小的数填充到 9

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll k;
string n;

void solve() {
    map<int, int> mp;
    ll len = n.length();
    ll sum = 0;
    for (int i = 0; i < len; ++i) {
        sum += n[i] - '0';
        ++mp[n[i] - '0'];
    }
    if (sum >= k) {
        cout << 0 << endl;
        return;
    }
    ll d = k - sum;  //需要补加的值
    ll cnt = 0;      //计数器
    for (auto e : mp) {
        if (e.second * (9 - e.first) < d)  //如果当前所有位置的这个数都不能满足条件
            d -= e.second * (9 - e.first), cnt += e.second;
        else {  //用掉部分当前位置的这个数即可满足条件
            cnt += d / (9 - e.first) + (d % (9 - e.first) > 0 ? 1 : 0);
            cout << cnt << endl;
            return;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    while (cin >> k >> n) {
        solve();
    }
    // system("pause");
    return 0;
}

C.Star sky—前缀和+思维

题意：在空中设置笛卡尔坐标系。有 n 个星星，第 i 个星星有坐标 (xi,yi) 和最大亮度 c ，每个星星有个初始亮度 si（0<si<c）。若 t 时刻亮度为 x ，则 t+1 时刻为 x+1, x+1<c 否则为 0
你想观察天空 q 次，第 i 你会在 ti 时刻观察一个和坐标轴平行的矩阵范围，矩阵左下角为 (xi1,yi1)，右上角为 (xi2,yi2)。对于每一次观察，你都想知道范围内星星亮度总和。注意若星星在边界上也算作内部

思路：多次查询还是求不同矩形区域的，很容易想到用二维前缀和。但是因为随着时间变化亮度是不断变化的，所以我们在开一维用 dp[i][j][k] 记录 (1,1) 到 (i,j) 形成的矩形区域内亮度为 k 的星星数量。在询问区间内星星总亮度的时候我们就遍历起初区间内亮度为 1~c 所有星星的个数乘上当前亮度的总和，至于当前亮度就用 (k+t)%(c+1) 处理就好了

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;

int n, q, c;
int suffix[maxn][maxn][11];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    while (cin >> n >> q >> c) {
        for (int i = 1; i <= n; ++i) {
            int x, y, s;
            cin >> x >> y >> s;
            ++suffix[x][y][s];  //前缀和统计(1,1)到(x,y)内亮度为s的星星数量
        }
        for (int k = 0; k <= c; ++k) {
            for (int i = 1; i <= 100; ++i) {
                for (int j = 1; j <= 100; ++j) {
                    suffix[i][j][k] = suffix[i][j][k] + suffix[i - 1][j][k] + suffix[i][j - 1][k] - suffix[i - 1][j - 1][k];  //再区域内之前的星星个数
                }
            }
        }
        while (q--) {
            int t, x1, y1, x2, y2;
            cin >> t >> x1 >> y1 >> x2 >> y2;
            int ans = 0;
            for (int k = 0; k <= c; ++k)
                ans += ((k + t) % (c + 1)) * (suffix[x2][y2][k] - suffix[x1 - 1][y2][k] - suffix[x2][y1 - 1][k] + suffix[x1 - 1][y1 - 1][k]);  //注意处在边界上的星星也算
            cout << ans << endl;
        }
    }
    // system("pause");
    return 0;
}

D.Palindromic characteristics—递归+思维

题意：给你一个串，让你求出 k 阶回文子串有多少个。k 从 1 到 n。k阶子串的定义是：子串本身是回文串，而且它的左半部分也是回文串。

  • 如果一个字串是k阶回文，那他一定还是k-1阶回文
  • 如果一个串是k阶回文，那么这个串需要满足： 1.它本是是回文的。 2.他的左半部分（长度的一半向下取整）是 k-1 回文的

思路：先找出所有的回文串：特殊处理长度为 1 和 2 的回文串，其他长度的回文串 [l,r] 肯定满足 [l+1,r-1] 是回文串同时 s[l]==s[r]，然后在此基础上确定每个回文串最大阶数，最后答案维护一个后缀和即可

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e3 + 100;

string s;
bool vis[maxn][maxn];  //判断[i,j]子串是否为回文串
int ans[maxn];         //统计阶数为k的回文串数量

int getk(int x, int y) {
    if (vis[x][y] == 0) return 0;  //不是回文串返还阶数0
    if (x == y) return 1;          //还是特殊判断长度为1和2的回文串阶数
    if (x + 1 == y) return 2;
    int mid = (y - x + 1) / 2;        //向下取整
    return getk(x, x + mid - 1) + 1;  //当前回文串最大阶数为左侧的回文串的最大阶数+1
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    while (cin >> s) {
        memset(vis, 0, sizeof vis);
        memset(ans, 0, sizeof ans);
        int len = s.length();
        for (int i = 0; i < len; ++i) {  //特殊寻找长度为1和2的回文串
            vis[i][i] = 1;
            if (i + 1 < len && s[i] == s[i + 1]) vis[i][i + 1] = 1;
        }
        for (int k = 3; k <= len; ++k) {  //寻找其他长度的回文串
            for (int l = 0; l < len; ++l) {
                int r = l + k - 1;
                if (r >= len) break;
                if (vis[l + 1][r - 1] && s[l] == s[r]) vis[l][r] = 1;
            }
        }
        for (int i = 0; i < len; ++i) {  //递归法确定每个回文串的最大阶数
            for (int j = i; j < len; ++j) {
                ++ans[getk(i, j)];  //对应的最大结束的计数器+1
            }
        }
        for (int i = len - 1; i >= 1; --i)
            ans[i] += ans[i + 1];  //高阶回文串也算低阶回文串所以后缀和处理
        for (int i = 1; i <= len; ++i)
            cout << ans[i] << ' ';
        cout << endl;
    }
    // system("pause");
    return 0;
}