bitset优化

bitset优化背包
$d{p}_{i,k}|=d{p}_{i-1.k-j\ast j}$ 其中$i$代表到第$i$个区间，选完数得到的平方和为$k$ 这种情况是否存在
$j$表示第$i$次选数为$j$

枚举$i,j,k$时间复杂度为$O(n{l}^3)$

用bitset表示dp中的第二维，将枚举$k$这一部分$O(l^2)$优化为$O(l^2/64)$

std::bitset<1000005> dp[105];
void solve()
{
	int n;
	cin>>n;
	std::vector<int> l(n+1),r(n+1);
	for (int i=1;i<=n;i++)
		std::cin>>l[i]>>r[i];
	dp[0][0]=1;
	for (int i=1;i<=n;i++)
		for (int j=l[i];j<=r[i];j++)
			dp[i]|=dp[i-1]<<(j*j);
	std::cout<<dp[n].count();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

简单字符串问题
暴力枚举中心点$O(n^2)$,用两个bitset顺逆标记每个字母所在的位置上，之后直接枚举中心点，利用位运算求重合部分数量 $O(n^2/64)$

char a[100005];
void solve(){
    int n;
    cin>>n;
    vector<bitset<100000>> vis1(26),vis2(26);
    for (int i=0;i<n;i++){
        cin>>a[i];
        vis1[a[i]-'a'][i]=1;
        vis2[a[i]-'a'][n-i-1]=1;
    }
    ll ans=0;
    for (int i=0;i<n;i++){
        ans+=((vis2[a[i]-'a']>>(n-i))&(vis1[a[i]-'a']>>(i+1))).count();
    }
    cout<<ans<<"\n";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

CF333E Summer Earnings
暴力做法直接枚举三个点，看最小的一条边，不断更新最大值 $O(n^3)$

换种角度：考虑枚举某个三角形中最小的边（两点），判断是否存在另一点到两点的距离大于此边

转换一下，先求出所有的边，然后进行从小到大排序，不断加边。如果当前加的这条边（枚举的最小的边）的两端点$x,y$，存在合法的另外一点$z$（此前存在$x$与$z$,$y$与$z$的两条边），则该边即为答案

如果用数组打标记，枚举$z$的方法，复杂度仍为$O(n^3)$
所以用bitset代替数组，直接用位运算和count判断是否存在某个$z$ 复杂度降为$O(n^3/64)$

struct segment{
    int x,y;
    double len;
};
double road(int x1,int y1,int x2,int y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int main(){
    int n;
    cin>>n;
    vector<int> ax(n+1),ay(n+1);
    for (int i=1;i<=n;i++){
        cin>>ax[i]>>ay[i];
    }

    vector<segment> b;
    for (int i=1;i<=n;i++){
        for (int j=i+1;j<=n;j++){
            b.push_back({i,j,road(ax[i],ay[i],ax[j],ay[j])});
        }
    }

    sort(b.begin(),b.end(),[&](segment i,segment j){
        return i.len>j.len;
    });

    vector<bitset<3005>> vis(n+1);
    for (auto i:b){
        if ((vis[i.x]&vis[i.y]).count()){
            cout<<fixed<<setprecision(9)<<(double)(sqrt(i.len)/2);
            return 0;
        }
        vis[i.x][i.y]=1;
        vis[i.y][i.x]=1;
    }
	return 0;
}
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