好久没上黑客说了......

话说，我发现帖子太容易沉了，建议在帖子有变动的时候（比如说评论）能把帖子顶上去

给个建议~

有人知道idea进入禅模式的快捷键吗

【求助】

---

##### 啥是滑动窗口

滑动窗口是基于双指针的一种思想，这类题通常是用单调双端队列辅助实现的。与单调栈类似，适用于适用于求子序列最值或目标值问题。在窗口滑动过程中，一侧作为出口，另一侧作为入口，就像队列出队入队一样，但时刻维护队列中的单调性。话不多说，上个例子就明白了。

---


##### 例题 剑指Offer 59 - I 滑动窗口的最大值

https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

**【题目描述】**

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

**示例:**

**输入:** nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

**输出**: [3,3,5,5,6,7]

![](https://content.hackertalk.net/pub/vXZwqx-eka0NKZ)


**提示：**

你可以假设 k 总是有效的，在输入数组 不为空 的情况下，1 ≤ k ≤ nums.length


**思路分析**

当使用暴力做法时，每次窗口弹出一个元素，又引进一个元素后，就需要对窗口内所有元素求一次最大值，每一次求最大值都需要O(n)的时间代价，所以整个暴力算法的时间复杂度为O(n²)。

在窗口内元素个数不足k个时，不作任何取最值操作，但因为所求是窗口最大值，因此辅助队列中的所有元素则需要时刻维持单调递减，当窗口内元素个数满足k个时，队列的对头即为当前窗口的最大值，求取最大值这一步骤的时间代价优化为了O(1)，极大地降低了暴力做法的时间复杂度，使整体的时间复杂度优化至接近线性。


**示例模拟**

当前nums = [1,3,-1,-3,5,3,6,7]，窗口大小为3

元素1进入后，当前窗口为[1]，当前队列为[1]

元素3进入后，当前窗口为[1, 3]，因需维持单调递减性，则队列弹出对头元素1，再将元素3入队，当前队列为[3]

元素-1进入后，当前窗口为[1, 3, -1]， 当前队列为[3, -1]，当前窗口内元素个数满足3个，则当前窗口的最大值即为队列的队头元素，即3，存入结果集。

元素-3进入后，当前窗口为[3, -1, -3]，当前队列为[3, -1, -3]，当前窗口内元素个数满足3个，则最大值为队头元素，即3，存入结果集。

......

直到遍历结束，将结果集返回。


**C++代码**

（STL中deque用法，在不开O2优化的前提下建议用数组模拟双端队列，效率更高）

```cpp
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> que;
        vector<int> ans;
        for(int i=0; i<nums.size(); i++)
        {
            if(!que.empty() && i-k+1 > que.front()) que.pop_front(); //新的来，旧的去 
            while(!que.empty() && nums[i] >= nums[que.back()]) que.pop_back(); //维持单调递减性
            que.push_back(i); //新的来
            if(i+1 >= k) ans.push_back(nums[que.front()]); //最大值即为队头，放入结果集
        }
        return ans;
    }
};
```


---

##### 实战 [NOIP2016 普及组] 海港

https://www.luogu.com.cn/problem/P2058

**题目描述**

小 K 是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。

小 K 对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第 i 艘到达的船，他记录了这艘船到达的时间 ti (单位：秒)，船上的乘客数 ki，以及每名乘客的国籍 xi,1, xi,2, ... , xi,k

小K统计了 n 艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的 24 小时（24小时 = 86400 秒）内所有乘船到达的乘客来自多少个不同的国家。

形式化地讲，你需要计算 n 条信息。对于输出的第 i 条信息，你需要统计满足 ti - 86400 < tp <= ti 的船只 p ，在所有的 xp,j 中，总共有多少个不同的数。


**输入格式**

第一行输入一个正整数 n，表示小 K 统计了 n 艘船的信息。

接下来 n 行，每行描述一艘船的信息：前两个整数 ti 和 ki 分别表示这艘船到达海港的时间和船上的乘客数量，接下来 ki 个整数 xi,j 表示船上乘客的国籍。

保证输入的 ti 是递增的，单位是秒；表示从小 K 第一次上班开始计时，这艘船在第 ti 秒到达海港。


**输出格式**

输出 n 行，第 i 行输出一个整数表示第 i 艘船到达后的统计信息。


**输入样例**

```
3
1 4 4 1 2 2
2 2 2 3
10 1 3
```


**输出样例**

```
3
4
4
```


**【样例解释 】**

第一艘船在第 1 秒到达海港，最近 24 小时到达的船是第一艘船，共有 4 个乘客，分别是来自国家 4,1,2,2 共来自 3 个不同的国家；

第二艘船在第 2 秒到达海港，最近 24 小时到达的船是第一艘船和第二艘船，共有 4 + 2 = 6 个乘客，分别是来自国家 4,1,2,2,2,3，共来自 4 个不同的国家；

第三艘船在第 10 秒到达海港，最近 24 小时到达的船是第一艘船、第二艘船和第三艘船，共有 4+2+1=7 个乘客，分别是来自国家 4,1,2,2,2,3,3，共来自 4 个不同的国家。


**数据范围**

1 ≤ n ≤ 105 

∑ki ≤ 3 ∗105 

1 ≤ xi,j ≤ 105 

1 ≤ ti ≤ 109


**思路分析**

根据题意，能够提炼出滑动窗口的模型，但具体实现上则需要确定窗口的元素对象。若是将船作为窗口内的元素，那么在滑动的过程中如何处理乘客的国籍信息呢？思来想去只能暴力求取，这么做的时间代价太大了。

若选择将乘客作为窗口内的元素，由于船只到达时间是单调递增的，因此到达时间可以作为乘客所乘船的标识，那么我们可以用一个二元组存储乘客的船只到达时间和国籍信息，利用哈希表筛选国籍信息。在窗口滑动过程中，利用24小时的时间条件作为窗口大小，将不满足时间条件的船只乘客弹出队列，同时哈希表去掉相应的国籍，而新满足条件的船只，将该船所有乘客入队，并加入哈希表更新国籍信息。哈希表大小代表当前国籍数量，输出即可。


**C++代码（STL中deque + 数组模拟哈希表）**

```cpp
#include<iostream>
#include<deque>
using namespace std;
​
const int N = 1e5 + 10;
​
typedef pair<int, int> PII; //第一个int存到达时间，第二个int存乘客国籍
​
int n, v[3*N], ans;
deque<PII> que;
​
int main()
{
    cin >> n;
    for(int i=0; i<n; i++)
    {
        int t, k;
        cin >> t >> k;
        while(!que.empty() && que.front().first <= t - 86400)
        {
            v[que.front().second] --;
            if(!v[que.front().second]) ans --;
            que.pop_front();
        }
        
        for(int j=0; j<k; j++)
        {
            int x;
            cin >> x;
            if(!v[x]) ans ++;
            v[x] ++;
            que.push_back({t, x});
        }
        
        cout << ans << endl;
    }
    
    return 0;
}
```

---

你学fei了吗？

**（转载请注明出处，侵权必究）**



【基础算法】滑动窗口！

黑客说的搜索功能好像不能用呐


##### 1.什么是单调栈

单调栈是一种简单数据结构，顾名思义，就是单调递增（或递减）的栈。

---

##### 2.单调有什么用？

单调意味着数据是有序的，数据变化是没有“回头路”的，一路走到底，此外，最重要的特性之一就是能够快速地找到最大值或者最小值。

【单调递增性函数图】

![](https://content.hackertalk.net/pub/YDOvOV-NegE3Nk)

【单调递增栈】

![](https://content.hackertalk.net/pub/5OVxmk-1mmx5r7)


---

##### 3.应用场景

最经典的案例就是运用单调栈在一个序列中求每个元素左边（或右边）第一个比它小（或大）的元素，其实就是求在单调栈中的最值，在遍历过程中时刻维护栈的单调性，那么每个元素对应栈中的最值就是答案。

具体实现可以使用数组模拟栈或者调用库函数（如C++的STL）

---

##### 4.举个例子

**【题目描述】**

给出项数为n的整数数列 a1，a2，a3，... ，an。

定义函数 f(i) 代表数列中第i个元素之后第一个大于ai的元素的**下标**，若不存在，则 f(i)=0。

试求出f(1,2,3,...n)。

**【输入格式】**

第一行一个正整数n

第二行n个正整数a1,a2,...,an

**【输出格式】**

一行n个整数f(1,2,...,n)的值。

**【输入样例】**

```
5
1 4 2 3 5
```

**【输出样例】**

```
2 5 4 5 0
```

**【数据范围】**

1≤n≤3e6, 1≤ai≤1e9


**思路**：简单来说就是求每一个元素右边第一个比它大的元素下标，符合单调栈的应用场景。由于是求右边的元素下标，因此首先我们需要从右往左遍历，求比它大的元素且从右向左遍历，因此栈中应该保持单调递减性，使用单调递减栈。

**样例分析：**

【第1步】下标为5的元素是5，栈为空，没有比它大的元素，依题意输出0即可，再将下标5放入栈中（注意下标从1开始）

【第2步】下标为4的元素是3，小于栈顶元素5，满足单调递减性，不需要弹出栈顶，将栈顶下标5放入结果集，再将下标4放入栈中

【第3步】下标为3的元素是2，小于栈顶元素3，满足单调递减性，不需要弹出栈顶，将栈顶下标4放入结果集，再将下标3放入栈中

【第4步】下标为2的元素是4，大于栈顶元素2，不满足单调递减性，弹出栈顶后继续判断，此时栈顶元素为3，仍然不满足单调递减性，因此继续弹出栈顶，新的栈顶元素为5，大于4，（终于）满足单调递减性，不需要弹出栈顶，直接将栈顶下标5放入结果集，再将当前的下标2放入栈中

【第5步】下标为1的元素是1，小于栈顶元素4，满足单调递减性，不需要弹出栈顶，将栈顶下标2放入结果集，再将下标1放入栈中

【第6步】遍历结束，输出结果集


**C++代码实现**

```cpp
#include<iostream>
using namespace std;
​
const int N = 3e6 + 10;
​
// n为序列长度，sta[]为模拟栈，tt为栈顶指针，a[]为输入序列，res[]存放结果集
int n, sta[N], a[N], tt, res[N];
​
int main()
{
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i]; //输入序列
    
    for(int i=n; i>=1; i--) //从右往左遍历
    {
        while(tt && a[i] >= a[sta[tt]]) tt --; //栈不能为空的情况下不满足单调性就弹出栈顶
        if(tt) res[i] = sta[tt]; //栈不为空的情况下，将当前栈顶放入结果集
        else res[i] = 0; //若栈为空，说明不存在比当前元素大的元素，依题意将0放入结果集
        sta[++ tt] = i; //动态地将当前元素存入栈中
    }
    
    //可以发现，整个过程都在维护栈的单调性
    
    for(int i=1; i<=n; i++) cout << res[i] << " "; //输出结果，大功告成
    cout << endl;
    
    return 0;
}
```


---


##### 5.实战 直方图中最大的矩形

来源：《算法竞赛进阶指南》

**【题目描述】**

直方图是由在公共基线处对齐的一系列矩形组成的多边形。

矩形具有相等的宽度，但可以具有不同的高度。

例如，图例左侧显示了由高度为 2,1,4,5,1,3,3 的矩形组成的直方图，矩形的宽度都为 1:

![](https://content.hackertalk.net/pub/6dre2v-e3z0mzV)

通常，直方图用于表示离散分布，例如，文本中字符的频率。

现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。

图例右图显示了所描绘直方图的最大对齐矩形。

**【输入格式】**

输入包含几个测试用例。

每个测试用例占据一行，用以描述一个直方图，并以整数 nn 开始，表示组成直方图的矩形数目。

然后跟随 n 个整数 h1，... ,hn。

这些数字以从左到右的顺序表示直方图的各个矩形的高度。

每个矩形的宽度为 1。

同行数字用空格隔开。

当输入用例为 n=0 时，结束输入，且该用例不用考虑。

**【输出格式】**

对于每一个测试用例，输出一个整数，代表指定直方图中最大矩形的区域面积。

每个数据占一行。

请注意，此矩形必须在公共基线处对齐。

**【输入样例】**

```
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
```

**【输出样例】**

```
8
4000
```

**【数据范围】**

1≤n≤1000001≤n≤100000, 0≤hi≤1000000000


**思路分析**：首先观察直方图很容易发现，每个x坐标对应的矩形条高度就是最大矩形的极限高度，而极限宽度则取决于左边能够延伸到哪里，右边能延伸到哪里。在高度能够确定的情况下，求面积只需要确定最大宽度，而求最值可以使用单调栈的思想。令每个矩形条向左延伸，直至碰到第一个比它矮的矩形条，将其坐标存入左极限集；向右延伸，直至碰到第一个比它矮的矩形条，将其坐标存入右极限集。最后遍历x轴的每个矩形条，求出每个矩形条对应的面积：高度*（右极限-左极限-1），取最大即可。

**C++代码实现**

```abap
#include<iostream>
#include<algorithm>
using namespace std;
​
typedef long long LL;
​
const int N = 1e5 + 10;
​
int n, h[N], l[N], r[N], sta[N]; //l[]为左极限集，r[]为右极限集, sta[]为模拟栈
​
int main()
{
    while(cin >> n, n)
    {
        h[0] = h[n+1] = -1;
        for(int i=1; i<=n; i++) cin >> h[i];
        
        int tt = 0;
        sta[0] = 0;
        for(int i=1; i<=n; i++) //从左往右遍历，求每个x的左极限
        {
            while(h[i] <= h[sta[tt]]) tt --;
            l[i] = sta[tt];
            sta[++ tt] = i;
        }
        
        tt = 0;
        sta[0] = n + 1;
        for(int i=n; i; i--) //从右往左遍历，求每个x的右极限
        {
            while(h[i] <= h[sta[tt]]) tt --;
            r[i] = sta[tt];
            sta[++ tt] = i;
        }
        
        LL res = 0;
        for(int i=1; i<=n; i++)
            res = max(res, (LL)h[i] * (r[i] - l[i] - 1)); //矩形面积公式
        
        cout << res << endl;
    }
    
    return 0;
}
```


---

这里有道力扣的面试题，跟上面的实战题类似，没想到在力扣里的难度是困难题，在竞赛里其实只是一道简单题= =

[链接点这里](https://leetcode.cn/problems/0ynMMM/)

---

##### 6.最后的话

上面的C++代码实现中的数组模拟栈可以换成库函数中的栈，思路是一样的。

你学fei了吗？

---

**（转载请注明出处，侵权必究）**



【基础算法】单调栈的妙用


##### 1.什么是并查集

并查集是一种基于树的数据结构，它对集合能够高效地实现以下操作：

（1）合并两个不同的集合

（2）询问两个元素是否在同一个集合内

（3）维护额外的信息，如权值，结点到祖宗节点的距离，集合中点的数量等。


##### 2.基本原理

每个集合用一棵树来表示，根节点的编号作为整个集合的编号，每个节点则存储其父节点的编号。

![](https://content.hackertalk.net/pub/e38V72-xGBvkyV)


##### 3.基本操作

设节点x，则父节点则为fa[x]，初始化时令所有x的父节点均为自己。

（1）判断树根：只有根节点的父节点是自己，因此只需要判断节点父节点是否等于本身，即

```cpp
if(x == fa[x])
{
    //操作
}
```


（2）求节点所在树的根节点（即求该集合的编号）：父节点不是自己就把自己更新成爹再去找

```cpp
if(x != fa[x])
{
    x = fa[x];
}
```


（3）合并两个集合：任意将其中一个集合的根节点赋值给另一个根节点的父节点即可完成合并操作

【合并前】

![](https://content.hackertalk.net/pub/JOo8me-0e0K04q)

【合并后】

![](https://content.hackertalk.net/pub/3wgzXQ-6NlPnZp)

```c++
//x，y分别是两个集合的根节点
fa[x] = y;
```


##### 4.优化：路径压缩法

每个节点在寻找根节点的过程，都可能要经历多次迭代更新才能找到根节点，当树的高度足够大时，寻找根节点的迭代过程的时间代价较高，因此我们可以用降低树的高度的方式间接减少时间代价。

具体操作是，最终寻找到根节点后，将路径上所有节点直接与根节点相连，即搜索路径上的所有节点的父节点均直接全部变为根节点。

【迭代过程】

![](https://content.hackertalk.net/pub/VpNQ6n-pyPQwNO)

【完成优化】

![](https://content.hackertalk.net/pub/a8J3VK-7dQ3lpy)




##### 5.核心代码实现

递归寻找根节点，找到后返回根节点并赋值给路径上所有节点作为父节点

```cpp
//求某节点的根节点+路径压缩
int find(int x)
{
    if(x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
```


##### 6.例题1 集合的合并与查询

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。

接下来 M 行，每行包含三个整数 Z_i,X_i,Y_i 。

当 Z_i=1 时，将 X_i 与 Y_i 所在的集合合并。

当 Z_i=2 时，输出 X_i 与 Y_i 是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

对于每一个 Z_i=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

样例 #1

样例输入 #1

```
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
```

样例输出 #1

```
N
Y
N
Y
```

提示

对于 30\% 的数据，N \le 10，M \le 20。

对于 70\% 的数据，N \le 100，M \le 10^3。

对于 100\% 的数据，1\le N \le 10^4，1\le M \le 2\times 10^5，1 \le X_i, Y_i \le N，Z_i \in \{ 1, 2 \}。


思路分析：简单合并和查询操作，不细说。

C++代码:

```cpp
#include<iostream>
using namespace std;
​
const int N = 1e4 + 10;
​
int n, m, fa[N];
​
int find(int x)
{
    if(x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
​
int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) fa[i] = i;
    
    while(m --)
    {
        int z, x, y;
        cin >> z >> x >> y;
        
        if(z == 1) fa[find(x)] = find(y);
        else
        {
            if(find(x) == find(y)) puts("Y");
            else puts("N");
        }
    }
    
    return 0;
}
```



##### 7.例题2 连通块中点的数量

题目描述

给定一个包含 nn 个点（编号为 1∼n1∼n）的无向图，初始时图中没有边。

现在要进行 mm 个操作，操作共有三种：

1. C a b，在点 aa 和点 bb 之间连一条边，aa 和 bb 可能相等；
2. Q1 a b，询问点 aa 和点 bb 是否在同一个连通块中，aa 和 bb 可能相等；
3. Q2 a，询问点 aa 所在连通块中点的数量；

输入格式

第一行输入整数 nn 和 mm。

接下来 mm 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。 Y ；否则输出 N 。

输出格式

第一行输入整数 nn 和 mm。

接下来 mm 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

样例 #1

样例输入 #1

```
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
```

样例输出 #1

```
Yes
2
3
```

数据范围

1 ≤ n,m ≤ 105


思路分析：设s[N]，给每个节点设置节点总数，但只有根节点的节点总数是有意义的，合并时更新根节点的节点总数即可。

C++代码：

```cpp
#include<iostream>
using namespace std;
​
const int N = 1e5 + 10;
​
int fa[N], s[N], n, m;
​
int find(int x)
{
    if(x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
​
int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        fa[i] = i;
        s[i] = 1;
    }
    
    while(m --)
    {
        string op;
        cin >> op;
        if(op == "C")
        {
            int x, y;
            cin >> x >> y;
            if(find(x) != find(y)) s[find(y)] += s[find(x)];
            fa[find(x)] = find(y);
        }
        else if(op == "Q1")
        {
            int x, y;
            cin >> x >> y;
            if(find(x) == find(y)) puts("Yes");
            else puts("No");
        }
        else
        {
            int x;
            cin >> x;
            cout << s[find(x)] << endl;
        }
    }
    
    return 0;
}
```



##### 8.实战1 朋友圈

（来源：集美大学第十三届蓝桥校选拔赛第三题）

题目描述

1. 某学校有n个学生，形成m个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如果A和B是朋友，且B和C是朋友，则A和C也是朋友。

   现在学校有重要消息要通知，把消息通知给某个人需要花费代价c，但朋友之间传递是不需要代价的，可以看成花费代价为0，并且当某个人知道这个消息后，就会把消息立即告诉他的朋友。

   请你计算把这个消息通知给所有人需要至少花费多少代价。

输入格式

第一行，包含两个整数n，m

第二行，包含n个整数，依次为c1,c2,....,c**n，表示通知消息给某个人所需要的花费

后面的m行每行按以下格式给出1个俱乐部的信息，其中学生从1−n编号：

第i个俱乐部的人数m**i（空格）学生1（空格）学生2…学生m**i

输出格式

输出一个整数，表示把消息通知给所有人至少花费多少代价

样例 #1

样例输入 #1

```
7 4
2 3 4 5 6 7 4
3 1 2 3
2 1 4
3 5 6 7
1 6
```

样例输出 #1

```
6
```

数据范围

对于50%的测试点，1≤n≤1000，1≤m≤30，1≤c**i≤1000

对于100%的测试点，1≤n≤30000，1≤m≤1000，1≤c**i≤1000


思路分析：将每个俱乐部输入的第一位同学作为根节点，再将该俱乐部的其他同学合并到同一集合，最后遍历所有集合即可。

C++代码：

```cpp
#include<iostream>
#include<unordered_map>
using namespace std;
​
const int N = 30010;
​
int n, m, fa[N], c[N], ans[N];
​
int find(int x)
{
    if(fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}
​
int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        cin >> c[i];
        fa[i] = i;
    }
    
    while(m --)
    {
        int num, head;
        cin >> num >> head;
        for(int i=1; i<num; i++)
        {
            int stu;
            cin >> stu;
            fa[find(stu)] = find(head);
        }
    }
    
    int res = 0;
    
    for(int i=1; i<=n; i++)
    {
        int stu = find(i);
        if(ans[stu]) ans[stu] = min(ans[stu], c[i]);
        else ans[stu] = c[i];
    }
    
    for(int i=1; i<=n; i++) res += ans[i];
    
    cout << res << endl;
    
    return 0;
}
```



##### 9.实战2 食物链

（来源：洛谷P2024[NOI2001]）

题目描述

1. 动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。

   现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。

   有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
   * 第一种说法是 1 X Y，表示 X 和 Y 是同类。
   * 第二种说法是2 X Y，表示 X 吃 Y 。

   此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
   * 当前的话与前面的某些真的话冲突，就是假话
   * 当前的话中 X 或 Y 比 N 大，就是假话
   * 当前的话表示 X 吃 X，就是假话

   你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入格式

第一行两个整数，N，K，表示有 N 个动物，K 句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式

一行，一个整数，表示假话的总数。

样例 #1

样例输入 #1

```
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
```

样例输出 #1

```
3
```

数据范围

对于50%的测试点，1≤n≤1000，1≤m≤30，1≤c**i≤1000

对于100%的测试点，1≤n≤30000，1≤m≤1000，1≤c**i≤1000


思路分析：将所有动物存入并查集中，每个节点存放该节点到根节点的距离。假定A吃B，B吃C，C吃A，因此在并查集中，可以设，到根节点的距离余1的点吃根节点，到根节点的距离余2的点被根节点吃，而余0的则是根节点的同类，那么在并查集这棵树上，所有关系就显而易见了。

C++代码：

```cpp
#include<iostream>
using namespace std;
​
const int N = 1e5 + 10;
​
int n, k, fa[N], d[N];
​
int find(int x)
{
    if(x != fa[x])
    {
        int t = find(fa[x]);
        d[x] += d[fa[x]];
        fa[x] = t;
    }
    return fa[x];
}
​
int main()
{
    cin >> n >> k;
    for(int i=1; i<=n; i++) fa[i] = i;
    
    int res = 0;
    while(k --)
    {
        int op, x, y;
        cin >> op >> x >> y;
        
        if(x > n || y > n) res ++;
        else
        {
            int fx = find(x), fy = find(y);
            
            if(op == 1)
            {
                if(fx == fy && (d[x] - d[y]) % 3) res ++;
                else if(fx != fy)
                {
                    fa[fx] = fy;
                    d[fx] = d[y] - d[x];
                }
            }
            
            else if(op == 2)
            {
                if(fx == fy && (d[x] - d[y] - 1) % 3) res ++;
                else if(fx != fy)
                {
                    fa[fx] = fy;
                    d[fx] = d[y] + 1 - d[x];
                }
            }
        }
    }
    
    cout << res << endl;
    return 0;
}
```


你学fei了吗？ :yum: 

【基础算法】彻底搞懂并查集

lowbit作用：快速找到一个数中二进制的最后一个1以及后面所有0的组合


lowbit核心：一个数的原码 & 补码（即该数的负数）


举个例子：

```
原码 = 101010101000000
补码 = 010101011000000 
原码&补码 = 000000001000000 = 1000000
```


算法应用例题：

求二进制中1的个数

```
#include<iostream>
using namespace std;

int lowbit(int n)
{
    return n & (-n);
}

int main()
{
    int n, res = 0;
    cin >> n;

    while(n)
    {
        n -= lowbit(n); //每次减掉最后一个1及其后面所有0的部分
        res++;
    }

    cout << res << endl;
    return 0;
}
```



【基础算法】位运算之lowbit操作

前些天一直在找便宜的云服务器，偶然间发现一免费的云平台，这里推荐给大家。

就是阿贝云，网站是https://www.abeiyun.com

说一下感受

1、阿贝云虽然是一小众的云平台，重在免费，该有的东西都有，还能免备案这是最舒服的。

2、使用了一天，上了项目，网速不慢。

3、唯一要指出来就是磁盘太小。

分享免费云服务器

拉取了rustbuster的v3.0.3版本文件, 二进制文件无法使用, 执行结果如下:

```bash
[root_cn@archlinux target]$ ./rustbuster-v3.0.3-x86_64-unknown-linux-gnu
./rustbuster-v3.0.3-x86_64-unknown-linux-gnu: error while loading shared libraries: libssl.so.1.1: cannot open shared object file: No such file or directory
```

拉取了main源码, 想自行尝试编译, 然后卡在了openssl, 以下为报错信息:

```rust
The following warnings were emitted during compilation:

warning: openssl-sys@0.9.47: build/expando.c:4:24: error: pasting "RUST_VERSION_OPENSSL_" and "(" does not give a valid preprocessing token
warning: openssl-sys@0.9.47:     4 | #define VERSION2(n, v) RUST_VERSION_##n##_##v
warning: openssl-sys@0.9.47:       |                        ^~~~~~~~~~~~~
warning: openssl-sys@0.9.47: build/expando.c:5:23: note: in expansion of macro ‘VERSION2’
warning: openssl-sys@0.9.47:     5 | #define VERSION(n, v) VERSION2(n, v)
warning: openssl-sys@0.9.47:       |                       ^~~~~~~~
warning: openssl-sys@0.9.47: build/expando.c:10:1: note: in expansion of macro ‘VERSION’
warning: openssl-sys@0.9.47:    10 | VERSION(OPENSSL, OPENSSL_VERSION_NUMBER)
warning: openssl-sys@0.9.47:       | ^~~~~~~

error: failed to run custom build command for `openssl-sys v0.9.47`

Caused by:
  process didn't exit successfully: `/mnt/d/work/file/rust/rustbuster/target/debug/build/openssl-sys-c5a482a9e0e49574/build-script-main` (exit status: 101)
  --- stdout
  cargo:rustc-cfg=const_fn
  cargo:rerun-if-env-changed=X86_64_UNKNOWN_LINUX_GNU_OPENSSL_LIB_DIR
  X86_64_UNKNOWN_LINUX_GNU_OPENSSL_LIB_DIR unset
  cargo:rerun-if-env-changed=OPENSSL_LIB_DIR
  OPENSSL_LIB_DIR unset
  cargo:rerun-if-env-changed=X86_64_UNKNOWN_LINUX_GNU_OPENSSL_INCLUDE_DIR
  X86_64_UNKNOWN_LINUX_GNU_OPENSSL_INCLUDE_DIR unset
  cargo:rerun-if-env-changed=OPENSSL_INCLUDE_DIR
  OPENSSL_INCLUDE_DIR unset
  cargo:rerun-if-env-changed=X86_64_UNKNOWN_LINUX_GNU_OPENSSL_DIR
  X86_64_UNKNOWN_LINUX_GNU_OPENSSL_DIR unset
  cargo:rerun-if-env-changed=OPENSSL_DIR
  OPENSSL_DIR unset
  cargo:rustc-link-lib=ssl
  cargo:rustc-link-lib=crypto
  OPT_LEVEL = Some("0")
  TARGET = Some("x86_64-unknown-linux-gnu")
  HOST = Some("x86_64-unknown-linux-gnu")
  CC_x86_64-unknown-linux-gnu = None
  CC_x86_64_unknown_linux_gnu = None
  HOST_CC = None
  CC = None
  CFLAGS_x86_64-unknown-linux-gnu = None
  CFLAGS_x86_64_unknown_linux_gnu = None
  HOST_CFLAGS = None
  CFLAGS = None
  CRATE_CC_NO_DEFAULTS = None
  DEBUG = Some("true")
  CARGO_CFG_TARGET_FEATURE = Some("fxsr,sse,sse2")
  running: "cc" "-O0" "-ffunction-sections" "-fdata-sections" "-fPIC" "-g" "-fno-omit-frame-pointer" "-m64" "-Wall" "-Wextra" "-E" "build/expando.c"
  cargo:warning=build/expando.c:4:24: error: pasting "RUST_VERSION_OPENSSL_" and "(" does not give a valid preprocessing token
  cargo:warning=    4 | #define VERSION2(n, v) RUST_VERSION_##n##_##v
  cargo:warning=      |                        ^~~~~~~~~~~~~
  cargo:warning=build/expando.c:5:23: note: in expansion of macro ‘VERSION2’
  cargo:warning=    5 | #define VERSION(n, v) VERSION2(n, v)
  cargo:warning=      |                       ^~~~~~~~
  cargo:warning=build/expando.c:10:1: note: in expansion of macro ‘VERSION’
  cargo:warning=   10 | VERSION(OPENSSL, OPENSSL_VERSION_NUMBER)
  cargo:warning=      | ^~~~~~~
  exit status: 1

  --- stderr
  thread 'main' panicked at /home/root_cn/.cargo/registry/src/mirrors.sjtug.sjtu.edu.cn-4f7dbcce21e258a2/openssl-sys-0.9.47/build/main.rs:126:13:

  Header expansion error:
  Error { kind: ToolExecError, message: "Command \"cc\" \"-O0\" \"-ffunction-sections\" \"-fdata-sections\" \"-fPIC\" \"-g\" \"-fno-omit-frame-pointer\" \"-m64\" \"-Wall\" \"-Wextra\" \"-E\" \"build/expando.c\" with args \"cc\" did not execute successfully (status code exit status: 1)." }

  Failed to find OpenSSL development headers.

  You can try fixing this setting the `OPENSSL_DIR` environment variable
  pointing to your OpenSSL installation or installing OpenSSL headers package
  specific to your distribution:

      # On Ubuntu
      sudo apt-get install libssl-dev
      # On Arch Linux
      sudo pacman -S openssl
      # On Fedora
      sudo dnf install openssl-devel

  See rust-openssl README for more information:

      https://github.com/sfackler/rust-openssl#linux

  note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
warning: build failed, waiting for other jobs to finish...
```

经过检查openssl与rust均为最新版本, 

```bash
[root_cn@archlinux target]$ sudo pacman -S rust
[sudo] password for root_cn:
warning: rust-1:1.77.2-1 is up to date -- reinstalling
resolving dependencies...
looking for conflicting packages...

Package (1)  Old Version  New Version  Net Change

extra/rust   1:1.77.2-1   1:1.77.2-1     0.00 MiB

Total Installed Size:  249.41 MiB
Net Upgrade Size:        0.00 MiB

:: Proceed with installation? [Y/n] n
[root_cn@archlinux target]$ sudo pacman -S openssl
warning: openssl-3.2.1-1 is up to date -- reinstalling
resolving dependencies...
looking for conflicting packages...

Package (1)   Old Version  New Version  Net Change

core/openssl  3.2.1-1      3.2.1-1        0.00 MiB

Total Installed Size:  11.45 MiB
Net Upgrade Size:       0.00 MiB

:: Proceed with installation? [Y/n] n
```

在网上找了一下, 查到资料, 在[rust-openssl的issues](https://github.com/sfackler/rust-openssl/issues/1227)中提到类似报错, 得到解释如下:

> If you are cross compiling to MUSL, you either need to point openssl-sys to the location that you have a copy of OpenSSL cross compiled to MUSL, or tell it to build a copy of OpenSSL itself with the vendored feature.
>
>	如果你是交叉编译到MUSL，你需要将openssl-sys指向你有一个交叉编译到MUSL的OpenSSL副本的位置，或者告诉它用vendored特性构建一个OpenSSL本身的副本。

由于不会rust, 依靠关键词"交叉编译"+"cargo"搜索到了[cargo交叉编译rust程序](https://blog.csdn.net/tyc880616/article/details/104371502), 顺着找到文件:

```
[root_cn@archlinux .cargo]$ cat ~/.cargo/config
[source.crates-io]
replace-with = 'sjtu' # 指定使用下面哪个源，修改为source.后面的内容即可

# 中国科学技术大学
[source.ustc]
registry = "https://mirrors.ustc.edu.cn/crates.io-index"

# 上海交通大学
[source.sjtu]
registry = "https://mirrors.sjtug.sjtu.edu.cn/git/crates.io-index/"

# 清华大学
[source.tuna]
registry = "https://mirrors.tuna.tsinghua.edu.cn/git/crates.io-index.git"

# rustcc社区
[source.rustcc]
registry = "https://code.aliyun.com/rustcc/crates.io-index.git"
```

没有找到交叉编译的设置, 由于本人不会rust, 线索断了, 尝试向大家寻求一波帮助, 非常感谢阅读.



急切寻求rust编译问题帮助(archlinux, openssl)

永久免费，无需注册

[https://good.xjai.top](https://good.xjai.top)

分享免费GPT4站点

[MoienTajik/AspNetCore-Developer-Roadmap (github.com)](https://github.com/MoienTajik/AspNetCore-Developer-Roadmap/blob/master/ReadMe.zh-Hant.md)

![](https://github.com/MoienTajik/AspNetCore-Developer-Roadmap/raw/master/aspnetcore-developer-roadmap.zh-Hant.png)



【轉貼】ASP.NET Core Developer Roadmap in 2024

南京大学数字金融 - 新华报业集团联合诚邀全职博士后！

【研究方向涵盖】

数智传播、数智金融经济、数据金融经济、数智政务、数智监管治理，以及“大数据、大模型、大计算”全新范式等方向理论与实践

 【具体研究领域】

包括 Bigdata4SocialScience、AI4SocialScience、LLM4SocialScience、Blockchain4SocialScience，以及先进信息技术融合创新在数智金融经济、数智传播社会、数智健康医疗、数智政务治理中的应用。

【薪资待遇优渥】

年薪可达 30 万人民币左右，另有绩效奖金及江苏省和南京市人才补贴。具体薪资需与HR面议，总收入依据专业背景和技能经验而定（计算机 AI 背景者薪资更优）。

【欢迎学科交叉、专业背景不限】

不限制专业背景，致力于构建一个多元、开放、包容的科研环境，因此，欢迎计算机、软件、大数据、人工智能、区块链、隐私计算、数据安全、数据科学等背景的博士人才，也热切邀请具有人文社科背景的博士加入我们的团队，共同探索信息技术与社会科学的交叉前沿。也欢迎其他编程能力强的理工科博士毕业生（即使没有AI等背景也欢迎）。

【南京大学研究中心】

南京大学研究中心为双院士领军的校级科研和创新平台，详情请见：fintech.nju.edu.cn。

【团队氛围】

学科交叉、理论与实践相结合、国际化视野、行业前沿视角和项目。

【联系我们】

请感兴趣的朋友将个人简历发送至邮箱:blockchainfintech@126.com。

【更多招募】 南京大学研究中心招收硕士生、博士生、博士后、青年教师、研究员，也欢迎访问、客座、联培以及科研助理（有些岗位可兼职或远程合作）等

欢迎加入我们，您将在这个富有挑战性和机遇的环境中，开启广阔的职业发展道路，实现个人价值与学术梦想的双赢！

期待您的加入，携手共创数智未来！

南京大学研究中心诚募博士后



![](https://image.hackertalk.net/images/62537abc-405f-44da-a67e-9f18082f3d74)















sqlmap -u "xxxxx.com/#/login" --all  --delay 1 --batch --random-agent

[CRITICAL]can't establish SSL connection.

![](https://image.hackertalk.net/images/4a856cac-750c-4972-aa1f-4bf02f000394)

sqlmap -r win.txt --dbs

**

[CRITICAL] anti-CSRF token 'XSRF-TOKEN' can't be found 


**


