Traning - 2017 ICPC 沈阳区域赛

这波总体还行,四题+罚时大概在铜牌区前部分, G题如果莽几波或许能过, 感觉还是要多刷题才行= =


F - Heron and His Triangle (00:52)

给定一个n,求一个最小的t满足$t \geq n$且长度为t-1, t, t+1的边组成的三角形面积为整数。

打了前面一部分表,用BM推出公式后上Java秒了。

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
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
public static void main(String[] args) {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
Task solver = new Task();
try {
while (true) {
solver.solve(in, out);
}
} catch (RuntimeException e) {
out.close();
}
}

public static class Task {
public static void solve(InputReader in, PrintWriter out) {
BigInteger[] a = new BigInteger[200];
a[0] = BigInteger.valueOf(4);
a[1] = BigInteger.valueOf(14);
for (int i = 2; i < 200; i++) {
a[i] = a[i - 1].multiply(BigInteger.valueOf(4)).subtract(a[i - 2]);
}
int T = in.nextInt();
while ((T--) > 0) {
BigInteger n = in.nextBigInteger();
for (int i = 0; i < 200; i++) {
if (a[i].compareTo(n) >= 0) {
out.println(a[i]);
break;
}
}
}
}
}

public static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;

public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}

public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}

public int nextInt() {
return Integer.parseInt(next());
}

public long nextLong() {
return Long.parseLong(next());
}

public double nextDouble() {
return Double.parseDouble(next());
}

public BigInteger nextBigInteger() {
return new BigInteger(next());
}

public BigDecimal nextBigDecimal() {
return new BigDecimal(next());
}
}
}

G - Infinite Fraction Path (Upsolved)

给定n结点的有向图,每个点有一个数字$Di$且仅有一条出边,问从哪个结点出发经过n个点后,路径上数字相连组成的数字最大

Solution:

想了好久的贪心都觉得会TLE, 结果一看题解居然是bfs+剪枝过的= =

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

// -------------------------head start here---------------------------------------
#define pb push_back
#define mp make_pair
#define sz(a) (int)a.size()
#define endl '\n'
#define all(a) a.begin(),a.end()
#define rep(i, n) for(int i = 0; i < int(n); i++)
#define drep(i, n) for(int i = int(n) - 1; i >= 0; i--)
#define Rep(i, a, b) for(int i = int(a); i <= int(b); i++)
#define dRep(i, a, b) for (int i = int(a); i >= int(b); i--)
#define mst(a, x) memset(a, x, sizeof a)

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using VI = vector<int>;
using VL = vector<long long>;

const int MAX = 150005;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const int Move[][3] = { { 0, 0 },{ 1, 0 },{ 0, 1 },{ 0, -1 },{ -1, 0 },{ 1, 1 },{ 1, -1 },{ -1, 1 },{ -1, -1 } };

inline ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template <class T> inline ll sqr(T x) { return 1ll * x * x; }
ll qpow(ll a, int t) { a %= MOD; ll b = 1; for (; t; t >>= 1, (a *= a) %= MOD) if (t & 1) (b *= a) %= MOD; return b; }
template <class T> inline bool chkmax(T& a, T b) { return (a < b) ? (a = b, 1) : 0; }
template <class T> inline bool chkmin(T& a, T b) { return (a > b) ? (a = b, 1) : 0; }
// -----------------------------head end here-------------------------------------

int n;
char s[MAX];
char ans[MAX];

struct Node {
int id, step;
Node(int a = 0, int b = 0) : id(a), step(b) {}
};

int used[MAX];
queue<Node> Q;

void BFS() {
while (!Q.empty()) {
Node u = Q.front(); Q.pop();

if (u.step >= n) continue;
if (s[u.id] < ans[u.step]) continue;
chkmax(ans[u.step], s[u.id]);

Node v = { (1ll * u.id * u.id + 1) % n, u.step + 1 };
if (s[v.id] < ans[v.step]) continue;
if (used[v.id] == v.step) continue;
used[v.id] = v.step;
Q.push(v);
chkmax(ans[v.step], s[v.id]);
}
}

int32_t main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int T, Case = 0; cin >> T;
while (T--) {
cin >> n >> s;

char mx = -1;
rep(i, n) {
chkmax(mx, s[i]);
ans[i] = 0, used[i] = -1;
}

while (!Q.empty()) Q.pop();
rep(i, n) {
if (s[i] == mx) {
Q.emplace(i, 0);
}
}
BFS();

cout << "Case #" << ++Case << ": ";
rep(i, n) cout << ans[i];
cout << endl;
}
}

I - Little Boxes (00:07)

签到题, 求$a+b+c+d$就好,不过数据刚好爆ull,上了一波Java。(long double 也可过)

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
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
public static void main(String[] args) {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
Task solver = new Task();
try {
while (true) {
solver.solve(in, out);
}
} catch (RuntimeException e) {
out.close();
}
}

public static class Task {
public static void solve(InputReader in, PrintWriter out) {
int T = in.nextInt();
while ((T--) > 0) {
BigInteger a = in.nextBigInteger(), b = in.nextBigInteger(), c = in.nextBigInteger(), d = in.nextBigInteger();
out.println(a.add(b).add(c).add(d));
}
}
}

public static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;

public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}

public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}

public int nextInt() {
return Integer.parseInt(next());
}

public long nextLong() {
return Long.parseLong(next());
}

