T1 4883. 灵知的太阳信仰
Description
在炽热的核熔炉中，居住着一位少女，名为灵乌路空。
据说，从来没有人敢踏入过那个熔炉，因为人们畏缩于空所持有的力量——核能。
核焰，可融真金。咳咳。
每次核融的时候，空都会选取一些原子，排成一列。然后，她会将原子序列分成一些段，并将每段进行一次核融。
一个原子有两个属性：质子数和中子数。
每一段需要满足以下条件：
1、同种元素会发生相互排斥，因此，同一段中不能存在两个质子数相同的原子。
2、核融时，空需要对一段原子加以防护，防护罩的数值等于这段中最大的中子数。换句话说，如果这段原子的中子数最大为x，那么空需要付出x的代价建立防护罩。求核融整个原子序列的最小代价和。Input
第一行一个正整数N，表示原子的个数。
接下来N行，每行两个正整数pi和ni，表示第i个原子的质子数和中子数。Output
输出一行一个整数，表示最小代价和。
Sample Input
5 3 11 2 13 1 12 2 9 3 13Sample Output
26Data Constraint
对于20%的数据，1<=n<=100
对于40%的数据，1<=n<=1000
对于100%的数据，1<=n<=105，1<=pi<=n，1<=ni<=2*104
军训 原题，一模一样，把代码复制过来删掉二分再改成min删掉limit就可以过了（划去，我自己打了一遍了的）。甚至不需要线段树！
考场上第一反应就是很像军训，但有感觉不像，想了想感觉贪心可以做，结果就wa了。
反思：多想想学过的知识，贪心尽量证明，不然你就会一分得不到。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define N 100010
using namespace std;
ll n;
ll pi[N];
ll ni[N], x, ans;
ll pos[N], l[N];
ll f[N], q[N], head = 1, tail;
int main() {
freopen("array.in", "r", stdin);
freopen("array.out", "w", stdout);
scanf("%lld", &n);
for(ll i = 1; i <= n; i++) {
scanf("%lld %lld", &pi[i], &ni[i]);
}
for(ll i = 1; i <= n; i++) {
l[i] = pos[pi[i]];
pos[pi[i]] = i;
l[i] = max(l[i], l[i-1]);
}
f[1] = ni[1];
q[++tail] = 1;
for(ll i = 2; i <= n; i++) {
while(head <= tail && q[head] < l[i]) head++;
while(head <= tail && ni[i] >= ni[q[tail]]) tail--;
q[++tail] = i;
f[i] = f[l[i]] + ni[q[head]];
for(ll j = head; j < tail; j++) {
f[i] = min(f[i], f[q[j]] + ni[q[j + 1]]);
}
}
printf("%lld", f[n]);
}
T2 4880. 询问
Description
Input
Output
Sample Input
20 4 1 10 7 5 19 7 3 12 8 11 15 12Sample Output
3Data Constraint
考场上想到权值小的如果被权值大的覆盖，那一定为no，如果并集为空，也一定为no。就是有考场上一些很弱智的问题：
- 怎么判断权值小的一定会被权值大的覆盖？从大到小排序就行了
- 怎么判断几条线段是否会被覆盖？用并查集就行了
- 怎么判断线段的并和交？最智障的问题，求mx和mn就行了。
总之就是做的题少了，不知道这些东西，犯的沙雕错误。另外，考场上一直在尝试用线段树维护，其实是多余的，几行并查集就行了，告诉我们当一个方向钻不通往往是错误的，不要死钻。或许换个方向就行了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
ll n, m;
struct q {
ll l, r, x;
} a[200010], b[200010];
ll fa[2000010];
ll find(ll x) {
ll r = x;
while(fa[r] != r) {
r = fa[r];
}
while(fa[x] != r) {
int fx = fa[x];
fa[x] = r;
x = fx;
}
return r;
}
void merge(ll x, ll y) {
fa[find(x)] = find(y);
}
bool cmp(q x, q y) {
if(x.x == y.x) {
if(x.r == y.r) return x.l < y.l;
return x.r < y.r;
}
return x.x > y.x;
}
bool check(ll x) {
for(ll i = 1; i <= n + 1; i++) {
fa[i] = i;
}
for(ll i = 1; i <= x; i++) {
b[i] = a[i];
}
sort(b + 1, b + 1 + x, cmp);
for(ll i = 1; i <= x; i++) {
ll mxl = b[i].l, mnl = b[i].l, mxr = b[i].r, mnr = b[i].r;
while(i < x && b[i].x == b[i + 1].x) {
i++;
mxl = max(mxl, b[i].l);
mnl = min(mnl, b[i].l);
mxr = max(mxr, b[i].r);
mnr = min(mnr, b[i].r);
}
if(mxl > mnr) return false;
if(find(mxl) > mnr) return false;
for(ll j = mnl; j <= mxr; j = find(j)) {
merge(j, j + 1);
}
}
return true;
}
int main() {
freopen("bales.in", "r", stdin);
freopen("bales.out", "w", stdout);
scanf("%lld %lld", &n, &m);
for(ll i = 1; i <= m; i++) {
scanf("%lld %lld %lld", &a[i].l, &a[i].r, &a[i].x);
}
ll l = 1, r = m, ans = 0;
while(l <= r) {
ll mid = (l + r) >> 1;
if(check(mid)) {
l = mid + 1;
} else {
r = mid - 1;
ans = mid;
}
}
printf("%lld", ans);
}
T3 5401. Star Way To Heaven
Description
Input
Output
Sample Input
10 5 2 1 1 2 3Sample Output
1.11803399Data Constraint
很简单，我们从上到下连边，然后选择一条最优的穿过去就行了。
考试时困扰我的就是怎么连边，其实使用Prim的思想，先找出对于上边界距离最小的，然后每次更新对于最小值的距离，最后直到连接下边界
为什么要二分？不需要啊。
困扰我的教训就是：不要懒，自己手打min、max。不然会被卡常
#include <cmath>
#include <cstdio>
#define ll long long
#define lf long double
ll n, m, k;
bool v[6010];
lf dis[6010], ans;
struct node {
lf x, y;
} a[6010];
lf Dis(node x, node y) {
return sqrt(pow(x.x - y.x, 2)+pow(x.y - y.y, 2));
}
lf max(lf x, lf y) {
return x > y ? x : y;
}
lf min(lf x, lf y) {
return x < y ? x : y;
}
int main() {
freopen("starway.in", "r", stdin);
freopen("starway.out", "w", stdout);
scanf("%lld %lld %lld", &n, &m, &k);
for(ll i = 1; i <= k; i++) {
scanf("%Lf %Lf", &a[i].x, &a[i].y);
dis[i] = m - a[i].y;
}
dis[++k] = m;
while(true) {
ll p = -1;
for(ll i = 1; i <= k; i++) {
if(!v[i] && (p == -1 || dis[i] < dis[p])) {
p = i;
}
}
v[p] = 1;
ans = max(ans, dis[p]);
if(p == k) break;
for(ll i = 1; i < k; i++) {
dis[i] = min(dis[i], Dis(a[p], a[i]));
}
dis[k] = min(dis[k], a[p].y);
}
printf("%.8Lf", ans / 2.0);
}