题目来源：Atcoder-abc278; Atcoder-abc277;

题目考点：

AT-17 FF

Problem Statement

题目解析

pair+set维护，不属于并查集，并查集不可取（因为关系不相通）

顺带提一句，emplace()和insert()相似，前者直接构造，比后者复制构造速度要快。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef pair<int,int> p;
set<p> se;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int t,x,y;cin>>t>>x>>y;
        switch(t)
        {
            case 1:
            se.insert(p(x,y));
            break;
            case 2:
            se.erase(p(x,y));
            break;
            case 3:
            if(se.find(p(x,y))!=se.end()&&se.find(p(y,x))!=se.end())cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
            break;
        }

    }
    system("pause");
    return 0;

}

AT-18 All Assign Point Add

Problem Statement

题目解析

这个题比较二的是case1的全范围区间重赋值。时间复杂度会被卡点。

这个题理论上可以使用树状数组+差分维护，但是一样躲不开

考试的时候想的解决办法是通过set维护版本号，每一次case1视作一次版本维护，set清空，如果set中查询不到这个目标操作点就是版本未更新的点，在当前版本号（case1输入的x）上操作后置入数组，set加入该点表示已经更新。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, q;
int betaversion = 0;
int a[200001];
set<int> s;
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], s.insert(i);
    cin >> q;
    while (q--)
    {
        int t, i, x;
        cin >> t;
        switch (t)
        {
        case 1:
            cin >> x;
            s.clear();
            betaversion = x;
            break;
        case 2:
            cin >> i >> x;
            if (s.find(i) != s.end())
            {
                a[i] += x;
            }
            else
            {
                a[i] = betaversion + x;
                s.insert(i);
            }
            break;
        case 3:
            cin >> i;
            if (s.find(i) == s.end())
            {
                a[i] = betaversion;
                s.insert(i);
            }
            cout << a[i] << endl;
        }
    }
    system("pause");
    return 0;
}

交了7发整个人都不好了……

研究题解发现题解也是采用的版本号想法，但是他是基于对上一版本曾经操作过的所有点置0，本次的左右操作全部记录在版本操作记录中，当切换版本的时候一个一个pop_back并且对应清0，同样是可以的。只不过我的想法是版本更新后再修改数组，题解是版本更新前就全部完成对应的重置。

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    using namespace std;
    
    unsigned N;
    cin >> N;

    // manage the sequence by the delta from `base`
    vector<unsigned long> A(N);
    unsigned base{};//很奇妙的赋值方法，这个是0

    for (auto &&a : A)cin >> a;//更加奇妙的auto关键字
    A.emplace(begin(A));//更加奇妙了

    // the positions that the deltas might be non-zero
    // initially, it contains all of 1, ..., N
    vector<unsigned> added_index(N);//当前版本所有对点操作记录
    iota(begin(added_index), end(added_index), 1U);//iota递增赋值函数，本题对其赋为1，2，3，4，5，表示初始化也是对应的第0版本操作记录
    unsigned Q;
    cin >> Q;

    for (unsigned _{}; _ < Q; ++_)//某种意义的极简写法
     {
        unsigned type;
        cin >> type;
        if (type == 1) {
            // Erase non-zero delta
            while (!empty(added_index)) //C++20函数，改成!added_index.empty()
            {
                A[added_index.back()] = 0;//上代版本对应操作清空
                added_index.pop_back();//版本记录清除
            }
            cin >> base;
        } else if (type == 2) {
            // Add to the index-th delta
            unsigned index, value;
            cin >> index >> value;
            A[index] += value;
            added_index.emplace_back(index);
        } else {
            // Find the sum of `base` and the index-th delta
            unsigned index;
            cin >> index;
            cout << base + A[index] << endl;
        }
    }
    return 0;
}

AT-19 Ladder Takahashi

Problem Statement

题目解析

划重点：离散化+bfs会超时，按照图论做不能离散化，会被卡点。

先说离散化的问题

上回写得很仓促没有暴露一个问题，就是去重后的长度性质相当于s.size(),针对vector行为的时候不需要进行加1操作：

对于数组而言，就需要加1了（从1开始的话，就理解为平移偏量）

离散化板子：

sort(S.begin(), S.end());
    int l = unique(S.begin(), S.end()) - S.begin();
    for (int i = 1; i <= n; i++)
    {
        mp[a[i]] = lower_bound(S.begin(), S.begin() + l, a[i]) - S.begin() + 1;
    }

