三月做题

做题记录

二二年3.7

codeforces 1239D Catowice City

题目

  • 标签 ：图论， 2-SAT， tarjan。

  • 题意 ：有 \(n\) 个人 \(m\) 只猫，要求选出 \(j\) 名裁判（人）和 \(p\) 只选手（猫），使得 \(j+p=N\)，且选出的人和猫都互相不认识。

  • 数据范围 ：\(1?t?10^5, 1?n?m?10^6, 1?a_i, b_i?n\)。

  • 做法 ： 这是一个二分图，由于第 \(i\) 只猫和第 \(i\) 个人不能都选，所以我们可以将第 \(i\) 个人和第 \(i\) 只猫缩成一个点, 对于一条从 \(x\) 连向 \(y\) 的边，表示如果 \(x\) 选了人，则 \(y\) 不能选猫, 容易发现，对于一个强连通分量中的点，要么全选人，要么全选猫, 对于出度为 \(0\) 的强连通分量（即编号为 \(1\)），由于没有出边，它不可能影响任何点，所以我们不妨令其选人，其它所有点都选猫（选猫也不会影响其他点）, 如果只有一个强连通分量，则无解。

分数 ： \(100\)。

code 
/**********
二二年3.7
kroyosh
cf 1239 D. Catowice City
2-SAT
**********/
#include 
#include 
#include 
#include 
#include 

#define pb push_back

using namespace std;

inline int read()
{
    int r = 0, f = 1;
    char c = getchar();
    while (c < '0' || '9' < c)
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while ('0' <= c && c <= '9')
    {
        r = r * 10 + (c - '0');
        c = getchar();
    }
    return r * f;
}

inline void write(int x)
{
    if (x < 0) putchar('-'), write(-x);
    else
    {
        if (x > 9) write(x / 10);
        putchar('0' + x % 10);
    }
}

const int N = 1e6 + 10, M = N << 1;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts, stk[N], top, siz[N];
int SCCid[N], SCC;
bool ins[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ ts;
    stk[ ++ top] = u;
    ins[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (ins[j])
            low[u] = min(low[u], dfn[j]);
    }
    if (low[u] == dfn[u])
    {
        int y;
        SCC ++ ;
        do
        {
            y = stk[top -- ];
            ins[y] = false;
            siz[SCC] ++ ;
            SCCid[y] = SCC;
        } while (y != u);
    }
}

void work()
{
    n = read(), m = read();
    SCC = ts = idx = top = 0;
    for (int i = 1; i <= n; i ++ )
    {
        h[i] = -1;
        dfn[i] = siz[i] = SCCid[i] = 0;
    }
    for (int i = 1; i <= m; i ++ )
    {
        int x = read(), y = read( );
        if (x == y) continue;
        add(x, y);
    }
    for (int i = 1; i <= n; i ++ )
        if (!dfn[i]) tarjan(i);
    if (SCC == 1)
    {
        puts("No");
        return ;
    }
    puts("Yes");
    write(siz[1]), putchar(' ');
    write(n - siz[1]), puts("");
    for (int i = 1; i <= n; i ++ )
        if (SCCid[i] == 1)
        write(i), putchar(' ');
    puts("");
    for (int i = 1; i <= n; i ++ )
        if (SCCid[i] != 1)
        write(i), putchar(' ');
    puts("");
}

int main()
{
    int T = read();
    while (T -- ) work();
    return 0;
}

二二年3.8

codeforces 1361C Johnny and Megan's Necklace

题目

  • 标签 ：图论， 欧拉回路。

  • 题意 ：用 \(n\) 条线连 \(n\) 对珍珠，使得这 \(2n\) 颗珍珠形成一个环。设一条线所连的两颗珍珠权值为 \(u\), \(v\)，则该线的权值为最大的整数 \(k\) 满足 \(2^k\)|\(u\)⊕\(v\)。如果 \(u\)=\(v\)，则 \(k=20\)。求所有新连的线的权值最小值的最大值并给出方案，即 2\(n\) 颗珍珠所形成的的环。

  • 数据范围 ：\(1 ?n ?5*10^5, 0?a, b?2^{20},1?p_i?2n\)。

  • 做法：从小到大贪心：因为所有新连的线 (\(u\),\(v\)) 都要满足 \(2^i\)∣\(u\)⊕\(v\)，所以 \(u\),\(v\) 在二进制下的后 \(i\) 位必须相等。这就启发我们对于每个原有的线 (\(u\),\(v\))，在新图 \(G_i\) 中添加一条边 \((u\) mod \(2^i\),\(v\) mod \(2^i\))，这样一来，如果答案能为 \(i\)，则无向图 \(G_i\)必有欧拉回路。

分数 ： \(100\)。

code 
/**********
二二年3.8
kroyosh
cf 1361C Johnny and Megan's Necklace
**********/
#include 
#include 
#include 
#include 

using namespace std;inline int read()
{
    int r = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        r = r * 10 + (c - '0');
        c = getchar();
    }
    return r * f;
}


