CFR-826-Div.3解题报告

发表于 更新于

F. Multi-Colored Segments

题意：数轴上有 nn 个线段，每个区间有一个颜色 cc，对于每个线段，求与它颜色不同的线段中与它的最短距离。距离定义为两个线段中的点集最近的两个点的距离，如果相交则为 00。

做法1

可以想到按颜色排序，正着扫一遍再反着扫一遍，每次维护当前颜色之前的所有颜色的贡献。

具体地，可以用两个 setset 分别维护出现过的所有 ll 和 rr 的位置，每次查询在当前区间 rr 左边的最大 rr 和当前区间 ll 右边的最小 ll。可以发现，这种做法有一个缺陷，即对于完全被包含的情况无法考虑到。于是我们可以离散化后维护一个权值树状数组，对于每个区间在 ll 处 +1+1，在 r+1r+1 处 −1-1，此时如果存在一个区间包含当前区间 [l,r][l,r]，则对应树状数组里的 1∼r1\sim r 的和大于 00。这是充分不必要条件，但显然不会出错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
struct seg{int l,r,c,num;} a[200010];
int b[400010],ans[200010],cnt=0;
int t[400010];
void add(int x,int y) {
    for(;x<=cnt;x+=x&-x) t[x]+=y;
}
int sum(int x,int res=0) {
    for(;x;x-=x&-x) res+=t[x];
    return res;
}
void chkmin(int &x,int y) {x=min(x,y);}
signed main() {
    int T;
    cin>>T;
    while(T--) {
        cnt=0;
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) ans[i]=1e9;
        for(int i=1;i<=n;i++) {
            cin>>a[i].l>>a[i].r>>a[i].c;
            b[++cnt]=a[i].l,b[++cnt]=a[i].r;
            a[i].num=i;
        }
        sort(b+1,b+cnt+1);
        cnt=unique(b+1,b+cnt+1)-b-1;
        for(int i=1;i<=n;i++) {
            a[i].l=lower_bound(b+1,b+cnt+1,a[i].l)-b;
            a[i].r=lower_bound(b+1,b+cnt+1,a[i].r)-b;
        }
        auto solve=[&]() {
            set<int> l,r;
            for(int i=1;i<=n;i++) {
                if(sum(a[i].r)>0) ans[a[i].num]=0;
                auto tmp1=l.lower_bound(a[i].l);
                if(tmp1!=l.end())
                    chkmin(ans[a[i].num],max(0,b[*tmp1]-b[a[i].r]));
                auto tmp2=r.upper_bound(a[i].r);
                if(tmp2!=r.begin()) {
                    tmp2--;
                    chkmin(ans[a[i].num],max(0,b[a[i].l]-b[*tmp2]));
                }
                if(a[i].c!=a[i+1].c) {
                    for(int j=i;j>0&&a[j].c==a[i].c;j--) {
                        add(a[j].l,1),add(a[j].r+1,-1);
                        l.insert(a[j].l);
                        r.insert(a[j].r);
                    }
                }
            }
        };
        sort(a+1,a+n+1,[](seg x,seg y){return x.c<y.c;});
        for(int i=1;i<=cnt;i++) t[i]=0;
        solve();
        sort(a+1,a+n+1,[](seg x,seg y){return x.c>y.c;});
        for(int i=1;i<=cnt;i++) t[i]=0;
        solve();
        for(int i=1;i<=n;i++)
            cout<<ans[i]<<" ";
        cout<<endl;
    }
    return 0;
}

做法2

同样是按颜色分开考虑，先处理出上文中 setset 维护的部分，然后再统一处理包含的情况。

对于包含的情况，ll 和 rr 分开考虑，我们对于每个坐标（离散化后）预处理出以它为 ll 的所有区间编号以及以它为 rr 的所有区间编号。从左往右扫每个位置，用 setset 维护包含这个位置的所有区间，当碰到 ll 时就加入区间，碰到 rr 时就删除区间。如果我们扫到一个 ll，发现 setset 里还有别的区间并且颜色个数多于 11 个，此时 setset 里所有的区间都是有相交的，答案全部赋成 00，然后从 setset 里删掉即可。维护颜色个数可以使用 mapmap。

