HDU 6098 Inversion

本文由 Ocrosoft 于 2017-08-10 19:48:06 发表

Inversion

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 130    Accepted Submission(s): 95

Problem Description
Give an array A, the index starts from 1.
Now we want to know Bi=maxi∤jAj , i≥2.
 

Input
The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with one integer n : the size of array A.
Next one line contains n integers, separated by space, ith number is Ai.
Limits
T≤20
2≤n≤100000
1≤Ai≤1000000000
∑n≤700000
 

Output
For each test case output one line contains n-1 integers, separated by space, ith number is Bi+1.
 

Sample Input
	
2 4 1 2 3 4 4 1 4 2 3
 

Sample Output
	
3 4 3 2 4 4
 

Solution
2017 Multi-University Training Contest – Team 6
题意:B[i]值是A中 下标不能被i整除的 那些数的最大值。如B[2]=max(A[3],A[5],A[7],…,A[2*n-1])。
思路:A中最大的那个值(设下标为i),一定是B中那些(设下标为j1,j2…,)位置的值,如果i%j1!=0,i%j2!=0,…;然后A中次大的那个值i2,是B中除了j1,j2…那些以外,k1,k2,…的值,当i2%k1!=0,最后所有n-1个值都求出来了结束。

#define C11
#include <set>
#include <map>
#include <stack>
#include <string>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <climits>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <functional>
#ifdef C11
#include <tuple>
#include <regex>
#include <random>
#include <complex>
#endif
using namespace std;
/** const var def */
const double eps = 1e-8;
const int maxn = 1e5 + 10;
const int MAXN = maxn * 4;
const int MOD = 1000000007;
/** type def */
typedef long long LL;
typedef pair<int, int> Pii;
typedef pair<LL, LL> Pll;
typedef vector<int> Vi;
typedef pair<double, double> Vec2;
#ifdef C11
using Vec3 = tuple<double, double, double>;
using Tp3 = tuple<int, int, int>;
#endif
/** easy def */
#define _link(x) x&&x
#define ms(a) memset(a,0,sizeof(a))
#define msr(a) memset(a,-1,sizeof(a))
/* first, second, position */
#define _f first
#define _s second
#define _p(_tp,_pos) get<_pos>(_tp)
/* operator */
Pii operator +(const Pii &x, const Pii &y) { return Pii(x.first + y.first, x.second + y.second); }
Pii operator -(const Pii &x) { return Pii(-x.first, -x.second); }
Pii operator -(const Pii &x, const Pii &y) { return x + (-y); }
Pii operator +=(Pii &x, const Pii &y) { return x = x + y; }
Pii operator -=(Pii &x, const Pii &y) { return x = x - y; }
#pragma region input&output
template<class T>inline T read(T &num)
{
	char CH; bool F = false;
	for (CH = getchar(); CH<'0' || CH>'9'; F = CH == '-', CH = getchar());
	for (num = 0; CH >= '0'&&CH <= '9'; num = num * 10 + CH - '0', CH = getchar());
	F && (num = -num);
	return num;
}
template<class T>inline T read()
{
	T num;
	return read(num);
}
#ifdef C11
template<class T, class... Args>inline int read(T &t, Args &...args)
{
	read(t);
	read(args...);
	return t;
}
#endif
template<class T> inline void print(T p, char ed = '\n')
{
	int stk[70], tp = 0;
	if (p < 0) { putchar('-'); p = -p; }
	if (!p) { putchar('0'); if (ed != '\0')putchar(ed); return; }
	while (p) stk[++tp] = p % 10, p /= 10;
	while (tp) putchar(stk[tp--] + '0');
	if (ed != '\0')putchar(ed);
}
#ifdef C11
template<class T, class... Args>inline void print(T t, Args ...args)
{
	print(t, '\0');
	if (sizeof...(args))putchar(' ');
	else putchar('\n');
	print(args...);
}
#endif
#pragma endregion

int main()
{
	int N; read(N);
	while (N--)
	{
		int n; read(n);
		vector<Pii> vec(n);
		set<int> s;
		for (int i = 0; i < n; ++i)
		{
			read(vec[i].first);
			if (i)s.insert(i + 1);
			vec[i].second = i + 1;
		}
		sort(begin(vec), end(vec), greater<Pii>());
		Vi ans(n + 1); //int cnt = 0;
		for (auto each : vec)
		{
			int p = each.second;
			for (auto it = begin(s); it != s.end();)
			{
				if (p%*it)
				{
					//++cnt;
					ans[*it] = each.first;
					it = s.erase(it);
					//if (cnt == n - 1)break;
				}
				else ++it;
			}
		}
		for (int i = 2; i <= n; i++)
			printf("%d%s", ans[i], i == n ? "\n" : " ");
	}
	return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 6098 Inversion

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址