NOIP1995 普及組 編碼問題 code

【問題描述】

設有一個數組 A ： ARRAY[0..N-1] OF INTEGER ；數組中存儲的元素為 0-N-1 之間的整數，且 A[I] ≠ A[J] ( 當 I ≠ J) 時。

例如： N=6 時，有：（ 4 ， 3 ， 0 ， 5 ， 1 ， 2 ）

此時，數組 A 的編碼定義如下：

A[0] 的編碼為 0 ：

A[I] 的編碼為：在 A[0] ， A[1] ，…… A[I-1] 中比 A[I] 的值小的元素的個數（ I=1 ， 2 ，…… N-1 ）

所以上面數組 A 的編碼為 :B=(0,0,0,3,1,2)

程序要求解決以下問題

① 給出數組 A 後，求出其編碼；

② 給出數組 A 的編碼後，求出 A 的原資料。

[數值遞推]OI練習題：整理牙刷 put 解題報告

【問題描述】

衆所周知，XW同學早晨起來是要刷牙的。

XW同學有 N 支牙刷，又有 N 個牙刷套 , 開始的時候，一支牙刷對應放在一個牙刷套中。可是有一天，XW同學把所有牙刷套裏的牙刷都拿出來，玩了一會兒，他又要把所有的牙刷都放回去。可是，他忽然一想，我可不可以使得沒有任何一支牙刷放回它原來的牙刷套裏面呢 ?

XW同學努力試了很久，卻一直沒有成功過一次。於是他斷定這個要求是無法達成的，你怎麼認爲的呢 ?

【輸入文件】

輸入文件 put.in 只包括一個整數 N ，表示牙刷和牙刷套的總數。

【輸出文件】

輸出文件 put.out ，如果存在滿足要求的方法，輸出放法方案總數 L 。因爲方案總數可能比較大，所以你可以將答案 Mod 1206 後再輸出。如果不存在滿足要求的方法，則輸出 "No Solution!”

【樣例輸入】

3

【樣例輸出】

2

【數據範圍】

對於 40 ％的數據，保證 N ≤ 9

對於 100 ％的數據，保證 N ≤ 100000

【分析】

就是一個公式，沒什麼好說的。

F[1]=0;

F[2]=1;

F[i]=(i-1)*(F[i-1]+F[i-2]) (i>=3)

注意同餘原理的應用。

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
unsigned long long F[100001];
int main()
{
    freopen("put.in","r",stdin);
    freopen("put.out","w",stdout);
    int N;
    scanf("%d\n",&N);
    F[1]=0;
    F[2]=1;
    for (int i=3;i<=N;i++)
        F[i]=((i-1)*(F[i-1]+F[i-2]))%1206;
    if(N<2)
        cout<<"No Solution!"<<endl;
    else
        cout<<F[N]<<endl;
    return 0;
}

[數值遞推]NOIP模擬題 ：產生01串 infinit 解題報告

【問題描述】

我們按以下方式產生序列：

1、 開始時序列是： " 1 " ；

2、 每一次變化把序列中的 " 1 " 變成 " 10 " ，" 0 " 變成 " 1 "。

經過無限次變化，我們得到序列" 1011010110110101101... "。

總共有 Q 個詢問，每次詢問爲：在區間A和B之間有多少個1。

任務 寫一個程序回答 Q個詢問

輸入 第一行爲一個整數 Q，後面有Q行，每行兩個數用空格隔開的整數 a , b 。

輸出 共 Q行，每行一個回答

約定

1 <= Q <= 5000

1 <= a <= b < 2^63

樣例

infinit.in	infinit.out
1 2 8	4

測試數據下載：http://zyf.ucoz.net/testdata/infinit.rar

【分析】

S1 = "1"
S2 = "10"
S3 = "101"
S4 = "10110"
S5 = "10110101"

Si 是 S(i+1)的前綴。

序列Si 是由序列 S(i-1)和S(i-2), 連接而成的。

即Si = S(i-1)+S(i-2) (實際上是Fibonacci數列)。

找到規律以後，可以先求出從位置1到位置X之間所有的1的個數。

用一個函數F計算，結果爲f(b)-f(a-1)。

每一項1的個數以及每一項的長度都符合數列規律.長度的第93項恰好大於2^63,所以遞推到92項即可  

 【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
unsigned long long F[95];
unsigned long long L[95];

