2018-2019 ACM-ICPC Asia Jakarta Regional Contest

有个队友咕咕了，打得一般，题目难度不是很难

---

A：

solver：czq

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define pb emplace_back
#define mp make_pair
#define eps 1e-8
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

string s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    int n = s.size(), zero = 0, one = 0;
    for (auto i : s) {
        if (i == '0') zero++;
        else one++;
    }
    if (zero == one) {
        if (s[0] == '0') {
            cout << "1";
            for (int i = 0; i < n - 1; i++) cout << "0";
        } else {
            cout << "0";
            for (int i = 0; i < n - 1; i++) cout << "1";
        }
        cout << endl;
    } else {
        for (int i = 0; i < n; i++) {
            if (zero > one) {
                if (s[i] == '0') s[i] = '1';
            } else {
                if (s[i] == '1') s[i] = '0';
            }
        }
        cout << s << endl;
    }
    return 0;
}

D：

solver：czq、zyh

一开始还看错题了，原来穿过的冰面是不算的，需要把地图中间的冰面换成草地

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define pb emplace_back
#define mp make_pair
#define eps 1e-8
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

const int MAXN = 555;
int n, m, ans = 0;
char a[MAXN][MAXN];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
    if (n == 1) {
        for (int i = 2; i < m; i++) {
            if (a[1][i] == '.') ans++;
        }
        printf("%d
", ans);
    } else if (n == 2) {
        for (int i = 2; i < m; i++) {
            if (a[1][i] == '.' && a[1][i] == a[2][i]) ans++;
        }
        printf("%d
", ans);
    } else if (m == 1) {
        for (int i = 2; i < n; i++) {
            if (a[i][1] == '.') ans++;
        }
        printf("%d
", ans);
    } else if (m == 2) {
        for (int i = 2; i < n; i++) {
            if (a[i][1] == '.' && a[i][1] == a[i][2]) ans++;
        }
        printf("%d
", ans);
    } else {
        int tmp = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if ((i == 1 || i == n) && (j == 1 || j == m)) continue;
                else if (i == 1 || i == n || j == 1 || j == m) {
                    if (a[i][j] == '#') tmp = 0;
                } else if (a[i][j] == '.') ans++;
            }
        }
        printf("%d
", ans + tmp);
    }
    return 0;
}

G：

solver：czq

挺弱智的图论题

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define pb emplace_back
#define mp make_pair
#define eps 1e-8
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

const int MAXN = 555;
int n, m, d[MAXN], cnt = 0, ans = 999, vis[MAXN][MAXN];
// since max d[x]+d[y] is 999

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    cnt = n * (n - 1) / 2;
    for (int i = 1; i <= m; i++) {
        int s, t; cin >> s >> t;
        d[s]++, d[t]++;
        vis[s][t] = vis[t][s] = 1;
        cnt--;
    }

    function<void(int, int)> solve = [&](int x, int y) {
        if (x > y) swap(x, y);
        d[x]++, d[y]++;
        vis[x][y] = vis[y][x] = 1;
        cnt--;
        for (int i = 1; i <= n; i++) {
            if (i == x || i == y) continue;
            if (!vis[x][i] && d[x] + d[i] >= ans) solve(x, i);
            if (!vis[y][i] && d[y] + d[i] >= ans) solve(y, i);
        }
    };

    while (cnt) {
        ans--;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (!vis[i][j] && d[i] + d[j] >= ans) {
                    solve(i, j);
                }
            }
        }
    }

    printf("%d
", ans);
    return 0;
}

H：

solver：czq

优先队列

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define pb emplace_back
#define mp make_pair
#define eps 1e-8
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

