bulbs专题

Codeforces Round 916 (Div. 3) G2. Light Bulbs (Hard Version)(思维题 随机化哈希)

题目 2n(2<=n<=2e5)个灯泡, 灯泡分n种,每种颜色恰有两个,灯泡颜色用1到i表示 你可以执行以下两种操作若干次: 1. 选择两个同色的灯泡i、j,如果一个亮,但是另一个不亮,就把另一个点亮 2. 选择三个不同位置的灯泡i,j,k(i<j<k),如果i和k都亮了,但是j不亮,就把j点亮 你初始时,可以手动点亮若干个灯泡, 求初始时最少手动点亮灯泡的个数,以及满足个数等于最少