2017-2018 ACM-ICPC Latin American Regional Programming Contest

Posted on | In

UnrealWings, 2018/10/31 16:00

Solution

C - Complete Naebbirac’s sequence

Solution of C

暴力枚举即可。

Code of 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
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
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

void solve();
int main() {
#ifdef Semon0x29a
    assert(freopen("Testing.txt", "r", stdin));
    clock_t st = clock();
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
#ifdef Semon0x29a
    clock_t ed = clock();
    cerr << (ed - st) * 1.0 / CLOCKS_PER_SEC << endl;
#endif
}

const int maxn = 1e4 + 5;
const int MOD = 1e9 + 7;

int a[maxn], cnt[maxn];

void solve() {
    int k, n;
    while (cin >> k >> n) {
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        memset(cnt, 0, sizeof cnt);
        for (int i = 1; i <= n; i++) {
            cnt[a[i]]++;
        }

        if ((n + 1) % k == 0) {
            int num = (n + 1) / k, count = 0;
            for (int i = 1; i <= k; i++) {
                if (cnt[i] == num) {
                    count++;
                }
            }
            if (count == k - 1) {
                for (int i = 1; i <= k; i++) {
                    if (cnt[i] != num) {
                        cout << "+" << i << endl;
                        break;
                    }
                }
                goto ed;
            }
        }
        if ((n - 1) > 0 && (n - 1) % k == 0) {
            int num = (n - 1) / k, count = 0;
            for (int i = 1; i <= k; i++) {
                if (cnt[i] == num) {
                    count++;
                }
            }
            if (count == k - 1) {
                for (int i = 1; i <= k; i++) {
                    if (cnt[i] != num) {
                        cout << "-" << i << endl;
                        break;
                    }
                }
                goto ed;
            }
        }
        if (n % k == 0) {
            int num = n / k, count = 0;
            for (int i = 1; i <= k; i++) {
                if (cnt[i] == num) {
                    count++;
                }
            }
            if (count == k - 2) {
                int sub = -1, add = -1;
                for (int i = 1; i <= k; i++) {
                    if (cnt[i] == num - 1) add = i;
                    else if (cnt[i] == num + 1) sub = i;
                }
                cout << "-" << sub << " +" << add << endl;
                goto ed;
            }
        }
        cout << "*" << endl;
    ed:;
    }
}

E - Enigma

Solution of E

记忆化搜索，vis[u][status] 表示枚举前u位、余数为status的状态是否visited。

Code of 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
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
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(a) (int)a.size()
#define endl '\n'
#define all(a) a.begin(), a.end()

inline bool _R(int & x) { return scanf("%d", &x) == 1; }
inline bool _R(long long &x) { return scanf("%lld", &x) == 1; }
inline bool _R(double &x) { return scanf("%lf", &x) == 1; }
inline bool _R(char &x) { return scanf(" %c", &x) == 1; }
inline bool _R(char *x) { return scanf("%s", x) == 1; }
template <typename T, typename U> inline bool _R(pair<T, U> &x) { return _R(x.first) && _R(x.second); }
inline bool Read() { return 1; }
template <typename T, typename... U> inline bool Read(T &head, U &... tail) { return _R(head) && Read(tail...); } 
inline void _W(const int &x) { printf("%d", x); }
inline void _W(const long long &x) { printf("%lld", x); }
inline void _W(const double &x) { printf("%.10f", x); }
inline void _W(const char &x) { putchar(x); }
inline void _W(const char *x) { printf("%s", x); }
template <typename T, typename U> inline void _W(const pair<T, U> &x) { _W(x.first); putchar(' '); _W(x.second); }
template <typename T> inline void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) { if (i != x.begin()) { putchar(' '); }}}
inline void Write() {}
template <typename T, typename... U> inline void Write(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); Write(tail...); }
const int Move[][2] = { { 0, 0 },{ 1, 0 },{ 0, 1 },{ 0, -1 },{ -1, 0 },{ 1, 1 },{ 1, -1 },{ -1, 1 },{ -1, -1 } };

#ifdef Semon0x29a
    #define debug(...) Write(__VA_ARGS__)
#else
    #define debug(...) 2333
#endif

typedef long long ll;
typedef vector<int> VI;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