这个题离散化会超时是因为循环的时间太长了，离散化完后需要再重复一遍建图再跑一遍的广搜，虽然也是但是常数太大了，最后就差200ms卡了一个Hack数据

这个题因为是梯子连通的区域问最高可以到达哪里，梯子连接的楼层可以乱窜，具有传递连通性，所以可以并查集维护，低的楼层向高楼层合并，查询1可以到哪里，然后对照离散表找回原来的点。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<int> S;
int a[200001], b[200001];
map<int, int> mp;
int father[2000001];
void init()
{
    for (int i = 1; i <= 2000001; i++)
        father[i] = i;
}
int getfather(int x)
{
    if (x != father[x])
        return father[x] = getfather(father[x]);
    return father[x];
}
void reset(int x, int y)
{
    x = getfather(x), y = getfather(y);
    if (x != y)
    {
        father[x] > father[y] ? father[y] = father[x] : father[x] = father[y];
    }
}
signed main()
{
    cin >> n;
    init();
    S.push_back(1);
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i], S.push_back(a[i]), S.push_back(b[i]);
    sort(S.begin(), S.end());
    int l = unique(S.begin(), S.end()) - S.begin();
    for (int i = 1; i <= n; i++)
    {
        mp[a[i]] = lower_bound(S.begin(), S.begin() + l, a[i]) - S.begin() + 1;
        mp[b[i]] = lower_bound(S.begin(), S.begin() + l, b[i]) - S.begin() + 1;
        reset(mp[a[i]], mp[b[i]]);
    }
    int ans = getfather(1);
    cout << S[ans - 1] << endl;
    system("pause");
    return 0;
}

但是看答案直接震碎了我的三观：非常干脆的纯广搜。确实，事实上这个题第一眼想到的就应该是广搜：

#include <iostream>
#include <queue>
#include <map>
#include <set>
using namespace std;
int main() {
    int n;
    cin >> n;
    map<int, vector<int>> graph;//这个map就真的很灵性，直接解决了vector太大开爆的情况。
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    queue<int> que;
    que.push(1);
    set<int> S;//set来做visit数组，确实是个新思路
    S.insert(1);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (int i : graph[v]) //auto简写机制真的太可怕了
        {
            if (!S.count(i)) //查询i在S中是否出现，multiset返回的是出现的次数
            {
                que.push(i);
                S.insert(i);
            }
        }
    }
    cout << *S.rbegin() << '\n';
}

AT-20 Takahashi's Solitaire

Problem Statement

题目解析

首先一开始看错题没注意到所有的全小于数，然后就多考虑了许多

题目情况下直接暴力搜连续区间数就可以，只有在结尾的时候会出现对于m-1的特判以及连续处理

但是一旦没有了所有的全小于数，就会复杂很多，和的特判会很麻烦，区间暴力搜就状态过于复杂了，不好书写。

本题是并查集的模板题，类似于带权并查集？（初始时指向自己，权值为自己的点数），因为初始时拍的牌会带走一片牌，而且这一片牌每一张都可以作为初始时拍下来的，具有连通性和传递性和集体性，所以可用并查集维护。同样只需要结尾特判m-1和a[1]==0的情况看结尾和1是否要合并。

如果a[i]和a[i-1]满足条件，就把a[i-1]向a[i]合并（小向大合并）（已排过升序）

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int sum = 0;
int fa[2000001], a[2000001], value[2000001];
#define father fa
int getfather(int x)
{
    if (x != fa[x])
    {
        father[x] = getfather(father[x]);
    }
    return father[x];
}
void reset(int x, int y)
{
    x = getfather(x), y = getfather(y);
    if (x != y)
    {
        father[x] = father[y];
        value[y] += value[x];
    }
    return;
}
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++)
    {
        sum += a[i];
        fa[i] = i;
        value[i] = a[i];
    }
    for (int i = 1; i <= n; i++)
    {

        if (a[i - 1] == a[i] || (a[i - 1] + 1) % m == a[i])
        {
            reset(i - 1, i);
        }
        if (i == n)
        {
            if (a[i] == m - 1 && a[1] == 0)
            {
                reset(i, 1);
            }
        }
    }
    int ans = sum;
    for (int i = 1; i <= n; i++)
    {
        int f = getfather(i);
        ans = min(ans, sum - value[f]);
    }
    cout << ans << endl;
    system("pause");
    return 0;
}

答案的暴力没这个好，就不看了。