BestCoder Round# 45 题解

http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=604

题目在HDOJ上是5272~5275

A:给你一个数,问你它的二进制表示中有多少组1(两个1如果中间没有0算一组)

模拟

B:给出一个序列\(a_1\sim a_n\),每次询问区间\([L,R]\)的逆序对个数

令\(ans[i][j]\)为区间\([i,j]\)的逆序对个数,暴力算出\(ans[1][1\dots n]\),然后考虑\(ans[i][j](i\ge 2)\)。\(ans[i][j]\)比\(ans[i-1][j]\)少了\(a_{i-1}\)这个数的贡献,所以计算\(ans[i]\)这一维的时候开一个变量\(cnt\),扫到\(j\)的时候,如果\(a_{i-1}>a_j\)则\(cnt++\),那么\(ans[i][j]=ans[i-1][j]-cnt\)。

当然也可以枚举起点用树状数组算出\(ans[i][j]\)(归并是做不到的233,BIT大法好),只不过复杂度由\(O(n^2)\)变成了\(O(n^2\ log\ n)\)。

C:给一棵树,资瓷两种操作:

\(0\ x\ y\):把编号为\(x\)的点的权值修改成\(y\)

\(1\ x\ y\):询问对于\(x~y\)路径上的点权是否都出现偶数次。如果不是,输出出现奇数次的那个点权。否则输出-1。保证每次询问的路径上最多只有一种点权出现了奇数次。

树链剖分模板题。。注意点权可以是0,要全部+1,输出的时候再减掉

注意如果是dfs树链剖分的话要开栈外挂。

这题我写的LCT TLE了,不知道有没有人用LCT过。。

呃。。贴的以前的模板,所以代码风格不太对不要在意。。

D:给出一堆平面上的点,每次询问\((L,R,x)\) ,要求用\([L,R]\)这些点拟合一个\(R-L\)阶多项式,输出\(x\)带入多项式之后得到的值。

牛顿插值模板题,不会的话请百度

 

发表评论

电子邮件地址不会被公开。

*