2019 CCPC 秦皇岛

极角排序 双指针

题意

二维平面上 $n$ 个点。

$q$ 次询问，每次询问给一个点 $P$ ，求 $P$ 和 $n$ 个点可构成多少个直角三角形。

$2 \le n \le 2000$

$1 \le q \le 2000$

$\vert x\vert \ ,\ \vert y\vert \le 10^9$

题解

若 $P$ 为直角点
1. 以 $P$ 为原点对 $n$ 个点做极角排序。
2. 枚举 $n$ 个点，以枚举点和 $P$ 为直角边，找到第三个点。
3. 用双指针维护。
若 $P$ 非直角点
1. 离线将所有询问的点加入 $n$ 个点。
2. 枚举 $n$ 个点作为直角点，将剩余的点以该点做极角排序。
3. 枚举极角排序后的点，当遇到询问的点时，将答案加入对应贡献。

代码

/* <<head>> */
const int N = 2e3+7;

// ------- 变量 ------- //

typedef long long T;
int sgn(T x) { return (x > 0) - (x < 0); }
struct P {
    T x, y; P () {} P (T x, T y) : x(x), y(y) {}
    P operator + (const P &b) const { return P(x + b.x, y + b.y); }
    P operator - (const P &b) const { return P(x - b.x, y - b.y); }
    T operator * (const P &b) const { return x * b.x + y * b.y; }
    T operator / (const P &b) const { return x * b.y - y * b.x; }
    bool isUp() const { return sgn(y) == 1 || !sgn(y) && sgn(x) == -1; }
    bool operator < (const P &b) const {
        return isUp() < b.isUp() || isUp() == b.isUp() && sgn(*this/b) > 0;
    }
    void scan() { ll tx, ty; scanf("%lld%lld", &tx, &ty); x = tx; y = ty; }
};

int n, Q, ans[N];
P p[N], q[N], v[N<<1];
pair <P, int> v2[N<<2];

// ------- 函数 ------- //

bool ls90(P &a, P &b) { return a * b > 0 && a / b >= 0; }
bool eq90(P &a, P &b) { return a * b == 0 && a / b > 0; }

void Init() {
    scanf("%d%d", &n, &Q);
    rep(i, 0, n) p[i].scan();
    rep(i, 0, Q) q[i].scan();

    memset(ans, 0, sizeof(ans));
}

int Solve() {
    rep(i, 0, Q) {
        rep(j, 0, n) v[j] = p[j] - q[i];
        sort(v, v + n);
        rep(j, 0, n) v[j+n] = v[j];
        int rl = 1, rr, f = 1;
        rep(l, 0, n) {
            for (; rl < l + n && ls90(v[l], v[rl]); rl++, f = 1);
            if (rl == l + n || !eq90(v[l], v[rl])) continue;
            for (rr = f ? rl + 1 : rr; rr < l + n && eq90(v[l], v[rr]); rr++);
            f = 0;
            ans[i] += rr - rl;
        }
    }
    rep(i, 0, n) {
        int nn = 0;
        rep(j, 0, n) if (j != i) v2[nn++] = mp(p[j] - p[i], -1);
        rep(j, 0, Q) v2[nn++] = mp(q[j] - p[i], j);
        sort(v2, v2 + nn);
        rep(j, 0, nn) v2[j+nn] = v2[j];
        int rl = 1, rr, f = 1;
        vi tmp;
        rep(l, 0, nn) {
            for (; rl < l + nn && ls90(v2[l].fi, v2[rl].fi); rl++, f = 1);
            if (rl == l + nn || !eq90(v2[l].fi, v2[rl].fi)) continue;
            if (f) {
                tmp.clear();
                if (v2[rl].se >= 0) tmp.pb(v2[rl].se);
            }
            for (rr = f ? rl + 1 : rr; rr < l + nn && eq90(v2[l].fi, v2[rr].fi); rr++)
                if (v2[rr].se >= 0) tmp.pb(v2[rr].se);
            f = 0;
            if (v2[l].se == -1) {
                for (auto o : tmp) ans[o]++;
            } else {
                ans[v2[l].se] += rr - rl - sz(tmp);
            }
        }
    }
    rep(i, 0, Q) printf("%d\n", ans[i]);
    return 0;
}

