读入两个数后直接进行拆解…小学数学啦

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
int t[105];
int a[105],b[105],c[105];
vector<int> ans,temp;
int n;
void dfs(int cur)
{
    if(ans.size())  return ;
    if(cur == n)
    {
        if(temp.front() != temp.back())
        ans = temp;
        return ;
    }
    if(temp.size() == 0)
    {
        temp.push_back(a[cur]);
        dfs(cur + 1);
        temp.pop_back();

        temp.push_back(b[cur]);
        dfs(cur + 1);
        temp.pop_back();

        temp.push_back(c[cur]);
        dfs(cur + 1);
        temp.pop_back();
    }
    else
    {
        if(temp.back() != a[cur])
        {
            temp.push_back(a[cur]);
            dfs(cur + 1);
            temp.pop_back();
        }

        if(temp.back() != b[cur])
        {
            temp.push_back(b[cur]);
            dfs(cur + 1);
            temp.pop_back();
        }

        if(temp.back() != c[cur])
        {
            temp.push_back(c[cur]);
            dfs(cur + 1);
            temp.pop_back();
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i = 0;i < n;i += 2)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            printf("%d %d ",-y,x);
        }
        puts("");
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

struct cow{
    int l,r,xu,p;
}a[50005];
bool operator > (cow a ,cow b){
    return a.r>b.r;
}
priority_queue<cow,vector<cow>,greater<cow> >q;
bool cmp_p(cow a,cow b){
    return a.p<b.p;
}
bool cmp_l(cow a,cow b){
    return a.l<b.l;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[i].l=x,a[i].r=y;
        a[i].p=i;
    }
    sort(a+1,a+1+n,cmp_l);
    int ans=1; 
    a[1].xu=1;
    q.push(a[1]);

    for(int i=2;i<=n;i++){
        if(q.top().r<a[i].l){
            a[i].xu=q.top().xu;
            q.pop();
        }
        else{
            ans++;
            a[i].xu=ans;

        }

        q.push(a[i]);

    }
    sort(a+1,a+1+n,cmp_p);
    printf("%d\n",ans);
    for(int i=1;i<=n;i++){
        printf("%d\n",a[i].xu);
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int t[105];
int a[105],b[105],c[105];
vector<int> ans,temp;
int n;
void dfs(int cur)
{
    if(ans.size())  return ;
    if(cur == n)
    {
        if(temp.front() != temp.back())
        ans = temp;
        return ;
    }
    if(temp.size() == 0)
    {
        temp.push_back(a[cur]);
        dfs(cur + 1);
        temp.pop_back();

        temp.push_back(b[cur]);
        dfs(cur + 1);
        temp.pop_back();

        temp.push_back(c[cur]);
        dfs(cur + 1);
        temp.pop_back();
    }
    else
    {
        if(temp.back() != a[cur])
        {
            temp.push_back(a[cur]);
            dfs(cur + 1);
            temp.pop_back();
        }

        if(temp.back() != b[cur])
        {
            temp.push_back(b[cur]);
            dfs(cur + 1);
            temp.pop_back();
        }

        if(temp.back() != c[cur])
        {
            temp.push_back(c[cur]);
            dfs(cur + 1);
            temp.pop_back();
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i = 0;i < n;i++)    scanf("%d",&a[i]);
        for(int i = 0;i < n;i++)    scanf("%d",&b[i]);
        for(int i = 0;i < n;i++)    scanf("%d",&c[i]);
        ans.clear();
        temp.clear();
        dfs(0);
        for(int i = 0;i < n;i++)
        printf("%d%c",ans[i]," \n"[i == n - 1]);
    }
    return 0;
}

Description

给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r，表示询问数列中第 l∼r 个数的和。
对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数 N,M。

第二行 N 个整数 A[i]。

接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

1≤N,M≤105,
|d|≤10000,
|A[i]|≤109

输入样例：

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出样例：

4
55
9
15

心得

以前写线段树的时候往往是学一次忘一次，但是自从看了算法训练营之后认识就加深到可以不忘记了。
总结下来无非以下几点：
1. build 创建线段树
2. query 查询
3. update 更新
4. pushdown 下传懒标记

我们的查询和更新统一写成区间覆盖式写法，个人认为这样写更方便更容易记忆。
模板：

type func(int u , int l , int r)
{


    if(tr[u].l>=l&& tr[u].r <= r) return something ;  //区间覆盖写法

    pushdown(u) ;  // 无论查询还是更新都会先下传懒标记


    int mid = (tr[u].l+tr[u].r) >> 1 ; 

    if(l <= mid) ans += func(u<<1 , l,r) ;   // 如果采取区间覆盖式写法，那么 区间参数 l,r 是不变的，一律不动传给下一次函数
    if(r> mid)  ans += func(u<<1|1 , l , r) ;

    // 而且值得注意的是，分情况讨论也只有这两种， l<= mid  和 r>mid 
}

参考文献

算法训练营

C++ 代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std ;

typedef long long LL ;

const int N = 1e5 +10 ;

int n , m; 
int w[N] ;
struct node 
{
    int l , r ;
    LL lazy, s ;
}tr[N*4] ;


void build(int u , int l , int r) 
{
    tr[u].l = l , tr[u].r = r ;
    if(l==r) 
    {
        tr[u].s = w[l] ;
        return ;
    }

    int mid = (tr[u].l + tr[u].r) >> 1 ;
    build(u<<1 , l ,mid) ;
    build(u<<1|1,mid+1,r) ;
    tr[u].s = tr[u<<1].s + tr[u<<1|1].s ;
}

void pushdown(int u) 
{
    if(tr[u].lazy)
    {
        tr[u << 1].lazy += tr[u].lazy ;
        tr[u << 1].s += tr[u].lazy * (tr[u <<1].r - tr[u << 1 ].l +1 ) ;
        tr[u << 1|1].lazy += tr[u].lazy ;
        tr[u <<1 |1].s += tr[u].lazy *(tr[u<<1|1].r - tr[u<<1|1].l +1) ;
        tr[u].lazy =0 ;
    }
}

LL sum(int u ,int l , int r)
{
    if(tr[u].l>=l&& tr[u].r <= r) return tr[u].s ;

    pushdown(u) ;

    LL ans = 0 ;
    int mid = (tr[u].l+tr[u].r) >> 1 ;
    if(l <= mid) ans += sum(u<<1 , l,r) ;
    if(r> mid)  ans += sum(u<<1|1 , l , r) ;
    return ans ;
}

void add(int u , int l , int r , int val) 
{
    if(tr[u].l >= l && tr[u].r <=r )
    {
        tr[u].lazy += val ;
        tr[u].s  += val * (tr[u].r-tr[u].l +1 ); 
        return ;
    }

    pushdown(u) ;

    int mid = (tr[u].l+tr[u].r) >> 1 ;
    if(l <= mid) add(u<<1 , l,r,val) ;
    if(r > mid ) add(u<<1 |1 , l,r, val) ;

    tr[u].s = tr[u<<1].s + tr[u<<1|1].s ;  
}


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

    for(int i = 0 ; i < m ; i ++) 
    {
        char op[2] ;
        scanf("%s",op) ;

        if(*op == 'Q')   // 查询
        {
            int l ,r ;
            scanf("%d%d",&l,&r) ;
            printf("%lld\n" ,sum(1,l,r)) ;
        }
        else   // 修改
        {
            int l , r , val ;
            scanf("%d%d%d",&l,&r,&val) ;
            add(1,l,r,val) ;
        }
    }

    return 0 ;
}

不知道怎么会事，就凑着凑着就对了，对二分的两种模板还是不知道什么时候用

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
const int N = 100010;
int n,q,ans1,ans2;
int a[N];

int main()
{
    cin >> n >> q ;
    for(int i=1;i<=n;i++) cin >> a[i] ;
    while(q--)
    {
        int k;
        cin >> k;
        int l=1,r=n;
        while(l<r)
        {
            int mid = l+r>>1;
            if(a[mid]<k)l=mid+1;
            else r=mid;
        }
        ans1 = l-1;
        if(a[l]!=k)ans1=-1;
        l=1,r=n;
        while(l<r)
        {
            int mid = l+r+1 >> 1;
            if(a[mid]<=k)l=mid;
            else r=mid-1;
        }
        ans2=l-1;
        if(a[l]!=k)ans2=-1;
        cout<<ans1<<" "<<ans2<<endl;
    }
    return 0;
}

题目描述

给定三个整数，请你找出它们中的最大值。

算法

使用三目运算符 ? :

注：

表达式1 ? 表达式2 : 表达式3表示：表达式1如果满足，则返回表达式2；表达式1如果不满足，则返回表达式3。其等价于

if(表达式1)
{
    表达式2;
}
else
{
    表达式3;
}

例如：c=a>b?a:b就会返回a，b中的较大值，并赋值给c。

C++代码：

#include<iostream>

using namespace std;

int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    cout<<( a > b ? a > c ? a : c : b > c ? b : c )<<" eh o maior"<<endl;  
    /*这里要注意加括号，因为三目运算符的优先级比左移运算符的优先级要低！
    括号里面的没有再加括号的原因是：三目运算符中?总是与其右边最近的:相匹配，所以，上边一行等价于：
    cout<<( a > b  ? (a > c ? a : c) : (b > c ? b : c) )<<" eh o maior"<<endl;
    这里的判断顺序为：
        先判断a>b
            如果a>b为真，则判断a>c
                为真返回a，为假返回c
            如果a>b为假，则判断b>c
                为真返回b，为假返回c
    这样就找到了三者中的最大值*/
}

