|
1月25日 shayndel |
||
|
时间段 |
记录 |
备注 |
|
8:00---8:30 |
|
|
|
8:30---9:00 |
二进制状态压缩&&hamilton路径 |
|
|
9:00----9:30 |
|
|
|
9:30---10:00 |
|
|
|
10:00—10:30 |
休息 |
|
|
10:30---11:00 |
成对变换&&lowbit运算 |
|
|
11:00---11:30 |
|
|
|
11:30---13:30 |
|
|
|
13:30---14:00 |
|
|
|
14:00—14:30 |
Lowbit运算&&map |
|
|
14:30—15:00 |
高一热假热身赛 |
|
|
15:00—15:30 |
|
|
|
15:30---16:00 |
看书（递归&&递推） |
|
|
16:00---16:30 |
|
|
|
16:30---17:00 |
|
|
|
17:00---18:30 |
|
|
|
18:30—21:30 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
分享交流：
（待书写）
附：可以贴各种资料或题解
1.24
0x01 位运算
快速幂取模：
要点：
1.通过对每个底数取模，降低底数规模。
1 int sum=1;
2 a=a%mod;
3 for(int i=1;i<=b;i++)
4 sum*=a;
5 sum%=mod;
2.把指数转化为2进制，再通过手段缩小指数的规模，用1的方法进行取模。若指数为偶数，两两合并。如7^16%mod=(7%mod)^16=(49%mod)^4=(49%mod)*(49%mod)^2···
1 #include <iostream>
2 using namespace std;
3 long long ksm(long long di,long long zhi,long long mod){
4 if(zhi==0)return 1%mod;
5 long long ans=1;
6 while(zhi){
7 if(zhi&1)
8 ans=ans*di%mod;
9 di=di*di%mod;
10 zhi>>=1;
11 }
12 return ans;
13 }
64位乘法：
- 类似快速幂思想，*变为+即可。
1 long long gcqm(long long a,long long b,long long mod){//类似快速幂思想，把b转化为二进制
2 long long ans=0;
3 while(b){
4 if(b&1)
5 ans=(ans+a)%mod;
6 a=a*2%mod;
7 b>>=1;
8 }
9 return ans;
10 }
2.a*b % mod=a*b-[a*b/mod]*p []表示向下取整
1 long long gcqm2(long long a,long long b,long long mod){//a*b % mod=a*b-[a*b/mod]*p []表示向下取整
2 a%=mod;
3 b%=mod;
4 long long c=(long double)a*b/mod;
5 long long ans=a*b-c*mod;
6 if(ans<0)ans+=mod;
7 else if (ans>=mod)ans-=mod;
8 return ans;
9 }
1.25
二进制状态压缩
Hamilton路径
这道DP的思路是floyd，用二进制进行状态压缩。用一个n位的二进制数表示状态，若第i为为1，则表示第i个点已经被经过。因此我们定义一个数组f[i,j]表示”点被经过的状态”对应的二进制位为i，且目前处于点j时的最短路径。
此时DP方程为f[i][j=min(f[i][j],f[i^1<<j][k]+weight[j][k]),因为当前时刻被经过的点的二进制数为i，处于点j。故最终目标为f[(1<<n)-1][n-1]。因为j点恰好经过一次，所以一定是刚刚经过的，所以在上一时刻被经过的点对应的二进制状态i的第j位赋值一定为0。也就是i^(1<<j)。且上一个经过的点可能是i^(1<<j)中任意一个是1的数位k，所以可以考虑这样的状态是最小值。
1 f[1][0]=0;
2 for(int i=1;i<1<<n;i++)
3 for(int j=0;j<n;j++)
4 if(i>>j&1)
5 for(int k=0;k<n;k++)
6 if((i^1<<j)>>k&1)
7 f[i][j]=min(f[i][j],f[i^1<<j][k]+weight[k][j]);
8 cout<<f[(1<<n)-1][n-1]<<endl;
逻辑运算的运算顺序
成对变换
对于非负整数n
当n为偶数时，n xor 1=n+1
当n为奇数时，n xor 1=n-1
所以0与1,2与3，4与5 关于xor 1 的计算成为成对变换。
Lowbit运算
对于非负整数n在二进制表示下“最低位的1以及后面所以的0构成的数值”。
Lowbit（n）=n&(~n+1)=n&(-n)
GCC编译器内置函数
Int_builtin_ctz(unsigned int x)
Int_builtin_ctzll(unsigned long long x)
返回x的二进制表示下最低位的1后边有多少个0
Int_builtin_popcount(unsigned int x)
Int_builtin_popcountll(unsigned long long x)
Map
