庆阳网站建设公司,营销方案现金充值什么意思,网站需求文档范例,在洪雅网站做企业招聘题意#xff1a;
有长度为 n 的数组 a #xff0c;全为 0#xff0c;接下来循环 n 次#xff0c;每次选出一段最长的连续区间 [l, r]#xff08;全为 0 #xff0c;如果一样长#xff0c;就选最左边的)。
如果 r−l1 是奇数#xff0c;那么 a[lr2]ia[\frac{lr}{2}]ia…题意
有长度为 n 的数组 a 全为 0接下来循环 n 次每次选出一段最长的连续区间 [l, r]全为 0 如果一样长就选最左边的)。
如果 r−l1 是奇数那么 a[lr2]ia[\frac{lr}{2}]ia[2lr]i;
否则a[lr−12]ia[\frac{lr-1}{2}]ia[2lr−1]i;i 是第几轮循环。
输出最终的数组 a。
题目
You are given an array a of length n consisting of zeros. You perform n actions with this array: during the i-th action, the following sequence of operations appears:
Choose the maximum by length subarray (continuous subsegment) consisting only of zeros, among all such segments choose the leftmost one; Let this segment be [l;r]. If r−l1 is odd (not divisible by 2) then assign (set) a[lr2]ia[\frac{lr}{2}]ia[2lr]i(where i is the number of the current action), otherwise (if r−l1 is even) assign (set) a[lr−12]ia[\frac{lr-1}{2}]ia[2lr−1]i. Consider the array a of length 5 (initially a[0,0,0,0,0]). Then it changes as follows:
Firstly, we choose the segment [1;5] and assign a[3]:1, so a becomes [0,0,1,0,0]; then we choose the segment [1;2] and assign a[1]:2, so a becomes [2,0,1,0,0]; then we choose the segment [4;5] and assign a[4]:3, so a becomes [2,0,1,3,0]; then we choose the segment [2;2] and assign a[2]:4, so a becomes [2,4,1,3,0]; and at last we choose the segment [5;5] and assign a[5]:5, so a becomes [2,4,1,3,5]. Your task is to find the array a of length n after performing all n actions. Note that the answer exists and unique.
You have to answer t independent test cases.
Input The first line of the input contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.
The only line of the test case contains one integer n (1≤n≤2⋅105) — the length of a.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 (∑n≤2⋅105).
Output For each test case, print the answer — the array a of length n after performing n actions described in the problem statement. Note that the answer exists and unique.
Example Input 6 1 2 3 4 5 6 Output 1 1 2 2 1 3 3 1 2 4 2 4 1 3 5 3 4 1 5 2 6
分析
我们可以直接暴力去做。即我们每次选出符合条件的 [l, r]然后对应的给 a[i] 赋值又得到了两个新的更小的区间我们需要存储下来并按照上述的规则对所有的区间排序。显然优先队列可以完美的满足我们的要求。优先队列的BFS。每次处理完一段区间后就把这段区间拆分丢进优先队列里就好。注意priority_queue本身是一个大根二叉堆所以重载运算符时符号要反一下 或者按照蓝书讲的 把len换成相反数。 #AC代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int M2e510;
int s[M];
int t,n,tot;
struct node
{int l,r,d;
};
bool operator(const node a,const node b)
{if(a.db.d)return 1;else if(a.db.d)if(a.lb.l)return 1;return 0;
}
int main()
{scanf(%d,t);while(t--){tot0;memset(s,0,sizeof(s));scanf(%d,n);priority_queuenodeq;node u,v;u.l1,u.rn,u.du.r-u.l1;q.push(u);while(!q.empty()){uq.top();q.pop();int xu.l;int yu.r;int mid(xy)1;s[mid]tot;//printf(%d****\n,s[mid]);v.lx,v.rmid-1,v.dv.r-v.l1;if(v.lv.r)q.push(v);v.lmid1,v.ry,v.dv.r-v.l1;if(v.lv.r)q.push(v);}for(int i1;in;i)printf(%d ,s[i]);printf(\n);}return 0;
}