B

C

D. Decimal

题意

输入 $n$ ，判断 $\frac{1}{n}$ 是否为无限小数。

$1 \le n \le 100$

题解

设 $x = \frac{1}{n}$ 是有限的 $k$ 位小数，则
\[x \cdot 10^{k} = 10^k /\ n\]
$x \cdot 10^k$ 等于多少不重要，但可以确定是一个整数，则
\[10^k\ \%\ n = 0\]
$a$ 可以被 $b$ 整除，则 $b$ 的质因子集合是 $a$ 的质因子集合的子集。
1. 质因子集合是一个可重集合
2. 集合中质因子的出现次数等于其在唯一分解中的指数
$10 ^ k$ 的质因子集合中，只出现质因子 $2$ 和 $5$ ，可出现 $0$ 次到无限次。
则 $n$ 的质因子集合中，应只能出现 $2$ 和 $5$ 。

代码

/* <<head>> */
// ------- 变量 ------- //

int n;

// ------- 函数 ------- //

void Init() {
    scanf("%d", &n);
}

int Solve() {
    while (n % 2 == 0) n /= 2;
    while (n % 5 == 0) n /= 5;
    return puts(n == 1 ? "No" : "Yes");
}

E. Escape

网络流 最大流

题意

$n \times m$ 的网格图，从上到下，从左到右，编号从 $1$ 到 $n$ 。

$a$ 个机器人在 $(0, p_i)$ ， $b$ 个出口在 $(n+1, e_i)$ ，

网格图中 $0$ 为空地， $1$ 为障碍，

可在空地中安排转向装置（上-右，上-左，下-右，下-左），

每个空地格子最多安排一个装置，机器人可互相穿过，

判断是否能让所有机器人到达任意出口。

$1 \le n, m \le 100$

$1 \le a,\ b,\ p_i,\ e_i \le m$

题解

网络流建图：

每个格子分成水平点和竖直点
水平点和相邻格子的水平点连无向边，容量为 $1$
竖直点和相邻格子的竖直点连无向边，容量为 $1$
每个格子的水平点和竖直点连无向边，容量为 $1$
源点连接入口的竖直点
汇点连接出口的竖直点
跑最大流，判断最大流的流量

（不会证明建图正确性）

代码

/* <<head>> */
const int N = 21000;
const int M = 61000;

// ------- 变量 ------- //

int n, m, a, b;
int p[107], q[107];
char s[107][107];

// ------- 函数 ------- //

struct Max_Flow {
    int n, no, dis[N], Q[N], cur[N], head[N];
    struct Edge {
        int s, t, v, net;
        Edge () {}
        Edge (int s, int t, int v, int net) : s(s), t(t), v(v), net(net) {}
    } e[M<<1];
    void init(int _n) {
        n = _n, no = 0;
        memset(head, -1, sizeof(head[0]) * (n+1));
    }
    void addEdge(int s, int t, int v) {
        e[no] = Edge(s, t, v, head[s]), head[s] = no++;
        e[no] = Edge(t, s, 0, head[t]), head[t] = no++;
    }
    bool bfs(int S, int T) {
        int qh = 0, qt = 0;
        memset(dis, -1, sizeof(dis[0]) * (n+1));
        dis[S] = 0, Q[qt++] = S;
        while (qh < qt) for (int i = head[Q[qh++]]; ~i; i = e[i].net) {
            if (e[i].v && !~dis[e[i].t]) {
                dis[Q[qt++] = e[i].t] = 1 + dis[e[i].s];
                if (e[i].t == T) return 1;
            }
        }
        return 0;
    }
    ll dinic(int S, int T) {
        int u, qt;
        ll maxflow = 0;
        while (bfs(S, T)) {
            memcpy(cur, head, sizeof(cur[0]) * (n+1));
            u = S, qt = 0;
            while (~cur[S]) {
                if (u == T) {
                    ll flow = LINF;
                    per(i, 0, qt) flow = min(flow, (ll)e[Q[i]].v);
                    per(i, 0, qt) {
                        e[Q[i]].v -= flow, e[Q[i]^1].v += flow;
                        if (!e[Q[i]].v) qt = i;
                    }
                    u = e[Q[qt]].s, maxflow += flow;
                } else if (~cur[u] && e[cur[u]].v && dis[u]+1 == dis[e[cur[u]].t]) {
                    Q[qt++] = cur[u];
                    u = e[cur[u]].t;
                } else {
                    while (u != S && !~cur[u]) u = e[Q[--qt]].s;
                    cur[u] = e[cur[u]].net;
                }
            }
        }
        return maxflow;
    }
} mxf;

