slowbyte
首页友链关于

Codeforces Round 1037 (Div. 3)

发表于 2025-07-21 2014 字 11 min read

文章目录
Codeforces Round 1027 (Div. 3)
Codeforces Round 1037 (Div. 3) 的 A-F 题解与思路。

本题解对应源码见仓库 solutions/xcpc/codeforces/1037div3/。

题目链接

A. Only One Digit

题意

给你一个整数 xx 。你需要找出最小的非负整数 yy ，使得数字 xx 和 yy 至少有一个共同的数位。换句话说，必须有一个十进制数字 dd 同时出现在数字 xx 和数字 yy 的表示中。

思路

找 xx 的最小数位值

示例代码

void solve() {
    string s;
    cin >> s;
    cout << *min_element(all(s)) << '\n';
}

B. No Casino in the Mountains

题意

给你一个由 nn 个数字组成的数组 aa 和一个数字 kk 。数值 aia_i 描述了第 ii 天的天气情况：如果第 ii 天下雨，则为 ai=1a_i = 1 ；否则，如果第 ii 天天气晴朗，则为 ai=0a_i = 0 。

让想尽可能多地游览山峰。徒步登顶一座山峰正好需要 kk 天，而在这些天中，每一天的天气都必须很好（ ai=0a_i = 0 ）。也就是说，从形式上看，只有当所有 jj 的所有 aj=0a_j = 0 都是好天气时，他才能在 ii 这一天开始远足。 (i≤j≤i+k−1)(i \leq j \leq i + k - 1) .

每次远足后，在开始下一次远足前，让必须休息至少一天，也就是说，在远足后的第二天，他不能再去远足。

求让最多可以游览的山峰数。

思路

O(N)O(N) 时间内模拟，遇到下雨计数器归零，否则直到达到 kk 天，再空一天

示例代码

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    fer(i, 0, n) cin >> arr[i];

    int res = 0;
    int cnt = 0;

    fer(i, 0, n) {
    	if(arr[i] == 0) cnt++;
    	else cnt = 0;
    	if(cnt == k) {
    		cnt = 0;
    		i++;
    		res++;
    	}
    }
    cout << res << '\n';
}

C. I Will Definitely Make It

题意

你得到了 nn 座塔，编号从 11 到 nn 。塔楼 ii 的高度为 hih_i 。在时间 00 ，你位于指数为 kk 的塔上，当前水位为 11 。

每秒，水位上升 11 个单位。在任何时刻，如果水位的**严格大于你所在高塔的高度，你就会灭亡。

你有一个神奇的能力：在 xx 时刻，你可以开始从塔楼 ii 传送到塔楼 jj ，需要 ∣hi−hj∣\lvert h_i - h_j \rvert 秒。也就是说，在 x+∣hi−hj∣x + \lvert h_i - h_j \rvert 时刻之前，您将在塔楼 ii ，而在 x+∣hi−hj∣x + \lvert h_i - h_j \rvert 时刻，您将移动到塔楼 jj 。您可以在刚刚到达塔楼 jj 的同一时刻开始新的传送。

例如，如果 n=k=4n=k=4 ， h=[4,4,4,2]h=[4, 4, 4, 2] ，那么如果您在 00 时刻从塔楼 44 开始传送到塔楼 11 ，移动过程如下：

请注意，如果塔楼 11 的高度为 55 ，您将无法立即传送到塔楼，因为您将在 22 时刻被淹没。

您的目标是在被水淹没之前到达高度最大的塔楼。

确定这是否可行。

思路

排序，然后依次往上爬，每次和如果爬能上去后的水位进行判断

示例代码

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    fer(i, 0, n) cin >> arr[i];

    int ori = arr[k - 1];

    sort(all(arr));
    if(ori == arr.back()) {
    	cout << "YES\n";
    	return;
    }

    //fer(i, 0, n) dbg_arr(arr, i);

    int id = upper_bound(all(arr), ori) - arr.begin();
    int t = 1;

    fer(i, id, n) {
    	int d = arr[i] - ori;
    	if(t + d <= ori + 1 && ori + d >= arr[i]) {
    		ori = arr[i];
    		t += d;
    	} else {
    		cout << "NO\n";
    		return;
    	}
    }
    cout << "YES\n";
}

D. This Is the Last Time

题意

您会得到 nn 个赌场，编号从 11 到 nn 。每个赌场由三个整数描述： lil_i 、 rir_i 和 realireal_i （ li≤reali≤ril_i \le real_i \le r_i ）。您最初有 kk 枚硬币。

只有当当前的硬币数 xx 满足 li≤x≤ril_i \le x \le r_i 时，您才能在赌场 ii 下注。下注后，您的金币数变为 realireal_i 。

您可以按照任意顺序游览赌场，无需游览所有赌场。每个赌场不能访问超过一次。

您的任务是找到最终能获得的最大金币数。

思路

思路1：

  • 按照 ww 排序，然后贪心，能取到更大的 ww 则取，最终的 ww 即答案

思路2：

  • bfsbfs，先按照 ll 排序，将能达到条件的区间放入队列，然后取 maxmax 后删除这个节点，因为只能用一次
  • 注意 map 内置的二分查找函数是 log(N) 的

示例代码1

void solve() {
    int n, k;
    cin >> n >> k;
    vector<array<int, 3>> arr(n);
    fer(i, 0, n) cin >> arr[i][1] >> arr[i][2] >> arr[i][0];

    sort(all(arr));

    for(auto [w, l, r] : arr) {
    	if(w <= k) continue;
    	if(l <= k && k <= r) {
    		k = max(k, w);
    	}
    }
    cout << k << '\n';
}

示例代码2