By SSRS_

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  for (int i = 0; i < t; i++){
    int n;
    cin >> n;
    vector<int> l(n), r(n), c(n);
    for (int j = 0; j < n; j++){
      cin >> l[j] >> r[j] >> c[j];
      c[j]--;
    }
    vector<vector<int>> id(n);
    for (int j = 0; j < n; j++){
      id[c[j]].push_back(j);
    }
    vector<int> ans(n, INF);
    for (int j = 0; j < 2; j++){
      set<int> st;
      for (int k = 0; k < n; k++){
        for (int x : id[k]){
          auto itr1 = st.lower_bound(l[x]);
          if (itr1 != st.end()){
            ans[x] = min(ans[x], *itr1 - l[x]);
          }
          if (itr1 != st.begin()){
            ans[x] = min(ans[x], l[x] - *prev(itr1));
          }
          auto itr2 = st.lower_bound(r[x]);
          if (itr2 != st.end()){
            ans[x] = min(ans[x], *itr2 - r[x]);
          }
          if (itr2 != st.begin()){
            ans[x] = min(ans[x], r[x] - *prev(itr2));
          }
        }
        for (int x : id[k]){
          st.insert(l[x]);
          st.insert(r[x]);
        }
      }
      reverse(id.begin(), id.end());
    }
    vector<int> x;
    for (int j = 0; j < n; j++){
      x.push_back(l[j]);
      x.push_back(r[j]);
    }
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    for (int j = 0; j < n; j++){
      l[j] = lower_bound(x.begin(), x.end(), l[j]) - x.begin();
      r[j] = lower_bound(x.begin(), x.end(), r[j]) - x.begin();
    }
    int cnt = x.size();
    vector<vector<int>> L(cnt), R(cnt);
    for (int j = 0; j < n; j++){
      L[l[j]].push_back(j);
      R[r[j]].push_back(j);
    }
    set<int> st;
    map<int, int> mp;
    for (int j = 0; j < cnt; j++){
      for (int k : L[j]){
        st.insert(k);
        mp[c[k]]++;
        if (mp.size() > 1){
          for (int a : st){
            ans[a] = 0;
          }
          st.clear();
        }
      }
      for (int k : R[j]){
        mp[c[k]]--;
        if (mp[c[k]] == 0){
          mp.erase(c[k]);
        }
        st.erase(k);
      }
    }
    for (int j = 0; j < n; j++){
      cout << ans[j];
      if (j < n - 1){
        cout << ' ';
      }
    }
    cout << endl;
  }
}

做法3

这次我们不用按颜色分开考虑。我们直接将每段区间分成两个端点，按坐标整体排序，再正反各扫一遍。以从左到右扫为例，扫的过程中维护之前区间中最近和次近的区间 rr 及其颜色（要求这两个值的颜色不同），每次询问如果与最近颜色相同，则取次近颜色，否则取最近颜色。

By jiangly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>

using i64 = long long;

constexpr int inf = 1E9;

