一、第六周学习总结表

本周学习完成情况

Contest	完成情况
博弈论入门练习	8/12
并查集练习	11/19
字符串	10/11
线段树1	7/15
图论(拓扑排序)	11/18
Atcoder比赛+补题	4/8
郑州大学比赛+补题	6/12
小白月赛比赛+补题	4/6
ccpc华为	2/12
总计	50/90

个人感悟
本周是最后一周，经过了40天的历练，感觉自己对算法有了一个全新的认识。对算法和数据结构整体的认知更加的清晰了。未来学习路线也逐渐有了方向。最直观的感受就是解题能力的提升，虽然像atcoder和codeforces上的思维题做题情况和暑假前也差不多，但是做题速度和读题速度有了非常大的进步。而新学习的知识也慢慢的能在各种比赛中用到了，比如上周日的牛客中的博弈论数论题的基础题都解了出来，非常有成就感。

暑期结束到开学的日子里，我将对整个暑假学习的进行一些巩固，把所有刷过的题目看一遍，没有做出的题目再尝试一遍。随后把图论的没有来的及讲完的东西自学完成。把刘汝佳白书所学过的东西都看一遍，以及算法进阶上的题目能做的对照题单尽量全部完成

二、本周学习新内容

1.LONG_LONG_MAX

中包含的，即long long 的最大值

9223372036854775807

2.字符串哈希

$f(s)=\Sigma_{i=1}^l s[i]\times p^{l-i} (\bmod M )$

原理：将字符串类比成一个p进制的数

且p通常取131 or 1331，在$2^{64}$范围内映射
为了防止指数爆炸的情况，定义成unsigned long long的形式，超出会自动取模

计算字符串的哈希值，即计算前缀和复杂度为$O(n)$

计算字符串后再次获取子串的哈希值，即计算区间和复杂度为$O(1)$

$ f[L, R]=(f[R]−f[L−1]×P ^{R−L+1} )$

typedef unsigned long long ull;
const int P=131;
const int N=1001;
ull h[N], p[N];

