华师一附中OI组

标题: P1152 欢乐的跳 [打印本页]
作者: admin    时间: 2020-3-20 20:37
标题: P1152 欢乐的跳
https://www.luogu.com.cn/problem/P1152

题目描述
一个n个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了[1,n-1]之间的所有整数，则称之符合“欢乐的跳”，如数组1 4 2 3符合“欢乐的跳”，因为差的绝对值分别为：3,2,1。

给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

输入格式
每组测试数据第一行以一个整数n(1≤n≤1000)开始，接下来nn个空格隔开的在[-10^8−10^8]之间的整数。

输出格式
对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出"Jolly"，否则输出"Not jolly"。

输入输出样例
输入 #1
4 1 4 2 3
输出 #1复制
Jolly
输入 #2复制
5 1 4 2 -1 6
输出 #2复制
Not jolly

作者: admin    时间: 2020-3-20 20:38
此题的主要任务是判断相邻的两个数的差值是不是覆盖了1-(n-1)这些数字，就像三连击里面那个一样，我们可以用一个数组b(i)表示0到n-1之间的数是否吹出现过，他的初值都是0，出现了就变成1，最后看看b数组中b(1)到b(n-1)是否全部是1，只要他们全部加起来的总和是n-1的话，那就说明里面全部是1，没有一个0。（这种做法和我以前那个三连击里面的做法有点不一样，也是正确的）

  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4. const int mm=1010;
  5. int n,a[mm],b[mm],i,s,x;
  6. int main()
  7. {
  8.         cin>>n;
  9.         for (int i=0; i<=n; i++) b[i]=0; //表示i这个数字没有出现
  10.         for (int i=1; i<=n; i++) cin>>a[i];
  11.         for (int i=2; i<=n; i++)
  12.         {
  13.                 x=abs(a[i]-a[i-1]);
  14.                 if (x<=n) b[x]=1; /// 为什么x<=n???  避免越界  x>mm怎么办！！
  15.         }
  16.         s=0;
  17.         for (i=1; i<=n-1; i++)  s+=b[i]; ///理想下每个都是1 加起来总和n-1
  18.         if (s==n-1) cout<<"Jolly";
  19.         else cout<<"Not jolly";
  20.         return 0;
  21. }
复制代码
作者: admin    时间: 2020-3-20 20:47
这个题还有一个技巧，就是没有必要用a数组去存放所有的数，我们读入数据的时候就做减法，保存这个差值，而不需要保存每个数，当然，这个技巧有点吹毛求疵，要求比较高。

  1.         cin>>n;
  2.         for (int i=0; i<=n; i++) b[i]=0; //表示i这个数字没有出现
  3.         cin>>x1;///读入第一个数
  4.         for (int i=1; i<=n; i++)
  5.         {
  6.                 cin>>x2; ///读入新数
  7.                 x=abs(x1-x2); ///后数减前数
  8.                 if (x<=n) b[x]=1; /// 为什么x<=n???  避免越界  x>mm怎么办！！
  9.                 x1=x2;   ///后数变前数
  10.         }
复制代码
作者: admin    时间: 2020-3-20 20:47
这个题还有一个技巧，就是没有必要用a数组去存放所有的数，我们读入数据的时候就做减法，保存这个差值，而不需要保存每个数，当然，这个技巧有点吹毛求疵，要求比较高。

  1.         cin>>n;
  2.         for (int i=0; i<=n; i++) b[i]=0; //表示i这个数字没有出现
  3.         cin>>x1;///读入第一个数
  4.         for (int i=1; i<=n; i++)
  5.         {
  6.                 cin>>x2; ///读入新数
  7.                 x=abs(x1-x2); ///后数减前数
  8.                 if (x<=n) b[x]=1; /// 为什么x<=n???  避免越界  x>mm怎么办！！
  9.                 x1=x2;   ///后数变前数
  10.         }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2