void solve() {
    int n;
    std::cin >> n;

    std::vector<std::array<int, 5>> pts(2 * n);
    for (int i = 0; i < n; i++) {
        int l, r, c;
        std::cin >> l >> r >> c;
        pts[2 * i] = {l, r, c, i, 0};
        pts[2 * i + 1] = {r, l, c, i, 1};
    }

    std::sort(pts.begin(), pts.end());

    std::vector<int> ans(n, inf);

    for (int t = 0; t < 2; t++) {
        std::array<int, 2> f[2];
        f[0] = f[1] = {-inf, -1};
        for (auto [x, y, c, i, o] : pts) {
            if (!o) {
                std::array g{y, c};
                if (g > f[0]) {
                    std::swap(g, f[0]);
                }
                if ((g > f[1] && g[1] != f[0][1]) || f[0][1] == f[1][1]) {
                    f[1] = g;
                }
            } else {
                for (auto [z, d] : f) {
                    if (d != c) {
                        ans[i] = std::min(ans[i], std::max(0, y - z));
                    }
                }
            }
        }
        std::reverse(pts.begin(), pts.end());
        for (auto &[x, y, c, i, o] : pts) {
            x = inf - x;
            y = inf - y;
            o ^= 1;
        }
    }

    for (int i = 0; i < n; i++) {
        std::cout << ans[i] << " \n"[i == n - 1];
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

做法4

暴力美学。将所有区间扔到 setset 里，如果没有颜色限制，询问一个区间的答案是很简单的。考虑枚举每个颜色，暴力将该颜色的所有区间全部从 setset 里删掉，然后询问该颜色每个区间的答案，最后将这些区间重新扔回 setset 里。

By Bench0310

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        multiset<int> l,r;
        auto add=[&](int a,int b)
        {
            l.insert(a);
            r.insert(b);
        };
        auto rm=[&](int a,int b)
        {
            l.erase(l.find(a));
            r.erase(r.find(b));
        };
        auto nxt=[&](multiset<int> &s,int x)->int
        {
            auto it=s.lower_bound(x);
            if(it!=s.end()) return (*it);
            else return 2000000000;
        };
        auto prv=[&](multiset<int> &s,int x)->int
        {
            auto it=s.upper_bound(x);
            if(it!=s.begin()) return (*prev(it));
            else return -1000000000;
        };
        auto go=[&](int a,int b)->int
        {
            if(nxt(r,a)<=b||prv(l,b)>=a) return 0;
            return min(a-prv(r,a),nxt(l,b)-b);
        };
        vector<array<int,3>> v[n+1];
        vector<array<int,4>> e(n);
        for(int i=1;i<=n;i++)
        {
            int a,b,c;
            cin >> a >> b >> c;
            v[c].push_back({a,b,i});
            e[i-1]={a,b,c,i};
            add(a,b);
        }
        vector<int> res(n+1,(1<<30));
        for(int i=1;i<=n;i++)
        {
            for(auto [a,b,j]:v[i]) rm(a,b);
            for(auto [a,b,j]:v[i]) res[j]=min(res[j],go(a,b));
            for(auto [a,b,j]:v[i]) add(a,b);
        }
        multiset<array<int,2>> s;
        vector<int> opt(n+1,0);
        for(int i=1;i<=n;i++) s.insert({opt[i],i});
        ranges::sort(e);
        for(auto [a,b,c,j]:e)
        {
            s.erase(s.find({opt[c],c}));
            opt[c]=max(opt[c],b);
            s.insert({opt[c],c});
            auto it=s.rbegin();
            if((*it)[1]==c) it++;
            if((*it)[0]>=b) res[j]=0;
        }
        for(int i=1;i<=n;i++) cout << res[i] << " \n"[i==n];
    }
    return 0;
}

G. Kirill and Company

题意：有一个无向图，边权为 11，给你 ff 个一型点的编号（可以重复）和 kk 个二型点的编号（可以重复）。你需要对于每个一型点选择任意一条从 11 到该节点的最短路并选中该路径上所有的二型点，求最少有多少二型点没被选中（即选中尽可能多的二型点）。k≤6k\le 6。

做法1

