emmm........很久很久以前 把6.2過了 所以emmmmmm 直接跳過 ，從6.1到6.3吧

Fence Rails

題目大意

N<=50個數(shù)A1,A2...

1023個數(shù),每個數(shù)數(shù)值<=128,B

問 A 們能拆分成多少個B,求最多的個數(shù)

樣例 解釋

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 排序，假設(shè)最優(yōu)個數(shù)為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 的枚舉過程加了相同長度的枚舉優(yōu)化 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

題目大意

一個字符串能否通過 正數(shù)次操作使得變?yōu)?/p>

Begin the Escape execution at the Break of Dawn

一次操作: 選取 ...C...O...W...,把C->O的字符串和O->W的字符串交換，然后去掉這三個選中C,O,W

題解

顯然 特判打表

我們已經(jīng)知道 目標(biāo)串 和 起始串

所以如果可行，那么 個數(shù)關(guān)系有C=O=W =(len(起始串)-len(目標(biāo)串))/3,所以預(yù)先篩選的一個優(yōu)化是，統(tǒng)計各個字符的個數(shù)，和目標(biāo)串進行比較

所以 當(dāng)比較是可能時，答案要么0 0,要么 1 字母C 的個數(shù)

我們可以優(yōu)化的點

字母個數(shù)統(tǒng)計

被C O W 分割的在任意時刻是 目標(biāo)串的子串

搜索順序先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 分割的 字串應(yīng)該是Goal的連續(xù)子串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 = Oif(o[0] != c[0] || o[0] != w[0] || w[0] != c[0]) {return false;}char pre[100];strcpy(pre, s); // 遞歸暫存// 查找順序 先找Orep(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]個數(shù)f1,f2..

5 <= R1 < R2 <= 40

在[R1,R2]范圍找[1,10]個數(shù)r1,r2..

ratio(i,j) = fi/rj

在max ratio/min ratio >= 3的限制下

把所有ratio(i,j)排序，最小化 排序后數(shù)組相鄰值 的差 的方差

求具體方案

題解

ratio(i1,j1)/ratio(i2,j2) = i1*j2/i2*j1

要使這個值的最大值大于3,注意到都是正數(shù)，也就是(max(i)*max(j))/(min(i)*min(j)) >= 3

然后因為ratio要先sort，再最小化 差 的方差，就感覺 無路可推，只能暴搜

優(yōu)化

默認(rèn)的限制減枝

個數(shù)少，運算過程相對有序 --> 計算順序+插入排序

搜一搜初中的方差變形公式，省掉最外層的1/n 有只用比較sum{平方}+(sum{}平方)/n

注意 以下代碼過了USACO 但是有潛在風(fēng)險，浮點數(shù)比大小！！ 如果是打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;// 數(shù)據(jù)量小 采用插入排序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);// 相鄰值的差的個數(shù) 比值的個數(shù)少1vf=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; }

總結(jié)

搜索+剪枝，剪究竟要怎么剪

引用一個大佬的話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.

重要的是 找到 能明確改變算法 復(fù)雜度的剪枝。

反過來分析

第1題

剩余 體積 處理，應(yīng)該能優(yōu)化了搜索樹的葉節(jié)點個數(shù)，十分關(guān)鍵

重復(fù)體積的搜索處理，優(yōu)化了枚舉體積的次數(shù)，對相同體積有多個的情況，從 可放空間數(shù)的相同個數(shù)次方，優(yōu)化到了？？？，不知道怎么表示，但是 大量減少了重復(fù)枚舉是肯定的

從大到小嘗試，優(yōu)化了末端個數(shù)？（嗎）

第2題

對于錯誤的預(yù)處理 直接一邊就否定掉了

目標(biāo)串的子串是一個有效的大優(yōu)化，當(dāng) 在 去掉COW 以后，連接出了 不應(yīng)該的字符串，可以立刻剪掉，對搜索空間優(yōu)化大

搜索順序 先O 還好 大概是常數(shù)倍數(shù)優(yōu)化

字符串hash，除了上面的方法，還可以 用其它的 比如神奇的偏移+異或字符串等等， 優(yōu)化的是很大的字符串比較代價，常數(shù)倍數(shù)

第3題

基本沒有剪枝[題目限制的剪枝是當(dāng)然

主要靠的是算法使用的性能優(yōu)化

優(yōu)化 排序[數(shù)量少的時候插入,在具體工程實踐中，數(shù)量較少的時候 也同樣會采取 數(shù)組取代map 進行遍歷，冒泡取代其它排序 ]

優(yōu)化 方差運算，目前這樣公式變化

默認(rèn) n-1次加法 1次除法，算平均數(shù)，n次減法,n次乘法,n-1次加法得到結(jié)果

優(yōu)化后 2(n-1)次加法 1次除法,1次減法n+1次乘法,得到結(jié)果

假設(shè)所有 運算類型時間代價相同，那么算是優(yōu)化掉了約1/4時間[然而一般來說減法的速度是比乘除快很多，再加上CPU的指令pipeline運算優(yōu)化，可能影響有，但不大

轉(zhuǎn)載于:https://www.cnblogs.com/CroMarmot/p/11112572.html

總結(jié)

以上是生活随笔為你收集整理的USACO 6.3 章节 你对搜索和剪枝一无所知QAQ的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。