unsigned long long Getm(unsigned long long  x)
{
    int i1;
    unsigned long long getm=0;
    while(x!=0)
    {
        for(i1=1;i1<=92;i1++)
        {
            if(L[i1]>x)
            {
                getm+=F[i1-1];
                x-=L[i1-1];
                break;
            }
        }
    }
    return getm;
}

int main()
{
    freopen("infinit.in","r",stdin);
    freopen("infinit.out","w",stdout);
   
    F[0]=0;
    F[1]=1,L[1]=1;
    F[2]=1,L[2]=2;
    for (int i=3;i<=92;i++)
    {
        F[i]=F[i-1]+F[i-2];
        L[i]=L[i-1]+L[i-2];
    }
    int N;
    scanf("%d\n",&N);
    for (int i=1;i<=N;i++)
    {
        unsigned long long a,b;
        cin>>a>>b;
        a--;
        cout<<Getm(b)-Getm(a)<<endl;
    }
    return 0;
} 

[數學遞推]NOIP模擬題：核電站問題 nucle 解題報告

【問題描述】

一個核電站有 N 個放核物質的坑，坑排列在一條直綫上。如果連續 M 個坑中放入核物質，則會發生爆炸，於是，在某些坑中可能不放核物質。

任務：對於給定的 N 和 M ，求不發生爆炸的放置核物質的方案總數。

【輸入格式】

輸入文件（nucle.in）只一行，兩個正整數 N ， M( 1<N<50 ， 2 ≤ M ≤ 5)

【輸出格式】

輸出文件 (nucle.out) 只有一個正整數 S ，表示方案總數。

【輸入輸出樣例】

輸入：

nucle.in

4 3

輸出：

nucle.out

13

【分析】

一開始我用組合數Combination寫的這個題，用了下面的公式：

  但是這種算法只能過3組測試數據，因為在判斷是否爆炸的問題上比較困難。

後來，我發現，這個題可以用 數值遞推來寫。

我們以N=6,M=4來舉例：
     在已經確定了前5個坑的情況下，如果再加上一個坑，只存在“放”與“不放”兩種方案，所以總數應為2*F[i-1]種。但是，如果有4個核物質放在一起，就會爆炸，那麼這種情況的實現條件就是i-M+1到i-1都放上了核物質，如果第i個坑再放，就會發生爆炸。所以，i-M+1到i-1都放上了核物質的方案總數就是它前面的方案數，即F[i-1-M]。

所以：F[i]=2*F[i-1]-F[i-1M]。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
long long F[100];
int main()
{
    freopen("nucle.in","r",stdin);
    freopen("nucle.out","w",stdout);
   
    int N,M;
    scanf("%d %d\n",&N,&M);
   
    F[4]=1;
    F[5]=1;
   
    for (int i=6;i<=N+6;i++)
    {
        F[i]=2*F[i-1]-F[i-1-M];
    }
    cout<<F[N+5]<<endl;
    return 0;
}

[數學遞推]OI練習題：Binacy

【題目描述】

求所有可以只用1和00拼成的長度爲N的二進制數的個數除以1 5746的餘數。

比如當N=4的時候，有5個可能的二進制：0011，0000，1001，1100，1111。

【輸入格式】

第一行一個正整數N

【輸出格式】

輸出所有可以只用1和00拼成的長度爲N的二進制數的個數除以15746的餘數。

【輸入樣例】

4

【輸出樣例】

5

【數據範圍】

在100％的數據中，1≤N<1000000

【分析】

先嘗試寫出前幾個，找找規律：

N=0時 結果為0

N=1時 結果為1

N=2時 結果為2

N=3時 結果為3

N=4時 結果為5

......

可以看出，這是斐波那契數列。

所以，只需要遞推出斐波那契數列即可。

遞推式：

               S[0]=0,S[1]=1,

               S[2]=2;

               S[n]=S[n-2]+S[n-1] (n>2)

【代碼】

這是我以前的代碼，不知道我當時為何要把前幾個數打成表。

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
unsigned long long S[1000001];
int main()
{
    freopen("binacy.in","r",stdin);
    freopen("binacy.out","w",stdout);
    int N;
    cin>>N;
    if(N<=4)
    {
        switch(N)
        {
        case 0:
            cout<<0<<endl;
            break;
        case 1:
            cout<<1<<endl;
            break;
        case 2:
            cout<<2<<endl;
            break;
        case 3:
            cout<<3<<endl;
            break;
        case 4:
            cout<<5<<endl;
            break;
        }
        return 0;
    }
    S[3]=3;
    S[4]=5;
    for (int i=5;i<=N;i++)
        S[i]=(S[i-1]+S[i-2])%15746;
    cout<<S[N]<<endl;
    return 0;
}

