《算法竞赛进阶指南》 0x21 ~ 0x24 代码 + 杂谈
树与图的遍历
- 可达性统计
给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。
数据 1≤N,M≤30000 这里folyd 跑 不仅数组开不下 还有n^3的复杂度chun
关于 这个点每个状态的用矩阵肯定存不下这些关系 所以可以考虑用int 二进制来进行压缩
还有bitset STL 进行非常长长度二进制存储和运算
可达性就可以考虑 topsort了 找到循序序列 之后 倒着来吧每个点 或 一下 就 吧可达点 付到上一个 完成统计
#include <iostream>
#include <bitset>
#include <queue>
using namespace std;
const int maxn = 3e4 + 5;
int n, m;
int head[maxn], cnt;
int to[maxn << 1], nxt[maxn << 1];
int deg[maxn], seq[maxn], k;
bitset<maxn> f[maxn];
void ade(int a, int b){
to[++ cnt] = b;
nxt[cnt] = head[a];
head[a] = cnt;
}
void topsort(){
queue<int> q;
for(int i = 1; i <= n; i ++ )
if(deg[i] == 0) q.push(i);
while(!q.empty()){
int x = q.front(); q.pop();
seq[++ k] = x;
for(int i = head[x]; i; i = nxt[i]) {
int y = to[i];
if(-- deg[y] == 0) q.push(y);
}
}
}
int main(){
cin >> n >> m;
for(int i = 1, a, b; i <= m; i ++ ) {
cin >> a >> b;
ade(a, b);
deg[b] ++;
}
topsort();
for(int i = n; i >= 1; i --) {
int x = seq[i];
f[x][x] = 1;
for(int j = head[x]; j; j = nxt[j])
f[x] |= f[to[j]];
}
for(int i = 1; i <= n; i ++) cout << f[i].count() << endl;
return 0;
}
DFS
- 小猫爬山
dfs 优化剪枝
首先 我们dfs 每次搜遍历一边考虑能装下 放入猫
这一操作完后 还原 进行不放入这个猫 加 一辆车的搜索
考虑优化 第一 我们排序每次选最大的 可以使开头第一搜索的选择性减低
显然 我们也可以加入 如果当前搜索车数量 大于min （n, ans） 直接return 放弃这个不好的解
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100;
int n, m, ans;
int car[maxn], cat[maxn];
void dfs(int num, int cnt){
if(cnt >= ans) return ;
if(num == n + 1) {
ans = cnt;
return ;
}
for(int i = 1; i <= cnt; i ++) {
if(car[i] + cat[num] <= m) {
car[i] += cat[num];
dfs(num + 1, cnt);
car[i] -= cat[num];
}
}
car[cnt + 1] = cat[num];
dfs(num + 1, cnt + 1);
car[cnt + 1] = 0;
}
bool cmp(int a, int b) {return a > b;}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> cat[i];
sort(cat + 1, cat + 1 + n, cmp);
ans = n;
dfs(1, 0);
cout << ans << endl;
return 0;
}
- Sudoko (acwing数据)
这个题数据好强啊 不预处理位运算超时的
首先考虑 选择可选位置最少的框填入搜索
其次这题必须加入位运算 行列宫 9位2进制表示出来 lowbit 取出最低位 遍历可选值
位元算 记得还原全部状态再进行下次搜索
#include <iostream>
using namespace std;
const int N = 9;
int row[N], col[N];
int ones[1 << N], map[1 << N];
int g[5][5];
char str[105];
inline int lowbit(int x) {
return x & -x;
}
inline int get(int x, int y) {
return row[x] & col[y] & g[x/3][y/3];
}
bool dfs(int cnt) {
if(cnt == 0) return 1;
int minv = 10, x, y;
for(int i = 0 ; i < N; i ++) for(int j = 0; j < N; j ++)
if(str[i * 9 + j] == '.') {
int t = ones[get(i, j)];
if(t < minv) minv = t, x = i, y = j;
}
for(int i = get(x, y); i; i -= lowbit(i)) {
int t = map[lowbit(i)];
row[x] -= 1 << t;
col[y] -= 1 << t;
g[x/3][y/3] -= 1 << t;
str[x * 9 + y] = '1' + t;
if(dfs(cnt - 1)) return 1;
row[x] += 1 << t;
col[y] += 1 << t;
g[x/3][y/3] += 1 << t;
str[x * 9 + y] = '.';
}
return 0;
}
void init(){
for(int i = 0; i < 9; i ++) row[i] = col[i] = (1 << 9) - 1;
for(int i = 0; i < 3; i ++)
for(int j = 0; j < 3; j ++)
g[i][j] = (1 << 9) - 1;
}
int main(){
for(int i = 0; i < N; i ++) map[1 << i] = i;
for(int i = 0; i < 1 << N; i ++) {
int s = 0;
for(int j = i; j; j -= lowbit(j)) s ++;
ones[i] = s;
}
while(cin >> str && str[0] != 'e') {
init();
int cnt = 0;
for(int i =0, k = 0; i < N; i ++)
for(int j = 0; j < N; j ++, k ++ )
if(str[k] != '.') {
int t = str[k] - '1';
row[i] -= 1 << t;
col[j] -= 1 << t;
g[i/3][j/3] -= 1 << t;
}else cnt ++;
dfs(cnt);
cout << str << endl;
}
return 0;
}
优化搜索
- 小木棍
预先处理出所有木棍的总长度，且保证枚举答案的值能被总长度整除。
预先处理出最长的和最短的木棍的长度，搜索时从最大长度到最小长度递减枚举。
若拼接当前木棍时已用了一根长为X的木棍，则dfs时从长度X开始搜索。
若某组拼接不成立 且此时 已拼接的长度为0 或 当前已拼接的长度与刚才枚举的长度之和为最终枚举的答案
则可直接跳出循环，因为此时继续枚举其它更小的值时，显然可能情况更少，且同样凑不完。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 50+5;
int n,m,x,sum,xz,flag,cnt;
bool cmp(int x,int y) {return x>y;}
bool vis[maxn];
int a[maxn];
void dfs(int len,int k,int lenth,int pos){
if(flag) return ;
if(k*lenth==sum){
cout<<lenth<<endl;
flag=1;
return ;
}
if(sum-len<a[cnt]) return ;
if(len==lenth){
dfs(0,k+1,lenth,1);
return ;
}
for(int i=pos;i<=cnt;i++){
if(!vis[i]&&len+a[i]<=lenth){
vis[i]=1;
dfs(len+a[i],k,lenth,i+1);
vis[i]=0;
if(len==0||len+a[i]==lenth) break;
while(a[i]==a[i+1])i++;
}
}
}
int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>m;
if(m<=50){
a[++cnt]=m;
sum+=m;
}
}
sort(a+1,a+1+cnt,cmp);
xz=sum>>1;
for(int i=a[1];i<=xz;i++){
if(sum%i==0){
dfs(0,0,i,1);
if(flag) break;
}
}
if(!flag) cout<<sum<<endl;
return 0;
}
acwing （重写版）
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100 + 5;
const int mod = 1e9 + 7;
int n, sum, len;
int a[maxn], cnt;
bool vis[maxn];
bool cmp(int a, int b) {
return a > b;
}
bool dfs(int k, int len, int p, int lenth){
if(k * lenth == sum) return 1;
if(len == lenth) return dfs(k + 1, 0, 1, lenth);
for(int i = p; i <= cnt; i++){
if(!vis[i] && len + a[i] <= lenth){
vis[i] = 1;
if(dfs(k, len + a[i], i + 1, lenth)) return 1;
vis[i] = 0;
if(len == 0) return 0;
if(len + a[i] == lenth) return 0;
while(a[i] == a[i + 1] && i <= cnt) i++;
}
}
return 0;
}
signed main() {
while(cin >> n && n) {
cnt = 0;
len = 0;
sum = 0;
for(int i = 1, l; i <= n; i ++) {
vis[i] = 0;
cin >> l;
if(l > 50) continue;
sum += l;
a[++ cnt] = l;
len = max (len, l);
}
sort(a + 1, a + cnt, cmp);
for(int i = len; i <= sum; i ++)
if(sum % i == 0 && dfs(0, 0, 1, i)) {
cout << i << endl;
break;
}
}
return 0;
}
- 奶油蛋糕
体积一定 让多层蛋糕表面积最小
最小体积+面积预处理 搜索超过限制return
从 上一层 最大r - 1，h - 1 开始搜索 情况树少
s + 2 * (n - v) / R[dep + 1] >= ans 放缩出来的公式 。。果然只加一层超了 再加也超
#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 100 + 5;
const int mod = 1e9 + 7;
int n, m, ans;
int R[maxn], H[maxn];
int mins[maxn], minv[maxn];
void dfs(int dep, int v, int s){
if(minv[dep] + v > n) return ;
if(mins[dep] + s >= ans) return ;
if(s + 2 * (n - v) / R[dep + 1] >= ans) return ;
if(dep == 0) {
if(v == n) ans = min(ans, s);
return ;
}
for(int r = min((int)sqrt(n - v), R[dep + 1] - 1); r >= dep; r --) {
for(int h = min((n - v) / r / r, H[dep + 1] - 1); h >= dep; h --) {
R[dep] = r, H[dep] = h;
dfs(dep - 1, v + r * r * h, s + 2 * r * h + (dep == m ? r * r : 0));
}
}
return ;
}
signed main() {
cin >> n >> m;
for(int i = 1; i <= 25; i ++) {
minv[i] = minv[i - 1] + i * i * i;
mins[i] = mins[i - 1] + i * i * 2;
}
R[m + 1] = H[m + 1] = 0x3f3f3f3f;
ans = 0x3f3f3f3f;
dfs(m, 0, 0);
cout << ans << endl;
return 0;
}
迭代加深
- 加成序列
预先设置深度， 搜索再树浅位置解
#include <iostream>
using namespace std;
const int maxn = 105;
int n;
int path[maxn];
bool dfs(int u, int k){
if (u == k) return path[u - 1] == n;
bool vis[maxn] = {0};
for (int i = u - 1; i >= 0; i -- )
for (int j = i; j >= 0; j -- ){
int s = path[i] + path[j];
if (s > n || s <= path[u - 1] || vis[s]) continue;
vis[s] = true;
path[u] = s;
if (dfs(u + 1, k)) return true;
}
return false;
}
int main(){
path[0] = 1;
while (cin >> n, n){
int k = 1;
while (!dfs(1, k)) k ++ ;
for (int i = 0; i < k; i ++ ) cout << path[i] << ' ';
cout << endl;
}
return 0;
}
双向搜索
- 送礼物
先优化搜索顺序
其次 先搜前一半 dfs出所有情况
再dfs后面n个 这样二分查可能最大值 不用在意dp数据量太。。。。orz
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 105;
int n, m, ans, k;
int w[maxn];
int wes[1 << 24], cnt;
void dfs1(int u, int s) {
if(u == k) {
wes[cnt ++] = s;
return ;
}
if((ll)s + w[u] <= m) dfs1(u + 1, s + w[u]);
dfs1(u + 1, s);
}
void dfs2(int u, int s) {
if(u == n) {
int l = 0, r = cnt - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if((ll)wes[mid] + s <= m) l = mid;
else r = mid - 1;
}
if((ll)wes[l] + s <= m) ans = max(ans, wes[l] + s);
return ;
}
if((ll)s + w[u] <= m) dfs2(u + 1, s + w[u]);
dfs2(u + 1, s);
}
bool cmp(int a, int b) {return a > b;}
int main(){
cin >> m >> n;
for(int i = 0; i < n; i ++) cin >> w[i];
sort(w, w + n, cmp);
k = n/2 + 2;
dfs1(0, 0);
sort(wes, wes + cnt);
cnt = unique(wes, wes + cnt) - wes;
dfs2(k, 0);
cout << ans << endl;
return 0;
}
