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 的原資料。

 

【輸入格式】

輸入由若干行組成：

第一行有兩個整數，m，n（1≤n,m≤100）；n表示數組長度，m表示問題個數。

下面有2*m行,每兩行是一個問題,每個問題的第一行是一個數字s,s=1時表示根據資料求編碼,s=2時表示根據編碼求資料,第二行是n個數，中間用空格隔開。

【輸出格式】

輸出資料有m行，每行表示一個問題的答案。

【輸入輸出樣例】

輸入文件名：code.in

2 6

1

4 3 0 5 1 2

2

0 0 0 3 1 2

輸出文件名：code.out

0 0 0 3 1 2

4 3 0 5 1 2

【分析】

常老師竟然拿一道十幾年前NOIP普及組的題當我們省選的模擬賽題～

雖說是當年普及組的最後一題，但是還是蠻簡單的，那個筆在紙上畫畫找找規律就行了。

對於由數據求編碼，從前往後模擬即可。 

對於由編碼求數據，從後往前遞推即可，看看我的代碼吧。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25588

01 /*
02 *Problem: NOIP1995 普及組
03 *Author: Yee-fan Zhu
04 *Email: zyfworks@gmail.com
05 */
06 #include <cstdio>
07 #include <cstdlib>
08 #include <cstring>
09 #include <iostream>
10 using namespace std;
11 int N,M;
12 const int MAXN=111;
13
14 int Num[MAXN];
15 int Ans[MAXN];
16
17 void Work1()
18 {
19     Ans[1]=0;
20     for(int i=2;i<=N;i++)
21     {
22         int Res=0;
23         for(int j=1;j<i;j++)
24         {
25             if(Num[j]<Num[i])
26                 Res++;
27         }
28         Ans[i]=Res;
29     }
30     for(int i=1;i<=N-1;i++)
31         printf("%d ",Ans[i]);
32     printf("%d\n",Ans[N]);
33 }
34
35 void Work2()
36 {
37     bool flag[MAXN];
38    
39     for(int i=0;i<=100;i++)
40         flag[i]=false;
41    
42     Ans[N]=Num[N];
43     flag[Ans[N]]=true;
44    
45     for(int i=N-1;i>=1;i--)
46     {
47         int tmp1=Num[i];
48         for(int j=0;j<=N-1;j++)
49         {
50             if(flag[j])
51                 continue;
52             int tmp2=0;
53             for(int k=i+1;k<=N;k++)
54             {
55                 if(Ans[k]<j)
56                     tmp2++;
57             }
58             int tmp3=tmp1+tmp2;
59             if(tmp3==j)
60             {
61                 Ans[i]=j;
62                 flag[j]=true;
63                 break;
64             }
65         }
66     }
67     for(int i=1;i<=N-1;i++)
68         printf("%d ",Ans[i]);
69     printf("%d\n",Ans[N]);
70 }
71
72 void solve()
73 {
74     scanf("%d %d\n",&M,&N);
75     int P;
76     for(int i=1;i<=M;i++)
77     {
78         scanf("%d\n",&P);
79         for(int j=1;j<=N;j++)
80             scanf("%d",&Num[j]);
81         if(P==1)
82             Work1();
83         else if(P==2)
84             Work2();
85     }
86 }
87
88 int main()
89 {
90     freopen("code.in","r",stdin);
91     freopen("code.out","w",stdout);
92     solve();
93     return 0;
94 }