Luogu 2783 有机化学之神偶尔会做作弊

去年NOIP之前做的,人生中第一道黑题,真是可喜可贺可喜可贺(虽然参考了题解) Tarjan缩点重新构图,然后统计题目给定两点的树上距离即可。 上代码

BZOJ 1067 [SCOI2007]降雨量

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 入门教程 #2 手柄控制

0x00 手柄概览

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;

0x01 摇杆与机器人控制

上面我们了解了如何通过编程获取手柄按键与摇杆的状态，下面我们将利用上面的知识开始实际操作。 假设我们的机器人有四个电机分别驱动机器人的前后左右四个轮子，我们将用两种方式通过摇杆控制机器人的运动。 以下的代码是双摇杆控制机器人运动的例子。通过两边摇杆的控制来使机器人比较灵活的前后运动与转弯。

    
    #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;
    }

VEX Robot C 入门教程 #1

rt，应老师要求，为了造福下届学弟学妹，特此写下此入门教程。（下届不是都用 V5 了吗（划掉）） 下面这篇教程相当于一个 Hello World 的例子，将通过程序驱动一个电机。

0x00 Robot C 程序结构

Robot C 中大部分基础语法与 C 语言相同，在此就不一一赘述了（其实是懒）。 一个简单的 Robot C 程序通常是以以下结构存在的:

#pragma config(blablablabla)

void fun(){
/*blablablabla*/
}

task main(){
/*blablablabla*/
}

其中 task 代表一个任务。Robot C 语言支持多任务，在后文中会对此进行介绍。 在将此程序烧写到主控盒后，程序会从 main() 任务开始执行。 在后面的教程中我将介绍有关 Robot C 的编程结构。

0x01 电机驱动

VEX EDR 主控共有十个电机端口，其中有八个为三线端口，其余两个为双线端口。 要通过程序控制电机，我们必须先配置电机。 在 Robot C 中，配置电机可以通过单击_Motor and Sensor Setup_按钮来配置，如图所示:

也可以通过以下代码来配置：

#pragma config(Motor, port2, left_front, tmotorVex393_MC29, openLoop, reversed)

配置完成后，即可开始编程来操控电机。

在 VEX Robot C 中，有一种十分方便的控制电机的方式，那就是 motor[] 数组。 通过使用motor[portX]可以操控端口 X 电机的功率，其中赋值范围为 $$ [-127,127] $$ 。当赋值为负时，电机会反转。 比如，以下代码会使端口 2 的电机正转 1s 后反转 1s 最后停止。

motor[port2] = 127;//将电机 2 设置为最大功率正转
wait1Msec(1000);//此语句的作用为使主控盒延时 1000ms 再执行下面的语句
motor[port2] = -127;//将电机 2 设置为最大功率反转
wait1Msec(1000);
motor[port2] = 0;

以上就是控制电机的一种简单方法了，下面来让我们写一个完整的 VEX Robot C 程序。

#pragma config(Motor, port2, Left, tmotorVex393_MC29, openLoop)

task main(){
    while(1){
        motor[port2] = 127
        wait1Msec(1000);
        motor[port2] = -127;
        wait1Msec(1000);
        motor[port2] = 0;
    }
}

0x02 编译 & 烧写程序

首先确保主控盒烧写了同 Robot C 同版本的固件。 将主控盒通过数据线连接至计算机后，待到主控盒两个 LED 灯变为绿色后，点击 Compile Program 对程序进行重新编译，然后点击 Download 按钮开始烧写程序。

Tyvj 1730 二逼平衡树

目前还没AC qaq