public double nextDouble() {
return Double.parseDouble(next());
}

public BigInteger nextBigInteger() {
return new BigInteger(next());
}

public BigDecimal nextBigDecimal() {
return new BigDecimal(next());
}
}
}

K - Rabbit (00:32)

有n只兔子,最外侧的兔子可以跳到任意两只其他兔子中间(不能重合), 问最多能跳多少次。

显然最优策略是全部往左跳or全部往右跳,两者取最优即可

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

#define endl "\n"

int a[505];

int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int T; cin >> T;
while (T--) {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}

long long res1 = 0, res2 = 0;
for (int i = 2; i < n; i++) {
res1 += a[i + 1] - a[i] - 1;
}
for (int i = 1; i < n - 1; i++) {
res2 += a[i + 1] - a[i] - 1;
}
cout << max(res1, res2) << endl;
}
}

L - Tree (01:43)

给定一棵有n个结点的树,你可以把任一结点染成给定的k种颜色中的任意一种,设$Ei$为使所有颜色为i的结点相连的最小边集,求最大的$E1 \bigcap E2 \bigcap … \bigcap Ek$的size

Solution:

只要使所有子树大小大于等于k的结点相连,所使用的边集即为所求。
(代码写得有点丑,看网上题解的dfs很流畅的样子。)

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

#define endl "\n"

const int MAX = 2e5 + 5;

int n, k, m;
vector<int> e[MAX];
int deg[MAX], cnt[MAX], vis[MAX];

int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int T; cin >> T;
while (T--) {
cin >> n >> k;
for (int i = 0; i <= n; i++) {
e[i].clear(); deg[i] = cnt[i] = vis[i] = 0;
}
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
deg[u]++, deg[v]++;
}

queue<int> Q;
for (int i = 1; i <= n; i++) {
if (deg[i] == 1) {
Q.push(i);
}
}
while (!Q.empty()) {
int u = Q.front(); Q.pop();
cnt[u]++;
for (int i = 0; i < (int)e[u].size(); i++) {
if (deg[e[u][i]] > 1) {
deg[u]--; deg[e[u][i]]--; cnt[e[u][i]] += cnt[u];
if (deg[e[u][i]] == 1) {
Q.push(e[u][i]);
}
}
}
}

int res = 0;
while (!Q.empty()) Q.pop();
for (int i = 1; i <= n; i++) {
if (cnt[i] >= k) {
Q.push(i);
break;
}
}
while (!Q.empty()) {
int u = Q.front(); Q.pop();
vis[u] = 1;
for (int i = 0; i < (int)e[u].size(); i++) {
int v = e[u][i];
if (!vis[v] && cnt[v] >= k) {
Q.push(v), ++res;
}
}
}
cout << res << endl;
}
}

M - Wandering Robots(Upsolved)

n * n的棋盘上有一个机器人,初始在(0, 0)处,每秒都会等概率地往四周完好的格子移动or不动,问机器人最终在一个满足$x + y \geq n - 1$的格子(x, y)上的概率

Solution:

棋盘四角的格子权值置为3, 四条边界上的格子置为4, 中间的置为5, 然后将坏格子的权值置为0,
它四周的格子权值减1(若大于0), 然后将符合条件的格子权值加起来,除以整个棋盘的权值和就可以了。

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

#define endl "\n"

const int Move[][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

map<pair<int, int>, int> Map;

bool angle(int x, int y, int n) {
if (x == 0 && y == 0) return true;
if (x == 0 && y == n - 1) return true;
if (x == n - 1 && y == 0) return true;
if (x == n - 1 && y == n - 1) return true;
return false;
}

bool border(int x, int y, int n) {
if (x == 0 || y == 0) return true;
if (x == n - 1 || y == n - 1) return true;
return false;
}

int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int T, Case = 0; cin >> T;
while (T--) {
int n, k; cin >> n >> k;

Map.clear();
while (k--) {
int x, y; cin >> x >> y;
Map[{ x, y }] += 5;
if (angle(x, y, n)) Map[{ x, y }] = min(Map[{ x, y }], 3);
else if (border(x, y, n)) Map[{ x, y }] = min(Map[{ x, y }], 4);
else Map[{ x, y }] = min(Map[{ x, y }], 5);

for (int i = 0; i < 4; i++) {
int xx = x + Move[i][0], yy = y + Move[i][1];
if (xx >= 0 && xx < n && yy >= 0 && yy < n) {
Map[{ xx, yy }]++;
if (angle(xx, yy, n)) Map[{ xx, yy }] = min(Map[{ xx, yy }], 3);
else if (border(xx, yy, n)) Map[{ xx, yy }] = min(Map[{ xx, yy }], 4);
else Map[{ xx, yy }] = min(Map[{ xx, yy }], 5);
}
}
}

long long up = 1ll * (n - 1) * (n - 2) / 2 * 5 + 9 + 8ll * (n - 2);
long long down = 1ll * (n - 2) * (n - 2) * 5 + 12 + 16ll * (n - 2);

if (!Map.empty()) {
for (auto i : Map) {
int x, y; tie(x, y) = i.first;
down -= i.second;
if (x + y >= n - 1) {
up -= i.second;
}
}
}

long long gcd = __gcd(up, down);
cout << "Case #" << ++Case << ": " << up / gcd << "/" << down / gcd << endl;
}
}