void Init() {
    scanf("%d%d%d%d", &n, &m, &a, &b);
    rep(i, 1, n+1) scanf("%s", s[i] + 1);
    rep(i, 0, a) scanf("%d", p+i);
    rep(i, 0, b) scanf("%d", q+i);
}

int Solve() {
    int S = 0, T = 2 * n * m + a + b + 1;
    mxf.init(T);
    rep(i, 1, n+1) rep(j, 1, m+1) if (s[i][j] == '0') {
        int id = (i-1) * m + j;
        if (j > 1 && s[i][j-1] == '0') {
            mxf.addEdge(id, id - 1, 1);
            mxf.addEdge(id - 1, id, 1);
        }
        if (i > 1 && s[i-1][j] == '0') {
            mxf.addEdge(id + n * m, id + n * m - m, 1);
            mxf.addEdge(id + n * m - m, id + n * m, 1);
        }
        mxf.addEdge(id, id + n * m, 1);
        mxf.addEdge(id + n * m, id, 1);
    }
    int d = n * m * 2 + 1;
    rep(i, 0, a) mxf.addEdge(i + d, p[i] + n * m, 1);
    rep(i, 0, b) mxf.addEdge((n-1) * m + q[i] + n * m, i + d + a, 1);
    rep(i, 0, a) mxf.addEdge(S, i + d, 1);
    rep(i, 0, b) mxf.addEdge(i + d + a, T, 1);
    return puts(mxf.dinic(S, T) == a ? "Yes" : "No");
}

F. Forest Program

仙人掌图 dfs 点双连通分量

题意

$n$ 个点 $m$ 条边，保证所有连通分量都是仙人掌。

求 “ 删掉若干条边使得剩下的所有连通分量都是树 ” 的方案数。

仙人掌：无自环、无重边的无向连通图，任意一条边，最多属于一个简单环。

定义两个方案不同，当且仅当删掉的边集不同。

$1 \le n \le 3 \cdot 10^5$

$0 \le m \le 5 \cdot 10^5$

题解

图中所有简单环，至少需要删掉一条边。
不在环上的边，可删可不删。
若共有 $c$ 个环，第 $i$ 个环上有 $a_i$ 条边，不在环上的边有 $b$ 条，则方案数为：
\[\large 2^b \cdot \prod_{i=1}^{c}(2^{a_i}-1)\]
如何求仙人掌图中有多少个环，以及每个环的大小
1. 仙人掌图中的每个环，即为一个点双连通分量，可直接套用模板 $DCC$ 求解。
2. 直接用 $dfs$ 遍历，记录节点深度。当遍历到已经走过的节点时，即为环。环的大小用两点深度相减即可。
注意图可能非连通。

代码

dfs

/* <<head>> */
const int MOD = 998244353;
const int N = 3e5+7;

// ------- 变量 ------- //

int n, m;
vi e[N];
int ans;
 
// ------- 函数 ------- //
 