先是写了线段树套splay,然而可耻的挂了.. 然后又写了分块,完美的tle了... 待更新

    
    //分块tle
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    //define
    const int maxn = 300 + 5;
    const int maxm = 5e5 + 5;
    const int inf = 0x7FFFFFFF;
    
    int chunk_len[maxn], chunk[maxn][maxn], a[maxm], n, m, cnt, len;
    
    void modify(int ck, int k){
        a[ck] = k;
        int tmp=(ck + len - 1) / len;
        for(register int i = 1; i <= chunk[tmp][0]; ++i)
            chunk[tmp][i] = a[(tmp - 1) * len + i];
        stable_sort(chunk[tmp] + 1,chunk[tmp] + chunk_len[tmp] + 1);
    }
    
    int __lower_bound(int aa[maxn], int k){
        int ll = 1, rr = aa[0];
        while(ll < rr){
            int mid = ll + rr >> 1;
            if(aa[mid] >= k)rr = mid;
            else ll = mid + 1;
        }
        if(aa[ll] >= k)return ll - 1;
        else return ll;
    }
    
    int __sub_search(int aa[maxn], int k){
        int ll = 1, rr = aa[0];
        while(ll < rr){
            int mid = ll + rr >> 1;
            if(aa[mid + 1] <= k)ll = mid + 1;
            else rr = mid;
        }
        if(aa[ll] <= k)return ll + 1;
        else return ll;
    }
    
    int pre(int l, int r, int k){
        int ll = (l + len - 1) / len;
        int rr = (r + len - 1) / len;
        int ans = -inf;
        if(ll != rr){
            for(register int i = l; i <= ll * len; ++i){
                if(a[i] < k) ans = max(ans, a[i]);
            }
            rr++;
            for(register int i = r; i >= (ll - 1) * len; --i){
                if(a[i] < k) ans = max(ans, a[i]);
            }
            for(register int i = ll; i < rr; ++i){
                if(int tmp = __lower_bound(chunk[i], k) != 0){
                    ans = max(chunk[i][tmp], ans);
                }
            }
        }else{
            for(register int i = l; i <= r; ++i){
                if(a[i] < k){
                    ans = max(ans, a[i]);
                }
            }
        }return ans;
    }
    
    int sub(int l, int r, int k){
        int ll = (l + len - 1) / len;
        int rr = (r + len - 1) / len;
        int ans = inf;
        if(ll != rr){
            for(register int i = l; i <= ll * len; ++i){
                if(a[i] > k) ans = min(ans, a[i]);
            }
            ll++;
            for(register int i = r; i >= (ll - 1) * len; --i){
                if(a[i] > k) ans = min(ans, a[i]);
            }
            for(register int i = ll; i < rr; ++i){
                if(int tmp = __sub_search(chunk[i], k) != chunk_len[i] + 1){
                    ans = min(chunk[i][tmp], ans);
                }
            }
        }else{
            for(register int i = l; i <= r; ++i){
                if(a[i] > k){
                    ans = min(ans, a[i]);
                }
            }
        }return ans;
    }
    
    int rnk(int l, int r, int k){
        int ll = (l + len - 1) / len;
        int rr = (r + len - 1) / len;
        int ans = 0;
        if(ll != rr){
            for(register int i = l; i <= ll * len; ++i){
                if(a[i] < k) ans++;
            }
            ll++;
            for(register int i = r; i >= (ll - 1) * len; --i){
                if(a[i] < k) ans++;
            }
            for(register int i = ll; i < rr; ++i){
                ans += __lower_bound(chunk[i], k);
            }
        }else{
            for(register int i = l; i <= r; ++i){
                if(a[i] < k){
                    ans++;
                }
            }
        }return ans+1;
    }
    
    int kth(int l, int r, int k){
        int ll = 0, rr = inf, ans = 0;
        while(ll < rr){
            int mid = ll + rr >> 1;
            if(rnk(l, r, mid) > k) rr = mid;
            else ll = mid+1, ans = mid;
        }return ans;
    }
    
    //main
    int main(){
        ios::sync_with_stdio(false);
        cin >> n >> m;
        for(register int i = 1; i <=n; ++i){
            cin >> a[i];
        }
        cnt = sqrt(n) + 2;len = cnt;
        for(register int i = 1; i <= cnt; ++i){
            for(register int j = 1; j <= len; ++j){
                chunk[i][j] = a[(i - 1) * len + j];
            }
            stable_sort(chunk[i] + 1, chunk[i] + len + 1);
            chunk_len[i] = len;
        }
        if(n % len != 0){
            cnt++;chunk_len[cnt] = n % len;
            for(register int i = 1; i <= chunk_len[cnt]; ++i){
                chunk[cnt][i] = a[(cnt - 1) * len + i];
            }
            stable_sort(chunk[cnt] + 1, chunk[cnt] + chunk_len[cnt] + 1);
        }
        int opt, x, y, z;
        while(m--){
            cin >> opt;
            if(opt == 1){
                cin >> x >> y >> z;
                cout << rnk(x, y, z) << endl;
            }
            else if(opt == 2){
                cin >> x >> y >> z;
                cout << kth(x, y, z) << endl;
            }
            else if(opt == 3){
                cin >> x >> y;
                modify(x, y);
            }
            else if(opt == 4){
                cin >> x >> y >> z;
                cout << pre(x, y, z) << endl;
            }else {
                cin >> x >> y >> z;
                cout << sub(x, y, z) << endl;
            }
        }
        return 0;
    }

Comments

BeyondLimits: tql%%%

Polarnova: 催更