noip2006总结
T1 能量項鏈
原題
在Mars星球上，每個Mars人都隨身佩帶著一串能量項鏈。在項鏈上有N顆能量珠。能量珠是一顆有頭標記與尾標記的珠子，這些標記對應著某個正整數(shù)。并且，對于相鄰的兩顆珠子，前一顆珠子的尾標記一定等于后一顆珠子的頭標記。因為只有這樣，通過吸盤（吸盤是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標記為m，尾標記為r，后一顆能量珠的頭標記為r，尾標記為n，則聚合后釋放的能量為mrn（Mars單位），新產生的珠子的頭標記為m，尾標記為n。
需要時，Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請你設計一個聚合順序，使一串項鏈釋放出的總能量最大。
例如：設N=4，4顆珠子的頭標記與尾標記依次為(2，3) (3，5) (5，10) (10，2)。我們用記號⊕表示兩顆珠子的聚合操作，(j⊕k)表示第j，k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能量為：
(4⊕1)=1023=60。
這一串項鏈可以得到最優(yōu)值的一個聚合順序所釋放的總能量為
((4⊕1)⊕2)⊕3）=1023+1035+10510=710。
輸入輸出格式
思路
代碼
#include <cstdio> #include <iostream> #include <cstring> #define RG register using namespace std; const int maxn=300+5; inline int read() {int x=0,w=1;char ch=0;ch=getchar();while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();if(ch=='-') w=-1,ch=getchar();while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*w; } int n; long long head[maxn],tail[maxn],f[maxn][maxn]; int main(){n=read();for(RG int i=1;i<=n;i++) head[i]=read();for(RG int i=1;i<n;i++) tail[i]=head[i+1];tail[n]=head[1];int m=n*2-1;for(RG int i=n+1;i<=m;i++){head[i]=head[i-n];tail[i]=tail[i-n];}memset(f,0,sizeof(f));for(RG int p=1;p<=n-1;p++) //枚舉長度 for(RG int i=1;i<=m-1;i++){int j=i+p; // i為頭 j為尾 if(j>m) break;for(RG int k=i;k<=j-1;k++){ //枚舉每一種斷開位置 f[i][j]=max(f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j],f[i][j]);}}long long ans=0;for(RG int i=1;i<=n;i++) ans=max(ans,f[i][i+n-1]); //從所有的斷開位置中選出最大值 printf("%lld\n",ans);return 0; }T2 金明的預算方案
原題
金明今天很開心，家里購置的新房就要領鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早，金明就開始做預算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子：
思路
有條件的背包模型，可以枚舉主件，有不取，取附件A，附件B，兩個附件四種情況。
if j>=a[i,0] then f[j]:=max(f[j],f[j-a[i,0]]+a[i,0]*b[i,0]);//取主件
if j>=a[i,0]+a[i,1] then f[j]:=max(f[j],f[j-a[i,0]-a[i,1]]+a[i,0]*b[i,0]+a[i,1]*b[i,1]);//取第一個附件
if j>=a[i,0]+a[i,2] then f[j]:=max(f[j],f[j-a[i,0]-a[i,2]]+a[i,0]*b[i,0]+a[i,2]*b[i,2]);//取第二個附件
if j>=a[i,0]+a[i,1]+a[i,2] then f[j]:=max(f[j],f[j-a[i,0]-a[i,2]-a[i,1]]+a[i,0]*b[i,0]+a[i,2]*b[i,2]+a[i,1]*b[i,1]);//取三個附件
代碼
#include<iostream> using namespace std; int main() {int a,b,mx=0;int i,j;int m,n,v[61]={0},p[61]={0},q;int v1[61]={0},v2[61]={0},p1[61]={0},p2[61]={0};int f[50001]={0};cin>>m>>n;m/=10;for(i=1;i<=n;i++){cin>>a>>b>>q;a/=10;if(q!=0){if(v1[q]==0){v1[q]=a;p1[q]=b;}else {v2[q]=a;p2[q]=b;}}else {v[i]=a;p[i]=b;}}for(int i=1;i<=n;i++)for(int j=m;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+v[i]*p[i]);if(j-v1[i]-v[i]>=0)f[j]=max(f[j],f[j-v1[i]-v[i]]+v1[i]*p1[i]+v[i]*p[i]);if(j-v2[i]-v[i]>=0)f[j]=max(f[j],f[j-v2[i]-v[i]]+v2[i]*p2[i]+v[i]*p[i]);if(j-v1[i]-v2[i]-v[i]>=0)f[j]=max(f[j],f[j-v1[i]-v2[i]-v[i]]+v1[i]*p1[i]+v2[i]*p2[i]+v[i]*p[i]);mx=max(f[j],mx);}cout<<mx*10;//system("pause");return 0; }作業(yè)調度方案
原題
我們現(xiàn)在要利用m臺機器加工n個工件，每個工件都有m道工序，每道工序都在不同的指定的機器上完成。每個工件的每道工序都有指定的加工時間。
每個工件的每個工序稱為一個操作，我們用記號j-k表示一個操作，其中j為1到n中的某個數(shù)字，為工件號；k為1到m中的某個數(shù)字，為工序號，例如2-4表示第2個工件第4道工序的這個操作。在本題中，我們還給定對于各操作的一個安排順序。
例如，當n=3，m=2時，“1-1，1-2，2-1，3-1，3-2，2-2”就是一個給定的安排順序，即先安排第1個工件的第1個工序，再安排第1個工件的第2個工序，然后再安排第2個工件的第1個工序，等等。
-
一方面，每個操作的安排都要滿足以下的兩個約束條件。
- 對同一個工件，每道工序必須在它前面的工序完成后才能開始；
- 同一時刻每一臺機器至多只能加工一個工件。
-
另一方面，在安排后面的操作時，不能改動前面已安排的操作的工作狀態(tài)。
由于同一工件都是按工序的順序安排的，因此，只按原順序給出工件號，仍可得到同樣的安排順序，于是，在輸入數(shù)據(jù)中，我們將這個安排順序簡寫為“1 1 2 3 3 2”。
還要注意，“安排順序”只要求按照給定的順序安排每個操作。不一定是各機器上的實際操作順序。在具體實施時，有可能排在后面的某個操作比前面的某個操作先完成。
例如，取n=3,m=2，已知數(shù)據(jù)如下：
則對于安排順序“1 1 2 3 3 2”，下圖中的兩個實施方案都是正確的。但所需要的總時間分別是10與12。
當一個操作插入到某臺機器的某個空檔時（機器上最后的尚未安排操作的部分也可以看作一個空檔），可以靠前插入，也可以靠后或居中插入。為了使問題簡單一些，我們約定：
- 在保證約束條件（1）（2）的條件下，盡量靠前插入。并且，我們還約定，如果有多個空檔可以插入，就在保證約束條件（1）（2）的條件下，插入到最前面的一個空檔。于是，在這些約定下，上例中的方案一是正確的，而方案二是不正確的。顯然，在這些約定下，對于給定的安排順序，符合該安排順序的實施方案是唯一的，請你計算出該方案完成全部任務所需的總時間。
格式
輸入格式
輸入文件的第1行為兩個正整數(shù)，用一個空格隔開：
m n （其中m（<20）表示機器數(shù)，n（<20）表示工件數(shù)）
第2行：m*n個用空格隔開的數(shù)，為給定的安排順序。
接下來的2n行，每行都是用空格隔開的m個正整數(shù)，每個數(shù)不超過20。
其中前n行依次表示每個工件的每個工序所使用的機器號，第1個數(shù)為第1個工序的機器號，第2個數(shù)為第2個工序機器號，等等。
后n行依次表示每個工件的每個工序的加工時間。
可以保證，以上各數(shù)據(jù)都是正確的，不必檢驗。
輸出格式
輸出文件只有一個正整數(shù)，為最少的加工時間。
樣例1
樣例輸入
2 3 1 1 2 3 3 2 1 2 1 2 2 1 3 2 2 5 2 4樣例輸出
10思路
- 并無特殊算法，題目較難理解（這是一道語文題）
代碼
#include <stdio.h> const int maxn = 25; int a[maxn*maxn], ord[maxn][maxn], time[maxn][maxn]; int vis[maxn*maxn][maxn*maxn], b[maxn], finish[maxn]; //vis表示用過的區(qū)間,注意數(shù)組問題 inline int Max ( int a, int b ) { return a > b ? a : b; } int main ( ) { //注意最重要的一句話： //同一個工件，每道工序必須在它前面的工序完成后才能開始 int n, m, ans; //freopen ( "in0.in", "r", stdin ); //freopen ( "in0.out", "w", stdout ); scanf ( "%d%d", &m, &n ); for ( int i = 0; i < n*m; i ++ ) { scanf ( "%d", &a[i] ); a[i] --; } for ( int i = 0; i < n; i ++ ) for ( int j = 0; j < m; j ++ ) { scanf ( "%d", &ord[i][j] ); ord[i][j] --; } for ( int i = 0; i < n; i ++ ) for ( int j = 0; j < m; j ++ ) scanf ( "%d", &time[i][j] ); ans = 0; for ( int i = 0; i < n*m; i ++ ) { int t = a[i], j = b[t]; int pos = finish[t]-1, k, sub = ord[t][j]; //pos從此工序完成的起點-1開始,下面會加1 do { pos ++; for ( k = 0; k < time[t][j]; k ++ ) if ( vis[sub][pos+k] ) { pos = pos+k; break ; } }while ( vis[sub][pos] ); for ( int l = pos; l < pos+time[t][j]; l ++ ) vis[sub][l] = 1; //將這段區(qū)間標記 ans = Max ( ans, pos+time[t][j] ); //找到最大時間 finish[t] = pos+k; //表示工序t完成需要的時間 b[t] ++; } printf ( "%d", ans ); return 0; }
2^k進制數(shù)
原題
設r是個2k 進制數(shù)，并滿足以下條件：
（1）r至少是個2位的2k 進制數(shù)。
（2）作為2k 進制數(shù)，除最后一位外，r的每一位嚴格小于它右邊相鄰的那一位。
（3）將r轉換為2進制數(shù)q后，則q的總位數(shù)不超過w。
在這里，正整數(shù)k（1≤k≤9）和w（k<w≤30000）是事先給定的。
問：滿足上述條件的不同的r共有多少個？
我們再從另一角度作些解釋：設S是長度為w 的01字符串（即字符串S由w個“0”或“1”組成），S對應于上述條件（3）中的q。將S從右起劃分為若干個長度為k 的段，每段對應一位2k進制的數(shù)，如果S至少可分成2段，則S所對應的二進制數(shù)又可以轉換為上述的2k 進制數(shù)r。
例：
設k=3，w=7。則r是個八進制數(shù)（23=8）。由于w=7，長度為7的01字符串按3位一段分，可分為3段（即1，3，3，左邊第一段只有一個二進制位），則滿足條件的八進制數(shù)有：
所以，滿足要求的r共有36個。
輸入輸出
輸入
輸入文件digital.in只有1行，為兩個正整數(shù)，用一個空格隔開：
輸出
輸出文件digital.out為1行，是一個正整數(shù)，為所求的計算結果，即滿足條件的不同的r的個數(shù)（用十進制數(shù)表示），要求最高位不得為0，各數(shù)字之間不得插入數(shù)字以外的其他字符（例如空格、換行符、逗號等）。
（提示：作為結果的正整數(shù)可能很大，但不會超過200位）
樣例
輸入
3 7輸出
36思路
題目中的那個從另一角度分析就已經(jīng)蘊含了這個題的基本思路。就以題目的例子為例，長度為7位的01字串按3位一段就這樣分：0 000 000。其中除了首段，每段都小于(111)2，也即小于2k，而首段自然是小于2w%k（對于w%k為0時也成立）了。
如果首段為0，則當這個2k進制數(shù)位數(shù)分別為2、3、…、[n/k]時，如果用b_max表示2k，對應的解的個數(shù)分別為C[b_max-1][2]、C[b_max-1][3]、…、C[b_max-1][n/k]（C[i][j]表示從i個數(shù)里選j個構成一組組合）。
如果首段不為0，設首段為x，則解就有c[b_max-x-1][n/k]個。
這樣，求解的個數(shù)就搞定了，剩下的活就是高精了。求組合數(shù)可以用這個公式：C[n][m]=C[n-1][m-1]+C[n-1][m]，這樣高精就只用加法了。
代碼
#include<iostream> using namespace std; int k,n,bx,hx,ans[201]; int c[512][512][100]; void plus1(int x[],int y[],int z[]) {z[0]=max(x[0],y[0]);for(int i=1;i<=z[0];i++) {z[i]+=x[i]+y[i];z[i+1]+=z[i]/10;z[i]%=10;}if(z[z[0]+1]!=0)z[0]++; } void plus2(int x[],int y[]) {x[0]=max(x[0],y[0]);for(int i=1;i<=x[0];i++) {x[i]+=y[i];x[i+1]+=x[i]/10;x[i]%=10;}if(x[x[0]+1]!=0)x[0]++; } int main() {cin>>k>>n;bx=1<<k;//2^khx=1<<(n%k);for(int i=0;i<=bx;i++)for(int j=0;j<=i;j++){if(j==0)c[i][j][0]=c[i][j][1]=1;else plus1(c[i-1][j],c[i-1][j-1],c[i][j]);}for(int i=2;i<=n/k&&i<bx;i++)plus2(ans,c[bx-1][i]);for(int i=1;i<hx&&n/k+i<bx;i++)plus2(ans,c[bx-i-1][n/k]);for(int i=ans[0];i>=1;i--)cout<<ans[i];cout<<endl;return 0; } ?轉載于:https://www.cnblogs.com/bbqub/p/7599370.html
總結
以上是生活随笔為你收集整理的noip2006总结的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 长安稳盈的动环监测系统怎么样？
- 下一篇： 荣威2021款RX5plus遥控钥匙里的