inline void write(int x)
{
    if (x < 0) putchar('-'), write(-x);
    else
    {
        if (x > 9) write(x / 10);
        putchar('0' + x % 10);
    }
}

const int N = 5e5 + 10, NS = (1 << 20) + 10;

int n, a[N], b[N], deg[NS];
int h[N + NS], e[N * 4], ne[N * 4], idx;
int stk[N * 4], top;
bool st[N *4];
int S, ans;

void add(int a, int b)
{
    e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

bool is_euler()
{
    for (int i = 1; i <= S; i ++ )
        if (deg[i] & 1) return false;
    return true;
}

void dfs(int u)
{
    for (int &i = h[u]; i; i = ne[i])
    {
        if (!st[i])
        {
            st[i] = st[i ^ 1] = 1;
            int j = e[i];
            dfs(j);
            stk[ ++ top] = j;
        }
    }
}

int main()
{
    n = read();
    for (int i = 1; i <= n; i ++ )
        a[i] = read(), b[i] = read();
    for (ans = 20; ans; ans -- )
    {
        S = (1 << ans) - 1;
        for (int i = 0; i <= S; i ++ )
            deg[i] = 0;
        for (int i = 1; i <= n; i ++ )
            deg[a[i] & S] ++, deg[b[i] & S] ++ ;
        if (!is_euler()) continue;
        for (int i = 1; i <= idx; i ++ ) st[i] = 0;
        idx = 1;
        for (int i = 1; i <= S + n + 1; i ++ ) h[i] = 0;
        for (int i = 1; i <= n; i ++)
        {
            add(i, (a[i] & S) + n + 1);
            add((a[i] & S) + n + 1, i);
            add(i, (b[i] & S) + n + 1);
            add((b[i] & S) + n + 1, i);
        }
        top = 0;
        dfs(1);
        int cnt = 0;
        for (int i = 1; i <= top; i ++ ) cnt += (stk[i] <= n);
        if (cnt != n) continue;
        write(ans);
        puts("");
        for (int i = 1; i <= top; i ++ )
            if (stk[i] <= n)
            {
                int s = (stk[i + 1] - n - 1);
                int id = stk[i];
                if ((a[id] & S) == s)
                    write(id * 2), putchar(' '), write(id * 2 - 1), putchar(' ');
                else
                    write(id * 2 - 1), putchar(' '), write(id * 2), putchar(' ');
            }
        puts("");
        return 0;
    }
    puts("0");
    for (int i = 1; i <= n * 2; i ++ )
        write(i), putchar(' ');
    return 0;
}

二二年3.11

codeforces 962F Simple Cycles Edges

题目

  • 标签 ：图论， tarjan。

  • 题意 ：给出一张 \(n\) 个点 \(m\) 条边的图, 求恰好被包含在一个简单环中的边。

  • 数据范围 ：\(1?n?10^5, 0?m?min(n * (n - 1) / 2, 10^5, 1?v, u?n, u ≠ v)\)。

  • 做法 ：找出所有点双连通分量，对于每个点双连通分量里如果只有一个环，那这个双连通分量里的所有边都是满足题意的，否则所有边都不满足题意，判断是否只有一个环只需要看点双连通分量内的点数是否等于边数即可。

分数 ： \(100\)。

code 

/**********
二二年3.10
kroyosh
cf 962F Simple Cycles Edges
tarjan
**********/
#include 
#include 
#include 
#include 
#include 

using namespace std;

inline int read()
{
    int r = 0, f = 1;
    char c=  getchar();
    while ('0' > c || '9' < c)
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while ('0' <= c && c <= '9')
    {
        r = r $ 10 + (c - '0');
        c = getchar();
    }
    return r * f;
}

const int N = 1e5 + 10, M = N << 1;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts;
int stk[N * 3], top;
int tot;
set ans, edge[N], node[N];


void add(int a, int b)
{
    e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

void tarjan(int u, int f)
{
    dfn[u] = low[u] = ++ ts;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if (!dfn[v])
        {
            stk[ ++ top] = i >> 1, stk[ ++ top] = u, stk[ ++ top] = v;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (dfn[u] <= low[v])
            {
                tot ++;
                int t1, t2;
                while (1)
                {
                    node[tot].insert(t1 = stk[top -- ]);
                    node[tot].insert(t2 = stk[top -- ]);
                    edge[tot].insert(stk[top -- ]);
                    if (t1 == v && t2 == u) break;
                }
            }
        }
        else if (dfn[v] < dfn[u] && v != f)
        {
            stk[ ++ top] = i >> 1, stk[ ++ top] = u, stk[ ++ top] = v;
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main()
{
    n = read(), m = read();
    memset(h, -1, sizeof h);
    idx = 1;
    for (int i = 1, x, y; i <= m; i ++ )
    {
        x = read(), y = read();
        add(x, y);
        add(y, x);
    }
    for (int root = 1; root <= n; root ++ )
        if (!dfn[root])
        tarjan(root, -1);
    for (int i = 1; i <= tot; i ++ )
        if (edge[i].size() == node[i].size())
        ans.insert(edge[i].begin(), edge[i].end());
    printf("%d\n", (int)ans.size());
    for (int x : ans) printf("%d ",x);
    return 0;
}

二二年3.18

SDOI 2018 战略游戏

题目

  • 标签 ：图论， 圆方树， tarjan， lca。

  • 题意 ：给一张 \(n\) 个点 \(m\) 条边的连通无向图，每次给定一个点集 \(S\) ，求有多少个不在 \(S\) 中的点满足删除后 \(S\) 中存在两个点不连通。

  • 数据范围 ：\(1?T?10,2?n?10^5,n-1?m?2×10^5,1?q?10^5\),对于每组测试数据, 有\(\sum|S|?2×10^5\)。

  • 做法 ： 先建出圆方树，则变为询问 \(S\) 在圆方树上对应的连通子图中的圆点个数减去 \(|S|\)。
    如何计算连通子图中的圆点个数？有一个方法：
    把圆点的权值放到它和它的父亲方点的边上，问题转化为求边权和。
    即把 \(S\) 中的点按照 DFS 序排序，计算排序后相邻两点的距离和（还包括首尾两点之间的距离），答案就是距离和的一半，因为每条边只被经过两次。
    最后，如果子图中的深度最浅的节点是圆点，答案还要加上 \(1\) ，因为我们没有统计到它。

分数 ： \(100\)。

code 
/**********
二二年3.18
kroyosh
SDOI 2018 战略游戏
圆方树
**********/
#include 
#include 
#include 
#include 
#include 

#define pb push_back

using namespace std;

inline int rd() {
    int r = 0, f = 1;
    char c = getchar();

    while (c < '0' || '9' < c) {
        if (c == '-')
            f = -1;

        c = getchar();
    }

    while ('0' <= c && c <= '9') {
        r = (r << 3) + (r << 1) + (c - '0');
        c = getchar();
    }

    return r * f;
}

const int N = 100010, M = N << 1;

int n, m, T, Q, S, a[N];
vector G[N], GY[M];
int new_id;
int dfn[M], low[N], ts, stk[N], top;
int fa[M][18], depth[M], dist[M], q[M];
int ans;

void tarjan(int u) {
    dfn[u] = low[u] = ++ ts;
    stk[ ++ top] = u;

    for (int j : G[u])
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);

            if (low[j] == dfn[u]) {
                ++ new_id;

                for (int x = 0; x != j; top --) {
                    x = stk[top];
                    GY[new_id].pb(x);
                    GY[x].pb(new_id);
                }
                GY[new_id].pb(u);
                GY[u].pb(new_id);
            }
        } else
            low[u] = min(low[u], dfn[j]);
}

void dfs(int u, int father) {
    dfn[u] = ++ ts;
    depth[u] = depth[fa[u][0] = father] + 1;
    dist[u] = dist[father] + (u <= n);

    for (int i = 0; i < 17; i ++)
        fa[u][i + 1] = fa[fa[u][i]][i];

    for (int j : GY[u])
        if (j != father)
            dfs(j, u);
}

int lca(int a, int b) {
    if (depth[a] < depth[b])
        swap(a, b);

    for (int k = 17; k >= 0; k --)
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];

    if (a == b)
        return a;

    for (int k = 17; k >= 0; k --)
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }

    return fa[a][0];
}

