2017-2018 ACM-ICPC Latin American Regional Programming Contest

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;
}
}