void solve() {
    int n, k;
    cin >> n >> k;
    vector<array<int, 3>> arr(n);

    fer(i, 0, n) cin >> arr[i][0] >> arr[i][1] >> arr[i][2];

    sort(all(arr));

    int ind = 0;
    multimap<int, int> mp;
   	queue<int> q;
   	q.push(k);
    int res = k;

    while(!q.empty()) {
    	int u = q.front(); q.pop();

    	while(ind < arr.size() && arr[ind][0] <= u) {
    		mp.emplace(arr[ind][1], arr[ind][2]);
    		ind++;
    	}

    	auto it = mp.lower_bound(u);
    	while(it != mp.end()) {
    		res = max(res, it->second);
    		q.push(it->second);
    		mp.erase(it);
    		it = mp.lower_bound(u);
    	}
    }
    cout << res << '\n';
}

E. G-C-D, Unlucky!

题意

判断是否存在一个数组，使得满足它的前缀 gcdgcd 数组是 pp ，后缀 gcdgcd 数组是 ss 。

思路

需要满足一下条件：

  • p.back() == s.front()
  • p是非递增的，并且严格有p[i + 1] % p[i] == 0
  • s是非递减的，并且严格有s[i] % s[i + 1] == 0
  • 对于每个i，必须有全局 gcd(g)=gcd(p[i],s[i+1])gcd(g) = gcd(p[i], s[i + 1])

示例代码

void solve() {
    int n;
    cin >> n;
    vector<int> p(n), s(n);

    fer(i, 0, n) cin >> p[i];
    fer(i, 0, n) cin >> s[i];

    if(p.back() != s.front()) {
    	cout << "NO" << '\n';
    	return;
    }

    int g = p.back();
    fer(i, 0, n - 1) {
    	if(p[i] % p[i + 1] || s[i + 1] % s[i]) {
    		cout << "NO" << '\n';
    		return;
    	}
    	if(gcd(p[i], s[i + 1]) != g) {
    		cout << "NO" << '\n';
    		return;
    	}
    }
    cout << "YES" << '\n';
}

F. 1-1-1, Free Tree!

题意

给定一棵树 ∗ ，其中有 n 个顶点，编号从 1 到 n 。每个顶点的初始颜色为 ai 。

树的每条边由三个数字定义： ui 、 vi 和 ci ，其中 ui 和 vi 是边的端点， ci 是边的参数。边的代价定义如下：如果顶点 ui 和 vi 的颜色相同，代价为 0 ；否则，代价为 ci 。

我们还给出了 q 个查询。每个查询的形式都是：将顶点 v 重绘为颜色 x 。这些查询相互依赖(每次查询后，颜色变化都会保留)。每次查询后，都需要输出树中所有边的成本总和。

∗ 树是没有循环的连通图。

思路

建树之后需要维护一下信息：

  • 邻接表vector<vector<pii>> g(n + 1, vector<pii>());
  • 每个节点的父节点fa表
  • 节点i指向父节点的边权重（不管颜色是否相同）vector<int> w(n + 1)
  • 每个节点的所有某种颜色的子节点的总权值vector<map<int, ll>> mp(n + 1);

步骤：

  • dfs可以解决fa表,w表，mp表的初始状态
  • 对于每次查询，都分别讨论对父节点的影响（贡献）变化，和子节点的关系（贡献变化）

示例代码

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> col(n + 1);
    fer(i, 1, n + 1) cin >> col[i];
    //vector<pii> g[n + 1];
    vector<vector<pii>> g(n + 1, vector<pii>());

    fer(i, 0, n - 1) {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }

    // mp[i][col]: 节点i的col颜色子节点总权值
    vector<map<int, ll>> mp(n + 1);
    vector<int> fa(n + 1, -1);
    // w[i]:i指向其父节点的边权值
    vector<int> w(n + 1);

    ll ans = 0;

    auto dfs = [&](this auto &&self, int u) -> void {
        for(auto [v, c] : g[u]) {
            if(v == fa[u]) continue;
            fa[v] = u;
            w[v] = c;
            mp[u][col[v]] += c;
            if(col[u] != col[v]) ans += c;
            self(v);
        }
    };
    dfs(1);

    // function<void(int)> dfs = [&](int u) -> void {
    //     for(auto [v, c] : g[u]) {
    //         if(v == fa[u]) continue;
    //         fa[v] = u;
    //         w[v] = c;
    //         mp[u][col[v]] += c;
    //         if(col[u] != col[v]) ans += c;
    //         dfs(v);
    //     }
    // };

    //dfs(1);

    while(q--) {
        int u, x;
        cin >> u >> x;

        if(fa[u] != -1) {
            if(col[u] == col[fa[u]]) {
                ans += w[u];
            }
            if(x == col[fa[u]]) ans -= w[u];

            mp[fa[u]][col[u]] -= w[u];
            mp[fa[u]][x] += w[u];
        }

        if(mp[u].count(col[u])) ans += mp[u][col[u]];
        if(mp[u].count(x)) ans -= mp[u][x];

        col[u] = x;
        cout << ans << '\n';
    }
}

推荐文章

1
Graph
并查集习题题解（牛客）
2
Graph
LCA（最近公共祖先）算法
3
DP
分组背包变式：每组最多选 $d_i$ 件
4
Graph
图的直径
5
Bitwise
位运算实用技巧

相关文章

1
Codeforces
Codeforces Round 1027 (Div. 3)
2
Codeforces
Codeforces Round 1013 (Div. 3)
3
Codeforces
Codeforces Round 1028 (Div. 2)
4
Codeforces
Codeforces Educational Round 179
5
Codeforces
Codeforces Round 1029 (Div. 3)