const int MAXN = 1e5 + 10;
struct Node {
    int l, r, c;
    Node() {}
    Node(int _l, int _r, int _c): l(_l), r(_r), c(_c) {}
    bool operator<(const Node &rhs)const {
        return l < rhs.l || (l == rhs.l && r < rhs.r);
    }
} que[MAXN];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
int n, m, qTop = 0, s = 0, a[MAXN], pre[MAXN], cnt0[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    pre[0] = cnt0[0] = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
        cnt0[i] = cnt0[i - 1] + (a[i] == 0 ? 1 : 0);
    }
    int flag = 1;
    for (int i = 0; i < m; i++) {
        int l, r, c;
        cin >> l >> r >> c;
        int tmp = pre[r] - pre[l - 1] + cnt0[r] - cnt0[l - 1] - c;
        if (tmp < 0) {
            cout << "Impossible" << endl;
            flag = 0;
        }
        que[i] = Node(l, r, tmp / 2);
    }
    if (!flag) return 0;
    sort(que, que + m);
    for (int i = 1; i <= n; i++) {
        while (qTop < m && que[qTop].l <= i) {
            pq.push(mp(que[qTop].c + s, que[qTop].r));
            qTop++;
        }
        while (pq.size() && pq.top().second < i) pq.pop();
        if (a[i]) continue;
        if (pq.empty() || pq.top().first > s) {
            s++, a[i] = -1;
        } else {
            a[i] = 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << " ";
        cout << a[i];
    }
    cout << endl;
    return 0;
}

I：

solver：czq

光速签到

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define pb emplace_back
#define mp make_pair
#define eps 1e-8
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

const int MAXN = 1e5 + 10;
int n, ans = 0;
string s[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];
    ans = s[n - 1][0] == 'T' ? 1 : 0;
    for (int i = n - 2; i >= 0; i--) {
        if (s[i][0] == 'L') ans ^= 1;
    }
    if (ans) cout << "TRUTH" << endl;
    else cout << "LIE" << endl;
    return 0;
}

J：

solver：czq、zyh

dfs搞出所有字串之后O(n)dp

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define pb emplace_back
#define mp make_pair
#define eps 1e-8
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

const int MAXN = 5e6 + 10, MAXM = 20;
struct Node {
    char s[MAXM];
    int id;
    bool operator<(const Node &rhs)const {
        int t = strcmp(s, rhs.s);
        return t ? t<0: id>rhs.id;
    }
} a[MAXN];
int n, aTop = 0, sum[MAXM];
char s[MAXM], t[MAXM];

int main() {

    function<void(int, int, int)> dfs = [&](int step, int length, int id) {
        if (!s[step]) {
            if (length) {
                copy(t, t + length, a[aTop].s);
                a[aTop++].id = id;
            }
            return;
        }
        dfs(step + 1, length, id);
        t[length] = s[step];
        dfs(step + 1, length + 1, id);
    };

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        dfs(0, 0, i);
    }
    for (int i = 1; i <= n; i++) sum[i] = INT_MIN;
    sort(a, a + aTop);
    for (int i = 0; i < aTop; i++) {
        sum[a[i].id] = max(sum[a[i].id], (int)strlen(a[i].s) + sum[a[i].id - 1]);
    }
    printf("%d
", max(sum[n], -1));
    return 0;
}

L：

solver：zyh

#include <bits/stdc++.h>
using namespace std;
char str[100];
long long p[61];
long long mask[61];
void init() {
    p[0] = 1;
    mask[0] = 1;
    for (int i = 1; i < 61; ++i) {
        p[i] = p[i - 1] * 2;
        mask[i] = p[i] | mask[i - 1];
    }
}
long long findMaxBit(long long x) {
    int cnt = 0;
    for (int i = 60; i >= 1; --i) {
        if (x & p[i]) cnt++;
        if (cnt == 2) return ((x >> (i + 1)) << i) | (mask[i - 1] & x);
    }
    return x >> 1;
}
void output(long long x) {
    if (x > 1) output(x >> 1);
    cout << (x & 1);
}
int main() {
    long long k, s = 0;
    cin >> k;
    cin >> str;

    init();
    //cout<<p[60]<<endl<<mask[60]<<endl;
    int len = strlen(str);
    for (int i = len - 1; i >= 0; --i) {
        if (str[i] == '1') s += p[len - i - 1];
    }
    int ans = 0;
    while (s > k) {
        ans++;
        s = findMaxBit(s);
        //output(s);
        //cout<<endl;
    }
    cout << ans;
}