Skip to content

2019-2020 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

Contents

Contest Info

Solved A B C D E F G H I J K L M
9/13 O O O O O - - - O - O O O
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • - 没有尝试

Solutions

A. Radio Prize

Solved By Dup4. 2:26(+)

题意：

给出一棵树，每个点有点权 t_i, 每条边有边权 w_i, 现在要对于每个点 i，计算 \sum\limits_{j = 1}^n [i \neq j](t_i + t_j) \cdot d(i, j)，其中 d(i, j) 表示 i \to j 的简单路径的长度。

思路：

将贡献拆成 t_id(i, j) + t_jd(i, j)，然后维护距离和、点权和、乘积和，换根 dp 即可。

Code 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
using pLL = pair<ll, ll>;
const int N = 1e5 + 10;
int n, a[N], fa[N], sze[N];
ll res[N];

struct Graph {
    struct E {
        int to, nx, w;
    } e[N << 1];
    int h[N], cnt;
    void init(int n) {
        for (int i = 0; i <= n; ++i) h[i] = -1;
        cnt = -1;
    }
    void addedge(int u, int v, int w = 0) {
        e[++cnt] = {v, h[u], w};
        h[u] = cnt;
    }
} G;

struct E {
    ll Sdis, Sval, S;
} f[N], g[N];

void dfs(int u) {
    f[u] = {0, 0, 0};
    sze[u] = 1;
    for (int i = G.h[u]; ~i; i = G.e[i].nx) {
        int v = G.e[i].to, w = G.e[i].w;
        if (v == fa[u])
            continue;
        fa[v] = u;
        dfs(v);
        sze[u] += sze[v];
        f[u].Sdis += f[v].Sdis + 1ll * sze[v] * w;
        f[u].Sval += f[v].Sval;
        f[u].S += f[v].S + f[v].Sval * w;
    }
    res[u] += 1ll * a[u] * f[u].Sdis + f[u].S;
    f[u].Sval += a[u];
}

void dfs1(int u) {
    for (int i = G.h[u]; ~i; i = G.e[i].nx) {
        int v = G.e[i].to, w = G.e[i].w;
        if (v == fa[u])
            continue;
        g[v].Sdis = g[u].Sdis + f[u].Sdis - f[v].Sdis - 1ll * sze[v] * w + 1ll * (n - sze[v]) * w;
        g[v].Sval = g[u].Sval + f[u].Sval - f[v].Sval;
        g[v].S = g[u].S + f[u].S - f[v].S - f[v].Sval * w + g[v].Sval * w;
        res[v] += 1ll * a[v] * g[v].Sdis + g[v].S;
        dfs1(v);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), res[i] = 0;
    G.init(n);
    for (int i = 1, u, v, w; i < n; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        G.addedge(u, v, w);
        G.addedge(v, u, w);
    }
    dfs(1);
    g[1] = {0, 0, 0};
    dfs1(1);
    for (int i = 1; i <= n; ++i) printf("%lld\n", res[i]);
    return 0;
}

B. Perfect Flush

Solved By Hsueh-. 3:00(+1)

题意：

给出 n 个数 x_i, 保证 1 \leq x_i \leq k，并且保证 1, \cdots k 中每个数至少出现了一次，现在要找出一个字典序最小的子序列，使得这个子序列是一个长度为 k 的排列。

思路：

利用单调栈，如果栈顶元素在后面存在且比当前元素大，则 pop 掉，如果当前元素本身就在栈中则 continue。

Code 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, k;
int a[N];
int res[N];
int cnt[N];
int in[N];
stack<int> st;

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        cnt[a[i]]++;
    }
    for (int i = 1; i <= n; ++i) {
        cnt[a[i]]--;
        if (in[a[i]])
            continue;
        while (!st.empty() && a[i] < st.top() && cnt[st.top()]) {
            in[st.top()] = 0;
            st.pop();
        }
        in[a[i]] = 1;
        st.push(a[i]);
    }
    for (int i = k; i >= 1; --i) {
        res[i] = st.top();
        st.pop();
    }
    for (int i = 1; i <= k; ++i) {
        printf("%d%c", res[i], " \n"[i == k]);
    }
    return 0;
}

