位运算

1.负数转化成二进制:先绝对值转化成二进制,然后取补码,加一即可

2.求x中含有1的个数

1
int __builtin_popcount(unsigned int x)

如果 $x$ 是 long long 类型 ,那么需要使用

1
int __builtin_popcountll(unsigned long long x)

似乎是 $O(1)$ 的,没测过实测下来比 $lowbit$ 快90$\%$

CCF用不用的了很难说,不过有替代品,实测慢不了多少(甚至数据比较大的时候还快了点)

1
2
3
4
5
6
7
inline int popcount(long long x)
{
x = (x & 0x5555555555555555ULL) + ((x >> 1) & 0x5555555555555555ULL);
x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);
x = (x & 0x0F0F0F0F0F0F0F0FULL) + ((x >> 4) & 0x0F0F0F0F0F0F0F0FULL);
return (x * 0x0101010101010101ULL) >> 56;
}

例题

P1225 黑白棋游戏

一个用位运算优化的题目,由于这种问题规模比较小 ( $n=4$ ) 因此可以考虑搜索,本题一共有 $2^{16}$ 种情况,并且每个情况需要尝试 $2^{6} $ 次增广 ($2^4*2^2$),如果进行最原始的逐个比较判重的话是需要在$2^4$ 的,这时候 $BFS$ 需要进行至多 $67108864$ 很难说能不能过

显然前面的优化已经很难做到了,只有考虑判重的时候,倘若我们把这个棋盘视为一个十六位的数,就可以 $O(1)$ 解决判重问题了

如何保证一个十六位的数和这个棋盘一一对应呢?只需要让第 $i$ 行第 $j$ 列左移$(i-1)*n+j-1$ 即可

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

int vis[65537];
int st,ed;
int f[65537];
int n=4,m=4;//这里为了方便查错视为n*m的棋盘,其中n=m=4
int ax[65537];
int ay[65537];
int bx[65537];
int by[65537];
int lst[65537];
int v[5][5];
int dx[]={1,-1,0,0}; //(x+dx[i],y+dy[i])分别表示上下左右的点
int dy[]={0,0,1,-1};

struct xy{
int x1,x2,y1,y2;
xy (int xx1=0,int yy1=0,int xx2=0,int yy2=0)
{
x1=xx1; y1=yy1; x2=xx2; y2=yy2;
}
};

stack <xy> s;

int imp(int x,int y) //判断是否合法
{
return x>=1&&x<=n&&y>=1&&y<=m;
}

int bfs()
{
queue <int> q;
q.push(st);
f[st]=0;
vis[st]=1;
while(!q.empty())
{
int t=q.front();
q.pop();
int i,j,k,l,dir;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
for(dir=0;dir<=3;dir++)
{
k=i+dx[dir]; l=j+dy[dir];
if(!imp(k,l)) continue;
if(!((t&v[i][j])^(t&v[k][l]))) continue;
//如果两个调换的位置奇偶性相同那就没必要
int looker=t;
looker^=v[i][j];
looker^=v[k][l];
if(vis[looker]) continue;
lst[looker]=t;
ax[looker]=i;
ay[looker]=j;
bx[looker]=k;
by[looker]=l; //记录交换的点对
vis[looker]=1;
f[looker]=f[t]+1;
q.push(looker);
}
}
return f[ed];
}

int main()
{
ios::sync_with_stdio(false);
register int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
v[i][j]=1<<((i-1)*m+j-1);
char t; for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>t;
if(t=='1') st|=v[i][j];
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>t;
if(t=='1') ed|=v[i][j];
}
cout<<bfs()<<endl;
while(ed!=st)
{
s.push(xy(ax[ed],ay[ed],bx[ed],by[ed]));
ed=lst[ed];
}
while(!s.empty())
{
cout<<s.top().x1<<s.top().y1<<s.top().x2<<s.top().y2<<endl;
s.pop();
}
return 0;
}

数学

五边形数

狭义五边形数 $p=1,5,12,22…$

求第 $n$ 项

广义的五边形数 $p_n=\frac{3n^2\pm n}{ 2}$

作用:拆分数

乘法 $\to $ 加法,取 $\log$ 即可,据说精度会炸,跑完 $\text{int}$ 发现没问题,