A. Creating Words（模拟）

使用swap函数对两个字符串第一位交换即可.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        string sx, sy;
        cin >> sx >> sy;
        swap(sx[0], sy[0]);
        cout << sx << ' ' << sy << endl;
    }
    return 0;
}

B.Maximum Multiple Sum(模拟)

因为n的范围极小，直接遍历找最大值并更新答案即可.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int n;cin >> n;
        int ans = 0, res;
        for (int i = 2; i <= n;i++){
            int mn = 0, cnt = 1;
            while(cnt*i<=n)
                mn += cnt * i, cnt++;
            //cout << i << ' ' << mn << endl;
            if(mn>ans)
                ans = mn, res = i;
        }
        cout << res << endl;
    }
    return 0;
}

C.Good Prefixes(前缀和)

遍历数组并统计符合的情况。不难想到，每次符合条件的情况必然是最大值等于剩余的和。所以，我们只需要遍历的同时维护最大值和前缀和，当前前缀满足要求时，当且仅当前缀和等于最大值的两倍。当然，对a[1]是否等于0进行特判。

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
#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
int a[200010], pre[200010];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int n, ans = 0;
        cin >> n;
        for (int i = 1; i <= n;i++)
            cin >> a[i];
        int mn = a[1];
        pre[1] = a[1];
        if (a[1] == 0)
            ans++;
        for (int i = 2; i <= n;i++){
            mn = max(mn, a[i]);
            pre[i] = pre[i - 1] + a[i];
            if(pre[i]==2*mn)
                ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

D.Manhattan Circle(字符串)

题意

给出一个的网格，在此网格会给出一个曼哈顿圆，其点集标记为”#”，求其圆心.

数据范围

思路

    观察样例可知，圆心位置一定是最多”#”所在行的中心，所以我们按行的顺序遍历并记录最大值和当行所含的”#”数量。
    但是本题的数据范围是乘积小于等于，所以不能开二维字符数组，只能每行依次输入一个字符串并记录其信息.

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
#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
#define inf 1e15
using namespace std;
typedef pair<int,int>pii;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, m;
        string s;
        cin >> n >> m;
        int idx, idy, mn = 0;
        for (int i = 1; i <= n;i++){
            cin >> s;
            int num = s.length(), res = 0;
            for (int j = 0; j < num;j++)
                if(s[j]=='#')
                    res++;
            if(res>mn){
                mn = res;
                int cnt;
                for (int j = 0; j < num;j++)
                    if(s[j]=='#'){
                        cnt = j;
                        break;
                    }
                idx = i, idy = cnt + (res - 1) / 2;
            }
        }
        cout << idx << ' ' << idy+1 << endl;
    }
    return 0;
}

E.Secret Box(暴力枚举+优化)

题意

给出一个三维的固定尺寸（x,y,z）的盒子B，现在有一个体积为k的盒子S，它的边长均为正整数，将S平放在B的正整数位置，求其最大的不同个不同位置的数量.

数据范围

思路

    很明显，从暴力的角度出发，三层循环依次枚举S的长、宽、高,满足条件是均不超过B的尺寸且乘积恰等于k，但是复杂度最高可达，显然无法通过本题。
    考虑消元，因为k的值是定值，也就是当长和宽确定且k能够整除长宽的乘积，那么高的值也能够确定.

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
#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
typedef pair<int,int>pii;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int x, y, z, k;cin >> x >> y >> z >> k;
        int ans = 0;
        for (int i = 1; i <= x;i++) // 枚举长度
            for (int j = 1; j <= y;j++){ //枚举宽度
                if(i*j<=k&&k%(i*j)==0){
                    int e = k / (i * j); //e显然为高度
                    if(e>z)continue;
                    int cntx = x - i + 1, cnty = y - j + 1, cntz = z - e + 1;
                    ans = max(ans, cntx * cnty * cntz);
                }
            }
        cout << ans << endl;
    }
    return 0;
}

F.Final Boss(思维+二分)

题意

Boss的生命值为h，我们拥有n次攻击，第i次攻击能造成点伤害，但使用完之后会有回合的冷却时间。最初，所有攻击均未冷却，每一回合可以使用任意未冷却的攻击一次。求击败Boss的回合数。

