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} data-recalc-dims=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带入多项式之后得到的值。

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

 

发表评论

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

*