BZOJ 1858 [SCOI2010] 序列操作
本来想用线段树做，但是考虑到用线段树的话pushup，pushdown函数有点复杂... 看到题目有覆盖操作立刻想到了珂朵莉树，于是现学了一波然后改了一下模板A了这道题。 (珂学是个好东西) (刷这道题全程循环夢違科(珂)学世紀2333333)
本来想用线段树做，但是考虑到用线段树的话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缩点重新构图,然后统计题目给定两点的树上距离即可。 上代码
todolist清理计划--; 很久很久以前暑假留的作业= = 将年份离散化，用线段树简单的维护最值，然后依照提议判断就好。
#include <iostream>
#include <cstdio>
#define MAYBE cout << "maybe" << endl
#define TRUE cout << "true" << endl
#define FALSE cout << "false" << endl
using namespace std;
//define
const int maxn = 50000 + 5;
int year[maxn], val[maxn], tree[maxn << 2];
int n, m;
void build(int rt, int l, int r){
if(l == r){
tree[rt] = val[l];return ;
}
int mid = l + r >> 1;
build(rt << 1, l ,mid);
build(rt << 1 | 1, mid + 1, r);
tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}
int query(int rt, int l, int r, int ll, int rr){
if(ll <= l && r <= rr){
return tree[rt];
}
int mid = l + r >> 1;
int ans = -1 * 0x7f7f7f7f;
if(ll <= mid)ans = max(ans, query(rt << 1, l, mid, ll, rr));
if(rr > mid)ans = max(ans, query(rt << 1 | 1, mid + 1, r, ll, rr));
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin >> n;
for(register int i = 1; i <= n; ++i)cin >> year[i] >> val[i];
build(1, 1, n);
cin >> m;
while(m--){
int x,y,u,v;
cin >> y >> x;
if(y >= x) { FALSE; continue; }
u=lower_bound(year+1, year+n+1, y) - year;
v=lower_bound(year+1, year+n+1, x) - year;
if(y == year[u] && x == year[v]){
if(val[u] < val[v]) FALSE;
else if(v == u+1){
if(x == y+1)TRUE;
else MAYBE;
}
else{
int w = query(1, 1, n, u+1, v-1);
if(w >= val[v]) FALSE;
else{
if(x-y == v-u)TRUE;
else MAYBE;
}
}
}
else if(y != year[u] && x == year[v]){
if(u == v) MAYBE;
else{
int w = query(1, 1, n, u, v-1);
if(w >= val[v]) FALSE;
else MAYBE;
}
}
else if(y == year[u] && x != year[v]) {
if(v == u+1) MAYBE;
else{
int w = query(1, 1, n, u+1, v-1);
if(val[u] <= w) FALSE;
else MAYBE;
}
}
else if(y != year[u] && x != year[v]) MAYBE;
}
return 0;
}
VEX 手柄共有四组按键与两组摇杆。 在 Robot C 中，手柄的操作也被抽象到一个数组 vexRT[] 上。 在这个数组中，按键以 BtnXY 命名，其中 X 代表按键属于哪一组，Y 代表按键具体的名称。比如 Btn7U 代表第七组按键的 U 键。而摇杆以通道 ChX 命名，其中 X 代表第几通道摇杆。比如 Ch1 代表第一通道的摇杆。 当一个按键按下时，vexRT 数组中对应下标的值会变为 1，而未按下时，数组对应下标的值为 0。 下面是判断一个按键是否被按下的代码，当按键 7U 被按下时，电机 port2 开始以最大速度正转，当按键被松开时，电机 port2 停止转动。
if(vexRT[Btn7U] == 1){
motor[port2] = 127;
}
else if(vexRT[Btn7U] == 0){
motor[port2] = 0;
}
摇杆输出的是一个线性变化的值，其区间大约在 $$[-127,127]$$ 之间，也就是说，我们可以将摇杆值直接赋值给电机，从而实现摇杆控制电机转速。
int speed = vexRT[Ch1];
motor[port2] = speed;
上面我们了解了如何通过编程获取手柄按键与摇杆的状态，下面我们将利用上面的知识开始实际操作。 假设我们的机器人有四个电机分别驱动机器人的前后左右四个轮子，我们将用两种方式通过摇杆控制机器人的运动。 以下的代码是双摇杆控制机器人运动的例子。通过两边摇杆的控制来使机器人比较灵活的前后运动与转弯。
#pragma config(Motor, port2, right_front, tmotorVex393_MC29, openLoop)
#pragma config(Motor, port7, left_back, tmotorVex393_MC29, openLoop, reversed)
#pragma config(Motor, port8, right_back, tmotorVex393_MC29, openLoop)
#pragma config(Motor, port9, left_front, tmotorVex393_MC29, openLoop, reversed)
int left_speed, right_speed, rtX, rtY;
const int noise = 15;//这里指摇杆的"噪音"，即当摇杆值大于这个值时电机才会开始运动。
void DualJoystick(){
left_speed = vexRT[Ch3];
right_speed =vexRT[Ch2];
if(abs(left_speed) > noise && abs(right_speed) > noise){
motor[right_back] = -1 * right_speed;
motor[right_front] = -1 * right_speed;
motor[left_back] = -1 * left_speed;
motor[left_front] = -1 * left_speed;
}else{
motor[right_back] = 0;
motor[right_front] = 0;
motor[left_back] = 0;
motor[left_front] = 0;
}
}
而如果我们要使用单个摇杆控制，我们就要用到差速法，通过获取单个摇杆横竖两个通道的值，分别计算两侧轮子需要的功率，从而实现机器人灵活的操作。 下面是代码。
#pragma config(Motor, port2, right_front, tmotorVex393_MC29, openLoop)
#pragma config(Motor, port7, left_back, tmotorVex393_MC29, openLoop, reversed)
#pragma config(Motor, port8, right_back, tmotorVex393_MC29, openLoop)
#pragma config(Motor, port9, left_front, tmotorVex393_MC29, openLoop, reversed)
int left_speed, right_speed, rtX, rtY;
const int noise = 15;//这里指摇杆的"噪音"，即当摇杆值大于这个值时电机才会开始运动。
void SingleJoystick(){
rtX = vexRT[Ch4];
rtY = vexRT[Ch3];
if(abs(rtX) > noise || abs(rtY) > noise){
if(rtY > -1 * noise){
left_speed = ((-1 * rtY) - rtX) >> 1;
right_speed = ((-1 * rtY) + rtX) >> 1;
}
else if(rtY < -1 * noise){
left_speed = ((-1 * rtY) + rtX) >> 1;
right_speed = ((-1 * rtY) - rtX) >> 1;
}
}
else{
right_speed = 0;
left_speed = 0;
}
motor[left_back] = left_speed;
motor[left_front] = left_speed;
motor[right_back] = right_speed;
motor[right_front] = right_speed;
}