T4 题目描述

小美拿到了一个大小为n的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有k个 0。小美想知道，一共有多少种不同的删除方案？

#include<iostream>
using namespace std;
int n,k;
const int N = 1e5+10;
int a[N];
int cnt2[N];
int cnt5[N];
int cnt_2,cnt_5;
void calc()
{
    for(int i = 0;i<n;i++)
    {
        int x = a[i];
        while(x % 2 == 0){
            x /= 2;
            cnt_2++;
            cnt2[i] ++;
        }
        while(x % 5 == 0){
            x /= 5;
            cnt_5++;
            cnt5[i]++;
        }
    }

}
int main()
{
    cin>>n>>k;
    for(int i = 0;i<n;i++) cin>>a[i];
    calc();

    long long res = 0;
    int l = 0;
    for(int r = 0;r<n;r++)
    {
        cnt_5 -= cnt5[r];
        cnt_2 -= cnt2[r];
        while(l <= r && min(cnt_2,cnt_5) < k){
            cnt_2 += cnt2[l];
            cnt_5 += cnt5[l];
            l++;
        }
        res += (long long) r - l + 1;
    }

    cout<<res<<endl;
}

T5 题目描述

小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。
现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？
事件共有 2 种：
1 u v：代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。
2 u v：代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。
注：介绍可以有多层，比如 2 号把 1 号介绍给 3 号，然后 3 号再把 1 号介绍给 4 号，这样 1 号和 4 号就认识了。
输入描述
第一行输入三个正整数n,m,q，代表总人数，初始的朋友关系数量，发生的事件数量。接下来的m行，每行输入两个正整数u,v，代表初始编号u的人和编号v的人是朋友关系。接下来的q行，每行输入三个正整数op,u,v，含义如题目描述所述。
1<=n <= 10^9
1<= m,q<= 10^5
1<= u,v<= n
1<= op <= 2

题目分析
①n太大，直接并查集数据爆
②删边 -> 逆向思维，反向处理查询恢复边即可

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
unordered_map<int, int> p;
typedef pair<int,int> PII;
int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y) {
    int a = find(x),b = find(y);
    if(a != b) p[a] = b;
}

struct node {
    int op;
    int u;
    int v;
} A[N];

int main() {
    int n, m, T;
    cin >> n >> m >> T;
    vector<node> query;
    set<PII> g;
    //init
    for(int i = 0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        p[u] = u,p[v] = v;
        g.insert({u,v});
    }
    for(int i = 0;i<T;i++)
    {
        int op,u,v;
        cin>>op>>u>>v;
        query.push_back({op,u,v});
        if(op == 1)
        {
            if(g.count({u,v}) || g.count({v,u}))
                g.erase({u,v});
        }
    }
    for(auto e : g){
        merge(e.first,e.second);
    }
    vector<string> res;
    int Q = query.size();
    for(int i = Q-1;i>=0;i--)
    {
        auto& t = query[i];
        if(t.op == 1) merge(t.u,t.v);
        else
        {
            if(find(t.u) == find(t.v))
                res.push_back("Yes");
            else res.push_back("No");
        }
    }
    reverse(res.begin(),res.end());
    for (string s : res) {
        cout << s << endl;
    }
    return 0;
}