赛前算法整理

· · 个人记录

基础算法

1. U479810

Contaminated Milk。

算法：模拟。

思路：将每个让喝过者产生问题的牛奶记录每个牛奶让什么人中毒的集合取交集即可。

问题：取交集时实现不清。

正解：维护全局数组 a 与局部对于每个牛奶的数组 b，每次统计 b 中的状态，a_{i} 或上 b_{i} 即可。

2.P4185

P4185 [USACO18JAN] MooTube G。

算法：并查集、连通块。

思路：发现可以对询问离线并按 k 进行排序，每次处理时将边权大于或等于 k 的边加入即可，答案即为这个点所在连通块的大小减去 1。

问题：没有考虑到进行离线操作。

3. P8074

P8074 [COCI 2009/2010 #7] SVEMIR。

算法：Kruskal 最小生成树。

思路：在证明所选边的正确性后使用克鲁斯卡尔即可。

错误：无法证明所选边的正确性。

证明：

  1. 首先证明：如果 A 到 B 的的边权为 w，那么由 A 到 B 的某一条路径上的所有边的边权均 \leq w，且这个路径上的点全部都在 A 与 B 按照某个维度的排序序列中：不妨假设 w=|x_{A}-x_{B}|，那么，按照 x 的排序序列中，因为 A 到 B 的边权为 w，那么 A 与 B 之间的所有相邻点对之间的边权都可以取到 \leq |x_{A}-x_{B}| 即 \leq w，那么这就相当于：在只保留一个维度作为建边的标准后，仍会有一条 A 到 B 的路径中的所有边均 \leq w。
  2. 证明这样建边跑的克鲁斯卡尔是正确的：这个问题相当于证明我们上面建的边形成的集合，包含了原来所需建出的所有边，首先考虑边 (u,v)，如果这个边在原本“所需”的边的集合中，而不在我们建出的边的集合中，那么根据 1，我们自己建的边集合中一定有 u 到 v 的路径上的每条边 \leq w，再结合克鲁斯卡尔算法的更新原理，即每次在未联通的情况下找到最小的边使得两个边相连，那么我们既可以用原来“所需”边集合的边更新，也可以用我们自己的边集合更新，那么由此证毕。

启发：在处理生成树问题时从不等式关系的角度证明边集正确性。

4.WZOI 2044/2445

上网。

算法：动态规划。

思路：考虑从每个点为结尾的点转移过来即可。

错误：没有想到线性规划的方程，写了搜索+神秘优化。

搜索 50pts 代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define int long long
#define pii pair<int,int>
using namespace std;
int n,T,ans=INT_MIN,cnt[2005],f[2005];
struct node {
    int st,ed,w;
}t[2005][2005];
void dfs(int x,int sum) {
    f[x]=max(f[x],sum);
    if(x>T){
        ans=max(ans,f[x]);
        return;
    }
    if(sum<f[x])return;
    dfs(x+1,sum);
    for(int i=1;i<=cnt[x];i++){
        dfs(t[x][i].ed+1,sum+t[x][i].w);
    }
}
signed main() {
    IOS
    cin>>n>>T;
    for(int i=1; i<=n; i++) {
        int x;
        cin>>x;
        for(int j=1,st,ed,w; j<=x; j++) {
            cin>>st>>ed>>w;
            t[st][++cnt[st]]={st,ed,w};
        }
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}

正解代码：

#pragma GCC optimize(2)
#include<vector>
#include<iostream>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define int long long
#define pii pair<int,int>
using namespace std;
int n,T,f[500005];
vector<pii> g[500005];
signed main() {
    IOS
    cin>>n>>T;
    for(int i=1;i<=n;i++){
        int m;
        cin>>m;
        for(int j=1;j<=m;j++){
            int x,y,c;
            cin>>x>>y>>c;
            g[y].push_back({x,c});
        }
    }
    for(int i=1;i<=T;i++){
        f[i]=f[i-1];
        for(auto p:g[i]){
            int x=p.first;
            int c=p.second;
            f[i]=max(f[i],f[x-1]+c);
        }
    }
    cout<<f[T];
    return 0;
}

5. P4181

P4181 [USACO18JAN] Rental Service S。

算法：贪心，双指针。

思路：极简，将出售牛奶收益更大的奶牛用于出售牛奶，剩下的考虑出租即可，统计收益的过程使用双指针。

错误：没有想出贪心策略。

6. CF1407D

CF1407D Discrete Centrifugal Jumps。

算法：单调队列+动态规划。

思路：考虑分类讨论后两个式子，发现其形式可以用单调队列维护，于是转移时运用单调队列即可。

错误：没有想到使用单调队列。

注

原本还有二分+BFS 维护联通块的题目，不方便挂。