Codeforces Round 928 (Div. 4)

A

模拟

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
#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()
{
string s;
cin>>s;
int suma=0;
int sumb=0;
for(auto c:s)
{
    if(c=='A')
    {
suma++;
    }
    else
    {
        sumb++;
    }
}
if(suma>sumb)
{
    cout<<"A"<<'\n';
}else
{
    cout<<'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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 10 + 5;
int t, n, a[N];
string s[N];
signed main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        memset(a, 0, sizeof(a));
        int b = 1;
        for (int i = 1; i <= n; i++)
        {
            cin >> s[i];
            for (char c : s[i])
                if (c == '1')
                    a[i]++;
            if (a[i] && a[i - 1] && a[i] != a[i - 1])
            {
                if (b)
                    cout << "TRIANGLE" << endl;
                b = 0;
            }
        }
        if (b)
            cout << "SQUARE" << endl;
    }
}

C

在外边预处理，然后里面用前缀和即可。

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
#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;
}
const int N = 2e5 + 100;
ll sum[N];
void solve()
{
    int n;
    cin >> n;
    cout << sum[n] << "\n";
}
int main()
{
    for (int i = 1; i <= N; i++)
    {
        int x = i;
        ll ans=0;
        while (x)
        {
            ans += x % 10;
            x /= 10;
        }
        sum[i] = sum[i - 1] + ans;
    }
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

D

考虑只有两个数异或在31位里面都是1，也就是0x7fffff才满足题意。因此可以直接用multiset进行模拟。

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
#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;
}
int n, inf = 0x7fffffff;
multiset<int> st;
void solve()
{
    cin >> n;
    st.clear();
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        auto p = st.find(x ^ inf);
        if (p == st.end())
        {
            st.insert(x);
            ++ans;
        }
        else
        {
            st.erase(p);
        }
    }
    cout << ans << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

E

推式子题目。

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;
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;
}
const int N = 2e5 + 100;
void solve()
{
    ll n, k;
    cin >> n >> k;

    ll cnt = 1, tmp = n;
    while (k > (tmp + 1) >> 1)
    {
        k -= tmp + 1 >> 1;
        tmp >>= 1, cnt <<= 1;
    }
    cout << (k * cnt << 1) - cnt << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

F

搜索（留给队友吧）

G

树形dp。

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 <iostream>
using namespace std;
const int N = 100005;
struct Edge
{
    int to, nxt;
} g[N << 1];
int h[N], idx;
int f[N][2];
string s;
void add(int a, int b)
{
    g[++idx].to = b, g[idx].nxt = h[a], h[a] = idx;
}
void dfs(int u, int fa)
{
    f[u][0] = f[u][1] = 0;
    for (int i = h[u]; i; i = g[i].nxt)
    {
        int j = g[i].to;
        if (j == fa)
            continue;
        dfs(j, u);
        f[u][0] += min(f[j][0], f[j][1] + 1);
        f[u][1] += min(f[j][1], f[j][0] + 1);
    }
    if (s[u] == 'P')
        {
            f[u][1] = 1e9;
        }
    else if (s[u] == 'S')
        {
            f[u][0] = 1e9;
        }
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        {
            h[i] = 0;
        }
    idx = 0;
    for (int i = 2; i <= n; i++)
    {
        int a;
        cin >> a;
        add(i, a);
        add(a, i);
    }
    cin >> s;
    s = " " + s;
    dfs(1, 1);
    cout << min(f[1][0], f[1][1]) << '\n';
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}