数据范围

思路

    首先，想要使得回合数最少就能击败Boss，那么每一回合只要有未冷却的，直接全部使用。所以，我们在第一轮直接使用所有的攻击，让Boss承受所有伤害，并进入冷却模式。
    接下来，我们就会发现，冷却时间相等的，必然会在其回合的倍数时叠加伤害，也就是该倍数回合的伤害就是其伤害值的总和，所以我们要统计同一冷却时间的伤害.
    若最终n回合,则造成的总伤害为,要求出最终的回合数，我们可以通过二分查找的方法求出满足条件的最小值.
PS:本题的二分上界inf最大只能取到约1e13

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
65
66
#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
#define inf 1e12
using namespace std;
struct node{
    int a, c;
    bool operator<(const node ss)const{
        return c < ss.c;
    }
} s[200010],b[200010];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int h, n, pre = 0;
        cin >> h >> n;
        for (int i = 1; i <= n; i++)
            cin >> s[i].a, pre += s[i].a;
        for (int i = 1; i <= n; i++)
            cin >> s[i].c;
        h -= pre;
        if(h<=0){ //对第一回合进行特判
            cout << "1" << endl;
            continue;
        }
        sort(s + 1, s + n + 1);
        //b数组表示同一冷却时间的伤害总和
        b[1].a = s[1].a, b[1].c = s[1].c;
        int cnt = 1;
        for (int i = 2; i <= n;i++)
            if(s[i].c!=s[i-1].c){
                cnt++;
                b[cnt].a = s[i].a;
                b[cnt].c = s[i].c;
            }else
                b[cnt].a += s[i].a;
        /*for (int i = 1; i <= n; i++)
            cout << s[i].c << ' ' << s[i].a << endl;
        for (int i = 1; i <= cnt;i++)
            cout << b[i].c << ' ' << b[i].a << endl;*/
        int l = 1, r = inf, ans;
        auto check = [&](int x) -> bool
        {
            int res = 0;
            for (int i = 1; i <= cnt;i++)
            {
                int temp = x / b[i].c;
                res += temp * b[i].a;
                if(res>=h)
                    return 1;
            }
            return 0;
        };
        while(l<=r){
            int mid = l + r >> 1;
            if(check(mid))
                r = mid - 1, ans = mid;
            else
                l = mid + 1;
        }
        cout << ans + 1 << endl;
    }
    return 0;
}

G.D-Funtion（快速幂取模）

题意

假设表示n的数位之和，有多少个整数满足且。对答案以进行取模。

数据范围

思路

    不难发现,满足的条件是任一数位乘以k后不会进位，也就是乘积不超过10。所以当时，一定不成立，数量为0.
    设每一位最大能出现的数值（相乘不会进位）为，则，于是，（从右往左第l-1数位）开始，到（第r-1数位）结束，由于最左数位的起始值必须从1开始，后续数位可以从0开始，所以每一位i作为左起始点的权值为,所以答案为.
    由于l与r的范围极大，不能直接对上式进行遍历操作，所以考虑化简。不难发现，中括号内是一个等比数列求和的形式，使用求和公式化简后可得，,对于求幂的操作，可以使用快速幂取模轻松求得，最后对答案进行取模操作即可.

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
#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
const int p = 1e9 + 7;
int power_mod(int a, int b, int mod){ //快速幂取模
    int res = 1;
    a = a % mod;
    while (b){
        if (b & 1)
            res = (res * a) % mod;
        b /= 2;
        a = (a * a) % mod;
    }
    return res;
}
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int l, r, k;cin >> l >> r >> k;
        if(k>=10){
            cout << 0 << endl;
            continue;
        }
        int m = 9 / k;
        int q = m + 1;
        int pow1 = power_mod(q, l, p), pow2 = power_mod(q, r, p);
        //cout << pow2 << endl;
        int ans = (pow2 - pow1 + p) % p; //减法需要再加一个模数防止负数形式
        cout << ans << endl;
    }
    return 0;
}