Online Judge：NOIP2016十连测第一场 T2
Label：暴力，Bitset
题目描述
在美丽的比特镇一共有n个景区，编号依次为1到n，它们之间通过若干条双向道路连接。
Byteasar 慕名来到了比特镇旅游，不过由于昂贵的门票费，他只能负担起 4 个景区的门票费。他可以在任意景区开始游览，然后结束在任意景区。
Byteasar 的旅游习惯比较特殊，一旦他路过了一个景区，他就一定会进去参观，并且他永远不会参观同一个景区两次。所以他想知道，有多少种可行的旅游路线，使得他可以恰好参观 4 个景区呢？即，有多少条简单路径恰好经过了 4 个点。
输入
第一行包含两个整数n，表示景区的总数。
第2至第n+1行，每行一个长度为n的01字符串，第i+1行第j个字符为0表示i和j之间没有道路，为1表示有一条道路。
输入数据保证\((i,j)\)的连接情况等于\((j,i)\)的连接情况，且\((i,i)\)恒为0。
输出
输出一行一个整数，即可行的路线总数。
样例
Input
4
0101
1010
0101
1010
Output
8
说明/提示
8 条路线分别为：
1->2->3->4，4->3->2->1，
2->3->4->1，1->4->3->2，
3->4->1->2，2->1->4->3，
4->1->2->3，3->2->1->4。
对于40%数据，\(n<=50\)
对于70%数据，\(n<=300\)
对于100%数据，\(n<=1500\)
题解
40pts
\(O(N^4)\)枚举四个点。
70pts
\(O(N^3)\)。
考虑枚举中间两个点\(p2,p3\)，现在要找到符合条件的对数{\(p1,p4\)}。需要满足的条件是这四个点两两都不相同。
设\(cnt[i]\)表示与i直接连通的点的个数(就是字符串中含1个数)，\(same[i][j]\)表示与i,j都直接相连的点的个数(就是两个字符串对应位都为1的位数)。
那么上面的符合条件的对数{\(p1,p4\)}就是\((cnt[p2]-1)*(cnt[p3]-1)-same[p2][p3]\)。都减一是因为\(p2,p3\)互相相连，新选的\(p1,p4\)不能跟这两个重了。
上面的枚举是\(O(N^2)\)的，预处理\(same[][]\)是\(O(N^3)\)的。
100pts
主要瓶颈在于\(same[][]\)的预处理，其实预处理的时候就马上想到用\(Bitset\)去优化常数，快速得到这个值，但是考试的时候觉得应该有\(N^2\)解法，结果Claris的正解就是这东西???。
所以利用\(Bitset\)二进制存储，计算两者与运算结果中1的个数。
复杂度为\(O(\frac{n^3}{64})\)，对于n<=1500的数据没问题。
#include<bits/stdc++.h>
using namespace std;
const int N=1510;
int n,cnt[N];
bitset<N>a[N];
int main(){
scanf("%d",&n);
register int i,j;char c;
for(i=1;i<=n;i++)for(j=1;j<=n;j++){
c=getchar();
while(c!='0'&&c!='1')c=getchar();
a[i][j]=c-'0';
cnt[i]+=c-'0';
}
long long ans=0;
for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)if(a[i][j]==1){
ans+=1ll*(cnt[i]-1)*(cnt[j]-1)-1ll*(a[i]&a[j]).count();
}
printf("%lld\n",ans<<1);
}
END
整理一下\(Bitset\)的用法。参考博客->
定义/初始化
<>中填的类似数组大小，后面可以开成单个变量，也可以开成一个数组。
bitset<LEN>a;
bitset<2333>b[N];
初始化大概有如下几种方式。
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("test.out","w",stdout);
//用string(似乎只能包含01，不然运行时会报错)
bitset<10>a (string("11011"));
cout<<"#1:"<<a<<endl;
//用整数(转为二进制)
a=123;
cout<<"#2:"<<a<<endl;
//直接像数组那样赋值(下标从0开始，长度为10)
for(int i=0;i<=9;i++){
int o;scanf("%d",&o);//测试时输入1 0 1 0 0 0 1 1 0 1
a[i]=o;
}
cout<<"#3:"<<a<<endl;
}
输出结果
#1:0000011011
#2:0001111011
#3:1011000101
运算操作
\(Bitset\)支持所有位运算。包括异或^、或|、与&、左移<<、右移>>等。
常用函数
查询类
1.返回1的个数
a.count();
2.返回是否有1
a.any();
操作类
3.全部变成1
a.set();
4.将右数第\(i+1\)位变成1（实际上就是将二进制的第i位变成1，下标从0开始）
a.set(i);
//例: a.set(2) 0000000100
5.全部变为0（()中间填数字时指定某一位，同上）
a.reset();
6.取反（()中间填数字时指定某一位，同上）
a.flip();
至于常数优化是多少，好像跟机器位数有关(32/64)。