题目描述

链接在此
AcWing 845

解题思路

本题思维量很大，很难。不得不说，y总的解题思路太妙了。下面来详细的分析一下y总的思路。

首先第一个突破点就是，为什么会想到用 BFS 。我们首先要将每一个三阶方阵的数值状态抽象为一个状态，这道题中需要求得的是一个最少的交换次数。那么，其实就是相当于求从初始状态到达最后规范状态的最短路长度。那么提到了最短路，而且本题中状态之间的距离都是相同的，距离就可以设为 $1$ ，这样的话就满足了使用 BFS 的所有条件了。那么好了，本题我们使用 BFS 进行搜索。

之后就需要考虑的点有两个：如何表征每个状态？状态之间应该如何转移？

首先来看第一个问题：如何表征每个状态？事实上，不难发现，每一个状态其实对应一个唯一的 $3\times3$ 方阵， 讲这个二维方阵降为一维行值，就得到了一个唯一的字符串。那么，可以看到实际上在搜索树中，每一个字符串都和唯一的距离值对应，这里定义距离值是根结点到当前状态的搜索路径最短长度，也就是 BFS 搜索出的长度。由于这种一一对应关系，不难想到要使用哈希表进行映射。所以我们使用 unordered_map 或各个语言中的 dict 或 Hashmap 等类似的结构来构建映射关系。这样的话第一个问题就解决了，我们得到了表征每个状态的方式。

