# Codeforces Round 970 (Div. 3)

A

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

void solve()
{
int a,b;
cin>>a>>b;
if(a%2==0&&b%2==0||a%2==0&&b&&a/2)
{
    cout<<"YES"<<'\n';
}
else
{
    cout<<"NO"<<'\n';
}


}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

B

枚举一下约数（注意是可开方数字）

之后计算一下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
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
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int N=1e3+100;
int a[N][N];
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
s=" "+s;
int ans=0;
for(auto c:s)
{
    if(c=='1')
    {
        ans++;
    }
}
for(int i=1;i<n;i++)
{
    if(n%i==0&&n/i==i)
    {
        //i行,n/i列
        int l=n/i;
        int r=i;
        if(ans!=l+l+r*2-4)
        {
            continue;
        }
        bool flag=1;
        for(int i=1;i<=l;i++)
        {
            if(s[i]!='1')
            {
                flag=0;
            }
        }
        for(int i=n;i>n-l;i--)
        {
                if(s[i]!='1')
                {
                    flag=0;
                }
        }
        for(int j=2;j<=r-1;j++)
        {
            if(s[(j-1)*l+1]!='1')
            {
                flag=0;
            }
        }
        if(flag)
        {
            cout<<"Yes"<<'\n';
            return ;
        }
    }
}


cout<<"No"<<'\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
void solve()
{
int l,r;
cin>>l>>r;
int ans=r-l;
ans*=2;
int x=sqrt(ans);
if(x*(x+1)>ans)
{
    x--;
}
cout<<x+1<<'\n';



}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

D

带权并查集秒了。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
int fa[maxn], r[maxn], sum[maxn];
int find(int x)
{
    if (fa[x] != x)
    {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}

void merge(int x, int y)
{
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY)
    {
        if (r[rootX] > r[rootY])
        {
            fa[rootY] = rootX;
            sum[rootX] += sum[rootY];
        }
        else if (r[rootX] < r[rootY])
        {
            fa[rootX] = rootY;
            sum[rootY] += sum[rootX];
        }
        else
        {
            fa[rootY] = rootX;
            sum[rootX] += sum[rootY];
            r[rootX]++;
        }
    }
}
void init(int n)
{
    iota(fa, fa + n, 0);
    fill(r, r + n, 0);
    fill(sum, sum + n, 0);
}
void solve()
{
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++)
    {
        cin >> p[i];
        p[i]--;
    }
    string s;
    cin >> s;
    init(n);
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '0')
        {
            sum[i] = 1;
        }
    }
    for (int i = 0; i < n; i++)
    {
        merge(i, p[i]);
    }

    for (int i = 0; i < n; i++)
    {
        cout << sum[find(i)] << " ";
    }
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

E

发现 n 为奇数时一定需要一次 1 操作，偶数时一定不需要 1 操作

对于 n 为偶数，先各自记录奇数位和偶数位每个字符出现的情况，然后分别枚举奇数位和偶数位的最终字符

对于 n 为奇数，先枚举删去哪个点，最终序列的奇数位是这个点前面的奇数位和后面的偶数位，再分别枚举奇数位和偶数位的最终字符。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 2e5 + 5;
string s;
int odd[N][26], even[N][26];

void solve()
{
    int n;
    cin >> n;
    cin >> s;
    s = " " + s;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= 25; ++j)
            odd[i][j] = even[i][j] = 0;
        if (i & 1)
            odd[i][s[i] - 'a'] = 1;
        else
            even[i][s[i] - 'a'] = 1;
        for (int j = 0; j <= 25; ++j)
            odd[i][j] += odd[i - 1][j], even[i][j] += even[i - 1][j];
    }
    int ans = 0x7fffffff;
    if (n & 1)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j <= 25; ++j)
                for (int k = 0; k <= 25; ++k)
                {
                    int x = odd[i - 1][j] + even[n][j] - even[i][j];
                    int y = even[i - 1][k] + odd[n][k] - odd[i][k];
                    ans = min(ans, n - 1 - x - y);
                }
        }
        cout << ans + 1 << '\n';
    }
    else
    {
        for (int i = 0; i <= 25; ++i)
            for (int j = 0; j <= 25; ++j)
                ans = min(ans, n - (odd[n][i] + even[n][j]));
        cout << ans << '\n';
    }
}

int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

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
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
int qpow(int x, int n)
{
    int ans = 1;
    while (n)
    {
        if (n & 1)
            ans = ans * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ans;
}
int inv(int x)
{
    return qpow(x, mod - 2);
}

void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    ll sum = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    ll q = (n - 1) * n / 2 % mod;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = (ans + a[i] * ((sum - a[i] + mod) % mod) % mod) % mod;
        ans %= mod;
    }
    ans = ans * inv(2) % mod;
    cout << ans * inv(q) % mod << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}