当前位置:网站首页>NWERC 2019 A

NWERC 2019 A

2020-12-07 21:59:08 sgxsgx

A. Average Rank

The National Weekly Escape Room Challenge (NWERC) is a long-running competition held in Eindhoven. Every week a new escape room is presented, and anyone who completes it in their first attempt gains one point.

At the end of each week, competitors are ranked by the total number of points accumulated so far, highest first. In the case of a tie, they share the same rank. In other words, the rank of a competitor is one more than the number of people with a strictly larger number of points.

In total there have been \(n\) participants in the contest, and the contest has been going for w weeks. For each week you are given a list of the competitors that gained a point that week. Your task is to calculate the average rank during the w-week competition for each competitor.
The figure illustrates the score progression in the third sample.

Input
The input consists of:

One line with two integers \(n\) and \(w\) (\(1≤n,w≤3⋅10^5\)), the number of competitors and the number of weeks. The competitors are numbered from \(1\) to \(n\).
\(w\) lines (one for each week), each containing an integer \(k\) (\(0≤k≤n\)) followed by \(k\) distinct integers \(c_1,…,c_k\) (\(1≤c_i≤n\) for all \(i\)), indicating that the \(k\) competitors \(c_1,…,c_k\) each gained a point that week.
The total number of points awarded is at most 1 million.

Output
Output \(n\) lines, the ith of which contains the average rank of the \(ith\) competitor during the \(w\)-week competition. Your answers should have an absolute or relative error of at most \(10^−6\).

题解

这题说实话思维量很大。

其实我们要先想到,操作总数小于一百万,也就是说,对于一个参赛者分数\(+1\), 受到修改的,只有和他同分的人以及他自己,修改一次,与他同分的人加一,他自己的排名也会随之变化。

然后我们考虑每个人的平均排名,实际上就是每周的排名之和。

假设我们暴力处理的话, 效率就是\(O(n*w)\).

考虑优化这个过程。

类比修改线段树的\(lazy_tag\), 我们对于每次\(+1\)修改的,利用差分的思想,到用到的时候再算进去。

说实话有点难想。

Code

#include<bits/stdc++.h>
#define _(d) while(d(isdigit(ch=getchar())))
#define rep(i,a,b) for(int i=a;i<=b;i++)
template<class T>void g(T&t){T x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;t=f*x;}
using namespace std;
const int N = 1e6 + 4;
typedef long long ll;
ll n, w, now[N], pre[N], cnt[N], p[N], sum[N];
int main(){
	g(n), g(w);
	cnt[1] = n;
	rep( i, 0, n ) sum[i] = w, p[i] = 1;
	rep( i, 1, w ){
		int Len; g(Len);
		while( Len-- ){
			int x; g(x);
			sum[ x ] += now[ p[x] ] - pre[ x ];
			now[ p[x] ] += ( w - i + 1 );
			cnt[ p[x] ] --;
			p[ x ] ++;
			sum[ x ] -= cnt[ p[x] ] * ( w - i + 1 );
			pre[ x ] = now[ p[x] ];
			cnt[ p[x] ]++;
		}
	}
	rep( i, 1, n ){
		sum[i] += now[ p[i] ] - pre[i];
		printf("%.11lf\n",1.0 * sum[i] / ( 1.0 * w ));
	}
	return 0;
}

版权声明
本文为[sgxsgx]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/sgxloveyy/p/14099960.html