上次补题好像把两次训练混在一起了，总之先按时间顺序补完这一次|ू･ω･` )
HDU-6301 不会的东西不能逃避.jpg
红小豆非常讨厌构造题，因为非常不会，并且非常逃避学习这类题，因为总也搞不清楚。
这次红小豆搞清楚了一道构造区间数字不重复数列的题。
首先，由于字典序最小，即每次可以直接提取可能值中最小值，且不重复，又可以插入删除，所以我们获得了set（噔噔噔）用ta来装可以填的数。接着，我们考虑大区间包着小区间的情况，显然大区间满足条件时小区间必然满足，所以我们这时可以把小区间视为大区间（合并）。然后，我们考虑互相分离的情况，这时应该把当前左端点到前一个左端点之间的数重新塞回set里，然后再抽一遍最小值。最后，我们考虑很麻烦的交叠情况，就是酱紫的：l1----l2---r1------r2，在l2---r1之间的数不能用在r1----r2中，而l1---l2之间的要塞回set，因此也是靠左端点的记录状态。
综上，我们需要知道每个位置对应的区间左端点，这个我们可以通过记录右端点的左端点，然后检查目前位置的后一个位置（倒着维护一遍必将有右端点），如果指向了更前面（位置编号更小）的地方，那就把目前位置的左端点更新为这个地方，不然的话就指着自己（这样没有被要求的地方就会不断把之前的数塞回set里，于是不断被填成1，得到最小字典序）。每个位置填数时，先将本次左端点和上次左端点之间的数塞回set，之后提取最小，最后从set里清除，输出。
乱码如下
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
int l, r;
int ans[];
int lh[];
int n, m, t; int main()
{
cin >> t;
while (t--) {
cin >> n >> m;
for (int i = ; i <= n; i++) {
ans[i] = ;
lh[i] = i;
}
for (int i = ; i <= m; i++) {
cin >> l>> r;
if (lh[r] > l)lh[r] = l;
}
for (int i = n - ; i >= ; i--)
if (lh[i + ] < lh[i])lh[i] = lh[i + ];
set<int>p;
for (int i = ; i <= n; i++)p.insert(i);
for (int i = ; i <= n; i++) {
for (int j = lh[i - ]; j < lh[i]; j++) p.insert(ans[j]);
ans[i] = *p.begin();
p.erase(p.begin());
if (i == )cout << ans[i];
else if (i == n)cout << " " << ans[n] << endl;
else cout << " " << ans[i];
} }
return ;
}
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，完。
#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[]; int main()
{
int t, n;
cin >> t;
while (t--) {
cin >> n;
for (int i = ; i < * n; i++) {
cin >> p[i].x >> p[i].y;
p[i].num = i + ;
}
sort(p, p + * n);
for (int i = ; i < *n; i += )
cout << p[i].num << " " << p[i + ].num << " " << p[i + ].num << endl;
}
return ;
}
HDU-6300
这次还有一个板子好长的空间几何，还有一个想专门整理一篇的反演|ू･ω･` )
emmm反正我今天不想写了，白天武大onsite很是自闭（但是一起打比赛又很开心），很困又充满迷茫的烦躁。机会留给有准备的人，可是如果每个溜过身边的机会都不想丢失，就要在疲惫之外努力承受总是差一点点的命运扼喉感。毕竟，果断就会白给，太菜才是原罪（支离破碎的发言）