USACO 6.3 章节 你对搜索和剪枝一无所知QAQ
emmm........很久很久以前 把6.2过了 所以emmmmmm 直接跳过 ，从6.1到6.3吧
Fence Rails
题目大意
N<=50个数A1,A2...
1023个数,每个数数值<=128,B
问 A 们能拆分成多少个B,求最多的个数
样例 解释
A:
30=30
40=18+19+3
50=15+16+17+2
25=24
B:
15 (ok)
16 (ok)
17 (ok)
18 (ok)
19 (ok)
20
21
25
24 (ok)
30 (ok)所以最多7个
题解
首先 如果对B 排序，假设最优个数为k个
显然 如果k个可行，那么排序后的B 的前k个可行
又 如果k个可行那么k-1个可行，综上又满足二分
先 sort+二分+从大到小放b （第4个点就超时了）
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
using namespace std;
const string filename = "fence8";
void usefile(){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
int n;
int a[100];
int la[100];
int suma;
int R;
int r[1100];
int sumr[1100];
int dfs(int idx){
per(i,0,n){
if(a[i] < r[idx]){
return false;
}
if(a[i] == a[i+1] && la[i] == la[i+1]){
continue;
}
if(la[i] < r[idx]){
continue;
}
if(idx == 0){
return true;
}
la[i] -= r[idx];
int ret = dfs(idx-1);
la[i] += r[idx];
if(ret){
return true;
}
}
return false;
}
bool test(int idx){
if(sumr[idx] > suma)return false;
return dfs(idx);
}
int main(){
usefile();
scanf("%d",&n);
rep(i,0,n){
scanf("%d",a+i);
}
rep(i,0,n){
la[i]=a[i];
suma += a[i];
}
sort(a,a+n);
scanf("%d",&R);
rep(i,0,R){
scanf("%d",r+i);
}
sort(r,r+R);
if(r[0] > a[n-1]){
cout<<0<<endl;
return 0;
}
sumr[0]=r[0];
rep(i,1,R){
sumr[i]=sumr[i-1]+r[i];
}
int l=0,r=R;
while(l+1<r){
int mid = (l+r)/2;
if(test(mid)){
l = mid;
}else{
r = mid;
}
}
cout<<l+1<<endl;
return 0;
}对B 的枚举过程加了相同长度的枚举优化 tle 5
int dfs(int idx,int stn = n){
per(i,0,stn){
if(a[i] < r[idx]){
return false;
}
if(a[i] == a[i+1] && la[i] == la[i+1]){
continue;
}
if(la[i] < r[idx]){
continue;
}
if(idx == 0){
return true;
}
la[i] -= r[idx];
int ret;
if(r[idx] == r[idx+1]){
ret = dfs(idx-1,i+1);
}else{
ret = dfs(idx-1);
}
la[i] += r[idx];
if(ret){
return true;
}
}
return false;
}增加了 无效残余木料 AC
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
using namespace std;
const string filename = "fence8";
void usefile(){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
int n;
int a[100];
int la[100];
int suma;
int R;
int r[1100];
int sumr[1100];
int dfs(int idx,int stn = n){
if(suma < sumr[idx]){
return false;
}
per(i,0,stn){
if(a[i] < r[idx]){
return false;
}
if(a[i] == a[i+1] && la[i] == la[i+1]){
continue;
}
if(la[i] < r[idx]){
continue;
}
if(idx == 0){
return true;
}
la[i] -= r[idx];
suma-=r[idx];
bool predel = la[i] < r[0];
if(predel){
suma -= la[i];
}
int ret;
if(idx > 0 && r[idx-1] == r[idx]){
ret = dfs(idx-1,i+1);
}else{
ret = dfs(idx-1);
}
if(predel){
suma += la[i];
}
suma+=r[idx];
la[i] += r[idx];
if(ret){
return true;
}
}
return false;
}
bool test(int idx){
if(sumr[idx] > suma)return false;
return dfs(idx);
}
int main(){
usefile();
scanf("%d",&n);
rep(i,0,n){
scanf("%d",a+i);
}
rep(i,0,n){
la[i]=a[i];
suma += a[i];
}
sort(a,a+n);
scanf("%d",&R);
rep(i,0,R){
scanf("%d",r+i);
}
sort(r,r+R);
if(r[0] > a[n-1]){
cout<<0<<endl;
return 0;
}
sumr[0]=r[0];
rep(i,1,R){
sumr[i]=sumr[i-1]+r[i];
}
int l=0,r=R;
while(l+1<r){
int mid = (l+r)/2;
if(test(mid)){
l = mid;
}else{
r = mid;
}
}
cout<<l+1<<endl;
return 0;
}综上 二分+暴搜+减枝+处理顺序贪心
Cryptcowgraphy
题目大意
一个字符串能否通过 正数次操作使得变为
Begin the Escape execution at the Break of Dawn
一次操作: 选取 ...C...O...W...,把C->O的字符串和O->W的字符串交换，然后去掉这三个选中C,O,W
题解
显然 特判打表
我们已经知道 目标串 和 起始串
所以如果可行，那么 个数关系有C=O=W =(len(起始串)-len(目标串))/3,所以预先筛选的一个优化是，统计各个字符的个数，和目标串进行比较
所以 当比较是可能时，答案要么0 0,要么 1 字母C 的个数
我们可以优化的点
- 字母个数统计
- 被C O W 分割的在任意时刻是 目标串的子串
- 搜索顺序先O
- 字符串hash [注意 这个方法 如果你是在打cf，那么很可能被hack
注意输入是一行....所以不要scanf %s
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
using namespace std;
const string filename = "cryptcow";
void usefile(){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
const char Goal[] = "Begin the Escape execution at the Break of Dawn";
const int Mod = 999983;
char s[110];
int ans, cnt;
bool hsh[Mod];
// 删除a b c位置上的, 交换a->b b->c
void work(int a, int b, int c) {
static char tmp[100];
int len = strlen(s), tot = 0;
for(int i = 0; i < a; ++i) {
tmp[tot++] = s[i];
}
for(int i = b + 1; i < c; ++i) {
tmp[tot++] = s[i];
}
for(int i = a + 1; i < b; ++i) {
tmp[tot++] = s[i];
}
for(int i = c + 1; i < len; ++i) {
tmp[tot++] = s[i];
}
tmp[tot] = 0;
strcpy(s, tmp);
}
int getHash() {
int ret = 0, len = strlen(s);
for(int i = 0; i < len; ++i) {
int num = (s[i]==' ')?1:(isupper(s[i]) ? s[i] - 'A' + 2 : s[i] - 'a' + 28);
ret = (ret * 57 + num) % Mod;
}
return ret;
}
bool dfs(int depth) {
if(strcmp(s, Goal) == 0) {
ans = depth;
return true;
}
int x = getHash();
if(hsh[x]) {
return false;
}
hsh[x] = true;
++cnt;
// 被C O W 分割的 字串应该是Goal的连续子串
static char sub[100];
int len = strlen(s);
int c[20], o[20], w[20];
c[0] = o[0] = w[0] = 0;
for(int i = 0, j = 0; i < len; ++i) {
if(s[i] == 'C' || s[i] == 'O' || s[i] == 'W') {
if(s[i] == 'C') {
c[++c[0]] = i;
}
if(s[i] == 'O') {
o[++o[0]] = i;
}
if(s[i] == 'W') {
w[++w[0]] = i;
}
sub[j] = 0;
if(!strstr(Goal, sub)) { //
return false;
}
j = 0;
}
else {
sub[j++] = s[i];
}
}
// C = W = O
if(o[0] != c[0] || o[0] != w[0] || w[0] != c[0]) {
return false;
}
char pre[100];
strcpy(pre, s); // 递归暂存
// 查找顺序 先找O
rep(j,1,o[0]+1){
per(k,1,w[0]+1){
if(w[k] < o[j])break;
rep(i,1,c[0]+1){
if(c[i] > o[j])break;
work(c[i], o[j], w[k]);
bool ret = dfs(depth + 1);
if(ret){
return true;
}
if(cnt > 200000) { // ............................
return false;
}
strcpy(s, pre);
}
}
}
return false;
}
int main() {
usefile();
cin.getline(s,100);
// scanf("%s",s);
int ret = dfs(0);
printf("%d %d\n", ret, ans);
return 0;
}Cowcycles
题目大意
25 <= F1 < F2 <= 80
在[F1,F2]范围找[1,5]个数f1,f2..
5 <= R1 < R2 <= 40
在[R1,R2]范围找[1,10]个数r1,r2..
ratio(i,j) = fi/rj
在max ratio/min ratio >= 3的限制下
把所有ratio(i,j)排序，最小化 排序后数组相邻值 的差 的方差
求具体方案
题解
ratio(i1,j1)/ratio(i2,j2) = i1*j2/i2*j1
要使这个值的最大值大于3,注意到都是正数，也就是(max(i)*max(j))/(min(i)*min(j)) >= 3
然后因为ratio要先sort，再最小化 差 的方差，就感觉 无路可推，只能暴搜
优化
- 默认的限制减枝
- 个数少，运算过程相对有序 --> 计算顺序+插入排序
- 搜一搜初中的方差变形公式，省掉最外层的
1/n有只用比较sum{平方}+(sum{}平方)/n
注意 以下代码过了USACO 但是有潜在风险，浮点数比大小！！ 如果是打cf，可能会被叉
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
using namespace std;
const string filename = "cowcycle";
void usefile(){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
int s1[20],s2[20];
int ans1[20],ans2[20];
int F,F1,F2;
int R,R1,R2;
int cnt;
double rate[100],diff[100];
double minvf=10000000;
void count(){
int k=0;
double sum=0,avg,vf=0,sumf=0,p;
// 数据量小 采用插入排序
rep(i,0,F){
rep(j,0,R){
p=(double)s1[i]/s2[j];
int l=++k;
while (rate[l-1]>=p) {
rate[l]=rate[l-1];
l--;
}
rate[l]=p;
}
}
rep(i,1,cnt){
diff[i]=rate[i+1]-rate[i];
sum+=diff[i];
sumf+=diff[i]*diff[i];
}
avg=sum/(cnt-1);// 相邻值的差的个数 比值的个数少1
vf=sumf-sum*avg;
if (vf<minvf) {
minvf=vf;
memcpy(ans1,s1,sizeof(int)*F);
memcpy(ans2,s2,sizeof(int)*R);
}
}
// 枚举后齿轮 从w 到R2-R+k+1
void sc2(int k,int w){
if (k==R){
if (s1[F-1]*s2[R-1]<3*s1[0]*s2[0]) // 题目限制条件剪枝
return;
count();
return;
}
rep(i,w,R2-R+k+2){
s2[k]=i;
sc2(k+1,i+1);
}
}
// 枚举前齿轮 从w到F2-F+k+1
void sc1(int k,int w){
if (k==F) {
sc2(0,R1);
return;
}
rep(i,w,F2-F+k+2){
s1[k]=i;
sc1(k+1,i+1);
}
}
int main() {
usefile();
cin>> F >> R >> F1 >> F2 >> R1 >> R2;
cnt=F*R;
sc1(0,F1);
rep(i,0,F){
cout << ans1[i] << " \n"[i==F-1];
}
rep(i,0,R){
cout << ans2[i] << " \n"[i==R-1];
}
return 0;
}
总结
搜索+剪枝，剪究竟要怎么剪
引用一个大佬的话https://apps.topcoder.com/forums/?module=Thread&threadID=669047&start=0&mc=6#1216077
Well, if the optimizations change the complexity of the solution asymptotically, you can quite sure.
Otherwise you can't depend on anything, I think.
重要的是 找到 能明确改变算法 复杂度的剪枝。
反过来分析
第1题
剩余 体积 处理，应该能优化了搜索树的叶节点个数，十分关键
重复体积的搜索处理，优化了枚举体积的次数，对相同体积有多个的情况，从 可放空间数的相同个数次方，优化到了？？？，不知道怎么表示，但是 大量减少了重复枚举是肯定的
从大到小尝试，优化了末端个数？（吗）
第2题
对于错误的预处理 直接一边就否定掉了
目标串的子串是一个有效的大优化，当 在 去掉COW 以后，连接出了 不应该的字符串，可以立刻剪掉，对搜索空间优化大
搜索顺序 先O 还好 大概是常数倍数优化
字符串hash，除了上面的方法，还可以 用其它的 比如神奇的偏移+异或字符串等等， 优化的是很大的字符串比较代价，常数倍数
第3题
基本没有剪枝[题目限制的剪枝是当然
主要靠的是算法使用的性能优化
优化 排序[数量少的时候插入,在具体工程实践中，数量较少的时候 也同样会采取 数组取代map 进行遍历，冒泡取代其它排序 ]
优化 方差运算，目前这样公式变化
默认 n-1次加法 1次除法，算平均数，n次减法,n次乘法,n-1次加法得到结果
优化后 2(n-1)次加法 1次除法,1次减法n+1次乘法,得到结果
假设所有 运算类型时间代价相同，那么算是优化掉了约1/4时间[然而一般来说减法的速度是比乘除快很多，再加上CPU的指令pipeline运算优化，可能影响有，但不大
本文其它博客链接
牛客:https://blog.nowcoder.net/n/2773db6ff811467a922070d9a5c64a39
github:https://yexiaorain.github.io/Blog/2019-07-01-USACO-6.3/
华为工作强度 838人发布