85-有趣的数

内存限制:64MB 时间限制:3000ms 特判: No

通过数:8 提交数:12 难度:2

题目描述:

把分数按下面的办法排成一个数表。

1/1 1/2 1/3 1/4…

2/1 2/2 2/3…

3/1 3/2 …

4/1…

…

我们以z字型方法给上表的每项编号。特定方法：第一项是1/1，然后是1/2、2/1、3/1、2/2、1/3、1/4、2/3……。编程输入项号N（1<=N<=100000），输出表中第N项。

输入描述:

第一行有一个整数m(0<m<=10)，表示有m组测试数据；

随后有m行，每行有一个整数N；

输出描述:

输出表中第N项

样例输入:

复制

4

3

14

7

12345

样例输出:

2/1

2/4

1/4

59/99

思路

将题目描述的数表输出出来，进行找规律，可以发现有如下规律：在一段连续的区间内，分子和分母加起来是固定的值。
假设分子分母之和为N，当N是奇数时，分子是从小到大（从1−&gt;N−11-&gt;N-11−>N−1）；当N是偶数时，分子从大到小（从N−1−&gt;1N-1-&gt;1N−1−>1）
对这个规律进行打表即可

不知道为什么，数组大小开到1e5会出错，明明数据范围是1e5

AC代码

/*

* @Author: WZY

* @School: HPU

* @Date:   2018-10-22 17:12:37

* @Last Modified by:   WZY

* @Last Modified time: 2018-10-22 22:48:31

*/

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <limits.h>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <set>

#include <string>

#include <time.h>

#define ll long long

#define ull unsigned long long

#define ms(a) memset(a,0,sizeof(a))

#define pi acos(-1.0)

#define INF 0x7f7f7f7f

#define lson o<<1

#define rson o<<1|1

#define bug cout<<"-------------"<<endl

#define debug(...) cerr<<"["<<#__VA_ARGS__":"<<(__VA_ARGS__)<<"]"<<"\n"

const double E=exp(1);

const int maxn=1e6+10;

const int mod=1e9+7;

using namespace std;

int a[maxn],b[maxn];

int k;

inline void init()

{

	k=0;

	for(int i=1;i<1000;i++)

	{

		if(i&1)

		{

			for(int j=1;j<i;j++)

			{

				a[++k]=j,b[k]=i-j;

				if(k>=maxn)

					return;

			}

		}

		else

		{

			for(int j=i-1;j>=1;j--)

			{

				a[++k]=j,b[k]=i-j;

				if(k>=maxn)

					return;

			}

		}

	}

}

int main(int argc, char const *argv[])

{

	ios::sync_with_stdio(false);

	#ifndef ONLINE_JUDGE

	    freopen("in.txt", "r", stdin);

	    freopen("out.txt", "w", stdout);

	    double _begin_time = clock();

	#endif

	init();

	int t;

	// for(int i=1;i<1000;i++)

	// {

	// 	debug(i);

	// 	debug(a[i]);

	// 	debug(b[i]);

	// }

	cin>>t;

	while(t--)

	{

		int n;

		cin>>n;

		cout<<a[n]<<"/"<<b[n]<<endl;

	}

	#ifndef ONLINE_JUDGE

	    long _end_time = clock();

	    printf("time = %lf ms.", _end_time - _begin_time);

	#endif

	return 0;

}