預計分數：100+50+50 實際分數：5+50+100 =.= 多重背包 (backpack.cpp/c/pas) (1s/256M) 題目描述 提供一個背包，它最多能負載重量為W的物品。 現在給出N種物品：對於第i類物品，一共有Ci件物品；對於每一件物品，重量為Wi，價值為Vi。 找出一種裝載方 ...
預計分數：100+50+50
實際分數：5+50+100
=.=
多重背包
(backpack.cpp/c/pas)
(1s/256M)
題目描述
提供一個背包，它最多能負載重量為W的物品。
現在給出N種物品：對於第i類物品，一共有Ci件物品；對於每一件物品，重量為Wi，價值為Vi。
找出一種裝載方式使得背包中的物品總價值最大。
輸入格式(backpack.in)
第一行兩個整數N，W，代表物品的種類與背包的總負重。
第2～N+1行，每行三個整數Wi, Vi, Ci，代表第i種物品的重量、價值與數量。
輸出格式(backpack.out)
僅一行，一個整數V，代表最大的總價值。
樣例輸入
3 9
5 8 2
3 6 2
2 1 5
樣例輸出
14
數據範圍與限制
1<=N<=20, 0<=W<=1000
1<=Wi<=100, 0<=Vi<=100, 0<=Ci<=100
一看見這道題的時候，我馬上想到了動態規劃完全背包問題，但無奈因為學習動歸年代久遠+沒怎麼學好，只能默默地打暴力；
數據範圍也挺小，老師的意思應該就是讓我們暴力。。
二十分鐘打完暴力，然後我習慣性的做了幾組極端數據改了改小錯誤就過了，
但是。。。。。。。。
因為我寫的回溯比較特殊。。。、
所以。。。。。。。。
只能過極端數據。。。。
。。。。。。。
我竟然，，被這種水題淹死了，，，
AC 代碼：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<stack> 6 #include<queue> 7 #include<algorithm> 8 using namespace std; 9 struct node 10 { 11 int w;//重量 12 int v;//價值 13 int num;//數量 14 int gdnum; 15 }a[40]; 16 int n,m; 17 int ans=0; 18 void dfs(int nownum,int nowv,int noww)// 當前 背包編號 價值 重量 19 { 20 if(nowv>ans&&noww<=m) {ans=nowv;} 21 if(noww>m||nownum>n)return; 22 23 int p=a[nownum].gdnum; 24 25 for(int i=0;i<=p;i++) 26 { 27 if(a[nownum].num>0) 28 { 29 a[nownum].num=a[nownum].num-i; 30 dfs(nownum+1,nowv+a[nownum].v*i,noww+a[nownum].w*i); 31 a[nownum].num=a[nownum].num+i; 32 } 33 } 34 35 36 //dfs(nownum+1,nowv,noww); 37 } 38 int main() 39 { 40 //freopen("backpack.in","r",stdin); 41 //freopen("backpack.out","w",stdout); 42 43 scanf("%d%d",&n,&m); 44 45 for(int i=1;i<=n;i++) 46 { 47 scanf("%d%d%d",&a[i].w,&a[i].v,&a[i].num); 48 a[i].gdnum=a[i].num; 49 } 50 51 52 dfs(1,0,0); 53 54 printf("%d",ans); 55 56 fclose(stdin); 57 fclose(stdout); 58 return 0; 59 }
迴圈序列
(circulate.cpp/c/pas)
(1s/256M)
題目描述
Alice與Bob在玩游戲：
Alice首先給出兩個數X與Y（X<=Y）；
Bob則按順序將X,X+1,X+2,…,Y-1,Y寫成一個大數S。
Alice最後將S首尾相連，讓其圍成一個圈。
這時，Bob想知道，從S的開頭出發，往後的第L位到第R位數字之和是多少。
輸入格式(circulate.in)
第一行四個整數X，Y，L，R,代表Alice的兩個數字和Bob想要知道的第L位到第R位的數字之和。
輸出格式(circulate.out)
僅一行，一個整數M，代表第L位到第R位的數字之和。
樣例輸入
10 11 4 12
樣例輸出
7
樣例解釋
Bob將數字寫成一行大數S = 1011；圍成一個圈後，從第4位到第12位分別是1,1,0,1,1,1,0,1,1，它們的和是7.
數據範圍與限制
對於50%的數據，L=1, X,Y,L,R<=1000；
對於100%的數據，S的長度不大於10000，X,Y,L,R<=100000000.
一開始讀題有些懵逼，但想了一會兒才發現也不是很難，也就是數據處理比較繁瑣。
於是二話不說就開始模擬。。。
但是敲完之後一看數據範圍才發現撐死也就過百分之五十的數據
想了一會兒又沒有想出什麼好演算法來。。。。
so硬著頭皮交了份模擬暴力代碼
果不其然->50分
正解：
因為從l-r很可能出現迴圈計算的情況，所以我們直接求出l和r對於生成字元串的倍數再加上餘數即可
因為在迴圈計算生成字元串的每一位數字的時候非常繁瑣，所以我們可以做一個首碼和，這樣可以大大降低時間複雜度
超時代碼：
TLE
AC代碼：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int x,y,l,r; 5 int a[10001]; 6 int numa=1; 7 int b[1001]; 8 int numb=1; 9 int qiu(int o) 10 { 11 return o/numa*a[numa]+a[o%numa]; 12 } 13 int main() 14 { 15 scanf("%d%d%d%d",&x,&y,&l,&r); 16 for(int i=x;i<=y;i++) 17 { 18 int p=i; 19 numb=1; 20 while(p!=0) 21 { 22 b[numb++]=p%10; 23 p=p/10; 24 } 25 for(int i=numb-1;i>=1;i--) 26 { 27 a[numa++]=b[i]; 28 } 29 } 30 numa--; 31 for(int i=1;i<=numa;i++) 32 { 33 a[i]=a[i-1]+a[i]; 34 } 35 cout<<qiu(r)-qiu(l-1);// -1是為了方式l號元素數兩遍 36 return 0; 37 }AC
合併游戲
merge.cpp/c/pas
(1s/256M）
題目描述
Cindy和Dan在玩一個游戲。
一開始Cindy想出了N個數，接著她把這N個數全部給了Dan。
Dan得到這組數後，它會挑出3個數（如果不足3個則全部挑出）。Dan會把這幾個數加起來變成一個數，然後再把這個數與剩下的數再放到一起。Dan會一直這樣做，直到最後只剩下一個數。
Cindy則會在旁邊記下每次Dan得到的數，她把這些數加起來，作為本次游戲的得分。她想知道，對於一組數，Dan能得到的最大的得分是多少？
輸入格式
第一行一個正整數N，代表這組數的個數；
第二行N個正整數，代表這N個整數。
輸出格式
一行一個整數，代表可能的最大得分。
樣例輸入(merge.in)
4
3 1 5 6
樣例輸出(merge.out)
29
樣例解釋
Dan可以首先把(3，5，6)這三個數先合併起來，得到3 + 5 + 6 = 14; 接著他把剩下的兩個數再合起來，得到1 + 14 = 15.這樣，總得分是最大的 14 + 15 = 29.
數據範圍與限制
對於50%的數據，N<=10
對於100%的數據，N<=1000，所有數不大於1000
當我讀完題目的時候，我就想到了動態規劃，想到了堆，想到了貪心，想到了優先隊列。。。。
但是哪一個都不會，，，，。。，，。，。，。，。。
so還是跟著感覺模擬
沒想到最後居然AC了=。=
好狗血。。。。。。
AC代碼
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<stack> 6 #include<queue> 7 #include<algorithm> 8 using namespace std; 9 int n; 10 int a[10001]; 11 int ans=0; 12 int flag=0; 13 int now=0; 14 int comp(const int &a ,const int & b) 15 { 16 return a>b; 17 } 18 void gett() 19 { 20 now=0; 21 if(a[1]!=-1&&a[2]==-1) 22 { 23 //ans=ans+a[1]; 24 flag=1; 25 return ; 26 } 27 for(int i=1;i<=3;i++) 28 { 29 if(a[i]==-1)continue; 30 now=now+a[i]; 31 a[i]=-1; 32 } 33 ans=ans+now; 34 a[1]=now; 35 sort(a+1,a+n+1,comp); 36 } 37 int main() 38 { 39 freopen("merge.in","r",stdin); 40 freopen("merge.out","w",stdout); 41 scanf("%d",&n); 42 43 for(int i=1;i<=n;i++) 44 scanf("%d",&a[i]); 45 46 sort(a+1,a+n+1,comp); 47 48 while(flag==0) 49 { 50 gett(); 51 } 52 53 printf("%d",ans); 54 fclose(stdin); 55 fclose(stdout); 56 return 0; 57 }AC
總結：
這次考試，不能說考的很好，因為我們學校有兩位大神拿了滿分，這個差距絕對不是一丁半點的，從思路到代碼，從樣例到極端數據，他們的能力遠遠在我之上
但又不能說考的很壞，起碼沒有犯跟前三次考試一樣的超低級錯誤（其實第一個題也犯了次低級錯誤=.=），也算是一個轉折點
第一題爆零（確實不值）
第二題超時（思維太窄）
第三題AC（有點運氣）
至少沒有出現那種一點思路都沒有純懵逼的題目，說明自己還有提升的空間
加油！
