「Ynoi2015」我回来了

发表于 | 更新于 | 分类于 | 阅读次数：

这个题主要是当做手写 bitset 板子来写的。

Idea：lxl Solution：lxl Std：lxl Data：lxl

对这题的评价：1/11

大概是 lxl 评价最低的题吧……

[Luogu 5068]

题意简述

珂朵莉给你一个无向图，每次查询的时候给一堆二元组 $(x_i,y_i)$ 。

求图中有多少个点 $u$ 与至少一个这次询问给出的二元组 $(x_i,y_i)$ 满足 $dist(u,x_i) \le y_i$ ，其中 $dist(u, v)$ 表示 $u, v$ 这两个点在图中的距离（不连通为 $\inf$），边权全为 $1$ 。

记 $n$ 为点数， $m$ 为边数， $q$ 为询问个数， $cnt$ 为给出二元组的总数。

$1\le n\le 10^3, 1\le m, q\le 10^5, cnt \le 2.1 \times 10^6$ 。

主要思路

每个点上记个 bitset $f[i]$ ， $f[i][j]$ 表示距离点 $i$ 不大于 $j$ 的点数。

可以 bfs 处理这些 bitset ，每次查询就是把一堆 bitset 或起来。

时间复杂度 $O(n\times m + \frac{n\times cnt}{\omega})$ ，空间 $O(\frac{n^3}{\omega})$ 。

参考代码

把 bitset 的大部分操作都写了一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
namespace my_std{
    using namespace std;
    #define reg register
    #define Rint register int
    #define FOR(i,a,b) for(register int i=(a),ed_##i=(b);i<=ed_##i;++i)
    #define ROF(i,a,b) for(register int i=(a),ed_##i=(b);i>=ed_##i;--i)
    #define FORit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)+1;i!=ed_##i;++i)
    #define ROFit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)-1;i!=ed_##i;--i)
    #define GO(x,p,e,i,v) for(register int i=p[x].head,v;i;i=e[i].link)
    #define MEM(x,v) memset(x,v,sizeof(x))
    #define fir first
    #define sec second
    #define pq priority_queue
    #define MP make_pair
    typedef long long LL;
    typedef double DB;
    typedef pair<int,int> PII;
    #define Templ(T) template<typename T>
    inline int read(){
        Rint ans=0,f=1;reg char c=getchar();
        while(!isdigit(c)){ f^=(c=='-'); c=getchar(); }
        for(;isdigit(c);c=getchar()) ans=ans*10+c-'0'; return f?ans:-ans;
    }
    Templ(_Tp) inline int chkmin(_Tp &x,_Tp y){ return x>y?x=y,1:0; }
    Templ(_Tp) inline int chkmax(_Tp &x,_Tp y){ return x<y?x=y,1:0; }
    #define using_mod
    const int mod = 998244353, N = 1010, ToT = 16, M = 100010;
    #ifdef using_mod
    inline void inc(int &x,const int &y){ x+=y; if(x>=mod) x-=mod; }
    inline int ksm(int x,LL y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res;}
    #endif
    Templ(_Tp) inline _Tp gcd(_Tp x,_Tp y){ return y?gcd(y,x%y):x; }
    #define FILE(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
    #define PBTXDY
}
using namespace my_std;

struct my_bitset{
    unsigned long long a[ToT];
    inline void reset(){ FOR(i, 0, ToT - 1) a[i] = 0ull; return; }
    inline void set(){ FOR(i, 0, ToT - 1) a[i] = ~0ull; return;}
    inline my_bitset(){ reset(); }
    inline void filp(int x){ a[x >> 6] ^= (1ull << (x & 63)); }
    inline void reset(int x){ a[x >> 6] &= ~(1ull << (x & 63)); }
    inline void set(int x){ a[x >> 6] |= (1ull << (x & 63)); }
    inline int test(int x){ return (a[x >> 6] >> (x & 63)) & 1; }
    inline int count(){ Rint res = 0; FOR(i, 0, ToT - 1) res += __builtin_popcountll(a[i]); return res; }
    //-----
    inline my_bitset operator ~()const {
        my_bitset res; FOR(i, 0, ToT - 1) res.a[i] = ~a[i]; return res;
    } inline my_bitset operator |(const my_bitset &B)const {
        my_bitset res; FOR(i, 0, ToT - 1) res.a[i] = a[i] | B.a[i]; return res;
    } inline my_bitset operator &(const my_bitset &B)const {
        my_bitset res; FOR(i, 0, ToT - 1) res.a[i] = a[i] & B.a[i]; return res;
    } inline my_bitset operator ^(const my_bitset &B)const {
        my_bitset res; FOR(i, 0, ToT - 1) res.a[i] = a[i] ^ B.a[i]; return res;
    } inline my_bitset operator <<(const int &t)const {
        my_bitset res; Rint High = t >> 6, Low = t & 63;
        unsigned long long Last = 0;
        FOR(i, 0, ToT - High - 1){
            res.a[i + High] = Last | (a[i] << Low);
            if(Low) Last = a[i] >> (64 - Low);
        }
        return res;
    } inline my_bitset operator >>(const int &t)const {
        my_bitset res; Rint High = t >> 6, Low = t & 63;
        unsigned long long Last = 0;
        ROF(i, ToT - 1, High){
            res.a[i - High] = Last | (a[i] >> Low);
            if(Low) Last = a[i] << (64 - Low);
        }
        return res;
    }
    //-----
    inline void operator |=(const my_bitset &B){ FOR(i, 0, ToT - 1) a[i] |= B.a[i]; return; }
    inline void operator &=(const my_bitset &B){ FOR(i, 0, ToT - 1) a[i] &= B.a[i]; return; }
    inline void operator ^=(const my_bitset &B){ FOR(i, 0, ToT - 1) a[i] ^= B.a[i]; return; }
    inline void operator <<=(const int &t){ *this = *this << t; }//懒了……
    inline void operator >>=(const int &t){ *this = *this >> t; }
}a[N][N], tmp;

#define inf (1001)
int n, m, q, dis[N], Que[M];
vector<int> G[N];

inline void bfs(int S){
    FOR(i, 1, n) dis[i] = inf;
    dis[S] = 0;
    Rint l = 0, r = 1, u, v;
    Que[0] = S;
    while(l < r){
        u = Que[l++];
        FOR(i, 0, int(G[u].size()) - 1){
            v = G[u][i];
            if(chkmin(dis[v], dis[u] + 1)) Que[r++] = v;
        }
    }
    FOR(i, 1, n) a[S][dis[i]].set(i);
    FOR(i, 1, n) a[S][i] |= a[S][i - 1];
}

int main(){
    n = read(), m = read(), q = read();
    Rint u, v, T;
    FOR(i, 1, m){
        u = read(), v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    FOR(i, 1, n) bfs(i);
    while(q--){
        T = read();
        tmp.reset();
        while(T--){
            u = read(), v = read();
            tmp |= a[u][v];
        }
        printf("%d\n", tmp.count());
    }
    return 0;
}