《算法竞赛进阶指南》0x01 ~ 0x02 代码 + 杂谈
0x01 位运算
位运算符
第 i 位为从右往左从0开始数
如果要设置 n 的第 i 位为1，n=（n|（1<<i）；
如果要设置 n 的第 i 位为0，n=（n &（~（1<<i））；
& 按位与
如果两个相应的二进制位都为1，则该位的结果值为1，否则为0
| 按位或
两个相应的二进制位中只要有一个为1，该位的结果值为1
^ 按位异或
若参加运算的两个二进制位值相同则为0，否则为1
~ 取反
~是一元运算符，用来对一个二进制数按位取\反，即将0变1，将1变0
<< 左移
用来将一个数的各二进制位全部左移N位，右补0
>> 右移
将一个数的各二进制位右移N位，移到右端 的低位被舍弃，对于无符号数，高位补0
补码
一个负整数（或原码）与其补数（或补码）相加，和为模。(C < 0);
-C + S = INT_MAX;
~n = -1 - n;
a^b
#include <iostream>
using namespace std;
typedef long long ll;
ll q_mod(ll a, ll b, ll p) {
ll res = 1 % p;
while(b){
if(b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int main(){
ll a, b, p;
cin >> a >> b >> p;
cout << q_mod(a, b, p) << endl;
return 0;
}
64位整数乘法(快速乘带mod)
#include <iostream>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
ll mul(ll a, ll b, ll p) {
ll res = 0;
while(b) {
if(b & 1) res = (res + a) % p;
a = (a << 1) % p;
b >>= 1;
}
return res;
}
int main(){
ll a, b, p;
cin >> a >> b >> p;
cout << mul(a, b, p) << endl;
return 0;
}
以上都是利用 b的二进制 有1的才有乘法和加法意义 所做的
lowbit
lowbIt(x) = (-x) & x; 获得最低位的 1 ;
最短 hamilton 路径
状压DP 居然第一节就有了 orz
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 20 + 5;
int mp[maxn][maxn];
int dp[(1 << 20) + 5][maxn];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= n; j ++ )
cin >> mp[i][j];
// for(int k=1;k<=n;k++){
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// if(mp[i][j]>mp[i][k]+mp[k][j]) mp[i][j]=mp[i][k]+mp[k][j];
// }
// }
// } 数据保证最短路 不然跑floyd先
memset(dp, 0x3f, sizeof dp);
//for(int i = 0; i <=n ; i ++ ) dp[1 << i][i] = 0; // 任意开始最短路径
dp[1][0] = 0;
for(int s = 1; s < (1 << n); s ++ ) {
for(int i = 0; i < n; i ++ ) {
if( !(s & (1 << i)) ) continue; // 借助这个城市
for(int j = 0; j < n; j ++ ) {
if(s & (1 << j)) continue; // 要去这个城市
dp[s | (1 << j)][j] = min(dp[s | (1 << j)][j], dp[s][i] + mp[i + 1][j + 1]);
}
}
}
cout << dp[(1 << n) - 1][n - 1] << endl;
return 0;
}
0x02递推与递归
枚举: 排列 组合 (多项式级和指数级别, 递归、循环 剪支);
递归实现指数型枚举
#include <iostream>
using namespace std;
const int maxn = 20;
int ans[maxn], hh, tt;
int n;
void dfs(int num){
if(num == n + 1) {
for(int i = hh; i < tt; i ++ ) {
cout << ans[i] << " ";
}cout << endl;
return;
}
dfs(num + 1);
ans[tt] = num;
tt ++;
dfs(num + 1);
tt --;
}
int main(){
cin >> n;
hh = 1, tt = 1;
dfs(1);
return 0;
}
递归实现组合型枚举
注意剪枝
#include <iostream>
using namespace std;
const int maxn = 30;
int ans[maxn], hh, tt;
int n, m;
void dfs(int num){
if(tt > m + 1|| tt + (n - num) < m)
return;
if(tt == m + 1) {
for(int i = 1; i < tt; i ++ ){
cout << ans[i] << " ";
}cout << endl;
return ;
}
ans[tt] = num;
tt ++;
dfs(num + 1);
tt --;
dfs(num + 1);
}
int main(){
cin >> n >> m;
hh = 1, tt = 1;
dfs(1);
return 0;
}
递归实现排列枚举型
#include <iostream>
using namespace std;
const int maxn = 15;
bool vis[maxn];
int ans[maxn], hh, tt;
int n, m;
void dfs(int num){
if(num == n + 1) {
for(int i = 1; i < tt; i ++ ) {
cout << ans[i] << " ";
}cout << endl;
return ;
}
for(int i = 1; i <= n; i ++ ) {
if(vis[i]) continue;
ans[tt] = i;
tt ++;
vis[i] = 1;
dfs(num + 1);
tt -- ;
vis[i] = 0;
}
}
int main(){
cin >> n;
hh = 1, tt = 1;
dfs(1);
return 0;
}
例题:
费解的开关
每一点 只影响上下左右
不妨枚举第一次方案 这样 之后每一层都必须根据上一层来处理 翻不翻
最后判断最后一层 是否可行就行
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 10;
int a[maxn][maxn], b[maxn][maxn];
int n, ans;
int solve(int k){
int res = 0;
for(int i = 2; i <= n; i ++ ) {
for(int j = 1; j <= n; j ++ ) {
if((a[i - 1][j] + b[i - 1][j] + b[i - 1][j - 1] + b[i - 1][j + 1] + b[i - 2][j]) & 1) {
res ++;
b[i][j] = 1;
}else {
b[i][j] = 0;
}
}
if(res + k > 6) return 0x3f3f3f3f;
}
for(int j = 1; j <= n; j ++ ) {
if((a[n][j] + b[n][j] + b[n][j - 1] + b[n][j + 1] + b[n - 1][j]) & 1) {
return 0x3f3f3f3f;
}
}
return res;
}
void dfs(int num, int k) {
if(num == n + 1) {
ans = min(solve(k) + k, ans);
return ;
}
b[1][num] = 0;
dfs(num + 1, k);
b[1][num] = 1;
dfs(num + 1, k + 1);
}
int main(){
int cas ;
cin >> cas;
n = 5;
while(cas --) {
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
string line;
for(int i = 1; i <= 5; i++ ) {
cin >> line;
for(int j = 1; j <= 5; j++ ) {
if(line[j - 1] == '0') a[i][j] = 1;
}
}
ans = 0x3f3f3f3f;
dfs(1, 0);
if(ans > 6) cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}
多汉诺塔问题
首先考虑n个盘子3塔的经典Hanoi问题，设dn表示求解n个盘子3塔问题的最少步数，显然有 dn=2∗dn−1+1
含义为把前n−1个盘子从A借助C转移到B，再将第n个盘子转移到C，最后把n−1个盘子从B借助A转移到C。
类似地，对于本题，设f[n]表示求解n个盘子4塔问题的最小步数，则有 fn=min(2∗fi+dn−i)(1≤i<n)
含义为把前i个盘子在4柱的情况下从A转移到B，再将n−i个盘子在3柱的情况下从A转移到D，最后再将i个盘子在4柱的情况下从B转移到D
那么对于n盘m塔的问题(m>4)，就有 fn,m=min(2∗fi,m+fn−i,m−1)(1≤i<n)
使得我们可以在O(n^2∗m)的复杂度内求解该问题
#include <iostream>
using namespace std;
const int maxn = 25 + 5 ;
int n, m;
int dp[20], d[20];
signed main() {
d[1] = 1;
for(int i = 2; i <= 15; i++) {
d[i] = d[i - 1] * 2 + 1;
}
memset(dp, 0x3f, sizeof(dp));
dp[1] = 1;
for(int i = 2; i <= 15; i++) {
for(int j = 1; j < i; j++) {
dp[i] = min(dp[i], d[i - j] + dp[j] * 2);
} // 2 * 4塔模式 + 1 * 3塔模式
}
for(int i = 1; i <= 12; i++) {
cout << dp[i] << endl;
}
return 0;
}
约数之和 这题不仅分治可以做… 矩阵快速幂 还有后面的数论一个解法 好像也提到过
这里先先补上书上的解法
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int mod = 9901;
const int maxn = 105;
int n, m;
int p[maxn], c[maxn], cnt;
void divide(int n) {
cnt = 0;
for(int i = 2; i <= sqrt(n); i++) {
if(n % i == 0) {
p[++cnt] = i, c[cnt] = 0;
while(n % i == 0)
n /= i, c[cnt]++;
}
}
if(n > 1)
p[++cnt] = n, c[cnt] = 1;
}
int q_mod(int a, int b) {
int res = 1;
while(b){
if(b & 1) res = 1ll* res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}
int dfs(int pt, int ct) {
if(ct == 0) return 1;
if(ct % 2 == 1)
return ((1ll + q_mod(pt, (ct + 1) / 2)) * dfs(pt, (ct - 1) / 2)) % mod;
else
return ((1ll + q_mod(pt, ct / 2)) * dfs(pt, (ct / 2) - 1) % mod + q_mod(pt, ct)) % mod;
}
int main(){
cin >> n >> m;
divide(n);
int ans = 1 ;
if(n == 0) ans = 0;
for(int i = 1; i <= cnt ; i ++ ) {
ans *= dfs(p[i], c[i] * m);
ans %= mod;
}
cout << ans << endl;
return 0;
}
分形之城
补充这个
ps : 坐标旋转公式
(x, y) 旋转 b 度 (逆时针)
s = x cos(b) – y sin(b)
t = x sin(b) + y cos(b)
坐标轴旋转
哔哩哔哩公司氛围 89人发布