inline int add(int a, int b) { return (a += b) >= MOD ? a - MOD : a; }
inline int mul(int a, int b) { return 1ll * a * b % MOD; }
inline int qpow(ll a, ll b) {
    int r = 1;
    for (; b; a = a * a % MOD, b >>= 1)
        if (b & 1) r = 1ll * r * a % MOD;
    return r;
}
 
int dep[N];
void dfs(int u, int f=0) {
    dep[u] = dep[f] + 1;
    for (auto v : e[u]) if (v != f) {
        if (!dep[v]) {
            dfs(v, u);
        } else if (dep[u] > dep[v]) {
            m -= dep[u] - dep[v] + 1;
            ans = mul(ans, add(qpow(2, dep[u] - dep[v] + 1), MOD-1));
        }
    }
}
 
void Init() {
    ans = 1;
 
    scanf("%d%d", &n, &m);
    rep(i, 1, n+1) e[i].clear();
    rep(i, 0, m) {
        int u, v; scanf("%d%d", &u, &v);
        e[u].pb(v); e[v].pb(u);
    }
}
 
int Solve() {
    rep(i, 1, n+1) if (!dep[i]) dfs(i);
    ans = mul(ans, qpow(2, m));
    return printf("%d\n", ans);
}

点双连通分量

注意：孤立点和孤立边也是点双分量，但它们不是环。

/* <<head>> */
const int MOD = 998244353;
const int N = 3e5+7;
 
// ------- 变量 ------- //
 
int n, m;
vi e[N];
int ans;
 
// ------- 函数 ------- //
 
inline int add(int a, int b) { return (a += b) >= MOD ? a - MOD : a; }
inline int mul(int a, int b) { return 1ll * a * b % MOD; }
inline int qpow(ll a, ll b) {
    int r = 1;
    for (; b; a = a * a % MOD, b >>= 1)
        if (b & 1) r = 1ll * r * a % MOD;
    return r;
}
 
vi Dcc[N], e2[N<<1];
int dfn[N], low[N], cut[N], id[N], dcc[N], S[N], top, cnt, num, no;
struct Vertex_Biconnected_Component {
    void DCC(int u, int rt) {
        dfn[u] = low[u] = ++no;
        S[top++] = u;
        if (e[u].empty()) { Dcc[++cnt].pb(u); return ; }
        int son = 0;
        for (auto v : e[u]) {
            if (!dfn[v]) {
                DCC(v, rt);
                low[u] = min(low[u], low[v]);
                if (low[v] >= dfn[u]) {
                    son++;
                    if (u != rt || son > 1) cut[u] = 1;
                    cnt++;
                    do { Dcc[cnt].pb(S[--top]); } while (S[top] != v);
                    Dcc[cnt].pb(u);
                }
            } else {
                low[u] = min(low[u], dfn[v]);
            }
        }
    }
    void run(int n) {
        no = top = cnt = 0;
        memset(dfn, 0, sizeof(dfn[0]) * (n+1));
        memset(cut, 0, sizeof(cut[0]) * (n+1));
        rep(i, 1, n+1) Dcc[i].clear();
        rep(i, 1, n+1) if (!dfn[i]) DCC(i, i);
        num = cnt;
        rep(i, 1, n+1) if (cut[i]) id[i] = ++num;
        rep(i, 1, num+1) e2[i].clear();
        rep(i, 1, cnt+1) for (auto o : Dcc[i]){
            if (cut[o]) { e2[i].pb(id[o]); e2[id[o]].pb(i); }
            else dcc[o] = i;
        }
    }
} vbc;
 
void Init() {
    ans = 1;
 
    scanf("%d%d", &n, &m);
    rep(i, 1, n+1) e[i].clear();
    rep(i, 0, m) {
        int u, v; scanf("%d%d", &u, &v);
        e[u].pb(v); e[v].pb(u);
    }
}
 