void solve();
int32_t main() {
#ifdef Semon0x29a
    assert(freopen("Testing.txt", "r", stdin));
    clock_t START = clock();
#endif
    solve();
    debug((clock() - START) * 1.0 / CLOCKS_PER_SEC);
}

const int MOD = 1e9 + 7;
inline ll sqr(ll a) { return a * a; }
inline ll add(ll a, ll b) { a += b; return (a >= MOD) ? (a - MOD) : a; }
inline ll sub(ll a, ll b) { a -= b; return (a < 0) ? (a + MOD) : a; }
inline ll mul(ll a, ll b) { a *= b; if (a >= MOD) a = a - a / MOD * MOD; return a; }
template <typename T> inline bool chkmin(T &a, T b) { return (a > b) ? (a = b, true) : false; }
template <typename T> inline bool chkmax(T &a, T b) { return (a < b) ? (a = b, true) : false; }
ll Pow(ll a, ll t) { ll b = 1; for (; t > 0; t >>= 1, a *= a) if (t & 1) b *= a; return b; }
ll qpow(ll a, ll t) { ll b = 1; for (; t > 0; t >>= 1, a = mul(a, a)) if (t & 1) b = mul(b, a); return b; }

// ******************************************************************************************************************************
// ******************************************************************************************************************************

const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;

int n;
string s;
vector<int> res;
bool vis[1005][1005];

bool DFS(int u, int status) {
    if (u == s.length()) {
        return !status;
    }
    if (vis[u][status]) return false;
    vis[u][status] = true;
    int l = u == 0 ? 1 : 0, r = 9;
    if (s[u] != '?') l = r = s[u] - '0';
    for (int i = l; i <= r; i++) {
        if (DFS(u + 1, (status * 10 + i) % n)) {
            res.push_back(i);
            return true;
        }
    }
    return false;
}

void solve() {
    while (cin >> s >> n) {
        res.clear();
        memset(vis, false, sizeof vis);
        if (!DFS(0, 0)) cout << "*" << endl;
        else {
            reverse(res.begin(), res.end());
            for (int &x : res) cout << x; cout << endl;
        }
    }
}

F - Fundrasing

Solution of F

先把数据按b从小到大排，按f从大到小排。然后把b、f均相同的项合并，离散化f，就可以用树状数组优化dp了。

Code of 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
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
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

void solve();
int main() {
#ifdef Semon0x29a
    assert(freopen("Testing.txt", "r", stdin));
    clock_t st = clock();
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
#ifdef Semon0x29a
    clock_t ed = clock();
    cerr << (ed - st) * 1.0 / CLOCKS_PER_SEC << endl;
#endif
}

typedef long long ll;

const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;

struct Node {
    int b, f;
    ll d;
    bool operator< (const Node& x) const {
        return b < x.b || (b == x.b && f > x.f);
    }
};

struct uniq : vector<int> {
    void solve() { sort(begin(), end()); erase(unique(begin(), end()), end()); }
    inline int getid(int x) { return lower_bound(begin(), end(), x) - begin(); }
}uni;

struct IT {
    ll a[maxn];
    void init() { memset(a, 0, sizeof a); }
    void upd(int i, ll x) {
        for (; i < maxn; i += (i & (-i))) {
            a[i] = max(a[i], x);
        }
    }
    ll query(int i) {
        ll ret = 0;
        for (; i > 0; i -= (i & (-i))) {
            ret = max(ret, a[i]);
        }
        return ret;
    }
}it;

int n;
Node a[maxn];

void solve() {
    while (cin >> n) {
        uni.clear();
        for (int i = 0; i < n; i++) {
            cin >> a[i].b >> a[i].f >> a[i].d;
            uni.push_back(a[i].f);
        }
        uni.solve();
        sort(a, a + n);

        int m = -1;
        for (int i = 1, j = 0; i < n; i++) {
            if (a[i].b == a[j].b && a[i].f == a[j].f) a[j].d += a[i].d;
            else a[++j] = a[i];
            m = j;
        }
        n = m + 1;

        it.init();
        for (int i = 0; i < n; i++) {
            int pos = uni.getid(a[i].f) + 1;
            it.upd(pos, it.query(pos - 1) + a[i].d);
        }
        cout << it.query(uni.size()) << endl;
    }
}

