zcmu 1979: 过分的谜题（思维） hdu 6227 Rabbits（思维+贪心）

1979: 过分的谜题

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 125  Solved: 85
[Submit][Status][Web Board]

Description

2060年是云南中医学院的百年校庆，于是学生会的同学们搞了一个连续猜谜活动：共有10个谜题，现在告诉所有人第一个谜题，每个谜题的答案就是下一个谜题的线索....成功破解最后一个谜题后，答案就是指向奖励的线索
在所有同学们的努力下，全校同学们获得了最后一个谜题，这个谜题有几十张纸，上面全是密密麻麻的数字以及'.'
第一页内容如下：
1,2,3,4,5,6
4,1,5,2,6,3
2,4,6,1,3,5
1,2,3,4,5,6
———3

1,2,3,4....32
.............
.............
———10

有细心的同学发现，这是对一组1-2n的序列进行如下移动：每次将前n个数字取出，按顺序依次插入到位于n+1,n+2...2n的数字后面，最后的数字表示多少次移动后会变回原来的序列
第二页内容如下：
1,2,3,4....64
.............
.............
———?

1,2,3,4....140
.............
.............
———?

同学们发现，越往后翻，这个序列的长度就越长，前面十几二十个数字的序列同学们还可以一步一步模拟做出来，但是到后来几千甚至上万的长度，就没有办法计算了，甚至中间一步做错，就步步都错。
这个谜题真是太过分了！但是奖励就在眼前，只要计算出所有答案，所有答案就是指引同学们获得奖励的线索，那么现在问题来了，同学们除了发现上面的n=最后那个数字/2之外，没有办法给你任何帮助，而作为一个计算机科学与技术专业的大佬，你自然就成为了同学们心目中拯救他们的英雄，所以你能不能写一个程序，当你知道n是多少的时候，可以直接得出答案呢？

Input

多组测试数据.每组数据的第一行包含一个正整数n(1<= n<=10000).

Output

每组数据输出一行整数表示最少需要经过几次移动能变回原序列，若不能，则输出"-1"

Sample Input

3 16

Sample Output

3 10

HINT

Source

jnxxhzz

【分析】列出几个例子之后，可以发现规律的。就是1这个数的位置，每次倍增，即1--2--4--8--...... 会如果长度大于序列长度的话，会循环，所以这里取余定位置。当1回到第一个位置的时候，表示回到原序列。主要就是找规律了。

【代码】

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;while(~scanf("%d",&n)){int ans=1,t=2;n*=2;while(t!=1){t=(t*2)%(n+1);ans++;}printf("%d\n",ans);}return 0;
}

hdu 6227 Rabbits（思维+贪心）

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2362    Accepted Submission(s): 1221

 

Problem Description

Here N (N ≥ 3) rabbits are playing by the river. They are playing on a number line, each occupying a different integer. In a single move, one of the outer rabbits jumps into a space between any other two. At no point may two rabbits occupy the same position.
Help them play as long as possible

Input

The input has several test cases. The first line of input contains an integer t (1 ≤ t ≤ 500) indicating the number of test cases.
For each case the first line contains the integer N (3 ≤ N ≤ 500) described as above. The second line contains n integers a1 < a2 < a3 < ... < aN which are the initial positions of the rabbits. For each rabbit, its initial position
ai satisfies 1 ≤ ai ≤ 10000.

Output

For each case, output the largest number of moves the rabbits can make.

Sample Input

5
3
3 4 6
3
2 3 5
3
3 5 9
4
1 2 3 4
4
1 2 4 5

Sample Output

1
1
3
0
1

 

【分析】

每次跳的兔子必须是两边的，是大范围内的两边。然后，可以从前往后跳也可以从后往前跳，这个要选择小的那个。

【代码】

#include<bits/stdc++.h>
using namespace std;
const int maxn=510;
int num[maxn],sum[maxn];
int main()
{int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);int len=0;for(int i=1;i<=n;i++)scanf("%d",&num[i]);for(int i=1;i<n;i++){sum[i]=num[i+1]-num[i]-1;len+=sum[i];}int ans=min(sum[1],sum[n-1]);printf("%d\n",len-ans);}return 0;
}