很自然的考虑状压 DP。首先预处理，令 f[i][s]f[i][s] 表示 ii 号点能否有一条路径经过 ss 的二型点。这个可以使用一次 BFS 处理出从 11 到每个节点的距离 dis[i]dis[i]，然后只考虑 i→j,dis[i]+1=dis[j]i\to j,dis[i]+1=dis[j] 的转移（为了保证是最短路）。统计答案时，可以使用 g[i][s]g[i][s] 表示前 ii 个一型点能否选中 ss 的二型点。这两次 DP 的状态均为 O(n×2k)O (n\times 2^k)，转移分别为 O(1)O(1) 和 O(2k)O(2^k)，可以通过此题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
using namespace std;
vector<int> a[10010];
int h[10010],x[6],dis[10010];
bool f[10010][70],done[10010],g[10010][70];
signed main() {
    int T;
    cin>>T;
    while(T--) {
        int n,m,t,k;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int s=0;s<64;s++)
                f[i][s]=0;
        for(int i=1;i<=n;i++)
            a[i].clear(),dis[i]=1e9,done[i]=0;
        for(int i=1;i<=m;i++) {
            int u,v;
            cin>>u>>v;
            a[u].push_back(v);
            a[v].push_back(u);
        }
        cin>>t;
        for(int i=1;i<=t;i++)
            for(int s=0;s<64;s++)
                g[i][s]=0;
        for(int i=1;i<=t;i++)
            cin>>h[i];
        cin>>k;
        for(int i=0;i<k;i++) {
            int tt;
            cin>>tt;
            x[i]=h[tt];
        }
        queue<int> q;
        q.push(1),dis[1]=0;
        while(!q.empty()) {
            int u=q.front();q.pop();
            if(done[u]) continue;
            done[u]=1;
            for(int v:a[u])
                if(!done[v]&&dis[v]>dis[u]+1)
                    dis[v]=dis[u]+1,q.push(v);
        }
        queue<pair<int,int> > q2;
        q2.push({1,0});
        while(!q2.empty()) {
            auto [u,s]=q2.front();q2.pop();
            if(f[u][s]) continue;
            for(int i=0;i<(1<<k);i++)
                if((i|s)==s) f[u][s]=1;
            for(int v:a[u])
                if(dis[v]==dis[u]+1) {
                    int tmp=s;
                    for(int i=0;i<k;i++)
                        if(x[i]==v) tmp|=(1<<i);
                    q2.push({v,tmp});
                }
        }
        for(int i=0;i<k;i++) {
            int tmp;
            for(int j=1;j<=t;j++)
                if(h[j]==x[i]) {
                    tmp=j;
                    break;
                }
            for(int j=tmp;j<=t;j++)
                h[j]=h[j+1];
        }
        g[0][0]=1;
        for(int i=1;i<=t-k;i++) {
            for(int s=0;s<(1<<k);s++) {
                for(int s2=0;s2<(1<<k);s2++) {
                    if((s2|s)!=s) continue;
                    if(!f[h[i]][s2]) continue;
                    int x=s^s2;
                    if(g[i-1][x]) g[i][s]=1;
                }
                for(int s2=0;s2<(1<<k);s2++)
                    if((s2|s)==s) g[i][s2]|=g[i][s];
            }
        }
        int ans=k;
        for(int s=0;s<(1<<k);s++)
            if(g[t-k][s])
                ans=min(ans,k-__builtin_popcount(s));
        cout<<ans<<endl;
    }
    return 0;
}

做法2

由于 nn 只有 10001000，可以考虑对每个二型点跑一遍 BFS，求出多源最短路，于是可以简化 DP 过程：枚举 ii 和 ss，直接判断从 11 经过 ss 中的二型点到达 ii 是否为最短路。

By jiangly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>

using i64 = long long;

constexpr int inf = 1E9;

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int f;
    std::cin >> f;

    std::vector<int> h(f);
    for (int i = 0; i < f; i++) {
        std::cin >> h[i];
        h[i]--;
    }

    int k;
    std::cin >> k;
    for (int i = 0; i < k; i++) {
        int p;
        std::cin >> p;
        p--;
        std::swap(h[i], h[p]);
    }

    auto bfs = [&](int s) {
        std::vector<int> d(n, -1);
        std::queue<std::array<int, 2>> q;
        q.push({s, 0});
        while (!q.empty()) {
            auto [x, v] = q.front();
            q.pop();
            if (d[x] != -1) {
                continue;
            }
            d[x] = v;
            for (auto y : adj[x]) {
                q.push({y, v + 1});
            }
        }
        return d;
    };

    auto d0 = bfs(0);
    std::sort(h.begin(), h.begin() + k, [&](int i, int j) {
        return d0[i] < d0[j];
    });
    std::vector<std::vector<int>> d(k);
    for (int i = 0; i < k; i++) {
        d[i] = bfs(h[i]);
    }

    std::vector<int> dp(1 << k);
    dp[0] = 1;

    for (int i = k; i < f; i++) {
        std::vector<int> good(1 << k);
        for (int s = 1; s < (1 << k); s++) {
            int lst = -1;
            int dist = 0;
            for (int i = 0; i < k; i++) {
                if (s >> i & 1) {
                    if (lst == -1) {
                        dist += d0[h[i]];
                    } else {
                        dist += d[lst][h[i]];
                    }
                    lst = i;
                }
            }
            dist += d[lst][h[i]];
            if (dist == d0[h[i]]) {
                good[s] = 1;
            }
        }

        for (int s = (1 << k) - 1; s; s--) {
            for (int t = s; t; t = (t - 1) & s) {
                dp[s] |= dp[s ^ t] & good[t];
            }
        }
    }

    int ans = k;
    for (int i = 0; i < (1 << k); i++) {
        if (dp[i]) {
            ans = std::min(ans, k - __builtin_popcount(i));
        }
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}