那么接下来，第二个问题，状态之间应该如何转移？事实上，对于每一个状态中的 $x$​​​​​ ，它的下一个状态只能有四种移动方式。这个移动方式其实和走迷宫问题 AcWing 844 走迷宫 是一样的。都是在这样的一个二维坐标系下进行移动。那么处理思路就可以完全照搬过来了。由于我们表征每一个状态是将二维矩阵转换成了一维的数组，首先我们找到字符 $x$​​​​ 所在一维字符串中的位置，之后需要进行运算求得其在二维中的位置。记 $k$​​ 为字符 $x$​​ 在一维字符串中的位置，矩阵大小为 $n\times m$​​ ，则运算公式为：$x=\lfloor k/n\rfloor,y=k\mod m$​ 。之后我们进行移动，移动后的坐标满足矩阵大小边界，我们就可以判定该移动后的状态就是搜索树中的一个状态点（结点）。我们得到了一个状态点的字符串形式，如果这个状态还没有被我们搜索到过，那么就更新其距离值，并加入状态与距离映射的哈希表中​​。这里不同语言的处理可能不相同，但如果是修改了原状态的字符串应注意要恢复现场，因为枚举四种移动方式时都是从原状态开始移动的。

有了以上的两个问题的解决作为基础，我们就可以套用 BFS 的模板了。将初始状态入队，之后当队列不空时持续出队队首元素，如果该元素就是最终的状态，证明已经搜索结束， BFS 也随之结束，返回搜索得出的距离最小值；如果该元素还处于中间的某一个状态的话，就需要向下继续搜索。我们枚举其状态的转移，如果状态没有出现过，便将其入队以便于后续的操作。最终如果以上的过程全都执行完毕，但还是没有搜索到最终的状态，证明以该初始状态为起点所构建的状态树（搜索树）中最后没有最终状态这一结点。则搜索结束，返回 $-1$ 。

