数论
高斯消元解异或线性方程组
输入一个包含 n 个方程 n 个未知数的异或线性方程组。
方程组中的系数和常数为 0 或 1，每个未知数的取值也为 0 或 1。
求解这个方程组。
异或线性方程组示例如下：
M[1][1]x[1] ^ M[1][2]x[2] ^ … ^ M[1][n]x[n] = B[1]
M[2][1]x[1] ^ M[2][2]x[2] ^ … ^ M[2][n]x[n] = B[2]
…
M[n][1]x[1] ^ M[n][2]x[2] ^ … ^ M[n][n]x[n] = B[n]
其中 ^ 表示异或(XOR)，M[i][j]表示第 i 个式子中 x[j] 的系数，B[i]是第 i 个方程右端的常数，取值均为 0 或 1。
核心思想: 异或 == 不进位的加法 那么等式与等式间的异或要一起进行才能保证等式左右两边依然是相等关系!
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
int n;
int a[N][N];
int gauss(){
int r, c;
for(r = c = 0; c < n; c++){
int t = r;
for(int i=r; i<n; i++)
if(a[i][c]){
t = i;
break;
}
if(!a[t][c]) continue;
for(int i = c; i <= n; i++){
swap(a[t][i],a[r][i]);
}
for(int i = r + 1; i < n; i++)
if(a[i][c])
for(int j = c; j <= n; j++)
a[i][j] ^= a[r][j];
r++;
}
if(r < n)
{
for(int i = r; i < n; i++)
if(a[i][n])
return 2;
return 1;
}
for(int i = n - 1; i >= 0; i--)
for(int j = i + 1; j < n; j++)
a[i][n] ^= a[i][j] & a[j][n];
return 0;
}
int main(){
cin >> n;
for(int i=0;i<n;i++)
for(int j=0;j<n+1;j++)
cin >> a[i][j];
int res = gauss();
if(res == 0){
for(int i=0;i<n;i++) cout << a[i][n] << endl;
}
else if(res == 1) puts("Multiple sets of solutions");
else puts("No solution");
return 0;
}
博弈论
Nim游戏
给定 n 堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
const int N = 110;
int n;
int f[N];
unordered_set<int> S;
int sg(int x){
if(f[x] != -1) return f[x];
for(int i=0;i<x;i++)
for(int j=0;j<=i;j++)
S.insert(sg(i) ^ sg(j));
//mex操作
for(int i=0;;i++){
if(!S.count(i))
return f[x] = i;
}
}
int main(){
cin >> n;
memset(f, -1, sizeof f);
int res = 0;
for(int i=0;i<n;i++){
int x;
cin >> x;
res ^= sg(x);
}
if(res) puts("Yes");
else puts("No");
return 0;
}
DP
01背包问题
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
版本1 二维
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> v[i] >> w[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++){
f[i][j] = f[i-1][j];
if(j >= v[i]) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
版本2 一维
我们定义的状态f[i][j]可以求得任意合法的i与j最优解，但题目只需要求得最终状态f[n][m]，因此我们只需要一维的空间来更新状态。
状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i])
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> v[i] >> w[i];
for(int i=1;i<=n;i++)
for(int j = m;j >= v[i]; j--){
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
cout << f[m] << endl;
return 0;
}
完全背包问题
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
版本1 朴素写法
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> v[i] >> w[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k*v[i]<=j;k++){
f[i][j] = max(f[i][j], f[i-1][j-v[i]*k]+w[i]*k);
}
cout << f[n][m] << endl;
return 0;
}
版本2 优化为二维
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> v[i] >> w[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++){
f[i][j] = f[i-1][j];
if(j >= v[i]){
f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}
最终优化版 优化为一维
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> v[i] >> w[i];
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++){
f[j] = max(f[j], f[j-v[i]] + w[i]);
}
cout << f[m] << endl;
return 0;
}
