2025-10-19 MX-S hetao1733837 的 record

感觉好猎奇啊，居然在补僵尸题……

LGP7057 [NWRRC 2015] Journey to the “The World’s Start”

​
原题链接：[NWRRC 2015] Journey to the “The World’s Start”

分析

T1 放绿在现在看来有一定的先见之明了，因为正赛确实放了一道降黄的绿……
题面有点哈人了……
那，我记录两个？一个时间，一个价格？感觉是个伪科学啊……
那，我可以做一个类似于背包的东西……设 $d{p}_i$ 表示我有 $i$ 元钱，到达 $n$ 站的最小时间。转移……我应该会吧……但是，数组开多少？
假了，那，发现用了还几个“那”了，我们换个思路，发现向左走并不优，而且更大的 $r$ 可以包含之前的，那直接二分不就行了吗？check 套一个 DP，设 $d{p}_i$ 表示经过 $i-1$ 和 $i$ 站的最小时间，转移形如 $d{p}_i=d_i+\underset{j=\max (0,i-x)}{\overset{i-1}{\min }}d{p}_j$。

正解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 50005; 
int n, t, p[N], d[N], dp[N];
int q[N];
bool check(int r){
    int head = 1, tail = 0;
    q[++tail] = 1; 
    dp[1] = 0; 
    for (int i = 2; i <= n; i++){
        while (head <= tail && q[head] < i - r){
            head++;
        }
        dp[i] = dp[q[head]] + d[i];
        while (head <= tail && dp[q[tail]] >= dp[i]){ 
            tail--;
        }
        q[++tail] = i;
    }
    return dp[n] <= t;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> t;
    t -= n - 1;
    for (int i = 1; i < n; i++){
        cin >> p[i];
    }
    for (int i = 2; i < n; i++){
        cin >> d[i];
    }
    int l = 1, r = n - 1;
    while (l < r){
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    int ans = 0x7f7f7f7f;
    for (int i = l; i < n; i++){
        ans = min(ans, p[i]);
    }
    cout << ans;
}

LGP4737 [CERC2017] Buffalo Barricades

原题链接：[CERC2017] Buffalo Barricades

分析

看完题感觉像二位前缀和……手模样例……
哦……原来这样啊……问题在于如何批量 merge……
呃……我看得不是很懂。
花花居然是抄题解的吗/ll
那我怎么办/ll
我尝试理解一下啊……要是理解不了……那，到八点半🕣吧，看不懂就 ctj……
呃……不算很懂吧，就是有一个时间维度，一个纵坐标维度，二者共同起作用，把这个维护了。就这，没了……
哦，换句话说：把加点变成删点。

正解

#include <bits/stdc++.h>
using namespace std;
const int N = 600005;
int n, m, father[N], cnt[N], ans[N], dsu[N];
struct node{
    int x, y, t;
}inp[N];
bool cmp(node tmp1, node tmp2){
    if (tmp1.y != tmp2.y)
        return tmp1.y > tmp2.y;
    return tmp1.t > tmp2.t;
}
set<pair<int, int>> s;
int find(int x){
    return x == dsu[x] ? x : dsu[x] = find(dsu[x]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> inp[i].x >> inp[i].y;
        inp[i].t = 0;
    }
    cin >> m;
    for (int i = 1; i <= m; i++){
        cin >> inp[i + n].x >> inp[i + n].y;
        inp[i + n].t = i;
    }
    sort(inp + 1, inp + n + m + 1, cmp);
    for (int i = 1; i <= n + m; i++){
        if (inp[i].t == 0){ 
            auto it = s.lower_bound({inp[i].x, 0});
            if (it != s.end()){
                cnt[it -> second]++;
            }
        }
        else{ 
            s.insert({inp[i].x, inp[i].t});
            auto it = s.find({inp[i].x, inp[i].t});
            if (++it != s.end()){
                father[inp[i].t] = it -> second;
            }
            while (true){
                it = s.find({inp[i].x, inp[i].t});
                if (it == s.begin())
                    break;
                it--;
                if (it -> second > inp[i].t)
                    s.erase(it);
                else
                    break;
            }
        }
    }
    for (int i = 1; i <= m; i++){
        dsu[i] = i;
    }
    for (int i = m; i >= 1; i--){
        ans[i] = cnt[find(i)];
        if (father[i]){ 
            int x = find(i), y = find(father[i]);
            dsu[x] = y;
            cnt[y] += cnt[x];
        }
    }
    for (int i = 1; i <= m; i++){
        cout << ans[i] << '\n';
    }
}

LGP7054 [NWRRC 2015] Graph

原题链接：[NWRRC 2015] Graph

分析

居然是一道黑吗？事情变得有意思了……不过个人认为，$CSP-S$ 放一道紫之后再放一个黑似乎并不很合理吧……但是，下赛季还真不一定……
呃……我好像没看题……并不很会吧……我得写文化了……看了应该是 fsz 的各种游记，我也想像他一样……
我去写✍文化了……
继续……
我似乎并非很会啊……
没有环？那……我为啥不整成树（似乎太冲动了）
还是不太会啊……我觉得直接看题解吧。
性质：若最终拓扑序为 p，那么存在一种最优方案满足所有加的边都形如 $p_i$ $\to$ $p_{i+1}$
找出所有入度为 $0$ 的点，取出其中最小的 $u$，如果他不是唯一可能入度为 $0$ 的点，那连一条入边；
反之，找出入度可能为 $0$ 的最大值将其替换。

正解

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, k, d[N], topo[N], ncnt;
vector<int> e[N];
priority_queue<int, vector<int>, greater<int>> fr;
priority_queue<int> to;
void del(int u){
	for (auto v : e[u]){
		if (!(--d[v])){
			fr.push(v);
		}
	}
}
bool vis[N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	for (int cs = 1, u, v; cs <= m; cs++){
		cin >> u >> v;
		e[u].push_back(v);
		d[v]++;
	}
	for (int i = 1; i <= n; i++){
		if (d[i] == 0){
			fr.push(i);
		}
	}
	int cnt = 0;
	while (ncnt < n){
		if (fr.empty()){
			int u = to.top();
			to.pop();
			del(u);
			topo[++ncnt] = u;
			continue;
		}
		int u = fr.top();
		fr.pop();
		if (cnt == k){
			del(u);
			topo[++ncnt] = u;
			continue;
		}
		if (!fr.empty()){
			cnt++;
			vis[u] = 1;
			to.push(u);
			continue;
		}
		if (to.empty()){
			del(u);
			topo[++ncnt] = u;
			continue;
		}
		int v = to.top();
		if (v < u){
			del(u);
			topo[++ncnt] = u;
			continue;
		}
		to.pop();
		to.push(u);
		fr.push(v);
		vis[u] = 1;
		cnt++;
	}
	for (int i = 1; i <= n; i++){
		cout << topo[i] << " ";
	}
	cout << '\n';
	cout << cnt << '\n';
	for (int i = 2; i <= n; i++){
		if (vis[topo[i]]){
			cout << topo[i - 1] << " " << topo[i] << '\n';
		}
	}
}