代码

C++

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;

int bfs(string start) {
    string end = "12345678x";
    unordered_map<string, int> d;
    queue<string> q;
    d[start] = 0;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    q.push(start);
    while (q.size()) {
        auto t = q.front(); q.pop();
        if (t == end) return d[t];
        int dist = d[t];
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                swap(t[k], t[3 * nx + ny]);
                if (!d.count(t)) {
                    d[t] = dist + 1;
                    q.push(t);
                }
                swap(t[k], t[3 * nx + ny]);
            }
        }
    }
    return -1;
}

int main() {
    string start;
    for (int i = 0; i < 9; i++) {
        char c;
        cin >> c;
        start += c;
    }
    cout << bfs(start);
    return 0;
}

Python

from collections import deque

def swap(src, a, b):
    edit = list(src)
    edit[a], edit[b] = edit[b], edit[a]
    return ''.join(edit)

def bfs(start):
    end = '12345678x'
    d = {start: 0, }
    q = deque()
    q.append(start)
    dx = [1, 0, -1, 0]; dy = [0, 1, 0, -1]
    while q:
        t = q.popleft()
        if t == end:
            return d[t]
        dist = d[t]
        k = t.index('x')
        x = k // 3; y = k % 3
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0 <= nx < 3 and 0 <= ny < 3:
                cur = swap(t, k, nx * 3 + ny)
                if cur not in d:
                    d[cur] = dist + 1
                    q.append(cur)
    return -1



if __name__ == '__main__':
    start = ''.join(input().split())
    print(bfs(start))

参考

y总讲解视频

题目描述

链接在此
AcWing 841

字符串前缀哈希法：

定义 ${h_n}$ 为字符串 $str$ 的前缀哈希值，其中 $h_i$ 为前 $i$ 位的哈希值。

那么该如何定义某一前缀字符串的哈希值？

​ 假定字符串为 $s_1s_2\cdots s_n$ ，那么字符串的 $h_i$ 对应的前缀为 $s_1s_2\cdots s_i$ ，定义字符串的数值为 $val$ ，我们把字符串转换成一个 $p$ 进制的数。那么，字符串 $s_1s_2\cdots s_i$ 对应的值为 $val=s_1\times p^{i-1}+s_2\times p^{i-2}+\cdots+s_i\times p^0$ ，定义哈希函数为 $h(x)=x\mod Q$ ，则最后得到的 $h(val)$ 就是 $h_i$ 的值。显然，$h(x)\in (0,Q)$​