int Solve() {
    vbc.run(n);
    rep(i, 1, cnt+1) {
        if (sz(Dcc[i]) < 3) continue;  // 孤立点和孤立边也是点双分量，但它们不是环
        ans = mul(ans, add(qpow(2, sz(Dcc[i])), MOD-1));
        m -= sz(Dcc[i]);
    }
    ans = mul(ans, qpow(2, m));
    return printf("%d\n", ans);
}

G

H

I. Invoker

dp

题意

输入字符串 $s$ 表示技能序列。
每个技能需要按下三个字母，三个字母的顺序可任意，最后按下 $R$ 确认。
上一个技能的后 $0 \sim 3$ 个字母可供当前技能使用（不考虑 $R$ ）。
求释放所有技能最少需要按几次。

$1 \le \vert s \vert \le 10^5$

题解

$dp[i][j]$ 表示释放完前 $i$ 个技能，第 $i$ 个技能按第 $j$ 种顺序（共 $6$ 种），最少需要按几次。
简单 $dp$ ，以及优雅的字符串预处理。

代码

/* <<head>> */
const int N = 1e5+7;

// ------- 变量 ------- //

int id[128];
char s[N];
char ski[] = "YVGCXZTFDB";
char tri[][5] = {
"QQQ", "QQW", "QQE", "WWW", "QWW", "WWE", "EEE", "QEE", "WEE", "QWE"
};
int order[][3] = {
{0, 1, 2},
{0, 2, 1},
{1, 0, 2},
{1, 2, 0},
{2, 0, 1},
{2, 1, 0}
};
int dp[N][6], cost[10][10][6][6];

// ------- 函数 ------- //

int work(int x, int y, int ii, int jj) {
    char a[5], b[5];
    rep(i, 0, 3) {
        a[i] = tri[x][order[ii][i]];
        b[i] = tri[y][order[jj][i]];
    }
    rep(i, 0, 3) {
        int ok = 1;
        rep(j, 0, 3-i) if (a[i+j] != b[j]) { ok = 0; break; }
        if (ok) return i;
    }
    return 3;
}

void Init() {
    scanf("%s", s);

    memset(dp, 0x3f, sizeof(dp));
    rep(i, 0, 10) id[ski[i]] = i;
    rep(i, 0, 10) rep(j, 0, 10) rep(ii, 0, 6) rep(jj, 0, 6)
        cost[i][j][ii][jj] = work(i, j, ii, jj);
}

int Solve() {
    int len = strlen(s);
    rep(i, 0, 6) dp[0][i] = 3;
    rep(i, 1, len) {
        int u = id[s[i]], v = id[s[i-1]];
        rep(j, 0, 6) rep(k, 0, 6)
            dp[i][j] = min(dp[i][j], dp[i-1][k] + cost[u][v][j][k]);
    }
    int ans = INF;
    rep(i, 0, 6) ans = min(ans, dp[len-1][i]);
    return printf("%d\n", ans + len);
}

J. MUV LUV EXTRA

kmp 最小循环节

题意

输入系数 $a$ 和 $b$ ，和一个字符串 $s$ 表示一个十进制小数。

找到一个循环节，循环节长度为 $l$ ，循环节在小数末尾循环出现的总长度为 $p$ ，

求 $a \times p - b \times l$ 的最大值。

$1 \le a\ ,\ b \le 10^9$

$1 \le \vert s\vert \le 10^7$

题解

枚举循环节出现的总长度 $p$ ，即枚举小数的后缀。
可将小数翻转，通过 $kmp$ 可求出每个前缀的最小循环节长度 $l$ 。
计算答案。

代码

/* <<head>> */
const int N = 1e7+7;

// ------- 变量 ------- //

int a, b;
char s[N];

// ------- 函数 ------- //

int net[N];
struct KMP {
    void get(char p[], int m) {
        net[0] = -1;
        for (int i = 0, j = -1; i < m;) {
            if (j == -1 || p[i] == p[j]) net[++i] = ++j;
            else j = net[j];
        }
    }
    int match(char s[], int n, char p[], int m) {
        get(p, m);
        for (int i = 0, j = 0; i < n;) {
            if (j == -1 || s[i] == p[j]) ++i, ++j;
            else j = net[j];
            if (j == m) return i - j;
        }
        return -1;
    }
} kmp;