void gethash(string s){
    for (int i = 1; i <= s.length(); i ++ )
    {
        h[i] = h[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }
}
ull get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main(){
    p[0]=1;
}

3.线段树

$O(log_n)$修改区间值，查询区间值

// Luogu P3372 【模板】线段树 1
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define lc p << 1
#define rc p << 1 | 1
#define N 100005
#define ll long long
#define mid(x, y) x + y >> 1
ll n;
ll num[N];
struct node
{
    ll l, r, sum, add;
} tr[N * 4];

//向上更新结点维护的值
void pushup(ll p)
{
    tr[p].sum = tr[lc].sum + tr[rc].sum;
}

void pushdown(ll p)
{
    auto &pp = tr[p], &pl = tr[lc], &pr = tr[rc];
    if (pp.add)
    { //懒惰标记
        pl.sum += pp.add * (pl.r - pl.l + 1);
        pr.sum += pp.add * (pr.r - pr.l + 1);
        pl.add += pp.add; //+=因为可能有多个懒惰值
        pr.add += pp.add;
        pp.add = 0;
    }
}

//建树,l,r代表的是线段的开始和结束
void build(ll p, ll l, ll r)
{
    tr[p] = {l, r, num[l], 0};
    if (l == r)
        return;
    ll m = mid(l, r);
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(p);
}

//区间修改
void update(ll p, ll x, ll y, ll k)
{
    if (x <= tr[p].l && tr[p].r <= y)
    {
        tr[p].sum += (tr[p].r - tr[p].l + 1) * k;
        tr[p].add += k;
        return;
    }
    ll m = mid(tr[p].l, tr[p].r); //寻找改向哪个方向递归查询目标点
    pushdown(p);
    if (x <= m)
        update(lc, x, y, k);
    if (y > m)
        update(rc, x, y, k);
    pushup(p);
}
//区间查询(x=y就是单点查询)
ll query(ll p, ll x, ll y)
{
    if (x <= tr[p].l && tr[p].r <= y)
        return tr[p].sum;
    ll m = mid(tr[p].l, tr[p].r);
    pushdown(p);
    ll sum = 0;
    if (x <= m)
        sum += query(lc, x, y);
    if (y > m)
        sum += query(rc, x, y);
    return sum;
}

int main()
{
    ll n, m;
    scanf("%lld%lld", &n, &m);
    for (ll i = 1; i <= n; i++)
    {
        scanf("%lld", &num[i]);
    }
    build(1, 1, n);
}

4.博弈论

01Bash博弈

(91条消息) HDU-2147 kiki‘s game 巴什博弈_hesorchen的博客-CSDN博客

只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取1个，最多取m个，最后取光者得胜

分析：

首先可以最简单的分析：

如果只有$m+1$个物品，那么先手最多取走m个物品，无论怎么取，后手都能取完。

那么推广到多个物品，只要 $n = (m+1)*k + p$，即 $n\bmod (m+1) != 0$

只要我们先手，取出p个物品，让剩下的物品数量变成$(m+1)$的倍数

那么只要对手任意取x个物品，先手只要再取$(m+1)-x$个物品，保证每次留给对手的局面都是$(m+1)$的倍数，那么我们就必赢

结论：

当$n\bmod(m+1)==0$时先手必败

void solve(){
    int n,m;
    cin>>n>>m;
    if(n%(m+1)==0){
        cout<<"second"<<endl;
    }else{
        cout<<"first"<<endl;
    }
}

02Wythoff博弈

有两堆各若干物品，两个人轮流从任意一堆中至少取出一个或者从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜。

这里的必输局势：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。从这些必输局势可以发现，每组的第一个是前面没有出现的最小正整数，ak=[k∗(1+5–√)/2], bk=ak+k, k=0,1,2,3…。

所以，先求出差值，差值*黄金分割比 == 最小值的话后手赢，否者先手赢。

double r = (sqrt(5) + 1) / 2;
int d = abs(a - b) * r;
if (d != min(a, b))  return true;
else  false;

注：如果a,b的值非常大的话，需要高精度来计算这个double类型的r

03Nim博弈

[ ] 异或的原理?

(91条消息) [学习笔记] （博弈论）Nim游戏和SG函数_A_Comme_Amour的博客-CSDN博客_nim博弈

Nim博弈：
即n堆个物品，每次可以里面取任意个,取到最后一个物品的人取胜。

Nim博弈必胜局势的证明

条件：有$n$堆牌$x_i$，每次任意堆取牌任意数量。即

$x_1\ x_2\ x_3 \ x_4 ···x_n $

已知：

$若当前x_1 \wedge x_2 \wedge x_3 \wedge x_4 \wedge ···x_n =0，则先手者操作必输，即为必败局势$

要证明：

$x_1 \wedge x_2 \wedge x_3 \wedge x_4 \wedge ···x_n\ !=0时，必能进行某种操作，使得对手成为必败局势$

即:

$当你有x_1 \wedge x_2 \wedge x_3 \wedge x_4 \wedge ···x_n\ !=0 \ \ \ \\你必有某种取牌法让你的对手有\\x_1 \wedge x_2 \wedge x_3 \wedge x_4 \wedge ···x_n =0$

证：

设所有数的异或为$x_0$，若$x_0\ !=0$，则说明其二进制上必有一位为1

则必然存在$x_i$,使得$x_i \wedge x_0 < x_i$,既然这个数比$x_{i}$小

那么就存在$x_i - x_i \wedge x_0<x_i$

所$x_i - (x_i - x_i \wedge x_0)=x_i \wedge x_0$

也就是说可以对$x_i$进行一个操作,即对第i堆牌$x_i$拿出$(x_i - x_i \wedge x_0)$张牌，让他$xi$张牌变成$x_i \wedge x_0$张牌

进行这一步操作之后，你的对手拿到的牌一定是

$x_1 \wedge x_2 \wedge x_3 \wedge x_4 \wedge ···x_n\ \wedge x_0 $

$=x_0 \wedge x_0=0$,

即所有数异或为0，即为必败局势

所以必然存在一种操作，使得对手成为必败局势

总结：

也就是说，要让对手成为必败局势,那么对$x_i$，取出$(x_i - x_i \wedge x_0)$，让牌数$x_i$变为$(x_i - x_i \wedge x_0)$即可

而这样的$x_i$的数量取决于$x_i \wedge x_0 < x_i$的数量

for (int k = 1; k <= n; k++)
{
    ans ^= num[k];
}

04ICG游戏

Nim游戏是经典的公平组合游戏(ICG)，对于ICG游戏我们有如下定义：

两名选手
两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个
游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它因素；局面的改变称为“移动”(move)
如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负

将ICG问题进行转化：任何一个ICG都可以通过把每个局面看作一个顶点，对每个局面和它的子局面连一条有向边来抽象这个“有向图游戏”

05PN分析

P-position：即必败点

所有终结位置，不能再走的位置，为必败点(P点)
某点开始的所有操作，都将进入必胜点(N点)的位置，为必败点

N-position：即必胜点

某点开始的所有操作，存在某一步能进入必败点(P点)的位置，为必胜点

分析步骤

将所有终结位置标记为必败点(P点);
将所有一步能进入必败点(P点)的位置标记为必胜点(N点);
如果从某个点开始的所有一步操作都只能进入必胜点(N点)，则将该位置标记为必败点(P点);
如果在步骤3中未能找到新的必败点(P点)，算法终止，否则返回步骤2.

06SG函数

[ ] SG异或的原理？

SG函数为计算博弈状态的函数，当SG[X] = 0时，说明先手必败

mex运算(minimal excludant)

$mex(S)=min\left\{不在集合中的自然数\right\}$

$sg(x)=mex\left\{ 每个sg(y)\ \ |\ \ y是x的后继\right\}$

SG函数的求法：

找出必败态
找出当前所有状态的前驱结点
根据定义计算结点SG值
重复上述步骤，直到整棵树建立完成

例题：集合Nim

集合-Nim游戏 - 天仔 - 博客园 (cnblogs.com)

代码模板

DFS序遍历DAG图

int n;
int sg[N];
vector<int> a[N];

// dfs序遍历DAG图求SG函数
int getSg(int cur)
{
    //如果有值，直接返回（记忆化搜索）
    if (sg[cur] != -1)
        return sg[cur];
    //如果没有，那就找
    
    //用于标记
    bool vis[N] = {false};
    
    //遍历当前结点的后继结点，dfs序求出他们的sg函数,并标记
    for (int i = 0; i < a[cur].size(); i++)
    {
        int next = a[cur][i];
        int pos = getSg(next);
        //为true的pos就是当前cur结点的后继的sg值
        vis[pos] = true;
    }

    // mex函数，找出最小的不在集合内的自然数
    for (int i = 0; i < n; i++)
    {
        if (vis[i] == false)
        {
            sg[cur] = i;
            break;
        }
    }
    return sg[cur];
}

非DFS,一次性打表

int f[15] = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987};
bool vis[N];
int sg[N];
void getSg(int n)
{
    memset(sg, 0, sizeof(sg));
    // sg[0]=0,所以循环从1开始
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof(vis));
        for (int j = 0; j <= n && f[j] <= i; j++)
            vis[sg[i - f[j]]] = true; //当前节点可以转到的下一状态标记
        for (int j = 0; j <= n; j++)
        { //查询当前后继状态SG值中最小的非零值
            if (vis[j] == false)
            {
                sg[i] = j;
                break;
            }
        }
    }
}