这里需要注意两点。首先，对于一个字符我们不能将其换算为 $0$​​ 。假如将 $A$​​ 映射成 $0$​​ ，那么 $AA$​​ 也就是 $0$​​ ，将会无法区分，这里我们采用其 ASCII 码去进行换算；第二，这里我们假设我们的哈希方法是不存在冲突的。一般经验值为 $p=131/13331$​​ 、 $Q=2^{64}$​​ 。

以上就是定义的字符串哈希方式。我们通过这样的定义方式就可以得到所有子串的哈希值。假定给出区间 $[l,r]$ ，那么根据前缀和的思想，我们需要的是 $h_r,h_{l-1}$ 这两个数。对于字符串 $str$ 内部而言，由于我们定义了要将字符串转化为一个 $k$ 进制的数，则从 $s_1$ 到 $s_n$ 为字符串的高位到低位。那么，我们再分别单独看两个子串，这两个前缀子串当中，$s_1$ 是高位，而 $s_{l-1},s_r$ 是低位。但两个子串相对而言，虽然他们的高位相同，但是，其实在数值上，以 $s_1$ 为例，这里我们用前缀字符串哈希值来代表某一个前缀子串，那么 $h_r$ 的 $s_1$ 对应的值应当是 $s_1\times p^{r-1}$ ，而相对应的 $h_{l-1}$ 中是 $s_1\times p^{l-2}$ 。可以看到，其实两个字符串的哈希值差了 $p^{r-1-(l-2)}=p^{r-l+1}$ 倍的。那么，如果想要进行 ”同等“ 的运算，我们就应当将小的哈希值字符串按位扩大相差的倍数才能进行运算。所以，我们就得到了计算区间 $[l,r]$ 的子串哈希值的公式为：$h_{l,r}=h_r-h_l\times p^{r-l+1}(l\leq r)$ 。这里需要说明的一点是，我们定义的哈希函数是 $h(x)=x\mod Q$ ，这里并不是不进行取模运算了，我们用 unsigned long long 存储所有的哈希值，unsigned long long 的阈值是 $2^{64}$ ，所以如果溢出了范围，也就相当于是对 $2^{64}$​ 进行取模运算了。

仿照我们上面扩大倍数的思想，我们得到哈希值的方式也很简单。相邻两位上相差的倍数就是 $p$ ，那么就有如下公式成立：$h_i=h_{i-1}\times p+s_i$ 。

typedef unsigned long long ULL;
const int P = 131;
char str[N];
ULL h[N], p[N];     // h stores hash values, p stores the pow of P

预处理

p[0] = 1;
for (int i = 1; i <= n; i++) {
    p[i] = p[i - 1] * P;
    h[i] = h[i - 1] * P + str[i];
}

获取某一区间内子串的哈希值

ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

判断两个子串是否完全相同：如果两个子串的哈希值完全相同，那么就判定两者完全相同。因为对于任意的每一个不同的字符串而言，其哈希值是唯一的。

bool judge(int l1, int r1, int l2, int r2) {
    if (get(l1, r1) == get(l2, r2)) return true;
    else return false;
}

代码

C++

#include <iostream>
using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

ULL h[N], p[N];
char str[N];

