1130模拟赛 T1共同好友 乱搞解法

· · 个人记录

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

题目大意

给一个图G，有Q次询问，每次询问两个点(u, v)，求有多少点和两个点都有连边

解法

对于所有询问，将度数较大的点作起点，度数较小的点作终点

以起点为第一关键字，终点为第二关键字将所有询问排序

按照排好的顺序遍历每个询问：

然后就A了

复杂度证明

分别考虑起点和终点贡献的复杂度

起点

对于所有起点，每个点只在第一次出现时被扫到一次，所有边只被两边的点各扫到一次

起点贡献的复杂度只有O(n+m)

终点

将所有点的度数从达到小排序，记第i大的度数值为d_i，这个点作过i次终点

贡献时间复杂度T=\sum_{i=1}^{n} a_i d_i

由于相同的询问被特判掉了，d_i最多只能作i-1次终点

显然，询问度数更大的点会使复杂度更高，前\sqrt q个节点分别作终点

T\leq \sum_{i=1}^{\sqrt q} (i-1)\cdot d_i

总边数对终点的度数和作出限制

\sum_{i=1}^{\sqrt q} d_i \leq 2m \forall k\in [1,\sqrt q]\quad kd_k+\sum_{i=k+1}^{\sqrt q}d_i\leq 2m T &= \sum_{i=1}^{\sqrt q} (i-1)\cdot d_i\\ &= \sum_{i=2}^{\sqrt q} (i-1)\cdot d_i\\ &= \frac{1}{2}(2d_2+\sum_{i=3}^{\sqrt q}d_i) + \sum_{i=3}^{\sqrt q} (i-\frac{3}{2})\cdot d_i\\ &\leq m + \sum_{i=3}^{\sqrt q} (i-\frac{3}{2})\cdot d_i\\ &= m + \frac{1}{2}(3d_3+\sum_{i=4}^{\sqrt q}d_i) + \sum_{i=4}^{\sqrt q} (i-2)\cdot d_i\\ &\leq 2m + \sum_{i=4}^{\sqrt q} (i-2)\cdot d_i\\ &\vdots\\ &\leq m\sqrt q \end{aligned}

当d_1 = d_2 = \cdots = d_{\sqrt q} = \frac{2m}{\sqrt q}时取等

由于经过多次放缩，实际常数比较小

最终复杂度为O(m\sqrt q)

代码

# include <vector>
# include <cstdio>
# include <cstring>
# include <algorithm>
# define ll long long
using namespace std;
const int MAXN = 100051;
const int MAXM = 1000051;
struct Query{
    int u, v, id;
    bool operator == (const Query &o) const{
        return u == o.u && v == o.v;
    }
    bool operator < (const Query &o) const{
        if (u != o.u) return u < o.u;
        else return v < o.v;
    }
} q[MAXN];
struct Edge{
    int u, v;
    bool operator == (const Edge &o) const{
        return u == o.u && v == o.v;
    }
    bool operator < (const Edge &o) const{
        if (u != o.u) return u < o.u;
        else return v < o.v;
    }
} e[MAXM];
int n, m, t, gsz;
int ans[MAXN];
int vis[MAXN];
int dg[MAXN];
int fte[MAXN];
vector <int> g[MAXN];
int read(){
    int nm = 0;
    char x = getchar();
    while (x < '0' || x > '9') x = getchar();
    while (x >= '0' && x <= '9'){
        nm = nm * 10 + x - '0';
        x = getchar();
    }
    return nm;
}
int main(){
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 1; i <= m; i++){
        e[i].u = read();
        e[i].v = read();
        if (e[i].u > e[i].v) swap(e[i].u, e[i].v);
    }
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= m; i++){
        if (e[i] == e[i - 1]) continue;
        g[e[i].u].push_back(e[i].v);
        g[e[i].v].push_back(e[i].u);
    }
    for (int i = 1; i <= t; i++){
        q[i].u = read();
        q[i].v = read();
        q[i].id = i;
        if (g[q[i].u].size() < g[q[i].v].size()) swap(q[i].u, q[i].v);
        else if (g[q[i].u].size() == g[q[i].v].size() && q[i].u < q[i].v) swap(q[i].u, q[i].v);
    }
    sort(q + 1, q + t + 1);
    for (int i = 1; i <= t; i++){
        if (q[i] == q[i - 1]){
            ans[q[i].id] = ans[q[i - 1].id];
            continue;
        }
        if (q[i].u != q[i - 1].u){
            for (int j = 0; j < g[q[i].u].size(); j++) vis[g[q[i].u][j]] = q[i].u;
        }
        if (q[i].u == q[i].v){
            ans[q[i].id] = g[q[i].u].size();
            continue;
        }
        int cnt = 0;
        for (int j = 0; j < g[q[i].v].size(); j++){
            cnt += (vis[g[q[i].v][j]] == q[i].u);
        }
        ans[q[i].id] = cnt;
    }
    for (int i = 1; i <= t; i++) printf("%d\n", ans[i]);
    return 0;
}