C. Coloring Contention

Solved By Hsueh-. 0:48(+)

题意：

  • 给出一个 n 个点 m 条边的无向图，没有重边，没有自环，Alice 可以将边染成红色或者蓝色，定义一条路径的 color change 次数为将路径上经过的边按顺序排列，任意两个相邻的边颜色不同即记一次 color change。
  • 现在 Bob 要选择一条 1 \to n 的路径，问 Alice 如果染色，使得 Bob 的最优解最大，即 color change 次数最多。输出这个最大值。

思路：

  • 显然答案的上界为 1 \to n 的 \mbox{最短路长度} - 1最短路长度，猜测一定能有一种方案能够做到。
Code 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 1e9;
int n, m;

vector<vector<int>> G;

int dis[N], use[N];

void bfs(int st) {
    for (int i = 1; i <= n; ++i) {
        dis[i] = INF;
        use[i] = 0;
    }
    queue<int> que;
    que.push(st);
    dis[st] = 0;
    use[st] = 1;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto &v : G[u]) {
            if (dis[v] > dis[u] + 1) {
                dis[v] = dis[u] + 1;
                que.push(v);
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    G.clear();
    G.resize(n + 1);
    for (int i = 1, u, v; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bfs(1);
    printf("%d\n", dis[n] - 1);
    return 0;
}

D. Dividing by Two

Solved By Hsueh-. 0:14(+)

题意：

  • 给定两个数字 A,B，对于 A 有两种操作：
  • 当 A 是偶数则可以除以 2。
  • 加一。
  • 问最小的操作次数使得 A 变成 B。

思路：

  • 如果 A < B 则很显然答案是两者差值。
  • 如果 A = B 则很显然答案是 0。
  • 剩下的模拟即可.
Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll a, b;

int main() {
    scanf("%lld %lld", &a, &b);
    ll res = 0;
    while (a > b) {
        if (a & 1)
            ++a;
        else
            a /= 2;
        ++res;
    }
    res += b - a;
    printf("%lld\n", res);
    return 0;
}

E. Rainbow Strings

Solved By Hsueh-. 0:18(+)

题意：

定义一个 rainbow string 为字符串中任意两个字符都不相同，现在给出一个字符串 s，问它有多少个子序列是 rainbow string。

思路：

答案为 \prod (\mbox{每个字符出现次数 + 1})每个字符出现次数。

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5 + 10;
const ll p = 11092019;

char s[N];
ll cnt[N];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for (int i = 1; i <= n; ++i) {
        cnt[s[i]]++;
    }
    ll res = 1;
    for (int i = 'a'; i <= 'z'; ++i) {
        res = res * (cnt[i] + 1) % p;
    }
    printf("%lld\n", res);
    return 0;
}

F. Carny Magician

UnSolved.

题意：

思路：

G. Glow, Little Pixel, Glow

UnSolved.

题意：

思路：

H. Pivoting Points

UnSolved.

题意：

思路：

I.Error Correction

Solved By Hsueh- & Dup4. 1:28(+1)

题意：

  • 给出 n 个字符串，每个字符串等长，并且任意两个字符不相同，定义任意两个字符串不可以共存当且仅当其中一个字符串可以通过交换一对字符变成另一个字符串，现在要求选出最大的字符串子集，使得其中任意两个字符串都可以共存。

思路：

  • 将不能共存的连边，等价于求最大独立集。
  • 但是求最大独立集的朴素算法是 O(n^4)，但是如果它是二分图，就等价于求最大匹配。
  • 那么考虑该图中不会有奇环，因为一次交换可以理解为一个逆序对，一个字符串经过若干次交换回到本身，肯定是经过偶数次交换。
  • 那么根据逆序对数量的奇偶性将字符串分成左右两边。
Code 
#include <bits/stdc++.h>

using namespace std;

const int N = 5e2 + 10;

int n;
int inv[N];
string s[N];
vector<vector<int> > G;
int linker[N], used[N];

bool dfs(int u) {
    for (auto v : G[u]) {
        if (!used[v]) {
            used[v] = true;
            if (linker[v] == -1 || dfs(linker[v])) {
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}

int hungray() {
    int res = 0;
    memset(linker, -1, sizeof linker);
    for (int u = 1; u <= n; ++u) {
        if (inv[u] % 2 == 0)
            continue;
        memset(used, false, sizeof used);
        if (dfs(u))
            ++res;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n;
    G.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
    }
    for (int i = 1; i <= n; ++i) {
        int sze = s[i].size();
        for (int j = 1; j <= n; ++j) {
            int cnt = 0;
            for (int k = 0; k < sze; ++k) {
                cnt += s[i][k] != s[j][k];
            }
            if (cnt == 2) {
                G[i].push_back(j);
            }
        }
        for (int j = 0; j < sze; ++j) {
            for (int k = j + 1; k < sze; ++k) {
                inv[i] += (s[i][j] > s[i][k]);
            }
        }
    }
    // for (int i = 1; i <= n; ++i) {
    //     cout << i << " " << inv[i] % 2 << endl;
    // }
    int res = hungray();
    // cout << res << endl;
    cout << n - res << endl;
    return 0;
}

J. Interstellar Travel

UnSolved.

题意：

思路：

K. Computer Cache

Solved By Dup4. 3:40(+)

题意：

有 m 个数据块，第 i 个数据块的长度为 s_i。

有一个 cache，支持三种操作：

  • 1 i p, 将第 i 个数据块加载进 cache, 起始位置为 p。
  • 2 p, 输出 cache 中第 p 个位置的数值。
  • 3 i l r, 将第 i 个数据块中的 [l, r] 中每个数字都 +1 \bmod 256，即 x_i = (x_i + 1) \bmod 256。

思路：

  • 考虑查询可能会查询历史版本，容易想到可持久化线段树。
  • 但是 5 \cdot 10^5 的数据量，在时间和空间上都不太允许，可以直接离线，记录版本号。
Code 
#include <bits/stdc++.h>
#define SZ(x) (int(x.size()))
#define fi first
#define se second
using namespace std;
using ll = long long;
using pII = pair<int, int>;
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
const int N = 5e5 + 10;
int n, m, q, ver[N], sze[N], res[N], isQuery[N];
vector<vector<int>> vec;

struct W {
    int i, p, ver;
};

struct SEG {
    struct node {
        W val, lazy;
        void init() {
            val = lazy = {-1, -1, -1};
        }
        void up(W _lazy) {
            val = _lazy;
            lazy = _lazy;
        }
    } t[N << 2], res;
    void down(int id) {
        W &lazy = t[id].lazy;
        if (lazy.i == -1)
            return;
        t[id << 1].up(lazy);
        t[id << 1 | 1].up(lazy);
        lazy = {-1, -1, -1};
    }
    void build(int id, int l, int r) {
        t[id].init();
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
    void update(int id, int l, int r, int ql, int qr, W v) {
        if (l >= ql && r <= qr) {
            t[id].up(v);
            return;
        }
        int mid = (l + r) >> 1;
        down(id);
        if (ql <= mid)
            update(id << 1, l, mid, ql, qr, v);
        if (qr > mid)
            update(id << 1 | 1, mid + 1, r, ql, qr, v);
    }
    W query(int id, int l, int r, int pos) {
        if (l == r)
            return t[id].val;
        int mid = (l + r) >> 1;
        down(id);
        if (pos <= mid)
            return query(id << 1, l, mid, pos);
        else
            return query(id << 1 | 1, mid + 1, r, pos);
    }
} seg;

struct TSEG {
    struct node {
        int lazy, sum;
        node() {
            lazy = sum = 0;
        }
        void up(int _lazy) {
            sum += _lazy;
            lazy += _lazy;
        }
        node operator+(const node &other) const {
            node res = node();
            res.sum = sum + other.sum;
            return res;
        }
    } t[N << 2];
    void down(int id) {
        int &lazy = t[id].lazy;
        t[id << 1].up(lazy);
        t[id << 1 | 1].up(lazy);
        lazy = 0;
    }
    void build(int id, int l, int r, const vector<int> &a) {
        if (l == r) {
            t[id].sum = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid, a);
        build(id << 1 | 1, mid + 1, r, a);
        t[id] = t[id << 1] + t[id << 1 | 1];
    }
    void update(int id, int l, int r, int ql, int qr, int v) {
        if (l >= ql && r <= qr) {
            t[id].up(v);
            return;
        }
        int mid = (l + r) >> 1;
        down(id);
        if (ql <= mid)
            update(id << 1, l, mid, ql, qr, v);
        if (qr > mid)
            update(id << 1 | 1, mid + 1, r, ql, qr, v);
    }
    int query(int id, int l, int r, int pos) {
        if (l == r)
            return t[id].sum;
        int mid = (l + r) >> 1;
        down(id);
        if (pos <= mid)
            return query(id << 1, l, mid, pos);
        else
            return query(id << 1 | 1, mid + 1, r, pos);
    }
} tseg;

struct E {
    int l, r;
    vector<pII> vec;
};

vector<vector<E>> OP;

int main() {
    scanf("%d%d%d", &n, &m, &q);
    vec.resize(m + 1);
    OP.clear();
    OP.resize(m + 1);
    seg.build(1, 1, n);
    for (int i = 1, sz; i <= m; ++i) {
        scanf("%d", &sz);
        sze[i] = sz;
        ver[i] = 0;
        vector<int> tmp(sz + 1);
        for (int j = 1, x; j <= sz; ++j) {
            scanf("%d", &x);
            tmp[j] = x;
        }
        vec[i] = tmp;
        //	dbg(i, sz);
    }
    for (int _q = 1; _q <= q; ++_q) {
        isQuery[_q] = 0;
        int op, i, l, r, p;
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d", &i, &p);
            seg.update(1, 1, n, p, p + sze[i] - 1, {i, p, ver[i]});
        } else if (op == 2) {
            scanf("%d", &p);
            isQuery[_q] = 1;
            W tmp = seg.query(1, 1, n, p);
            //	dbg(_q, tmp.i, tmp.p, tmp.ver);
            if (tmp.i == -1) {
                res[_q] = 0;
            } else if (tmp.ver == 0) {
                res[_q] = vec[tmp.i][p - tmp.p + 1];
            } else {
                //		dbg(_q);
                OP[tmp.i][tmp.ver - 1].vec.push_back(pII(_q, p - tmp.p + 1));
            }
        } else {
            scanf("%d%d%d", &i, &l, &r);
            ++ver[i];
            OP[i].push_back({l, r, {}});
        }
    }
    for (int i = 1; i <= m; ++i) {
        int _n = sze[i];
        tseg.build(1, 1, _n, vec[i]);
        for (auto &_it : OP[i]) {
            tseg.update(1, 1, _n, _it.l, _it.r, 1);
            for (auto &it : _it.vec) {
                res[it.fi] = tseg.query(1, 1, _n, it.se);
            }
        }
    }
    for (int i = 1; i <= q; ++i)
        if (isQuery[i])
            printf("%d\n", res[i] % 256);
    return 0;
}

L. Carry Cam Failure

Solved By ltslts. 1:59(+)

题意：

定义十进制下的异或和（即不进位加法），和以此为基础的乘法运算。给出一个 n，求 n 在这个规则下的最小的平方根，如果不存在输出 -1。

思路：

因为不会进位，所以 n 如果拥有偶数位，肯定不存在平方根，所以平方根的长度为 \displaystyle \frac{len(n)+1}{2}。因为 len(n)<= 25，并且平方根每一位可能的数字最多只有两个，暴力搜索记录最小的合法的平方根即可，时间复杂度 \displaystyle O(2^{len(n) / 2})。

Code 
#include <bits/stdc++.h>

using namespace std;

const int N = 100;

string st;
int a[N], b[N];
int n;
bool flag;
long long ans;

void gao(int t) {
    if (t > (n + 1) / 2) {
        for (int i = t; i <= n; ++i) {
            int x = 0;
            for (int j = 1; j < t; ++j) {
                x += b[j] * b[i - j + 1];
            }
            x = x % 10;
            if (x != a[i])
                return;
        }
        flag = false;
        long long y = 0;
        for (int i = t - 1; i > 0; --i) y = y * 10 + b[i];
        if (y < ans)
            ans = y;
    } else
        for (int i = 0; i < 10; ++i) {
            int x = 0, y = 0;
            b[t] = i;
            for (int j = 1; j <= t; ++j) {
                x += b[j] * b[t - j + 1];
            }
            x = x % 10;
            if (x == a[t])
                gao(t + 1);
        }
}

int main() {
    cin >> st;
    n = st.length();
    ans = 100000000000000;
    for (int i = 0; i < n; ++i) {
        a[n - i] = st[i] - 48;
    }
    if (n & 1) {
        flag = true;
        gao(1);
        if (flag)
            cout << -1 << endl;
        else
            cout << ans << endl;
    } else
        cout << -1 << endl;
    return 0;
}

M. Maze Connec

Solved By Hsueh-. 2:10(+)

题意：

思路：

  • 存在一张迷宫，将其旋转 45^o，问最小破坏几面墙使得所有位置都可以逃出迷宫
  • 答案很显然是联通块数量减一，然后研究一下联通规则判断即可
Code 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int n, m;
char s[N][N];
int vis[N][N];

void gao(int x, int y) {
    if (x < 0 || x > n + 1 || y < 0 || y > m + 1)
        return;
    vis[x][y] = true;
    if (s[x + 1][y] == '.' && !vis[x + 1][y])
        gao(x + 1, y);
    if (s[x - 1][y] == '.' && !vis[x - 1][y])
        gao(x - 1, y);

    if (s[x][y + 1] == '.' && !vis[x][y + 1])
        gao(x, y + 1);
    if (s[x][y - 1] == '.' && !vis[x][y - 1])
        gao(x, y - 1);

    if (s[x + 1][y + 1] == '.' && !vis[x + 1][y + 1] && s[x + 1][y] == '\\')
        gao(x + 1, y + 1);
    if (s[x - 1][y + 1] == '.' && !vis[x - 1][y + 1] && s[x - 1][y] == '/')
        gao(x - 1, y + 1);

    if (s[x + 1][y - 1] == '.' && !vis[x + 1][y - 1] && s[x + 1][y] == '/')
        gao(x + 1, y - 1);
    if (s[x - 1][y - 1] == '.' && !vis[x - 1][y - 1] && s[x - 1][y] == '\\')
        gao(x - 1, y - 1);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
    for (int i = 0; i <= m + 1; ++i) {
        gao(0, i);
        gao(n + 1, i);
    }
    for (int i = 0; i <= n + 1; ++i) {
        gao(i, 0);
        gao(i, m + 1);
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i][j] == '/' && s[i][j + 1] == '\\' && s[i + 1][j] == '\\' && s[i + 1][j + 1] == '/')
                res++;
            else if (s[i][j] == '.' && !vis[i][j]) {
                res++;
                gao(i, j);
            }
        }
    }
    printf("%d\n", res);
    return 0;
}
Last update: March 27, 2022
Created: March 27, 2022
Back to top