三、题解一览

1.博弈论练习 - H - A Chess Game

题目标签

博弈论；SG函数

题目描述

给定一个DAG图，以及一些棋子，判断是否能获胜

题目解析

经典的SG函数的应用。

用dfs序遍历一个DAG图求解SG函数

先判断值是否存在（记忆化搜索）
当前结点能走的所有结点并dfs，打上标记
mex函数找出最小不存在集合内的自然数

通过代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 1100
using namespace std;
int n;
int sg[N];
vector<int> a[N];
// dfs序遍历DAG图求SG函数
int getSg(int cur)
{
    //如果有值，直接返回（记忆化搜索）
    if (sg[cur] != -1)
        return sg[cur];

    //如果没有，那就找
    //用于标记
    bool vis[N] = {false};
    //遍历当前结点的后继结点，dfs序求出他们的sg函数,并标记
    for (int i = 0; i < a[cur].size(); i++)
    {
        int next = a[cur][i];
        int pos = getSg(next);
        //为true的pos就是当前cur结点的后继的sg值
        vis[pos] = true;
    }

    // mex函数，找出最小的不在集合内的自然数
    for (int i = 0; i < n; i++)
    {
        if (vis[i] == false)
        {
            sg[cur] = i;
            break;
        }
    }
    return sg[cur];
}

int main()
{
    ios;
    while (cin >> n)
    {
        bool v[N];
        memset(sg, -1, sizeof(sg));
        memset(v, 0, sizeof(v));
        for (int i = 0; i < n; i++)
        {
            int t;
            cin >> t;
            a[i].clear();
            for (int j = 0; j < t; j++)
            {
                int temp;
                cin >> temp;
                a[i].push_back(temp);
                v[i] = true;
            }
        }
        int q;
        while (cin >> q && q != 0)
        {
            int ans = 0;
            while (q--)
            {
                int temp;
                cin >> temp;
                ans ^= getSg(temp);
            }
            if (ans == 0)
                cout << "LOSE" << endl;
            else
                cout << "WIN" << endl;
        }
    }
}