void work() {
    n = rd(), m = rd();

    for (int i = 1; i <= n; i ++)
        G[i].clear(), low[i] = dfn[i] = 0;

    for (int i = 1; i <= n << 1; i ++)
        GY[i].clear();

    for (int i = 1, x, y; i <= m; i ++) {
        x = rd(), y = rd();
        G[x].pb(y);
        G[y].pb(x);
    }

    new_id = n;
    ts = 0;
    tarjan(1);
    top -- ;
    ts = 0;
    dfs(1, 0);
    Q = rd();

    while (Q --) {
        S = rd();
        ans = -2 * S;

        for (int i = 1; i <= S; i ++)
            a[i] = rd();

        sort(a + 1, a + S + 1, [](int a, int b) {
            return dfn[a] < dfn[b];
        });

        for (int i = 1; i <= S; i ++) {
            int u = a[i], v = a[i % S + 1];
            ans += dist[u] + dist[v] - 2 * dist[lca(u, v)];
        }

        if (lca(a[1], a[S]) <= n)
            ans += 2;

        printf("%d\n", ans / 2);
    }
}

int main() {
    T = rd();

    while (T --)
        work();

    return 0;
}
题

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Windows cmd 启动 tomcat 中文乱码问题

微积分(A)随缘一题[7]

tensorboard图表显示不全的问题

Ubuntu 断网问题解决

struts2升级至2.5.26遇到的问题

OracleDataReader.Read()耗时过高问题的解决办法

recokemq整合问题

执行上下文与执行上下文栈：变量声明提升与函数声明提升 执行上下文 执行上下文栈 测试

JAVA List<Object[]>取值问题

修复 layer插件 在 bootstrap 4.x 下按钮颜色问题

Scss支持多主题切换的方案实现

标签