inline ULL gethash(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    scanf("%s", str + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }
    while (m--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (gethash(l1, r1) == gethash(l2, r2)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

Python

def gethash(l, r):
    return (h[r] - h[l - 1] * p[r - l + 1]) % (1 << 64)

if __name__ == '__main__':
    n, m = map(int, input().split())
    P = 131
    s = ' ' + input()
    h = [0] * len(s)
    p = [0] * len(s)
    p[0] = 1
    for i in range(1, n + 1):
        h[i] = (h[i - 1] * P + ord(s[i])) % (1 << 64)
        p[i] = (p[i - 1] * P) % (1 << 64)
    for _ in range(m):
        l1, r1, l2, r2 = map(int, input().split())
        if gethash(l1, r1) == gethash(l2, r2):
            print("Yes")
        else:
            print("No")

题目描述

链接在此
AcWing 240

解题思路

看了各位大佬的题解知道了，本题的实质其实是一个带权并查集。所有能产生关系的元素最后都应该属于一个大集合，区别元素种类的方式就是节点到根结点的距离。对于这道题而言，我们把他提到的产生的关系（不论是谁吃谁还是谁和谁是同类）都扔进一个集合中。原因是只要两个元素之间产生关系，那么扔进集合当中必定可以推断出他们之间的关系。有了这个基础之后，我们应当怎样推断出并查集树中两个节点直接的关系呢？我们需要定义节点间的距离，这也就是带权并查集的核心所在。我们定义如果存在食物链 $A\to B$​ ，那么两节点间距离为 $1$​ ，每个节点到其自身的距离为 $0$​ 。那么对于两个任意节点 $A,B$​ 我们不难发现其关系如下：（假设两点之间距离小于等于 $3$​）
$$
d(A,B):=
\begin{cases}
0&A=B\\
1&B\to A\\
2&A\to B\\
\end{cases}
$$
其中 $d(A,B)$​​ 代表了两点间的距离。

那么，我们就很容易能通过距离知道任意节点 $A$​ 和根结点 $r$​ 的关系：
$$
d(A)-d(r)=d(A)\equiv
\begin{cases}
0&A=r\\
1&r\to A\\
2&A\to r\\
\end{cases}\ \
(\text{mod } 3)
$$
定义 $d(x)$ 为节点 $x$ 进行路径压缩后到根结点的距离。

推广到任意节点，将 $r$ 替换成任意节点 $B$​​ ，我们就能得到并查集树中两个节点之间的关系：
$$
d(A)-d(B)\equiv
\begin{cases}
0&A=B\\
1&A\to B\\
2&A\leftarrow B\\
\end{cases}\ \
(\text{mod } 3)
$$
思路清楚了，接下来来分析代码如何实现。我们定义数组 ${d_n}$ 为每个节点到其父节点的距离。首先将两种一定为假话的情况抛去。之后来看剩下的情况。

我们首先应该重定义 find() 函数，因为我们需要在 find() 结束后同时去维护过某一个节点到其根结点的距离，也就是进行路径压缩后到其父节点的距离。由于我们之前实现的 find() 函数使用递归实现了路径压缩的原理，所以我们这里维护一轮递归中的思路就是每次都要将当前所选中的结点向上提到其父节点的父亲上去，能够和其父节点在同一层级上。所以我们每轮递归中都需要找到其父亲的父节点，也就是 find(p[x]) ，之后，由于路径压缩，这时当前节点的父节点已经改变。那么同时的我们就需要维护这个结点到其父节点的距离 $d_x$ 了。显然，距离需要增加其父节点到父节点的父节点之间的距离，即 $d_{p_x}$​ 。最后，重新绑定父节点为原结点的父节点的再上一层父节点。一轮递归完成。当所有递归都退出后，正好我们完成了路径压缩的全过程，而此时，我们的 $d_x$ 存储的也恰好就是当前节点到根结点的距离了。

所以我们重定义了 find() 函数，我们就可以先使用该函数来判断输入进来的两个节点是否属于同一个集合当中。此时也同时完成了对两个节点的路径压缩。我们也知晓了两个节点到根结点的距离，我们也就能够通过与根结点之间的关系推断两个节点之间之间的关系了。

第一种情况，两个节点当前属于同一个集合中，证明这两个节点之前必定能产生某种关系。那么此时这句话就可能是假的。那么就套用对于并查集树中任意两节点关系的定义，我们不难得到两个条件语句中的条件。当然假话应当是怎么样的也显而易见。第一种情况结束。

第二种情况，如果两个节点当前不属于同一个集合中，证明两个节点之前没有任何关系，那这句话必定是真话。此时我们要做的就是更新两个节点之间的关系和距离数组的值。显然，我们首先需要将两个集合合并。这里不妨设合并的方式是将 $x$​​ 作为 $y$​​ 的子树。这时就需要从节点 $p_x$​​ 向节点 $p_y$​​ 增加一条边，$p_y$​​​ 作为新的根结点，并赋予距离值使得输入的关系成立。

设新增加的边的权值为 $i$​​ 。如果输入两个节点是同类，即 $y=x$​​，那么有 $d(x)+i-d(y)\equiv0(\text{mod }3)$​​ 成立，不妨设 $d(x)+i-d(y)=0$​​ ，解得 $d(p_x)=i=d(y)-d(x)$​​ ；如果输入的关系是 $y\to x$​​ ，那么有 $d(x)+i-d(y)\equiv1(\text{mod }3)$​ 成立，不妨设 $d(x)+i-d(y)=1$ ，解得 $d(p_x)=i=1+d(y)-d(x)$ 。需要说明的是，此处的 $d(k)$ 仍表示节点 $k$​ 到其父节点的距离。

本题结束。​

代码

C++

#include <iostream>
using namespace std;

const int N = 50010;

int p[N], d[N];
int res;

int find(int x) {
    if (p[x] != x) {
        int pa = find(p[x]);
        d[x] += d[p[x]];
        p[x] = pa;
    }
    return p[x];
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) p[i] = i;
    int att, x, y;
    while (k--) {
        scanf("%d%d%d", &att, &x, &y);
        if (x > n || y > n) res++;
        else if (att == 2 && x == y) res++;
        else {
            int px = find(x), py = find(y);
            if (px == py) {
                if (att == 1 && (d[x] - d[y]) % 3) res++;
                if (att == 2 && (d[x] - d[y] - 1) % 3) res++;
            }
            else {
                p[px] = py;
                if (att == 1) d[px] = d[y] - d[x];
                if (att == 2) d[px] = 1 + d[y] - d[x];
            }
        }
    }
    printf("%d", res);
    return 0;
}

Python

def find(x):
    if p[x] != x:
        pa = find(p[x])
        d[x] += d[p[x]]
        p[x] = pa
    return p[x]

if __name__ == '__main__':
    n, k = map(int, input().split())
    p = [i for i in range(n + 1)]
    d = [0] * (n + 1)
    res = 0
    for _ in range(k):
        att, x, y = map(int, input().split())
        if x > n or y > n:
            res += 1
        elif att == 2 and x == y:
            res += 1
        else:
            px = find(x); py = find(y)
            if px == py:
                if att == 1 and (d[x] - d[y]) % 3:
                    res += 1
                if att == 2 and (d[x] - d[y] - 1) % 3:
                    res += 1
            else:
                p[px] = py
                if att == 1:
                    d[px] = d[y] - d[x]
                if att == 2:
                    d[px] = 1 + d[y] - d[x]
    print(res)

参考

y总讲解视频

多重背包问题优化中至于为什么可以表示出所有的可能，注意这里是 “表示” 可以参考下面这个图，对于下一个组而言前面的所有可能都已经表示过了，只关注本组的选择与不选择，因为dp数组本身是集合的一个属性的表示，而优化过后的枚举过程实际上是符合数学表达的，所以拥有正确性。

比如：

当在选择是否选择两个物品的时候就包含了是否选择一个物品（的两种情况从而加在一起是4中情况），以此类推在选择是否选三个物品的时候就包含了前面所有的可能，从而表示了0~7这么多种可能性。

其中比较难以理解的地方在于，这种表示不是显示的表示（比如把每个数具体的表示出来），而是由于选择与不选择的性质决定的一种表示。朴素做法中最终dp数组的那个位置存的是最大值，我们只是以同样的方式进行代换，而选择的一个最大的值。在选择与不选择之间就表达了两种情况，在下一次选择与不选择的过程中就表达了四种情况，从可以指数的表达情况，时间复杂度则变为$O(lgN)$，而其原理就是二进制的每位的权重的组合来表达一个数