2.POJ2182 - Lost Cows

题目标签

线段树

题目描述

一共有n个数为1-n，随机进行排列

现在你不知道每个数的大小是多少

你只知道每个数的前面一共有多少个数比他小，给出2到n（第一个数默认为0）

现在请你还原出这个数的序列

题目解析

从后往前遍历，num数组

推导出，$ans[i]=(1-n)中除去ans[i,n]出现过的数后，第num[i]+1大的数$

这里的除去，只是用数组模拟时的说法，实际上，每个数前面的数(可以和他比较的数) 就是不包含已经计算的数(即后面的数)

而如果用数组来模拟这一过程，会出现TLE的现象

所以这题可以用线段树来做

而线段树的做法不再是维护一个数组，有没有被选中过。而是每一个结点都记录当前区间内还剩下多少个数len(可以被比较的数)

初始化时，将每个区间的len都记录为r-l+1,比如[1,5]就是5

每次查询的时候，需要动态的去修改区间的长度，与修改sum类似，每个被访问的（区间包含的）都需要进行修改

ll query(ll cur, ll k)//表示寻找cur区间内第k小的值
{
    pushup(cur);
    if (tr[cur].l == tr[cur].r)
        return tr[cur].r;
    ll sum = 0;
    if (k <= tr[lc].len)
        sum += query(lc, k);
    else
        sum += query(rc, k - tr[lc].len);
    return sum;
}

查询时，用k来查询，与左边的len进行比较。

如果小于len，就继续向左遍历，即找第len小的数

如果大于len，就向右遍历，并query(rc,k-tr[lc].len)，意味寻找右边区间内第k-tr[lc].len小的数

比如

左区间剩下两个数
右区间剩下三个数
- 此时如果查找第3小的数，就是递归查找右区间第1小的数
  - 因为线段是从小到大排的，所以右区间第1小的数就是，1+2（左区间的数）=3小的数
- 此时如果查找第2小的数，就是递归查找左区间第2小的数

通过代码

// Luogu P3372 【模板】线段树 1
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define lc cur << 1
#define rc cur << 1 | 1
#define N 9000
#define ll long long
#define mid(x, y) x + y >> 1
ll n;
ll num[N];
struct node
{
    ll l, r, len;
} tr[N * 4];

//向上更新结点维护的值
void pushup(ll cur)
{
    tr[cur].len--;
}

//建树,l,r代表的是线段的开始和结束
void build(ll cur, ll l, ll r)
{
    tr[cur].l=l;tr[cur].r=r;tr[cur].len=r-l+1;
    if (l == r)
        return;
    ll m = mid(l, r);
    build(lc, l, m);
    build(rc, m + 1, r);
}

ll query(ll cur, ll k)
{
    pushup(cur);
    if (tr[cur].l == tr[cur].r)
        return tr[cur].r;
    ll sum = 0;
    if (k <= tr[lc].len)
        sum += query(lc, k);
    else
        sum += query(rc, k - tr[lc].len);
    return sum;
}

int main()
{
    ll n;
    ll ans[N] = {0};
    scanf("%lld", &n);
    for (ll i = 2; i <= n; i++)
    {
        scanf("%lld", &num[i]);
    }
    build(1, 1, n);
    for (int i = n; i >= 1; i--)
    {
        ans[i] = query(1, num[i] + 1);
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%lld\n", ans[i]);
    }
}

3.拓扑排序 - B - Following Orders

题目标签

拓扑排序

DFS

题目描述

给定一个字母序列

以及字母之间的关系

按字典序以及字母之间的关系求出所有的全排列

题目解析

求拓扑全排列

按照常规全排列的思想用DFS去搜索

首先按照常规方法读入，这里注意要把字母转换为数字，再进行sort排序，保证最后输出的一定是按字典序来的

记录答案，记录对应的字母，输出答案再把数字转换为字母即可

搜索：

每次dfs，按照排序后的数字进行遍历

将没有访问过的和入度为0的进行下一次dfs

dfs前把该数打上标记

他连接的所有点的入读都减一
这个点的vis记录为true

通过代码

