# 并查集

Acwing239 奇偶游戏

原题链接:Acwing239

题目大意:小A和小B在玩一个游戏。

首先,小A写了一个由0和1组成的序列S,长度为N。

然后,小B向小A提出了M个问题。

在每个问题中,小B指定两个数 l 和 r,小A回答 S[l~r] 中有奇数个1还是偶数个1。

机智的小B发现小A有可能在撒谎。

例如,小A曾经回答过 S[1~3] 中有奇数个1, S[4~6] 中有偶数个1,现在又回答 S[1~6] 中有偶数个1,显然这是自相矛盾的。

请你帮助小B检查这M个答案,并指出在至少多少个回答之后可以确定小A一定在撒谎。

即求出一个最小的k,使得01序列S满足第1~k个回答,但不满足第1~k+1个回答。

……

READ MORE

Acwing238 银河英雄传说

原题链接:Acwing238

题目大意:有一个划分为N列的星际战场,各列依次编号为1,2,…,N。

有N艘战舰,也依次编号为1,2,…,N,其中第i号战舰处于第i列。

有T条指令,每条指令格式为以下两种之一:

1、M i j,表示让第i号战舰所在列的全部战舰保持原有顺序,接在第j号战舰所在列的尾部。

2、C i j,表示询问第i号战舰与第j号战舰当前是否处于同一列中,如果在同一列中,它们之间间隔了多少艘战舰。

现在需要你编写一个程序,处理一系列的指令。

……

READ MORE

Acwing237 程序自动分析

原题链接:Acwing237

题目大意:考虑一个约束满足问题的简化版本:假设$x_1,x_2,x_3,…$代表程序中出现的变量,给定$n$个形如$x_i=x_j$或$x_i≠x_j$的变量相等/不等的约束条件,判定上述所有约束条件是否能同时被满足。

现在给出一些约束满足问题,请分别对它们进行判定。

……

READ MORE

Acwing1252 搭配购买

原题链接:Acwing1252

题目大意:Joe觉得云朵很美,决定去山上的商店买一些云朵。

商店里有 $n$ 朵云,云朵被编号为 $1,2,…,n$,并且每朵云都有价格和价值。

但是商店老板跟他说,一些云朵要搭配来买才好 ,买一朵云则与这朵云有搭配的云都要买。

但是Joe的钱有限,求能买到的最大价值。

……

READ MORE

Acwing1250 格子游戏

原题链接:Acwing1250

题目大意:Alice和Bob玩了一个古老的游戏:首先画一个 $n×n$ 的点阵。接着,他们两个轮流在相邻的点之间画上红边和蓝边:

1.png

直到围成一个封闭的圈为止,“封圈”的那个人就是赢家。求游戏结束一共需要几步?

……

READ MORE

Recents
Categories
Tags
Links