void Init() {
    scanf("%d%d%s", &a, &b, s);
}

int Solve() {
    int len = strlen(s);
    reverse(s, s + len);
    kmp.get(s, len);
    ll ans = -LINF;
    rep(i, 1, len+1) {
        if (s[i-1] == '.') break;
        ans = max(ans, 1ll * a * i - 1ll * b * (i - net[i]));
    }
    return printf("%lld\n", ans);
}

K. MUV LUV UNLIMITED

博弈论

题意

一颗 $n$ 个节点的有根树，根节点为 $1$ 。

两人轮流博弈。

每一轮，可拿走当前树中若干叶子节点（至少一个）。

最后拿走根节点者为胜。

$2 \le n \le 10^6$

题解

（无法找到通向题解的思路，只能从题解中提炼一些思想）

题解给出，关键点在于：父亲度数大于 $1$ 的叶子节点

如果该节点存在
- 若移除该节点后为必败态，则当前状态为必胜态，必胜策略就是移除该节点
- 若移除该节点后为必胜态，那么
  - 由于移除该节点后，不产生新的叶子节点（因为父亲度数大于 $1$ ）
  - 所以，必胜态使用的策略，当前状态同样可以使用
  - 则当前状态也为必胜态
如果该节点不存在
- 则当前状态中，所有叶子节点的父亲度数都为 $1$
- 那么，目标就是将状态转移到：该节点存在的状态
- 目前，所有 “父亲度数大于 $1$ 的节点（包括根节点）” 都是潜在节点
- 则，找到所有叶子节点向上到达这些潜在节点所需的距离（经过几条边）
- 对于一条链，双方轮流取的情况下
  - 若距离为奇数，则必败
  - 若距离为偶数，则必胜
- 目前，有多条链
  - 若距离全为奇数，则必败
  - 若距离存在偶数，则必胜

提炼思想：

状态转移
1. 状态 $1$ 可通过策略 $(x)$ 转移到必胜态 $2$
2. 必胜态 $2$ 可通过策略 $(y)$ 转移到必败态 $3$
3. 但策略 $(x)$ 和策略 $(y)$ 不冲突
4. 则状态 $1$ 可通过策略 $(x, y)$ 达到必败态 $3$
5. 则状态 $1$ 也是必胜态
状态决策
1. 若目前有多个独立状态
2. 若全为必败态，则必败
3. 若存在必胜态，则必胜

代码

/* <<head>> */
const int N = 1e6+7;

// ------- 变量 ------- //

int n;
vi e[N];

// ------- 函数 ------- //

int ok, dis[N];
void dfs(int u, int f = 1) {
    if (u == 1 || sz(e[f]) > 1) dis[u] = 0;
    else dis[u] = dis[f] + 1;
    for (auto v : e[u]) {
        if (sz(e[v]) == 0 && sz(e[u]) > 1) ok = 1;
        dfs(v, u);
    }
}

void Init() {
    scanf("%d", &n);

    ok = 0;
    rep(i, 1, n+1) e[i].clear();
    rep(i, 2, n+1) {
        int p; scanf("%d", &p);
        e[p].pb(i);
    }
}

int Solve() {
    dfs(1);
    if (ok) {
        puts("Takeru");
    } else {
        rep(i, 1, n+1) if (!sz(e[i]) && ~dis[i] & 1) ok = 1;
        if (ok) puts("Takeru");
        else puts("Meiya");
    }
    return 0;
}

2019 CCPC Qinhuangdao Onsite

A. Angle Beats

B

C

D. Decimal

E. Escape

F. Forest Program

G

H

I. Invoker

J. MUV LUV EXTRA

K. MUV LUV UNLIMITED

L

CATALOG

FEATURED TAGS

FRIENDS