#include<bits/stdc++.h>
#define N 1001
using namespace std;
int n;
bool vis[N];
int in[N];
int g[N][N];
int num[N];
int ans[N];
// TODO:BFS怎么做这道题
//转换成数字
//顺序遍历num,遇到的如果入度为0了，那么就添加，并用ans记录。
// vis记录是否访问，以便不重复
// dfs要进行回溯
void toposort(int cur)
{
    if (cur == n)
    {
        for (int i = 0; i < n; i++)
        {
            printf("%c", +char(ans[i] + 'a'));
        }
        printf("\n");
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (vis[num[i]] == false && in[num[i]] == 0)
        {
            vis[num[i]] = true;
            ans[cur] = num[i];
            //下一个点的访问到的点
            for (int j = 0; j < n; j++)
            {
                if (g[num[i]][num[j]])
                    in[num[j]]--;
            }
            toposort(cur + 1);
            //回溯
            vis[num[i]] = false;
            for (int j = 0; j < n; j++)
            {
                if (g[num[i]][num[j]])
                    in[num[j]]++;
            }
        }
    }
}
int main()
{
    string line;
    while (getline(cin, line))
    {
        memset(vis, false, sizeof(vis));
        memset(in, 0, sizeof(in));
        memset(g, 0, sizeof(g));

        n = 0;
        for (int i = 0; i < line.size(); i++)
        {
            if (line[i] >= 'a' && line[i] <= 'z')
                num[n++] = line[i] - 'a';
        }
        sort(num, num + n);
        getline(cin, line);
        int cnt = 0, temp[2]; //每两个字母读取一次
        for (int i = 0; i < line.size(); i++)
        {
            if (line[i] != ' ')
                temp[cnt++] = line[i] - 'a';
            if (cnt == 2)
            {
                cnt = 0;
                g[temp[0]][temp[1]] = 1;
                in[temp[1]]++; //入度
            }
        }
        toposort(0);
        printf("\n");
    }
}

4.博弈论练习 - C - Being a Good Boy in Spring Festival

题目标签

博弈论；

nim博弈；

题目描述

有m堆牌，可以任意牌堆中取走任意张，全部取光游戏结束，拿走最后一张牌的人获胜

求先手要获胜，第一步有多少种可能

题目解析

根据nim博弈的结论

要让对手成为必败局势,那么对$x_i$，取出$(x_i - x_i \wedge x_0)$，让牌数$x_i$变为$(x_i - x_i \wedge x_0)$即可

而这样的$x_i$的数量取决于$x_i \wedge x_0 < x_i$的数量

于是先求出所有的数的异或

再遍历每一个数即可

通过代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define N 1001
#define inf 0x3f3f3f
using namespace std;
void solve(ll n){
    ll a[101]={0};
    ll sum=0;
    ll ans=0;
    for (ll i = 0; i < n; i++)
    {
        cin>>a[i];
        sum^=a[i];
    }
    for (ll i = 0; i < n; i++)
    {
        if(a[i]>(sum^a[i])){
            ans++;
        }
    }
    cout<<ans<<endl;
}

int main()
{
    ll n;
    while (cin>>n && n!=0)
    {
        solve(n);
    }
    return 0;
}

5.博弈论练习 - D - Fibonacci again and again

题目标签

博弈论;

nim博弈

SG函数

题目描述

有n堆牌，每次可以任意堆里取x张牌

x必须是斐波那契数列中的数

题目解析

首先打斐波那契表

因为题目数据直到1000，所有直接手写一个就可以

然后就是打表sg函数

通过代码

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int f[15] = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987};
int s[N];
int sg[N];
void getSg(int n){
    memset(sg,0,sizeof(sg));
    //sg[0]=0,所以循环从1开始
    for(int i=1;i<=n;i++){
        memset(s,0,sizeof(s));
        for(int j=0;j<=n&&f[j]<=i;j++)
            s[sg[i-f[j]]]=1;//当前节点可以转到的下一状态标记
        for(int j=0;j<=n;j++){ //查询当前后继状态SG值中最小的非零值
            if(!s[j]){
                sg[i]=j;
                break;
            }
        }
    }
}
int main()
{
    int a, b, c;
    getSg(1001);
    while (cin >> a >> b >> c && a != 0 && b != 0 && c != 0)
    {
        memset(f, -1, sizeof(f)); //初始化f均为-1,方便在sg函数中查看x是否被记录过
        int res = 0;
        res ^= sg[a];
        res ^= sg[b];
        res ^= sg[c];
        //观察异或值的变化,基本原理与Nim游戏相同

        if (res != 0)
            printf("Fibo\n");
        else
            printf("Nacci\n");
    }
    return 0;//
}

