Codeforces Round #731 (Div. 3)

 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;

int main() {
    int t;
    cin >> t;
    while(t --){
        int x1, y1, x2, y2, xf, yf;
        cin >> x1 >> y1 >> x2 >> y2 >> xf >> yf;
        if(x1 == x2 && x1 == xf && ((yf >= y1 && yf <= y2) || (yf <= y1 && yf >= y2)))
            cout << abs(y1 - y2) + 2 << endl;
        else if(y1 == y2 && y1 == yf && ((xf >= x1 && xf <= x2) || (xf <= x1 && xf >= x2)))
            cout << abs(x1 - x2) + 2 << endl;
        else 
            cout << abs(x1 - x2) + abs(y1 - y2) << endl;
    }
    return 0;
}

 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

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int st = -1;
        for (int i = 0; i < s.size(); i++)
            if (s[i] == 'a')
                st = i;

        if (st == -1) {
            cout << "NO" << endl;
            continue;
        }

        bool flag = true;
        char now = 'b';
        for (int l = st - 1, r = st + 1; l >= 0 || r < s.size(); now++) {
            if (l >= 0 && s[l] == now)
                l--;
            else if (r < s.size() && s[r] == now)
                r++;
            else
                flag = false;
        }

        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

 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

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int M = 1e5 + 7;
int a[M], b[M], ans[M];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int k, n, m;
        scanf("%d%d%d", &k, &n, &m);
        for (int i = 1; i <= n; i ++)
            scanf("%d", &a[i]);

        for (int i = 1; i <= m; i ++)
            scanf("%d", &b[i]);
        a[n + 1] = b[m + 1] = INF; //数组末尾后一个为INF，方便后面判断
        int cnt = 1;
        for (int i = 1, j = 1; i <= n || j <= m;) {
            while (i <= n && a[i] <= k) {
                ans[cnt ++] = a[i];
                if (a[i] == 0) k++;
                i ++;
            }
            while (j <= m && b[j] <= k) {
                ans[cnt++] = b[j];
                if (b[j] == 0) k++;
                j ++;
            }
            if (a[i] <= k || b[j] <= k)
                continue;
            else
                break;
        }

        if (cnt != n + m + 1)
            printf("-1\n");
        else {
            for (int i = 1; i <= n + m; i ++)
                printf("%d ", ans[i]);
            printf("\n");
        }
    }
    return 0;
}

 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

#include <bits/stdc++.h>
using namespace std;
const int M = 2e5 + 7;
int num[M], ans[M];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &num[i]);

        int last = num[1];
        for (int i = 2; i <= n; i++) {
            ans[i] = (last | num[i]) ^ num[i];
            last = ans[i] ^ num[i];
        }

        for (int i = 1; i <= n; i++)
            printf("%d ", ans[i]);
        printf("\n");
    }
    return 0;
}

 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

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int M = 3e5 + 7;
int a[M], temp[M], ans[M], n, k;
bool st[M];

void bfs() {
    priority_queue<PII, vector<PII>, greater<PII>> heap;

    for (int i = 1; i <= k; i++)
        heap.push({temp[i], a[i]});

    while (heap.size()) {
        auto now = heap.top();
        heap.pop();

        if (st[now.y]) continue;

        st[now.y] = true;
        ans[now.y] = now.x;

        if (now.y > 1)
            heap.push({now.x + 1, now.y - 1});
        if (now.y < n)
            heap.push({now.x + 1, now.y + 1});
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        memset(st, 0, sizeof st);
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= k; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= k; i++) scanf("%d", &temp[i]);

        bfs();

        for (int i = 1; i <= n; i++)
            printf("%d ", ans[i]);
        printf("\n");
    }
    return 0;
}

  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

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int M = 1e6 + 7;
int prime[M], cnt, num[M];
bool st[M];

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void get_prime(int x) {
    for (int i = 2; i <= x; i++) {
        if (!st[i])
            prime[cnt++] = i;
        for (int j = 0; prime[j] <= x / i; j++) {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}

bool cmp(PII a, PII b) {
    if (a.first != b.first)
        return a.first > b.first;
    else
        return a.second < b.second;
}

int main() {
    get_prime(1e6);//筛一下质数
    int t;
    scanf("%d", &t);
    while (t--) {
        map<int, int> mp;
        vector<PII> vec;
        int n, m = 0, g = 0;
        scanf("%d", &n);
        bool same = true;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &num[i]);
            if (same && i > 1 && num[i] != num[i - 1])
                same = false;
            if (!g)
                g = num[i];
            else
                g = gcd(g, num[i]);
            m = max(m, num[i]);

            int now = num[i];//对每一个数进行质因数分解
            for (int j = 0; j <= 1e3 && prime[j] <= now; j++) {
                if (now % prime[j] == 0) {
                    mp[prime[j]]++;
                    while (now % prime[j] == 0) {
                        now /= prime[j];
                    }
                }
            }
            if (now != 1)
                mp[now]++;
        }
        if (same) {
            printf("0\n");
            continue;
        }

        for (auto it : mp) {
            vec.push_back({it.second, it.first});
        }
        sort(vec.begin(), vec.end(), cmp);//按出现次数对质因数排序

        for (int i = 1; i <= n; i++)
            num[i] /= g;

        int ans = 1, count_num = 0;
        for (auto it : vec) {
            if (count_num++ > 1e3 || it.first <= ans)
                break;
            int k = 0, now = 0, head = 0;
            for (int j = 1; j <= n; j++) {
                if (num[j] % it.second == 0)
                    k++;
                else {
                    if (num[1] % it.second == 0 && !head)
                        head = k;

                    now = max(now, k);
                    k = 0;
                }
            }
            if (k) {
                now = max(now, k + head);
            }
            ans = max(ans, now);
        }
        cout << ans << endl;
    }
    return 0;
}