Traning - 2017 ICPC 沈阳区域赛

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

---

F - Heron and His Triangle (00:52)

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

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

Code:

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:

#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:

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:

#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:

#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:

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