Bitset
使用bitset需要引用<bitset>头文件。
其声明方法为:
std::bitset<N>s; (N为s长度)
常用函数：
b.any() 判断b中是否存在值为1的二进制位
b.none() 判断b中是否不存在值为1的二进制位
b.count() 判断b中值为1的二进制位个数
b.size() 判断b中二进制位的个数
b[pos] 访问b中在pos处的二进制位
b.test(pos) 判断b中在pos处的二进制位是否为1
b.set() 把b中所有二进制位都置为1
b.set(pos) 把b[pos]置为1
b.reset() 把b中所有二进制位都置为0
b.reset(pos) 把b[pos]置为0
b.flip() 把b中所有二进制位逐位取反
b.flip(pos) 把b[pos]取反
滚动数组
memset(dp, inf, sizeof(dp)) ;
dp[0][N]=0;
for(int k = 1, i = 1; i <= n; i ++, k ^= 1){
memset(dp[k], inf, sizeof(dp[k])) ;
for(int j = -5000; j <= 5000; j ++)
dp[k][j + N] = min(dp[k ^ 1][j + c[i] + N], dp[k ^ 1][j - c[i] + N] + 1) ;
}
int ans;
for(int i=0;i<=5000;i++){
ans=min(dp[n&1][i+N],dp[n&1][-i+N]);
if(ans<1000) break;
}
多重背包
//分堆过程
while(k<=s){
//小于等于和小于都可以,因为如果出现等于的情况就是s=2^(k+1)-1,下面的if判断会处理掉
cnt++;//cnt先++=>下标从1开始
w[cnt] = k * wi;//k个物品为一堆
v[cnt] = k * vi;
s-=k;
k*=2;
}
if(s>0){
//如果存在最后一个堆
cnt ++;
//最后一个堆有s'个i物品
w[cnt] = s * wi;
v[cnt] = s * vi;
}
}
n = cnt;//物品由n个变成了nlogs个 别忘了这句
区间DP
for (int len = 1; len <= n; len++) {
// 区间长度
for (int i = 1; i + len - 1 <= n; i++) {
// 枚举起点
int j = i + len - 1; // 区间终点
if (len == 1) {
dp[i][j] = 初始值
continue;
}
for (int k = i; k < j; k++) {
// 枚举分割点，构造状态转移方程
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
}
}
}
树形dp
void dfs(int u,int fa){
for(int i=0;i<g[u].size();i++){
int v = g[u][i];
if(v==fa) continue;
dfs(v,u);
for(int k=m;k>=0;k--)
for(int j=1;j<=k;j++)
dp[u][k] = max(dp[u][k],dp[u][k-j]+dp[v][j]);
}
for(int i=m;i>=1;i--){
dp[u][i] = dp[u][i-1] + w[u];
}
}
状压dp
f[0] = 0;
for (int mask = 1; mask < (1 << n); ++mask) {
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
f[mask] = min(f[mask], f[mask ^ (1 << i)] + (nums1[__builtin_popcount(mask) - 1] ^ nums2[i]));
}
}
}
return f[(1 << n) - 1];
int f[17][1<<17];
int dfs(int x,int y){
if(f[x][y])return f[x][y];
int ans=0;
for(auto i:v[st[x][st[x].size()-1]])
if(!((y>>(i-1))&1))ans=max(ans,dfs(i,y|(1<<(i-1))));
return f[x][y]=ans+st[x].size();
}
for(int i=1;i<=n;i++)cin>>st[i],v[st[i][0]].push_back(i);
for(int i=1;i<=n;i++)ans=max(ans,dfs(i,(1<<(i-1))));
1.是方格图求状态数、最大最小值。
这种题一般是把每一行/列看做一个状态来转移的。预处理出每一行的所有状态，然后根据状态转移方程进行转移。
该状态左右不相邻： !(i& i<< 1)
2.给你一个集合，然后每次从中选出一个数，选过的数不能再选
dp[st] += dp[st^(1<<(i-1))] (st&(1<<(i-1)) != 0)
模拟退火
const double eps=1e-18;
const double delta=0.999;//调了一年的参数一般为0.97~1.0
class Solution {
public:
vector<int> a,b;
int ans=INT_MAX;//答案
double fun(){
int res=0;
for(int i=0;i<a.size();i++)
res+=(a[i]^b[i]);
ans=min(ans,res); //取最小
return res;
}
int sa(){
random_shuffle(b.begin(), b.end()); //打乱，随机分布
int n=a.size();
for(double t=1e6;t>eps;t*=delta){
int x=rand()%n,y=rand()%n;
int last=fun(); //没有交换前的异或值之和
swap(b[x],b[y]); //交换后的异或值之和
int now=fun();
int de=now-last;
if(de<0){
//比当前优秀就要
}
else if(!(exp(-1.0*de/t)*RAND_MAX>rand())) // 模拟退火的法则，我也搞不懂，背一下就好了
swap(b[x],b[y]); //不符合法则，回溯。
}
return ans;
}
int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
for(int i:nums1) a.push_back(i);
for(int i:nums2) b.push_back(i);
return sa();
}
};