6.并查集练习 - C - The Suspects

题目标签

并查集

题目描述

某地爆发了疫情

给出一堆序列，表示这些人曾存在同一场所，为密接

已知0号为携带者，所有和他为密接的人都会被感染

求最后感染的总人数

题目解析

记录结点数量的并查集，统计0号结点所在位置的并查集的大小即可

记录结点数量：每个并查集的数量记录在最大祖先结点上，所有人初始化为1

每次合并时，让合并后的祖先更新size大小

查询时查询size[find(0)]即可

通过代码

#include<bits/stdc++.h>
using namespace std;
int fa[30005];
int size[30005];
inline int find(int x)
{
    while (x != fa[x])
        x = fa[x] = fa[fa[x]];
    return x;
}
void merge(int x, int y)
{
    x=find(x);
    y=find(y);
    if(x==y) return;
    fa[y] = x;
    size[x]+=size[y];
}
int main()
{
    int n, m;
    while (cin >> n >> m && n+m!=0)
    {
        memset(fa,0,sizeof(fa));
        memset(size,0,sizeof(size));
        for (int i = 0; i < n; i++)
        {
            fa[i] = i;
            size[i]=1;
        }
        for (int i = 0; i < m; i++)
        {
            int num;cin>>num;
            int father;cin>>father;
            for (int j = 1;j < num; j++)//合并所有
            {
                int son;cin>>son;
                merge(father,son);
            }
        }//
        cout<<size[find(0)]<<endl;
    }
}

7.并查集练习 - D - Find them, Catch them

题目标签

并查集

题目描述

有两个帮派的人分别为龙和虎

现有n人，编号为1-n，要么隶属于龙，要么隶属于虎

现在每行给出一个操作符和两个数

D表示两个人不是同一帮派的

A表示查询这两个人是否为同一帮派的

题目解析

使用到种类并查集

普通并查集是以朋友的朋友还是朋友的思路串在一起

而种类并查集是以敌人的敌人是朋友联系在一起

所以要开两倍数组，以n为分界线

表示朋友时，那么在分界线内合并

即merge(a,b);merge(a+n,b+n)

表示敌人时，那么跨过分界线合并

即merge(a+n,b);merge(a,b+n)

算法学习笔记(7)：种类并查集

若有三种不同种类，则开三倍数组

通过代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int fa[200010];
inline int find(int x)
{
    while (x != fa[x])
        x = fa[x] = fa[fa[x]];
    return x;
}
void merge(int x, int y)
{
    fa[find(y)] = find(x);
}
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int m, n;
        scanf("%d%d",&n,&m);
        for (int i = 0; i <=2*n; i++)
        {
            fa[i] = i;
        }
        for (int i = 0; i < m; i++)
        {
            char op[2];
            int b, c;
            scanf("%s %d %d",op,&b,&c);
            if (op[0] == 'D') //合并不同类
            {              //合并
                merge(b + n, c);
                merge(b, c + n);
            }
            else if(op[0] == 'A')
            {
                if (find(b) == find(c))
                {
                    printf("In the same gang.\n");
                }
                else if (find(b + n) == find(c))
                {
                    printf("In different gangs.\n");
                }
                else
                {
                    printf("Not sure yet.\n");//
                }
            }
        }
    }
}

22暑期ACM集训周记06

一、第六周学习总结表

本周学习完成情况

个人感悟

二、本周学习新内容

1.LONG_LONG_MAX

2.字符串哈希

3.线段树

4.博弈论

01Bash博弈

02Wythoff博弈

03Nim博弈

04ICG游戏

05PN分析

06SG函数

三、题解一览

1.博弈论练习 - H - A Chess Game

题目标签

题目描述

题目解析

通过代码

2.POJ2182 - Lost Cows

题目标签

题目描述

题目解析

通过代码

3.拓扑排序 - B - Following Orders

题目标签

题目描述

题目解析

通过代码

4.博弈论练习 - C - Being a Good Boy in Spring Festival

题目标签

题目描述

题目解析

通过代码

5.博弈论练习 - D - Fibonacci again and again

题目标签

题目描述

题目解析

通过代码

6.并查集练习 - C - The Suspects

题目标签

题目描述

题目解析

通过代码

7.并查集练习 - D - Find them, Catch them

题目标签

题目描述

题目解析

通过代码