255.格子游戏
题目:
Alice和Bob玩了一个古老的游戏：首先画一个nxn的点阵(下图n=3)。接着，他们两个轮流在相邻的点之间画上红边和蓝边：
直到围成一个封闭的圈（面积不必为1)为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了!
他们甚至在游戏中都不知道谁赢得了游戏。
于是请你写一个程序，帮助他们计算他们是否结束了游戏?
输入格式
输入数据第一行为两个整数n和m。n表示点阵的大小，m表示一共画了m条线。
以后m行，每行首先有两个数字(x,y)，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是D，则是向下连一条边，如果是R就是向右连一条边。
输入数据不会有重复的边且保证正确。
输出格式
输出一行：在第几步的时候结束。
假如m 步之后也没有结束，则输出一行"draw"。
数据范围
1≤n≤200
1≤m≤24000
思路:
1.并查集可以实现
①合并两个集合②查询某个元素的祖宗节点。
有以下几种优化
①路径压缩O(logn)②按秩合并O(logn)
两个优化一起用的话，时间复杂度为O(α(n))，只要n＜2**2**2**2**2**2，α(n)＜5。所以可以看成是线性的时间复杂度。
最常用的扩展有两个。①在维护并查集的同时可以记录一下每一个集合的大小。我们一般把这个属性绑定在根节点上，树里的点是否正确无所谓。②我们还可以记录每个点到根节点的距离。这个就必须得绑定到每一个元素身上。这个距离也可以用来表示这个元素和根节点的关系，类似算法基础课的食物链。像食物链这种题，不止可以用带权并查集做，也可以用扩展域并查集来做。如果我们要维护k类关系，用带权并查集来做时间复杂度是和k没关系的，而用扩展域则是O(k)的时间复杂度。
2.就看是否围成了一个封闭的圈。我们可以用无向图的Tarjan算法来做，但是没有必要那么麻烦。我们每一次画一条边，就相当于把两个点相连。画一条边，出现环就等价于这两个点在连边前就在同一个连通块中了。如果没在一个集合，加边后一定不会形成环。所以我们采用并查集来做。
3.其次，我们把二维坐标转化为一维坐标比较好做。那么就把(x,y)转化为x×n+y，前提是x,y都从0开始。
代码(c++):
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 40010;
int n, m;
int p[N];
int get(int x, int y)
{
return x * n + y;
}
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n * n; i ++ ) p[i] = i;
int res = 0;
for (int i = 1; i <= m; i ++ )
{
int x, y;
char d;
cin >> x >> y >> d; //cin可过滤空格和制表符和回车
x --, y -- ; //下标也要映射，从0开始
int a = get(x, y);
int b;
if (d == 'D') b = get(x + 1, y); //终点的编号，往下走
else b = get(x, y + 1); //往右走
int pa = find(a), pb = find(b);
if (pa == pb)
{
res = i;
break;
}
p[pa] = pb;
}
if (!res) puts("draw");
else cout << res << endl;
return 0;
}
256.搭配购买
题目:
Joe觉得云朵很美，决定去山上的商店买一些云朵。
商店里有n朵云，云朵被编号为1, 2, ..., n，并且每朵云都有一个价值。
但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。但是Joe的钱有限，所以他希望买的价值越多越好。
输入格式
第1行包含三个整数n，m，w，表示有n朵云，m个搭配，Joe有w的钱。第2～n+1行，每行两个整数ci, di表示i朵云的价钱和价值。
第n+2~n+1+m行，每行两个整数ui，vi，表示买ui就必须买vi，同理，如果买vi就必须买ui。
输出格式
一行，表示可以获得的最大价值。
数据范围
1≤n≤10000
0≤m≤5000
1≤w≤10000
1≤ci≤5000
1≤di≤100
1≤ui,vi≤n
思路:
1.是01背包问题。并且凡是在一个连通块里的云朵，要买就全买，要不买就全不买。所以我们可以把这个块看成一个物品，用并查集。先用并查集找出所有连通块，然后做一次01背包。
代码(c++):
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int n, m, vol;
int v[N], w[N];
int p[N];
int f[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m >> vol;
for (int i = 1; i <= n; i ++ ) p[i] = i;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
while (m -- )
{
int a, b;
cin >> a >> b;
int pa = find(a), pb = find(b);
if (pa != pb)
{
v[pb] += v[pa];
w[pb] += w[pa];
p[pa] = pb;
}
}
for (int i = 1; i <= n; i ++ )
if (p[i] == i) //只有是根节点的时候，它才代表一组物品，我们才能算它
for (int j = vol; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[vol] << endl;
return 0;
}
257.程序自动分析
题目:
在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本：假设x1,x2,x3,...代表程序中出现的变量，给定n个形如xi=xj或者xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。
例如，一个问题中的约東条件为：x1=x2,x2=x3,x3=x4,x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定。
输入格式
输入文件的第1行包含1个正整数t，表示需要判定的问题个数，注意这些问题之间是相互独立的。对于每个问题，包含若干行：
第1行包含1个正整数n，表示该问题中需要被满足的约束条件个数。
接下来n行，每行包括3个整数i,j,e,描述1个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1，则该约束条件为xi=xj；若e=0，则该约束条件为xi≠xj。
输出格式
输出文件包括t行。
输出文件的第k行输出一个字符串“YES”或者“NO”（不包含引号，字母全部大写），“YES”表示输入中的第k个问题判定为可以被满足，“NO”表示不可被满足。
数据范围
1≤n≤1000000
1≤i, j≤1000000000
思路:
1.数据范围非常大，所以想办法缩小。我们会用到的变量数量其实最多只有二百万，所以我们需要离散化。可以保序，排序，判重，二分。不要求排序可以用map，hash表。这里我们采用map。代码会简单很多。
2.这里我们怎么去判断矛盾呢？首先约束条件的顺序是无所谓的。因此我们可以先考虑所有的相等约束。如果xi＝xj，我们把i和j合并。然后考虑不等条件，如果在一个集合中那么就不成立。反之不在同一个集合里就继续判断下一个。
代码(c++):
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 200010;
int n, m;
int p[N];
unordered_map<int, int> S;
struct Query
{
int x, y, e;
}query[N];
int get(int x)
{
if (S.count(x) == 0) S[x] = ++ n; //没出现过分配一个n
return S[x];
}
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
n = 0; //对于每一个初始化的问题，我们认为点数是0
S.clear();
scanf("%d", &m);
for (int i = 0; i < m; i ++ )
{
int x, y, e;
scanf("%d%d%d", &x, &y, &e);
query[i] = {get(x), get(y), e};
}
for (int i = 1; i <= n; i ++ ) p[i] = i;
for (int i = 0; i < m; i ++ ) //合并所有相等约束条件
if (query[i].e == 1)
{
int pa = find(query[i].x), pb = find(query[i].y);
p[pa] = pb;
}
bool has_conflict = false;
for (int i = 0; i < m; i ++ ) //检查所有不等条件
if (query[i].e == 0)
{
int pa = find(query[i].x), pb = find(query[i].y);
if (pa == pb)
{
has_conflict = true;
break;
}
}
if (has_conflict) puts("NO");
else puts("YES");
}
return 0;
}
258.银河英雄传说
题目:
有一个划分为N列的星际战场，各列依次编号为1,，2，...，N。
有N艘战舰，也依次编号为1， 2，...，N, 其中第i号战舰处于第i列。
有T条指令，每条指令格式为以下两种之一：
1、M i j，表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j号战舰所在列的尾部。
2、C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。
现在需要你编写一个程序，处理一系列的指令。
输入格式
第一行包含整数T，表示共有T条指令。
接下来T行，每行一个指令，指令有两种形式：M i j或C i j。
其中M和C为大写字母表示指令类型，i和j为整数，表示指令涉及的战舰编号。
输出格式
你的程序应当依次对输入的每一条指令进行分析和处理：
如果是M i j形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是C i j形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目，如果第i号战舰与第号战舰当前不在同一列上，则输出-1。
数据范围
N≤30000
T≤500000
思路:
1.不问间隔多少战舰，可以直接并查集。但是如果要同时维护间隔多少战舰，怎么做呢？如果单独做需要O(n²)的时间复杂度，我们可以用前缀和的思想，统一维护当前战舰到排头距离。假设两个战舰x,y在同一列，d(x)为x距离排头的举例。那么当x≠y的时候|d(x)-d(y)|-1就是间隔战舰数量。如果x＝y，特判，为0。
2.那么怎么去算呢？我们可以让排头当根节点。假设a移动b后面，那么让a的父亲指向b。首先b不用做任何变化，我们只需要对a中的每个点到排头的距离+size，此处size为b中的战舰数量。实际上我们只需要把a段的排头存的数+size即可，因为我们的答案是根据a的排头来计算的。也就是d[pa]＝size[pb]。至于合并的数量问题，直接size[pb]+＝size[pa]。
代码(c++):
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30010;
int m;
int p[N], sz[N], d[N];
int find(int x)
{
if (p[x] != x)
{
int root = find(p[x]);
d[x] += d[p[x]];
p[x] = root;
}
return p[x];
}
int main()
{
scanf("%d", &m);
for (int i = 1; i < N; i ++ )
{
p[i] = i;
sz[i] = 1;
}
while (m -- )
{
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'M')
{
int pa = find(a), pb = find(b);
if (pa != pb)
{
d[pa] = sz[pb];
sz[pb] += sz[pa];
p[pa] = pb;
}
}
else
{
int pa = find(a), pb = find(b); //因为在计算abs(d[a] - d[b]) - 1)之前我们已经执行了find(a)和find(b)，所以这里的a,b的距离已经被更新为到根的距离的值了
if (pa != pb) puts("-1");
else printf("%d\n", max(0, abs(d[a] - d[b]) - 1));
}
}
return 0;
}
259.奇偶游戏
题目:
小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个回答。
输入格式
第一行包含一个整数N，表示01序列长度。第二行包含一个整数M，表示问题数量。
接下来M行，每行包含一组问答：两个整数l和r，以及回答“even”或“odd”，用以描述S[l～r]中有奇数个1还是偶数个1。
输出格式
输出一个整数k，表示01序列满足第1~k个回答，但不满足第1~k+1个回答，如果01序列满足所有回答，则输出问题总数量。
数据范围
N≤10⁹
M≤10000
思路:
1.由数据范围，长度很长，但是询问很少，所以我们可以用离散化。其次我们可以用前缀和的思想来做。假设S[L～R]中有奇数个1，Si＝a1+……+ai，因为序列里只有0和1，所以这表示前i个数里1的个数。那么就代表S[R]-S[L-1]为奇数，也代表S[R]和S[L-1]奇偶性不同。同理，偶数个1代表奇偶性相同。实际上就类似于食物链那道题目。
2.但是奇偶性不矛盾，等价于本问题不矛盾吗？是等价的。只要奇偶性没矛盾，我们就可以构造出一个S0-SN的合法奇偶性方案。那是否能构造出相应的01序列呢？是可以的，我们可以直接让ai＝|Si - Si-1|即可。
3.那么信息就化简成了两类，①x,y是同一类②x,y是不同类。用带边权的并查集怎么做呢？我们这里每个点有一个d[x]，这个d[x]表示和p[x]的关系，如果等于偶数就代表和根节点同类，奇数就和根节点是不同类。
假设x和根关系是d[x]，和根节点关系是d[y]，判断x和y的关系只需要判断d[x]+d[y]的奇偶性即可，奇数就代表x,y不是同类，偶数就代表同类。
4.对于①x，y是同一类，说明x，y在同一个集合里，那么关系就是已知的。这里我们信息还有传递性，只要知道x,y的关系和y,z的关系，那么就一定可以判断出x,z的关系。这里我们可以用异或运算，如果异或后是0，那么没矛盾，如果是1就有矛盾。如果当前x，y不是同一类，那么我们就要进行集合合并，我们不妨把x合并到y里。
其中因为在模2意义下-1≡1，所以？＝-dx-dy＝dx+dy。所以最终我们的d[px]取成dx^dy就可以了。
5.对于②x，y是不同类，我们有类似结论。px＝py则检查dx^dy，如果是0表示有矛盾，1表示无矛盾。如果px≠py，将d[px]赋值为dx^dy^1。
6.带扩展域的并查集最好是在种类数不太多的情况下使用。这里可以看成是用的枚举的思想，每个点x拆成x和x+n，x表示如果x是偶数，用x+n来表示x是奇数的情况。如果x和y是同类的话，如果x是奇数那么y也是奇数，如果x是偶数，y也是偶数。
我们先来考虑两个元素在一个集合里，是什么含义。这里指的是同一个集合里，有一个条件成立，那么集合里其他所有条件全部成立。所以如果x是奇数，那么y是奇数，他们两个就是一个集合里的，一个成立，另一个就必须成立。我们应该合并x+n和y+n。同理，如果x是偶数，y也是偶数那么应该合并x和y。至于矛盾，我们只需要判断x+n和y是否在一个集合里或者判断x和y+n是否在一个集合里。
同理，如果x和y是异类，那么如果x是偶数，那么y是奇数。如果x是奇数，那么y是偶数。
另外值得注意的是，这里原来的元素已经不是元素了。而且变成了条件，x就表示x是偶数。
代码(c++):
①带边权写法:
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 20010; //一万个询问则两万个点
int n, m;
int p[N], d[N];
unordered_map<int, int> S;
int get(int x)
{
if (S.count(x) == 0) S[x] = ++ n; //离散化函数
return S[x];
}
int find(int x)
{
if (p[x] != x)
{
int root = find(p[x]);
d[x] += d[p[x]];
p[x] = root;
}
return p[x];
}
int main()
{
cin >> n >> m;
n = 0; //n是没有用的，因为我们要做离散化
for (int i = 0; i < N; i ++ ) p[i] = i;
int res = m; //无矛盾输出问题总数量
for (int i = 1; i <= m; i ++ )
{
int a, b;
string type;
cin >> a >> b >> type;
a = get(a - 1), b = get(b);
int t = 0;
if (type == "odd") t = 1;
int pa = find(a), pb = find(b);
if (pa == pb)
{
if (((d[a] + d[b]) % 2 + 2) % 2 != t) //+2是防负数。不可以直接用d[a]^d[b]!=t，如果想用可以把find函数里的+＝改成^＝，或者这里改为if ((d[a] ^ d[b]) % 2 != t)。如果直接用d[a]^d[b]!=t，假设d[a] = 2，d[b] = 1，那么异或结果是3，而正确代码的逻辑应该是(2+1)%2＝1。假设t为1，然后3!=1判定了矛盾，实际上3≡1，不应该判定矛盾。但是对于合并来说，加或者异或都可以
{
res = i - 1; //有矛盾，输出矛盾问题的上一个问题编号即可
break;
}
}
else
{
p[pa] = pb;
d[pa] = d[a] ^ d[b] ^ t;
}
}
cout << res << endl;
return 0;
}
②扩展域写法:
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 40010, Base = N / 2; //N为上个版本代码的2倍
int n, m;
int p[N];
unordered_map<int, int> S;
int get(int x)
{
if (S.count(x) == 0) S[x] = ++ n;
return S[x];
}
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
n = 0;
for (int i = 0; i < N; i ++ ) p[i] = i;
int res = m;
for (int i = 1; i <= m; i ++ )
{
int a, b;
string type;
cin >> a >> b >> type;
a = get(a - 1), b = get(b);
if (type == "even") //同类
{
if (find(a + Base) == find(b))
{
res = i - 1;
break;
}
p[find(a)] = find(b); //没矛盾就合并，本行和下一行的两种情况
p[find(a + Base)] = find(b + Base);
}
else //异类
{
if (find(a) == find(b))
{
res = i - 1;
break;
}
p[find(a + Base)] = find(b);
p[find(a)] = find(b + Base);
}
}
cout << res << endl;
return 0;
}
