NOIP 2013 火柴排队
很经典的一道题了,然而以前一直懒得做Orz 离散化+树状数组求逆序对
很经典的一道题了,然而以前一直懒得做Orz 离散化+树状数组求逆序对
RT,一道裸的 Kruskal 重构树题。因为存在点与点之间不连通的问题,所以在跑完 Kruskal 以后对每个树以并查集的根为根进行剖分求LCA。
本来想用线段树做,但是考虑到用线段树的话pushup,pushdown函数有点复杂... 看到题目有覆盖操作立刻想到了珂朵莉树,于是现学了一波然后改了一下模板A了这道题。 (珂学是个好东西) (刷这道题全程循环夢違科(珂)学世紀2333333)
这道题是某次 Luogu 月赛的题目。关于这道题的代码,非常神奇的是,这是比赛时某学长看到管理员提交记录的编译信息中含有一句神奇的内建函数 __builtin_popcount() ,然后根据那句话反推出来的。(喂喂喂这算作弊吧) 下面是 GNU 对这个函数的定义
— Built-in Function:
int __builtin_popcount (unsigned int x)
Returns the number of 1-bits in x.
然后是代码
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
using namespace std; //define
unsigned long long ans[3],n,a,b,c,d,x; //main
int main(){
ios::sync_with_stdio(false);
cin>>n>>a>>b>>c>>d>>x;
for(int i=1;i<=n;i++){
x=(a%d*(x%d*x%d)+b*x%d+c)%d;ans[__builtin_popcount(x)&1]++;
}
cout<<ans[0]*ans[1]<<endl;
return 0;
}
xkzzzz: 大家好我是传说中的学长
去年NOIP之前做的,人生中第一道黑题,真是可喜可贺可喜可贺(虽然参考了题解) Tarjan缩点重新构图,然后统计题目给定两点的树上距离即可。 上代码