Kyooma's Blog

2022-10-21周赛

  • ~6.47K 字

题目来自: 2017-2018 ICPC Central Quarter Final of Northeastern European Regional Collegiate Programming Contest

B - Rectangles

SOLUTION

可以推出答案和$n$以及$n+1$的因子有关系，分解质因数爆搜就行了。

CODE
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define fi first
#define se second
#define ls p<<1
#define rs p<<1|1
const int N=1e5+10;
const int INF=2e9;

vector<pii> p;
vector<pll> ans;
ll n;

void calc(ll x){
    for(ll i = 2; i * i <= x; i++){
        if(x % i == 0){
            int c = 0;
            while(x % i == 0) x /= i, c++;
            p.emplace_back(i, c);
        }
    }
    if(x > 1) p.emplace_back(x, 1);
}

void dfs(int now, ll k){
    if(now >= p.size()){
        ll x = 2 * n + k + 2;
        ll y = (4 * n * n + 4 * n) / k + 2 * n + 2;
        if(x > y) return;
        ans.emplace_back(x, y);
        return;
    }
    ll r = 1;
    for(int i = 0; i <= p[now].second; i++, r *= p[now].first){
        dfs(now + 1, k * r);
    }
}

void solve(){
    cin >> n;
    calc(n);
    calc(n + 1);
    for(auto & i : p){
        if(i.first == 2){
            i.second += 2;
            break;
        }
    }
    dfs(0, 1);
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for(pll i : ans){
        cout << i.first << ' ' << i.second << '\n';
    }
}

int main() {
    int T=1;
    ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
    for(int i=1;i<=T;i++) {
//        printf("Case #%d: ", i);
        solve();
    }
}

K - Tower of Hanoi

SOLUTION

打表找规律，可以发现只有两种循环方式，而且是和层数有关系的。

用字典树维护即可。

CODE
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define fi first
#define se second
#define ls p<<1
#define rs p<<1|1
const int N = 3e6+10;
const int INF=2e9;

int trie[N][3], color[N], tot;

void insert(int id, string s){
    reverse(s.begin(), s.end());
    int p = 0;
    for(char i : s){
        int to = i - 'A';
        if(!trie[p][to]){
            trie[p][to] = ++tot;
        }
        p = trie[p][to];
    }
    if(color[p] == 0) color[p] = id;
}

int find(int n){
    int p = 0, k = 0, now = 0;
    string t1 = "ABBCCA", t2 = "ACCBBA";
    while(k < n){
        k++;
        if(k & 1){
            int l = t1[(now * 2) % 6] - 'A';
            int r = t1[(now * 2 + 1) % 6] - 'A';
            if(trie[p][r]) p = trie[p][r], now = (now * 2 + 1) % 6;
            else p = trie[p][l], now = (now * 2) % 6;
        }else{
            int l = t2[(now * 2) % 6] - 'A';
            int r = t2[(now * 2 + 1) % 6] - 'A';
            if(trie[p][r]) p = trie[p][r], now = (now * 2 + 1) % 6;
            else p = trie[p][l], now = (now * 2) % 6;
        }
    }
    return color[p];
}

void solve(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        string s;
        cin >> s;
        insert(i, s);
    }
    cout << find(n);
}

int main() {
    int T=1;
    ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
    for(int i=1;i<=T;i++) {
//        printf("Case #%d: ", i);
        solve();
    }
}

L - Fence

SOLUTION

凸包周长模板题。

CODE
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;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define fi first
#define se second
#define ls p<<1
#define rs p<<1|1
const int N = 3e6+10;
const int INF=2e9;
const double eps = 1e-9, pi = acos(-1.0);

int n, m;

int sgn(double x){
    if(fabs(x) < eps) return 0;
    if(x > 0) return 1;
    return -1;
}

struct point{
    double x, y;
    point(double a = 0.0, double b = 0.0) : x(a), y(b){}
    bool operator < (point t) const{
        if(sgn(x - t.x) == 0) return y < t.y;
        return x < t.x;
    }
    point operator - (point p) const{
        return {x - p.x, y - p.y};
    }
    double operator ^ (point p) const{
        return x * p.y - y * p.x;
    }
}p[N], ans[N];

double dis(point a, point b){
    a = a - b;
    return sqrt(a.x * a.x + a.y * a.y);
}

double Andrew(){
    sort(p, p + n);
    int p1 = 0, p2;
    for(int i = 0; i < n; i++){
        while(p1 > 1 && sgn((ans[p1] - ans[p1 - 1]) ^ (p[i] - ans[p1 - 1])) <= 0) p1--;
        ans[++p1] = p[i];
    }
    p2 = p1;
    for(int i = n - 2; i >= 0; i--){
        while(p2 > p1 && sgn((ans[p2] - ans[p2 - 1]) ^ (p[i] - ans[p2 - 1])) <= 0) p2--;
        ans[++p2] = p[i];
    }
    double sum = 0;
    for(int i = 1; i < p2; i++){
//        cout << ans[i].x << ' ' << ans[i].y << '\n';
        sum += dis(ans[i], ans[i + 1]);
    }
//    cout << ans[p2].x << ' ' << ans[p2].y << '\n';
    return sum;
}

void solve(){
    int pn;
    double r;
    cin >> pn >> r;
    for(int i = 0, c; i < pn; i++){
        cin >> c;
        for(int j = 0; j < c; j++){
            double x, y;
            cin >> x >> y;
            p[n++] = point(x, y);
        }
    }
    double res = Andrew() + 2. * pi * r;
    printf("%.5lf", res);
}

int main() {
    int T=1;
    ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
    for(int i=1;i<=T;i++) {
//        printf("Case #%d: ", i);
        solve();
    }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可