I - Imperial roads(-4, unsolve)

Solution of I(temp)

先构造MST(最小生成树)，然后对于每个询问，判断该边是否在MST上。
若在，则$res$为mst的边权和。若不在，将该边加到mst上，此时会构成环，将环上除该边外的最长边去掉即可，$res$即为$SumMST + w - max(环上边权)$

J - Jumping frog

Solution of J

忘记题意了…做法大概是直接枚举= =

Code of J

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
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(a) (int)a.size()
#define endl '\n'
#define all(a) a.begin(), a.end()

inline bool _R(int & x) { return scanf("%d", &x) == 1; }
inline bool _R(long long &x) { return scanf("%lld", &x) == 1; }
inline bool _R(double &x) { return scanf("%lf", &x) == 1; }
inline bool _R(char &x) { return scanf(" %c", &x) == 1; }
inline bool _R(char *x) { return scanf("%s", x) == 1; }
template <typename T, typename U> inline bool _R(pair<T, U> &x) { return _R(x.first) && _R(x.second); }
inline bool Read() { return 1; }
template <typename T, typename... U> inline bool Read(T &head, U &... tail) { return _R(head) && Read(tail...); } 
inline void _W(const int &x) { printf("%d", x); }
inline void _W(const long long &x) { printf("%lld", x); }
inline void _W(const double &x) { printf("%.10f", x); }
inline void _W(const char &x) { putchar(x); }
inline void _W(const char *x) { printf("%s", x); }
template <typename T, typename U> inline void _W(const pair<T, U> &x) { _W(x.first); putchar(' '); _W(x.second); }
template <typename T> inline void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) { if (i != x.begin()) { putchar(' '); }}}
inline void Write() {}
template <typename T, typename... U> inline void Write(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); Write(tail...); }
const int Move[][2] = { { 0, 0 },{ 1, 0 },{ 0, 1 },{ 0, -1 },{ -1, 0 },{ 1, 1 },{ 1, -1 },{ -1, 1 },{ -1, -1 } };

#ifdef Semon0x29a
    #define debug(...) Write(__VA_ARGS__)
#else
    #define debug(...) 2333
#endif

typedef long long ll;
typedef vector<int> VI;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

void solve();
int32_t main() {
#ifdef Semon0x29a
    assert(freopen("Testing.txt", "r", stdin));
    clock_t START = clock();
#endif
    solve();
    debug((clock() - START) * 1.0 / CLOCKS_PER_SEC);
}

const int MOD = 1e9 + 7;
inline ll sqr(ll a) { return a * a; }
inline ll add(ll a, ll b) { a += b; return (a >= MOD) ? (a - MOD) : a; }
inline ll sub(ll a, ll b) { a -= b; return (a < 0) ? (a + MOD) : a; }
inline ll mul(ll a, ll b) { a *= b; if (a >= MOD) a = a - a / MOD * MOD; return a; }
template <typename T> inline bool chkmin(T &a, T b) { return (a > b) ? (a = b, true) : false; }
template <typename T> inline bool chkmax(T &a, T b) { return (a < b) ? (a = b, true) : false; }
ll Pow(ll a, ll t) { ll b = 1; for (; t > 0; t >>= 1, a *= a) if (t & 1) b *= a; return b; }
ll qpow(ll a, ll t) { ll b = 1; for (; t > 0; t >>= 1, a = mul(a, a)) if (t & 1) b = mul(b, a); return b; }

// ******************************************************************************************************************************
// ******************************************************************************************************************************

const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int n;
string s;
bool ok[maxn];

void solve() {
    while (cin >> s) {
        n = s.length();
        memset(ok, false, sizeof ok);
        for (int i = 1; i < n; i++) {
            if (n % i != 0) continue;
            for (int j = 0; j < n; j++) {
                bool flag = true;
                for (int k = 0; k <= n / i; k++) {
                    if (s[(j + k * i) % n] != 'R') {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    ok[i] = true;
                    break;
                }
            }
        }
        int res = 0;
        for (int i = 1; i < n; i++) {
            if (ok[__gcd(i, n)]) {
                res++;
            }
        }
        cout << res << endl;
    }
}