LCA

CodeForces 832D Misha, Grisha and Underground

Posted on

昨晚疯狂掉分的第四题,其实比第三题还简单……
搞不懂cf又不按套路出牌了……先是来一个巨简单的,让每个人都不得不去签到,随后是坑题,然后是压轴题,再然后才是普通题,难题……

题意:
给你一棵树,每次询问3个点,要你求出3个点两两构成的路径中选出两条,使得他们相交的长度最长。

思路:
这道题并不难,先求出LCA,再分类讨论一下即可,但是但是但是但是!!分类的情况会非常非常多,就图而言就有4种,还要考虑各自的位置。
必须得总结一下,不然跟着写会疯掉。
考虑让每个点为两条路径的相交点,分三种情况讨论。
而每种情况中,当两个路径各自的lca相同时,除了该点的所在的路径以外只要求出另外两个点的lca长度 - 三点lca 路径长度即可。
否则,就只剩下第三个点为另外两点的父亲这一情况,所以长度为 根节点到所讨论的结点距离 减去 非父亲结点的另外两个结点的 lca 的距离。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary));

const int maxn = 1e5 + 5;

int n, q, v, idx = 1, qidx = 1;
int head[maxn], qhead[maxn];
bool vis[maxn];
int root[maxn];
int lca[maxn * 3], dis[maxn];

struct node {
    int to, next;
    node() {}
    node(int _to, int _next) { to = _to, next = _next; }
} edges[maxn * 2];

struct qnode {
    int to, next, idx;
    qnode() {}
    qnode(int _to, int _next, int _idx) { to = _to, next = _next, idx = _idx; }
} qedges[maxn * 6];

int a[maxn], b[maxn], c[maxn];

void addEdge(int u, int v)
{
    edges[idx] = node(v, head[u]);
    head[u] = idx++;
    edges[idx] = node(u, head[v]);
    head[v] = idx++;
}

void addQEdge(int u, int v, int id)
{
    qedges[qidx] = qnode(v, qhead[u], id);
    qhead[u] = qidx++;
    qedges[qidx] = qnode(u, qhead[v], id);
    qhead[v] = qidx++;
}

int findRoot(int x)
{
    return root[x] == x ? x : root[x] = findRoot(root[x]);
}

void tarjan(int u)
{
    root[u] = u;
    vis[u] = true;
    for (int it = qhead[u]; it != 0; it = qedges[it].next) {
        int v = qedges[it].to;
        if (vis[v])
            lca[qedges[it].idx] = findRoot(v);
    }
    for (int it = head[u]; it != 0; it = edges[it].next) {
        int v = edges[it].to;
        if (!vis[v]) {
            dis[v] = dis[u] + 1;
            tarjan(v);
            root[v] = u;
        }
    }
}

int query(int da, int ab, int ac, int bc)
{
    if (ab == ac)
        return da - dis[ab] + dis[bc] - dis[ab] + 1;
    else
        return da - max(dis[ab], dis[ac]) + 1;
}

int main()
{
    scanf("%d %d", &n, &q);
    range(i, 2, n)
    {
        scanf("%d", &v);
        addEdge(i, v);
    }
    each(i, q)
    {
        scanf("%d %d %d", a + i, b + i, c + i);
        addQEdge(a[i], b[i], i * 3);
        addQEdge(a[i], c[i], i * 3 + 1);
        addQEdge(b[i], c[i], i * 3 + 2);
    }
    tarjan(1);
    q *= 3;
    for (int i = 0; i < q; i += 3) {
        int al = query(dis[a[i / 3]], lca[i], lca[i + 1], lca[i + 2]);
        int bl = query(dis[b[i / 3]], lca[i + 2], lca[i], lca[i + 1]);
        int cl = query(dis[c[i / 3]], lca[i + 1], lca[i + 2], lca[i]);
        printf("%d\n", max(al, max(bl, cl)));
    }
    return 0;
}
Ruby

CodeForces 832 B Petya and Exam

Posted on

比赛时候用c++ 搞了一个小时还没出来,结束后用ruby写了个正则改了两次就过了……

真的是崩溃……

题意:
?替代任意好字符,* 替代任意数目的坏字符

思路:
正则瞎搞

AC Code

good = gets.to_str.chomp
pattern = gets.to_str
key = pattern.strip.gsub("?","["+good+"]").gsub("*","[^"+good+"]*")
rg = Regexp.new("^"+key+"$")

n = gets.to_i
n.times do
    buf = gets.to_str
    if rg =~ buf
        puts "YES"
    else
        puts "NO"
    end
end