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 的个数

我们可以优化的点

  1. 字母个数统计
  2. 被C O W 分割的在任意时刻是 目标串的子串
  3. 搜索顺序先O
  4. 字符串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. 默认的限制减枝
  2. 个数少，运算过程相对有序 --> 计算顺序+插入排序
  3. 搜一搜初中的方差变形公式，省掉最外层的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://www.cnblogs.com/CroMarmot/p/11112572.html

github:https://yexiaorain.github.io/Blog/2019-07-01-USACO-6.3/

全部评论

相关推荐

11-25 15:30
已编辑
麻城理工学校 嵌入式软件开发
秋招真的有不焦虑的人吗？
最近又搬回宿舍了，在工位坐不住，写一写秋招起伏不断的心态变化，也算对自己心态的一些思考表演式学习从开始为实习准备的时候就特别焦虑，楼主一开始选择的是cpp后端，但是24届这个方向已经炸了，同时自己又因为本科非92且非科班，所以感到机会更加迷茫。在某天晚上用java写出hello&nbsp;world并失眠一整晚后选择老本行干嵌入式。理想是美好的，现实情况是每天忙但又没有实质性进展，总是在配环境，调工具，顺带还要推科研。而这时候才发现自己一直在表演式学习，徘徊在设想如何展开工作的循环里，导致没有实质性进展。现在看来当时如果把精力专注在动手写而不是两只手端着看教程，基本功或许不会那么差。实习的焦虑5月，楼主...
耶比：哲学上有一个问题，玛丽的房间：玛丽知道眼睛识别色彩的原理知道各种颜色，但是她生活在黑白的房间里，直到有一天玛丽的房门打开了她亲眼看到了颜色，才知道什么是色彩。我现在最大可能的减少对非工作事情的思考，如果有一件事困扰了我， 能解决的我就直接做（去哪里或者和谁吵架等等……），解决不了的我就不想了，每一天都是最年轻的一天，珍惜今天吧
投递比亚迪等公司10个岗位 > 秋招被确诊为…… 牛客创作赏金赛
点赞 评论 收藏
分享
11-23 09:35
北京理工大学 Java
说说字节两年工作体验
一开始字节的氛围还不错，大家都在努力推动&nbsp;TikTok&nbsp;的国际化，翻译文档、说英语，甚至还成立了各种小组来解决沟通问题，感觉一切都在朝着好的方向发展。不过，后面就开始变味了。文档永远跟不上，大家觉得写文档浪费时间，结果就是你得自己去找人问，很多时候人家根本不理你。还有就是公司文化，管理层和普通员工之间的距离感太大了，完全不顾员工的工作体验。大家都在拼命追求结果，根本不在乎你是否累得脱发、婚姻危机。每次你需要支持的时候，经理们总是让你自己去找人。同事之间的关系也很微妙，大家为了自保，第一反应就是投诉和甩锅，完全没有合作的氛围。
字节跳动公司氛围 558人发布
点赞 评论 收藏
分享
11-11 09:31
香港中文大学 后端
“面试官出车祸了今天面试要取消了”
Hello_WordN：咱就是说，除了生命其他都是小事，希望面试官平安，希望各位平时也多注意安全
点赞 评论 收藏
分享
10-08 00:57
门头沟学院 Java
点赞 评论 收藏
分享
11-24 12:23
快手_电商_支付技术(实习员工)
分享一下我的日常实习经历
bg中下流211本，26后端选手欢迎大佬们与我多多交流，互相学习~美团&nbsp;-&nbsp;火车票供应链组一面（7.3），第一次面大厂，很激动紧张，答出来80%，还是挂了字节&nbsp;-&nbsp;火山引擎一面（8.1），都答上来了，反馈说26届不适合业务对接，估计没hc了，但是hr说面评很好小米&nbsp;-&nbsp;一面（8.1），面试官评价很好阿里&nbsp;-&nbsp;高德地图（8.2），被狠狠拷打了，疯狂问，一直问到不会为止，还是自己太菜了小米&nbsp;-&nbsp;二面（8.2）oc快手&nbsp;-&nbsp;商业化一面（8.8）快手&nbsp;-&nbsp;商业化二面（8.9）oc字节&nbsp;-&nbsp;Data（8.12），计网操作系统场景题，一道mid，一道hard，mid手撕出来了，对于hard（课程表，方法是...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
233277次浏览 2030人参与
# 在职场上，你最讨厌什么样的同事 #
5712次浏览 81人参与
# 阿里云管培生offer #
58957次浏览 1748人参与
# 25届秋招总结 #
396497次浏览 3975人参与
# 哪些公司校招卡第一学历 #
32829次浏览 105人参与
# 地方国企笔面经互助 #
6535次浏览 16人参与
# 北方华创开奖 #
66002次浏览 549人参与
# ai智能作图 #
21346次浏览 262人参与
# 硬件兄弟们 甩出你的华为奖状 #
77942次浏览 625人参与
# 实习，投递多份简历没人回复怎么办 #
2435790次浏览 34703人参与
# 工作中，你有没有遇到非常爱骂人的领导？ #
4723次浏览 47人参与
# 实习与准备秋招该如何平衡 #
722786次浏览 8551人参与
# 我的实习求职记录 #
6121326次浏览 83953人参与
# 如果再来一次，你还会选择这个工作吗？ #
110423次浏览 1109人参与
# 25届机械人为了秋招做了哪些准备？ #
24989次浏览 355人参与
# 签了三方后想毁约怎么办 #
18563次浏览 111人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
9952次浏览 213人参与
# 机械求职避坑tips #
22153次浏览 240人参与
# 游戏求职进展汇总 #
52758次浏览 344人参与
# 夸夸我的求职搭子 #
132017次浏览 1360人参与
# 腾讯求职进展汇总 #
207561次浏览 1694人参与
# 实习想申请秋招offer，能不能argue薪资 #
35782次浏览 308人参与
牛客网
牛客企业服务