题解：P17823 [COCI 2026/2027 #1] 卡片 / Karte

ybc_zhb · 2026-11-10 19:55:45 · 题解

题目描述

给定 n 个牌，牌的正面的颜色是 a_i，反面是 b_i，对于每个 k=1,2,\dots,n：

• 只考虑前 k 张卡片；
• 每张卡片可以任意选择一面朝上；
• 问最多能显示出多少种不同的颜色。

不同的 k 之间互不影响，每张卡片在每次计算时都可以重新选择朝上的一面。

解题思路

阅读题目发现，每张卡片只能在 a_i 和 b_i 中贡献一个，自然的想到了要建模，对于每张牌，在 a_i 和 b_i 中连一条边，表示可以在 a_i 和 b_i 中选。然后有两种情况：

• 现在建模后是一个树，那么从这里面选，只能选 v-1 个点（ v 为树当前的结点数），因为树有 v-1 条边。
• 现在建模之后是一个图，就代表里面有环，那么可以把 v 个全部选中，因为环可以互相错位的选，最终全部选出。

题目中要求最多有多少种颜色，就是求所有出现的的颜色减去无环的连通块，用并查集维护连通块，每次加入的时候判断是否构成环，计算贡献就可以了，如果还有不懂的可以看代码。

代码部分

#include<bits/stdc++.h>
#define int long long
#define MAX 0x3f3f3f3f3f3f3f3f
#define MIN -0x3f3f3f3f3f3f3f3f
using namespace std;
int read ()
{
    int f = 1 , res = 0 , c = getchar ();
    while ( c < '0' || c > '9' )
    {
        if ( c == '-' )
        {
            f = -1;
        }
        c = getchar ();
    }
    while ( c >= '0' && c <= '9' )
    {
        res = ( res << 1 ) + ( res << 3 ) + c - '0';
        c = getchar ();
    }
    return res * f;
}
int fa [ 100010 ] , sz [ 100010 ] , n , sum , cnt;//sum维护一共有多少种颜色，cnt维护有多少个连通块是树（不是环） 
bool flag [ 100010 ] , vis [ 100010 ];//vis标记是否访问，flag标记是否连通块i是否有环 
int find ( int x )//并查集 
{
    if ( fa [ x ] == x )
    {
        return x;
    }
    return fa [ x ] = find ( fa [ x ] );
}
void add ( int x )//加入新点 
{
    if ( !vis [ x ] )
    {
        vis [ x ] = 1;
        fa [ x ] = x;
        sz [ x ] = 1;
        flag [ x ] = 0;
        sum++;
        cnt++;
    }
}
signed main()
{
    n = read ();
    for ( int i = 1 ; i <= n ; i++ )
    {
        int u = read () , v = read ();
        add ( u );
        add ( v );
        if ( u == v )//自环 
        {
            if ( !flag [ find ( u ) ] )
            {
                flag [ find ( u ) ] = 1;
                cnt--;
            }
        }
        else
        {
            int x = find ( u ) , y = find ( v );
            if ( x == y )//在同一连通块，构成环 
            {
                if ( !flag [ x ] )
                {
                    flag [ x ] = 1;
                    cnt--;
                }
            }
            else
            {
                if ( sz [ x ] < sz [ y ] )//合并 
                {
                    swap ( x , y );
                }
                cnt += !( flag [ x ] || flag [ y ] ) - !flag [ x ] - !flag [ y ];
                fa [ y ] = x;
                sz [ x ] += sz [ y ];
                flag [ x ] = flag [ x ] || flag [ y ];
            }
        }
        printf ( "%lld " , sum - cnt );
    }
    return 0;
}