AtCoder Beginner Contest 254

By xiaruize

A - Last Two Digits

签到题：

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
// Problem: A - Last Two Digits
// Contest: AtCoder - AtCoder Beginner Contest 254
// URL: https://atcoder.jp/contests/abc254/tasks/abc254_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e5 + 10;

// bool st;
int n;

// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n;
    if (n % 100 >= 10)
        cout << n % 100 << endl;
    else
        cout << "0" << n % 100 << endl;
    return 0;
}

B - Practical Computing

模拟题，乱搞就行

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
// Problem: B - Practical Computing
// Contest: AtCoder - AtCoder Beginner Contest 254
// URL: https://atcoder.jp/contests/abc254/tasks/abc254_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e5 + 10;

// bool st;
int n;
int a[50][50];
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n;
    a[1][1] = 1;
    cout << 1 << endl;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
            cout << a[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}

C - K Swap

把原数组分成k个，分别是下标模k为0,1,...,k−10,1,...,k-1

对于每个数组单独排序，再合并为原数组，检查是否有序即可

时间复杂度O(nlogn)O(nlogn)

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
// Problem: C - K Swap
// Contest: AtCoder - AtCoder Beginner Contest 254
// URL: https://atcoder.jp/contests/abc254/tasks/abc254_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int n, k;
vector<int> g[N];
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        g[i % k].pb(x);
    }
    for (int i = 0; i < k; i++)
        sort(ALL(g[i]));
    int pre = 0;
    for (int i = 1; i <= n; i++)
    {
        if (g[i % k][(i - 1) / k] < pre)
        {
            No;
            return 0;
        }
        pre = g[i % k][(i - 1) / k];
    }
    Yes;
    return 0;
}

D - Together Square

个人觉得D和E放反了。。。

这题对于每个ii，都可以通过分解质因数，在O(i)O(\sqrt i )求得一个最小的xx，使得x⋅ix\cdot i为一个平方数

此时，对于任意一个平方数kk，x⋅i⋅kx\cdot i \cdot k也为平方数

可以通过数学，或者二分求kmaxk_{max}

累计答案

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// Problem: D - Together Square
// Contest: AtCoder - AtCoder Beginner Contest 254
// URL: https://atcoder.jp/contests/abc254/tasks/abc254_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int n;
vector<int> pre;
bool notpr[N];
vector<int> p;
// bool en;

void init()
{
    for (int i = 2; i <= 2e5; i++)
    {
        if (!notpr[i])
        {
            int x = i + i;
            while (x <= 2e5)
            {
                notpr[x] = 1;
                x += i;
            }
        }
    }
    for (int i = 2; i <= 2e5; i++)
    {
        if (!notpr[i])
            p.pb(i);
    }
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n;
    init();
    int res = 0;
    pre.pb(1);
    for (int i = 2; i * i <= n; i++)
        pre.pb(i * i);
    // cerr << p.size() << endl;
    for (int i = 1; i <= n; i++)
    {
        int x = 1, k = i;
        for (auto v : p)
        {
            int cnt = 0;
            while (k % v == 0)
            {
                k /= v;
                cnt++;
            }
            if (cnt & 1)
                x *= v;
            if (!k || v * v > k)
                break;
        }
        if (k)
            x *= k;
        int l = 0, r = pre.size() - 1;
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;
            if (pre[mid] * x <= n)
                l = mid;
            else
                r = mid - 1;
        }
        res += l + 1;
        // cerr << res << endl;
    }
    cout << res << endl;
    return 0;
}

E - Small d and k

似乎就是一个bfs，没什么难度。

注意dfs判重不好写，建议还是bfs。

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
// Problem: E - Small d and k
// Contest: AtCoder - AtCoder Beginner Contest 254
// URL: https://atcoder.jp/contests/abc254/tasks/abc254_e
// Memory Limit: 1024 MB
// Time Limit: 3500 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 150010ll;