NOIP2007普及組 hanoi雙塔問題

【問題描述】

給定A、B、C三根足夠長的細柱，在A柱上放有2n箇中間有孔的圓盤，共有n個不同的尺

寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤足不加區分的(下圖爲n=3的情形)。現要將

這些圓盤移到C柱上，在移動過程中可放在B柱上暫存。要求：

(1)每次只能移動一個圓盤；

(2)A、B、C三根細柱上的圓盤都要保持上小下大的順序；

任務：設An爲2n個圓盤完成上述任務所需的最少移動次數，對於輸入的n，輸出An。

【輸入】

輸入文件hanoi.in爲一個正整數n，表示在A柱上放有2n個圓盤。

【輸出】

輸出文件hanoi.out僅一行，包含一個正整數，爲完成上述任務所需的最少移動次數An。

【輸入輸出樣例1】

hanoi.in

1

hanoi.out

2

【輸入輸出樣例2】

hanoi.in

2

hanoi.out

6

【限制】

對於50％的數據，1<=n<=25

對於100％的數據，l<=n<=200

【提示】

設法建立An與An-1的遞推關係式。

【分析】

設F(x)表示移動2x個圓盤的最小步數。

很容易推出F(x)=2*X^2-2

或者這樣寫：F(x)=F(x-1)*2 最後的F(n)再減2即可，這樣寫可以把高精度乘法換成高精度加法。

【滿分代碼】

//hanoi雙塔問題
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
using namespace std;

char result[1000]; 
void Highj(char a[],char b[]) 
{ 
    int x[1000],y[1000]; 
    int i,l,la,lb; 
    char temp[1000]; 
    for (i=0;i<999;i++){x[i]=0;y[i]=0;} //初始化 
    la=strlen(a); 
    lb=strlen(b); 
     
    //把char型數組 按正倒序  變成整型數組 
    if (la<=lb) 
    { 
        for (i=la-1;i>=0;i--) 
            y[i]=a[la-1-i]-'0'; 
        for (i=lb-1;i>=0;i--) 
            x[i]=b[lb-1-i]-'0'; 
        l=la; 
    } 
    else  
    { 
        for (i=la-1;i>=0;i--) 
            x[i]=a[la-1-i]-'0'; 
        for (i=lb-1;i>=0;i--) 
            y[i]=b[lb-1-i]-'0';     
        l=lb;         
    } 
     
    //執行加法運算 
    for (i=0;i<l;i++) 
    { 
        x[i]=x[i]+y[i]; 
        if (x[i]>=10)  
        { 
            x[i]-=10; 
            x[i+1]+=1; 
        } 
    } 
     
    //再把整型數組按照倒序轉換成char型數組 
    for (i=999;i>=0;i--) 
        temp[999-i]=x[i]+'0'; 
     
    //從不是0的一位開始輸出結果 
    for (i=0;i<=999;i++) 
    { 
        if (temp[i]>'0') 
        { 
            for(int j=i;j<=999;j++) 
                result[j-i]=temp[j]; 
            return; 
        } 
    } 
    //如果沒有一位大於0 
    result[0]='0'; 
    return; 
}  

int main()
{
 freopen("hanoi.in","r",stdin);
 freopen("hanoi.out","w",stdout);
 long long num=1;
 int n;
 cin>>n;
 if (n<90)
 {
  for (int i=1;i<=n;i++)
   num=num*2;
  num=num*2-2;
  cout<<num<<endl;
  return 0;
 }
 if (n>=90)
 {
  char two[1];
  two[0]='2';
  memset(result,'\0',sizeof(result));
  result[0]='1';
  for (int i=1;i<=n+1;i++) 
  {
   Highj(result,result);
  }
  int len=strlen(result);
  if (result[len-1]-'0'>=2)
   result[len-1]=result[len-1]-2;
  else 
  {
   result[len-1]=result[len-1]-2+10;
   result[len-1]=result[len-2]-2;
  }
  cout<<result<<endl;
 }
 return 0;
}

---