[数]补题ver.

骑猪看日落 2022-01-06 10:09 262阅读 0赞

上次补题好像把两次训练混在一起了，总之先按时间顺序补完这一次|ू･ω･\` )

*HDU-6301*　　不会的东西不能逃避.jpg

红小豆非常讨厌构造题，因为非常不会，并且非常逃避学习这类题，因为总也搞不清楚。

这次红小豆搞清楚了一道构造区间数字不重复数列的题。

首先，由于字典序最小，即每次可以直接提取可能值中**最小值**，且**不重复**，又可以**插入删除**，所以我们获得了**set**（噔噔噔）用ta来装可以填的数。接着，我们考虑大区间包着小区间的情况，显然大区间满足条件时小区间必然满足，所以我们这时可以把小区间视为大区间（合并）。然后，我们考虑互相分离的情况，这时应该把当前左端点到前一个左端点之间的数重新塞回set里，然后再抽一遍最小值。最后，我们考虑很麻烦的交叠情况，就是酱紫的：l1----l2---r1------r2，在l2---r1之间的数不能用在r1----r2中，而l1---l2之间的要塞回set，因此也是靠左端点的记录状态。

综上，我们需要知道每个位置对应的区间左端点，这个我们可以通过记录右端点的左端点，然后检查目前位置的后一个位置（倒着维护一遍必将有右端点），如果指向了更前面（位置编号更小）的地方，那就把目前位置的左端点更新为这个地方，不然的话就指着自己（这样没有被要求的地方就会不断把之前的数塞回set里，于是不断被填成1，得到最小字典序）。每个位置填数时，先将本次左端点和上次左端点之间的数塞回set，之后提取最小，最后从set里清除，输出。

乱码如下

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<set>
    using namespace std;
    int l, r;
    int ans[100005];
    int lh[100005];
    int n, m, t;
    
    int main()
    {
        cin >> t;
        while (t--) {
            cin >> n >> m;
            for (int i = 0; i <= n; i++) {
                ans[i] = 1;
                lh[i] = i;
            }
            for (int i = 1; i <= m; i++) {
                cin >> l>> r;
                if (lh[r] > l)lh[r] = l;
            }
            for (int i = n - 1; i >= 1; i--)
                if (lh[i + 1] < lh[i])lh[i] = lh[i + 1];
            set<int>p;
            for (int i = 1; i <= n; i++)p.insert(i);
            for (int i = 1; i <= n; i++) {
                for (int j = lh[i - 1]; j < lh[i]; j++)    p.insert(ans[j]);
                ans[i] = *p.begin();
                p.erase(p.begin());
                if (i == 1)cout << ans[i];
                else if (i == n)cout << " " << ans[n] << endl;
                else cout << " " << ans[i];
            }
    
        }
        return 0;
    }

HDU-6301

我看到的题解里用pair来存要求区间，可是后面并没有再用到这个区间，所以就直接用l和r吧。定义在循环里的set就可以每次都清空了（比如某次搜索wa到爆炸是因为队列定义在了外面嘤）。第一个循环不从0开始的话（因为我后面从1开始）就会有很多零被填到数列里。。。

*HDU-6300*　　有些东西总是要学会的，脑子有坑是为了增大皮层面积

发现一道水题，反而补的时候wa了两次，然后改了排序cmp学会了bool operator（一直固执地手写cmp），最后发现是输出错误（逐渐KAI化）。我是三个三个跳着输出的，i最后还是会到3\*n，想着输出n次就定了小于n嘤

给的是n，输入点输出点都是3\*n，完。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    struct node {
        int x, y, num;
        bool operator < (const node&a) const{
            if (a.x == x)return y < a.y;
            return x < a.x;
        }
    }p[3005];
    
    int main()
    {
        int t, n;
        cin >> t;
        while (t--) {
            cin >> n;
            for (int i = 0; i < 3 * n; i++) {
                cin >> p[i].x >> p[i].y;
                p[i].num = i + 1;
            }
            sort(p, p + 3 * n);
            for (int i = 0; i < 3*n; i += 3)
                cout << p[i].num << " " << p[i + 1].num << " " << p[i + 2].num << endl;
        }
        return 0;
    }

HDU-6300

这次还有一个板子好长的空间几何，还有一个想专门整理一篇的反演|ू･ω･\` )

emmm反正我今天不想写了，白天武大onsite很是自闭（但是一起打比赛又很开心），很困又充满迷茫的烦躁。机会留给有准备的人，可是如果每个溜过身边的机会都不想丢失，就要在疲惫之外努力承受总是差一点点的命运扼喉感。毕竟，果断就会白给，太菜才是原罪（支离破碎的发言）

转载于:https://www.cnblogs.com/non-/p/10707315.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211227/ab484995d802482aa5a3989fd28b7350.png