序：这篇论文起初第一眼看的时候觉得没什么用处，后来CYY说这篇写的还是不错的，于是花了一天仔细看了看
就把文中一些比较重要的结论和思想列出来当作回忆
1.1 读取某一位 pos: x>>pos&1
1.2 改变某一位 pos： 变为1：x|(1<<pos)
变为0：x&~(1<<pos)
取反：x^(1<<pos)
2.1 求1的个数：
利用分治的思想，将32个1字节的转变为16个2字节再转化直到1个32字节的 也就是答案
再利用因为其个数限制不会爆一些字节 于是进行代码缩短
具体证明：见论文
3.1求前缀/后缀0的个数
列出求前缀方法，后缀方法类似
这里主要用到的就是二分的思想，
先判断高16位是否为0，如果x>>16为0，则前16位为前缀0，于是在1--15位上二分即可，
否则只有高16位一位为0，于是x>>16位再接着二分即可
4.1求第k个1的位置
于是我们利用二分和文中提的一种差表法即可
5.1提取末尾连续的1
我们考虑在最后+1，最右边连续的1会变成0，于是我们可以利用这个性质得出公式
x&(x^(x+1))
6.1 lowbit(i)
定义：i在二进制下保留最低位1的二进制
公式：
前两个利用到5.1相反的性质，一个数-1，最右边连续的1会变成0
最后一个则利用补码的性质，也是最常用的
7.1本文最重要的用于实现题目简化的数据结构也就是bitset
加入、删除为 o(1) 的
取交集、并集、1的个数等为o(n/w)的 w为进制长宽
8.1枚举子集
考虑将子集大小排序输出就可以了，于是我们每次输出比x小1的子集y，再由y输出y‘....
y=x&(x-1); x=y;
9 T
9.1 筷子
2n+1个数 某个数x出现次数为奇数，其余的为偶数，求x
Sor：直接将所有数^起来即可
9.2 Codeforces 97D
Sor：我们考虑对于这个图建一个set，于是我们考虑每个点对应
set中的第i*m+j个，于是我们的上下左右移动也就转变为
>>m 、<<m 、<<1 、>>1 于是我们就可以利用这个来
模拟即可
9.3 Codeforces 232E
Sor：我们考虑在x轴二分一个mid考虑x1<=mid<=x2的询问
我们只需要找l--mid-1以及mid+1--r的点能到mid上那些点，
用set存下即可，最后只需判断f[x1][y1]与g[x2][y2]是否存在
交集即可，f和g数组可以利用dp解决，而询问可以利用分治即可
9.4 不会
10 代码：
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> #include<bitset> using namespace std; int n,m,k; char s[200000]; int work() { bitset<23000> a, b, c, e; for (int i=0; i<n; i++) { scanf("%s",s); for (int j=0; j<m; j++) { (s[j]=='#'?a:b).set(i*m+j); (s[j]=='E'?e.set(i*m+j):0); } } c=b; scanf("%s",s); for (int i=0; i<k; i++) { if (e==c) return i; if (s[i]=='U') c=((c>>m)&b) | (c&(a<<m)); if (s[i]=='D') c=((c<<m)&b) | (c&(a>>m)); if (s[i]=='L') c=((c>>1)&b) | (c&(a<<1)); if (s[i]=='R') c=((c<<1)&b) | (c&(a>>1)); } if (e==c) return k; return -1; } int main() { while (scanf("%d%d%d",&n,&m,&k)!=EOF) { printf("%d ",work()); } return 0; }
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> #include<bitset> #include<vector> #define pb push_back #define N 505 using namespace std; int n,m,k; char a[N][N]; struct data{ int id,x1,x2,y1,y2; }q; typedef vector<data> V; bitset<N> f[N][N],g[N][N]; V v; bool ans[600005]; int read() { int x=0,f=1; char ch; while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') f=-1; while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9'); return x*f; } void solve(int l,int r,V v) { if (l>r) return ; int mid=(l+r)>>1; for (int i=mid; i>=l; i--) for (int j=m; j>=1; j--){ f[i][j]=0; if (a[i][j]=='.'){ if (i==mid) f[i][j][j]=1; else f[i][j]|=f[i+1][j]; if (j!=m) f[i][j]|=f[i][j+1]; } } for (int i=mid; i<=r; i++) for (int j=1; j<=m; j++){ g[i][j]=0; if (a[i][j]=='.'){ if (i==mid) g[i][j][j]=1; else g[i][j]|=g[i-1][j]; if (j!=1) g[i][j]|=g[i][j-1]; } } V v1,v2; for (V::iterator it=v.begin(); it!=v.end(); it++){ q=*it; if (q.x2<mid) v1.pb(q); else if (q.x1>mid) v2.pb(q); else ans[q.id]=(f[q.x1][q.y1]&g[q.x2][q.y2]).any(); } solve(l,mid-1,v1); solve(mid+1,r,v2); } int main() { n=read(); m=read(); for (int i=1; i<=n; i++) scanf("%s",a[i]+1); k=read(); for (int i=1; i<=k; i++) { q.id=i; q.x1=read(),q.y1=read(),q.x2=read(),q.y2=read(); v.pb(q); } solve(1,n,v); for (int i=1; i<=k; i++) if (ans[i]) printf("Yes "); else printf("No "); return 0; }