例19 歡樂的跳
題目描述
一個n個元素的整數陣列，如果陣列兩個連續元素之間差的絕對值包括了[1,n-1]之間的所有整數，則稱之符合“歡樂的跳”，如陣列1 4 2 3符合“歡樂的跳”，因為差的絕對值分別為：3,2,1，
給定一個陣列，你的任務是判斷該陣列是否符合“歡樂的跳”，
輸入格式
每組測驗資料第一行以一個整數n(1≤n≤1000)開始，接下來n個空格隔開的整數，
輸出格式
對于每組測驗資料，輸出一行若該陣列符合“歡樂的跳”則輸出"Jolly"，否則輸出"Not jolly"，
輸入樣例 #1
4 1 4 2 3
輸出樣例 #1
Jolly
輸入樣例 #2
5 1 4 2 -1 6
輸出樣例 #2
Not jolly
（1）編程思路，
為了判斷陣列兩個連續元素之間差的絕對值是否包括了[1,n-1]之間的所有整數，定義一個陣列int hash[1001]，其中hash[i]=0表示整數i未出現，hash[i]=1表示整數i出現過，初始時，hash陣列的全部元素值均為0，
對n個元素的陣列a，用回圈for (i=1;i<n;i++)對陣列中連續兩個元素的差的絕對值d（d=abs(a[i]-a[i-1])）進行處理，若差的絕對值d小于n，則置hash[d]=1，表示整數d出現了，
之后，判斷陣列hash的情況，若陣列元素hash[1]~hash[n-1]的值全為1，則表示陣列a中兩個連續元素之間差的絕對值包括了[1,n-1]之間的所有整數，
（2）源程式，
#include <stdio.h>
#include <math.h>
int main()
{
int hash[1001]={0},a[1001],n,i,d;
scanf("%d",&n);
for (i=0;i<n;i++)
scanf("%d",&a[i]);
for (i=1;i<n;i++)
{
d=abs(a[i]-a[i-1]);
if (d<=n-1) hash[d]=1;
}
for (i=1;i<=n-1;i++)
if (hash[i]==0) break;
if (i<n)
printf("Not jolly\n");
else
printf("Jolly\n");
return 0;
}
習題19
19-1 校門外的樹
本題選自洛谷題庫 （https://www.luogu.org/problem/P1047）
題目描述
某校大門外長度為L的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是1米，我們可以把馬路看成一個數軸，馬路的一端在數軸0的位置，另一端在L的位置；數軸上的每個整數點，即0,1,2,…,L，都種有一棵樹，
由于馬路上有一些區域要用來建地鐵，這些區域用它們在數軸上的起始點和終止點表示，已知任一區域的起始點和終止點的坐標都是整數，區域之間可能有重合的部分，現在要把這些區域中的樹（包括區域端點處的兩棵樹）移走，你的任務是計算將這些樹都移走后，馬路上還有多少棵樹，
輸入格式
第一行有2個整數L((1≤L≤10000)和 M(1≤M≤100)，L代表馬路的長度，M代表區域的數目，L和M之間用一個空格隔開，
接下來的M行每行包含2個不同的整數，用一個空格隔開，表示一個區域的起始點和終止點的坐標，
輸出格式
1個整數，表示馬路上剩余的樹的數目，
輸入樣例
500 3
150 300
100 200
470 471
輸出樣例
298
（1）編程思路，
定義陣列int f[10001]，其中f[i]=1表示坐標為i的位置有一棵樹，f[i]=0表示坐標為i的位置的樹被移走了，初始時，陣列的元素f[0]~f[l]全部置為1，表示長度為L的馬路上每間隔1米有一棵樹，
每輸入一組區域的起始點和終止點的坐標begin和end，就將f[begin]~f[end]之間的陣列元素的值修改為0，表示樹被移走了，
最后，統計陣列f中值為1的元素的個數，就是馬路上剩余的樹的數目，
（2）源程式，
#include <stdio.h>
int main()
{
int l,m,begin,end,i,cnt;
int f[10001];
scanf("%d%d",&l,&m);
for (i=0;i<=l;i++)
f[i]=1;
while (m--)
{
scanf("%d%d",&begin,&end);
for (i=begin;i<=end;i++)
f[i]=0;
}
cnt=0;
for (i=0;i<=l;i++)
{
if (f[i]==1)
cnt++;
}
printf("%d\n",cnt);
return 0;
}
19-2 校門外的樹（增強版）
本題選自洛谷題庫 （https://www.luogu.org/problem/P1276）
題目描述
校門外馬路上本來從編號0到L，每一編號的位置都有1棵樹，有砍樹者每次從編號A到B處連續砍掉每1棵樹，就連樹苗也不放過（記 0 A B ，含A和B）；幸運的是還有植樹者每次從編號C到D 中凡是空穴（樹被砍且還沒種上樹苗或樹苗又被砍掉）的地方都補種上樹苗（記 1 C D，含C和D）；問最終校門外留下的樹苗多少棵？植樹者種上又被砍掉的樹苗有多少棵？
輸入格式
第一行L和N，表示校園外原來有L+1棵樹，并有N次砍樹或種樹的操作，
以下N行，砍樹或植樹的標記和范圍，每行3個整數，
L（1 <= L <= 10000）和 N（1 <= N <= 100）
輸出格式
共兩行，第1行校門外留下的樹苗數目，第2行種上又被拔掉的樹苗數目，
輸入樣例
10 3
0 2 6
1 1 8
0 5 7
輸出樣例
3
2
（1）編程思路，
本題思路與上題類同，同樣定義陣列int f[10001]，其中f[i]=1表示坐標為i的位置有一棵樹，f[i]=2表示坐標為i的位置補種了一顆樹苗，f[i]=0表示坐標為i的位置的樹或樹苗被移走了，初始時，陣列的元素f[0]~f[l]全部置為1，表示長度為L的馬路上每間隔1米有一棵樹，
程式中根據砍樹或種樹的操作對陣列f的相應元素進行處理，具體見源程式，
（2）源程式，
#include <stdio.h>
int main()
{
int l,n,m,begin,end,i,cnt1,cnt2;
int f[10001];
scanf("%d%d",&l,&n);
for (i=0;i<=l;i++)
f[i]=1; // 初始為一棵樹
cnt2=0; // 種上又被砍掉的樹苗數
while (n--)
{
scanf("%d%d%d",&m,&begin,&end);
if (m==0) // 砍樹或樹苗
{
for (i=begin;i<=end;i++)
{
if (f[i]==2) cnt2++; // 樹苗被砍掉了
f[i]=0;
}
}
else // 種樹苗
{
for (i=begin;i<=end;i++)
if (f[i]==0)
f[i]=2;
}
}
cnt1=0; // 留下的樹苗數
for (i=0;i<=l;i++)
{
if (f[i]==2)
cnt1++;
}
printf("%d\n%d\n",cnt1,cnt2);
return 0;
}
19-3 珠心算測驗
題目描述
珠心算是一種通過在腦中模擬算盤變化來完成快速運算的一種計算技術，珠心算訓練，既能夠開發智力，又能夠為日常生活帶來很多便利，因而在很多學校得到普及，
某學校的珠心算老師采用一種快速考察珠心算加法能力的測驗方法，他隨機生成一個正整數集合，集合中的數各不相同，然后要求學生回答：其中有多少個數，恰好等于集合中另外兩個（不同的）數之和？
最近老師出了一些測驗題，請你幫忙求出答案，
輸入格式
共兩行，第一行包含一個整數n，表示測驗題中給出的正整數個數，
第二行有n個正整數，每兩個正整數之間用一個空格隔開，表示測驗題中給出的正整數，
輸出格式
一個整數，表示測驗題答案，
輸入樣例
4
1 2 3 4
輸出樣例
2
說明/提示
【樣例說明】
由1+2=3,1+3=4，故滿足測驗要求的答案為2，
注意，加數和被加數必須是集合中的兩個不同的數，
（1）編程思路，
為了判斷集合中有多少個數恰好等于集合中另外兩個（不同的）數之和，定義一個陣列int hash[10001]，其中hash[i]=0表示整數i作為和值未出現，hash[i]=1表示整數i作為和值第1次出現了，hash[i]=2表示整數i作為和值不止1次出現了，只能算一次，初始時，hash陣列中，屬于集合元素的hash陣列相應元素值置1，其余非集合元素的相應hash元素值均為0，
用二重回圈
for (i=0;i<n-1;i++)
for (j=i+1;j<n;j++)
對集合中任意兩個不同元素的和值t（t=num[i]+num[j]）進行處理，若和值t的對應的hash[t]等于1，表示集合中存在元素t為另外兩個不同元素的和，計數，同時置hash[t]=2，以避免下次再出現和值t產生重復計數，
（2）源程式，
#include <stdio.h>
int main()
{
int n,i,j,t,cnt=0,num[100];
int hash[10001]={0};
scanf("%d",&n);
for (i=0;i<n;i++)
{
scanf("%d",&num[i]);
hash[num[i]]=1;
}
for (i=0;i<n-1;i++)
for (j=i+1;j<n;j++)
{
t=num[i]+num[j];
if (t<=10000 && hash[t]==1)
{
cnt++;
hash[t]=2; // 注意：1+4和2+3也算重復，需去掉
}
}
printf("%d\n",cnt);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/61765.html
標籤：C