Codeforces Round 952 (Div. 4)

A

模拟题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
void solve()
{
string a,b;
cin>>a>>b;
swap(a[0],b[0]);
cout<<a<<" "<<b<<'\n';
}
int main()
{
    int t ;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

B

直接暴力累加即可。

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;
void solve()
{
    int n;
    cin >> n;
    int maxn = 0;
    int ans;
    for (int i = 2; i <= n; i++)
    {
        int j = i;
        int sum = 0;
        int x = 0;
        while (x + j <= n)
        {
            x += j;
            sum += x;
            if (sum > maxn && x <= n)
            {
                maxn = sum;
                ans = i;
            }
        }
    }
    cout << ans << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

C

O(n)扫一遍即可。

遇到大的记录，sum加上之前大的数字。

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;
using ll = long long;
void solve()
{
    int n;
    cin >> n;
    ll sum = 0;
    ll maxn = 0;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ll x;
        cin >> x;
        if (x >= maxn)
        {
            sum += maxn;
            maxn = x;
        }
        else
        {
            sum += x;
        }
       // cout<<sum<<' '<<maxn<<'-'<<'\n';
        if (sum == maxn||sum==0&&maxn==0)
        {
            ans++;
        }
    }
    cout << ans << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

D

观察到一个现象，只要是中间那个点，上下左右一定是相同的，其他点并没有这个现象。因此只需要用二维度的前缀和即可。

注意开数组开vector。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    vector<vector<int>> s(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            if (c == '#')
            {
                a[i][j] = 1;
            }
            else
            {
                a[i][j] = 0;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 1)
            {
                //(i,1,)(i,j)==(i,j)-(i,m)                                                                                  //(1,j)-(i,j)  (i,j)--(n,j)
                if (s[i][j] - s[i - 1][j] - s[i][1 - 1] + s[i - 1][1 - 1] == s[i][m] - s[i - 1][m] - s[i][j - 1] + s[i - 1][j - 1] && s[i][j] - s[1 - 1][j] - s[i][j - 1] + s[1 - 1][j - 1] == s[n][j] - s[i - 1][j] - s[n][j - 1] + s[i - 1][j - 1])
                {
                    cout << i << ' ' << j << '\n';
                    return;
                }
            }
        }
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

E

由于每次计算个数的公式是(x - a + 1) * (y - b + 1) * (z - 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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
    ll x, y, z, k;
    ll ans = 0, cnt = 0;
    cin >> x >> y >> z >> k;
    for (ll a = 1; a <= x; a++)
    {
        for (ll b = 1; b <= y; b++)
        {
            if (k % (a * b) != 0 || k % (a * b) > z)
            {
                continue;
            }
            ll c = k / (a * b);
            cnt = (x - a + 1) * (y - b + 1) * (z - c + 1);
            ans = max(ans, cnt);
        }
    }
    cout << ans << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

F

很明显的具有单调性适合进行二分答案的题目。

相信想到二分的话一定是可以解决这道题的。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<ll> a(m + 1);
    vector<ll> b(m + 1);
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
    }
    ll l = 1, r = 1e12;
    ll ans = 1;
    while (l <= r)
    {
        ll mid = l + r >> 1;
        ll sum = 0;
        for (int i = 1; i <= m; i++)
        {
            ll cs = (mid - 1) / b[i] + 1;
            sum += cs * a[i];
            if (sum >= n)
                break;
        }
        if (sum >= n)
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    cout << ans << "\n";
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

G

首先用到一点前缀和的思想。

答案等于r那一部分减去l那一部分。

然后考虑猜个结论：不进位乘法可以满足要求，因此每次都是9/k进行快速幂即可。

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>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
// 非递归快速幂
ll ksm(ll a, ll n,int MOD)
{
    int ans = 1;
    while (n)
    {
        if (n & 1)               // 如果n的当前末位为1
            ans = a * ans % MOD; // ans乘上当前的a
        a = a * a % MOD;         // a自乘
        n >>= 1;                 // n往右移一位
    }
    return ans;
}
void solve()
{

    ll l, r, k;
    cin >> l >> r >> k;
    cout << (ksm((9 / k) + 1, r, MOD) - ksm((9 / k) + 1, l, MOD) % MOD + MOD) % MOD << "\n";
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}