// bool st;
int n, m;
vector<int> g[N];
bool vis[N];
int res = 0;
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    int t;
    cin >> t;
    while (t--)
    {
        int x, k;
        cin >> x >> k;
        res = 0;
        memset(vis, 0, sizeof(vis));
        queue<pii> q;
        q.push({x, 0});
        while (!q.empty())
        {
            int now = q.front().fir, st = q.front().sec;
            q.pop();
            vis[now] = 1;
            res += now;
            if (st == k)
                continue;
            for (auto v : g[now])
                if (!vis[v])
                {
                    q.push({v, st + 1});
                    vis[v] = 1;
                }
        }
        cout << res << endl;
    }
    return 0;
}

F - Rectangle GCD

参考资料

对于一个h1=w1=1,h2=w2=Nh_1=w_1=1,h_2=w_2=N的矩阵

gcd(ai+bj)(1≤i,j≤N)=gcd(gcd(ai+b1)(1≤i≤N),gcd(bj−bj−1)(2≤j≤N))=gcd(a1+b1,ai−ai−1(2≤i≤N),bj−bj−1(2≤j≤N))gcd(a_i+b_j) (1\leq i,j \leq N)\\= gcd(gcd(a_i+b_1)(1\leq i\leq N),gcd(b_j-b_{j-1})(2\leq j \leq N))\\= gcd(a_1+b_1,a_i-a_{i-1}(2\leq i\leq N),b_j-b_{j-1}(2\leq j\leq N))

把这个性质推广到整体，可以用两棵线段树分别维护a,ba,b的gcdgcd

时间复杂度 O(N+Q(logN+logA+logB))O(N+Q(logN+logA+logB))

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
// Problem: F - Rectangle GCD
// Contest: AtCoder - AtCoder Beginner Contest 254
// URL: https://atcoder.jp/contests/abc254/tasks/abc254_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

#define ls p << 1
#define rs p << 1 | 1

// bool st;
int n, q;
int a[N], b[N], c[N], d[N];
// bool en;

int gcd(int x, int y)
{
    if (x == 0)
        return y;
    return gcd(y % x, x);
}

int seg[N << 2];

void pushup(int p)
{
    seg[p] = gcd(seg[ls], seg[rs]);
}

void build(int p, int l, int r)
{
    if (l == r)
    {
        seg[p] = c[l];
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(p);
}

int query(int p, int l, int r, int ll, int rr)
{
    if (ll <= l && r <= rr)
    {
        return seg[p];
    }
    int mid = l + r >> 1;
    int res = 0;
    if (mid >= ll)
        res = gcd(query(ls, l, mid, ll, rr), res);
    if (mid < rr)
        res = gcd(query(rs, mid + 1, r, ll, rr), res);
    return res;
}

int seg2[N << 2];

void pushup2(int p)
{
    seg2[p] = gcd(seg2[ls], seg2[rs]);
}

void build2(int p, int l, int r)
{
    if (l == r)
    {
        seg2[p] = d[l];
        return;
    }
    int mid = l + r >> 1;
    build2(ls, l, mid);
    build2(rs, mid + 1, r);
    pushup2(p);
}

int query2(int p, int l, int r, int ll, int rr)
{
    if (ll <= l && r <= rr)
    {
        return seg2[p];
    }
    int mid = l + r >> 1;
    int res = 0;
    if (mid >= ll)
        res = gcd(query2(ls, l, mid, ll, rr), res);
    if (mid < rr)
        res = gcd(query2(rs, mid + 1, r, ll, rr), res);
    return res;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        c[i] = abs(a[i] - a[i - 1]);
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
        d[i] = abs(b[i] - b[i - 1]);
    }
    build(1, 1, n);
    build2(1, 1, n);
    while (q--)
    {
        int h1, h2, w1, w2;
        cin >> h1 >> h2 >> w1 >> w2;
        if (h1 == h2 && w1 == w2)
            cout << a[h1] + b[w1] << endl;
        else if (h1 == h2)
            cout << gcd(a[h1] + b[w1], query2(1, 1, n, w1 + 1, w2)) << endl;
        else if (w1 == w2)
            cout << gcd(a[h1] + b[w1], query(1, 1, n, h1 + 1, h2)) << endl;
        else
        {
            cout << gcd(gcd(a[h1] + b[w1], query(1, 1, n, h1 + 1, h2)), query2(1, 1, n, w1 + 1, w2)) << endl;
        }
    }
    return 0;
}