2017多校6 1003 Inversion

2024-04-01 19:08
文章标签 2017 多校 1003 inversion

本文主要是介绍2017多校6 1003 Inversion,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://acm.hdu.edu.cn/showproblem.php?pid=6098



给出一组数列,共有n个数,输出n-1个数,第i个输出的是所给数列中下标不是i的整除数中的最大的数。
模拟过程必定超时。因为是除去所有的整除数,意味着第i个数本身是不看的,那其实就很简单了,只要对整个数列倒序排序,然后每次输出的时候从大的开始遍历,判断是否能整除即可。



#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
struct node
{int num;int a;
}s[111111];
bool cmp(node x,node y)
{return x.num>y.num;
}
int b[111111];
int main()
{int T;int n;cin>>T;while(T--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&s[i].num);s[i].a=i;}sort(s+1,s+n+1,cmp);for(int i=2;i<=n;i++){for(int j=1;j<=n;j++){if(s[j].a%i==0)continue;else{b[i]=s[j].num;break;}}}int p=0;for(int i=2;i<=n;i++){if(p++)cout<<" ";printf("%d",b[i]);}cout<<endl;}return 0;
}


这篇关于2017多校6 1003 Inversion的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/867923

相关文章

FZOJ 2166 inversion

算是一道模拟题吧,,,此题就逆序数不用归并排序之类的,而是用双层for循环模拟求解,,因为题意中要求任意两个数交换位置,所以只需在双层for循环中模拟两个数交换即可,在模拟的过程中,不需要准确的求出模拟之后的逆序数,只需要考虑逆序数的变化量为多少,最后,求出变化量最小的,用最初的逆序数求得最后结果。。。 其中模拟两个数交换之后逆序数的变化量解法: 如下: 有   a,b,c,d,e,f,g

【Hdu】Minimum Inversion Number(逆序,线段树)

利用线段树在nlogn的时间复杂度内求一段数的逆序。 由于给的序列是由0 ~ n -1组成的,求出初始的逆序之后可以递推出移动之后的逆序数。 #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const in

2015多校联合训练第三场Work(hdu5326)

题意: a是b的上司,b是c的上司,则a是c的上司,问构成一个树种,有多人是 k个人的上司 思路: 先找出root,然后dfs一下就行 #include <bits/stdc++.h>#define LL long longusing namespace std;const int MAXN = 1e6;int f[105];int n, k;int mp[101][101];

2015年多校联合训练第三场RGCDQ(hdu5317)

题意: f(i)代表i数中有的素数的种数,给出区间[l,r],求区间内max(gcd(f(i))), 由于i最大是1e6,2*3*5*7*11*13*17>1e6,故最多不超过7种素数, 先打表打出1e6内的素数种数表,然后用sum[i][j]代表1-i个数中,还有j个素数的个数,最后用sum[r][j] - sum[l-1][j]求出区间内含有j个素数的数的个数,暴力找出1,2,3,4,5

2015多校联合训练第一场Tricks Device(hdu5294)

题意:给一个无向图,给起点s,终点t,求最少拆掉几条边使得s到不了t,最多拆几条边使得s能到t 思路: 先跑一边最短路,记录最短路中最短的边数,总边数-最短边数就是第二个答案 第一个答案就是在最短路里面求最小割,也就是求最大流,然后根据最短路在建个新图,权为1,跑一边网络流 模板题,以后就用这套模板了 #include <iostream>#include <cstdio>#incl

2015多校联合训练第一场Assignment(hdu5289)三种解法

题目大意:给出一个数列,问其中存在多少连续子序列,子序列的最大值-最小值< k 这题有三种解法: 1:单调队列,时间复杂度O(n) 2:RMQ+二分,时间复杂度O(nlogn) 3:RMQ+贪心,时间复杂度O(nlogn) 一:RMQ+二分 RMQ维护最大值,最小值,枚举左端点i,二分找出最远的符合的右端点j,答案就是ans += j - i+1;(手推一下就知道) 比如1 2 3

2015年多校联合训练第一场OO’s Sequence(hdu5288)

题意:给定一个长度为n的序列,规定f(l,r)是对于l,r范围内的某个数字a[i],都不能找到一个对应的j使得a[i]%a[j]=0,那么l,r内有多少个i,f(l,r)就是几。问所有f(l,r)的总和是多少。 公式中给出的区间,也就是所有存在的区间。 思路:直接枚举每一个数字,对于这个数字,如果这个数字是合法的i,那么向左能扩展的最大长度是多少,向右能扩展的最大长度是多少,那么i为合法的情况

MapReduce算法 – 反转排序(Order Inversion)

译者注:在刚开始翻译的时候,我将Order Inversion按照字面意思翻译成“反序”或者“倒序”,但是翻译完整篇文章之后,我感觉到,将Order Inversion翻译成反序模式是不恰当的,根据本文的内容,很显然,Inversion并非是将顺序倒排的意思,而是如同Spring的IOC一样,表明的是一种控制权的反转。Spring将对象的实例化责任从业务代码反转给了框架,而在本文的模式中,在map

2017 版本的 WebStorm 永久破解

1.  在IntelliJ官网中下载 最新版本的WebStorm   下载地址:https://www.jetbrains.com/webstorm/download/#section=windows 2. 获取注册码    获取地址:http://idea.lanyus.com/   点击获取注册码,然后将注册码复制,再打开最新版的WebStorm,将注册码粘贴到激活框中就大功告

2014多校联赛总结

转眼间2014年暑期多校联赛已经落下帷幕,下面是关于暑期比赛的一些总结. 题型统计: 2014 Multi-University Training Contest 1--by FZU A:数学(费马小定理) B:网络流(最小K路径覆盖) C:树形dp(树的重心+数据结构) D:贪心 (巧妙) E:数学+dp(隐含马尔科夫模型) F:线段树(函数式+二分) G:线段树+状态压