bitset小专题（待续）

bitset：一个01位如果用bool存的话需要 1byte，而用bitset只需要 1bit(=1/8 byte)
每次两个集合取并的时候可以除以一个大常数（32/64），从而优化复杂度

LOJ515
设 \(dp[i]\) 表示考虑到第 \(i\) 个区间，能形成的和的状态是0/1（该位为1代表可以出现这个数，否则不能）
转移就枚举一下当前区间 or 一下即可
注意这里不能用 1<<i 这种写法，因为会爆int

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 105;

int n;
int a[maxn], b[maxn];
bitset<101 * 101 * 101>dp[2];

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];

    for (int i = 1; i <= n; i++) {
        dp[i & 1].reset();

        for (int j = a[i]; j <= b[i]; j++) {
            dp[i & 1] |= (dp[i & 1 ^ 1] << (j * j));
        }

        if (i == 1)
            for (int j = a[i]; j <= b[i]; j++)
                dp[i & 1][j * j] = 1;
    }

    cout << dp[n & 1].count();

    return 0;
}

abc287_ex
帮助理解floyd本质的好题
floyd的代码一般是这样：

for(int k=1;k<=n;k++){
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    }   
  }
}

这里 \(k\) 的深层含义就是：\(i\rightarrow j\) 的路径上，（去除了起点终点）路径上的点的编号均不超过 \(k\) 时的最短距离
每次 \(k+1\) 的时候，就相当于 \((i,j)\) 的路径上可以出现 \(k+1\) 这个点，因此用 \(dis[i][k']+dis[k'][j]\) 更新之
这个题实际上就考察了floyd的本质。每次枚举一下路径上的最大点 \(k\)，然后传递闭包即可
又因为我们只需要记录是否（路径上只利用 \(1..k\) 的点）可达即可，因此可以用bitset优化一下，时间复杂度 \(O(\frac{n^3+nQ}{32})\)

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;

int n,m;
bitset<2005>acc[2005];
int s[10005], t[10005], ans[10005];
signed main(){
	memset(ans,-1,sizeof ans);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		acc[x][y] = 1;
	}
	int Q;
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++){
		scanf("%d%d",&s[i],&t[i]);
	}
	for(int k=1;k<=n;k++){
		acc[k][k] = 1;
		for(int i=1;i<=n;i++){
			if(acc[i][k])acc[i] |= acc[k];
		}
		for(int i=1;i<=Q;i++){
			int u=s[i], v=t[i];
			if(u<=k && v<=k && acc[u][v] && ans[i]==-1){
				ans[i] = k;
			}
		}
	}
	for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
	
	return 0;
}