Codeforces Round 933 (Div. 3)

Codeforces Round 933 (Div. 3)

A

思路

数据量较小，遍历所有可能累加即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];

    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (a[i] + b[j] <= k)
                ans++;
        }
    }
    cout << ans << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

B

思路

对于 \(a_{i-1}\ (2\le i\le n-1)\) ，想让 \(a_{i-1}\) 变为 \(0\) 只能对 \(a_{i}\) 操作，遍历所有的可能操作的索引，进行最优操作即使 \(a_{i-1}\) 变为 \(0\)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 2; i < n; i++)
    {
        a[i] -= 2 * a[i - 1];
        a[i + 1] -= a[i - 1];
        a[i - 1] -= a[i - 1];

        if (a[i] < 0 || a[i + 1] < 0)
        {
            cout << "NO\n";
            return;
        }
    }

    cout << (a[n] == 0 && a[n - 1] == 0 ? "YES\n" : "NO\n");
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

C

思路

对于 \(map\) 和 \(pie\) 只需删除中间的 \(a\) 和 \(i\) 即可变为漂亮的。

对于 \(mapie\) 需要删除中间 \(p\) 即可变为漂亮的

所以我们只需找出 \(map\) 和 \(pie\) 的数量即可，特别的是如果一个 \(p\) 同时被 \(map\) 和 \(pie\) 使用，优先给 \(map\)

故答案为 \(\mathrm{cnt}(map)+\mathrm{cnt}(pie)\)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (i < n - 2 && s.substr(i, 3) == "map" || s.substr(i, 3) == "pie")
            ans++, i += 2;
    }
    cout << ans << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

D

思路

模拟题意，进行 \(BFS\)，特别的是本题需要去重，故使用 \(set\)，否则如果每次都给两个方向传球会 \(TLE\)

还需注意编号是从 \(1\) 开始的，要对取模后的 \(0\) 进行处理。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

    set<int> now, tmp;
    now.insert(x);

    while (m--)
    {
        int d;
        char flag;
        cin >> d >> flag;

        tmp.clear();
        for (int it : now)
        {
            if (flag == '0' || flag == '?')
                tmp.insert((it + n + d) % n);
            if (flag == '1' || flag == '?')
                tmp.insert((it + n - d) % n);
        }

        now = tmp;
    }

    if (*now.begin() == 0)
    {
        now.erase(0);
        now.insert(n);
    }

    cout << now.size() << '\n';
    for (int it : now)
        cout << it << ' ';
    cout << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

E

思路

动态规划，对每一行进行操作

\(dp[i]\) 表示当桥的长度为 \(i\) 时的花费。

状态转移方程为：\(dp[i] = \min(dp[i-d-1], \dots, dp[i-1])+(a[i]+1)\)，即从能搭过来的花费最小的支架搭到 \(i\)

需要连续建造 \(k\) 座桥，故用前缀和优化

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n, m, k, d;
    cin >> n >> m >> k >> d;

    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    vector<ll> res(n + 1);
    for (int i = 1; i <= n; i++)
    {
        vector<ll> dp(m + 1);
        dp[1] = 1;
        multiset<ll> st = {dp[1]};
        for (int j = 2; j <= m; j++)
        {
            if (j - d - 1 - 1 >= 1)
                st.erase(st.find(dp[j - d - 1 - 1]));
            dp[j] = *st.begin() + a[i][j] + 1;
            st.insert(dp[j]);
        }
        res[i] = dp[m];
    }

    partial_sum(res.begin(), res.end(), res.begin());
    ll ans = 0x3f3f3f3f3f3f3f3f;
    for (int i = k; i <= n; i++)
        ans = min(ans, res[i] - res[i - k]);
    cout << ans << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

F

思路

二分答案 \(d\)

对于每个相邻的问题，判断间隔是否大于 \(d\)，如果大于 \(d\) 则需要元素，记录有多少间隔过大。

如果只有一个间隔过大，我们要先判断间隔可能插入的元素大小，通过二分查找判断是否存在此元素

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, k;
vector<int> a, d, f;

bool check(int x)
{
   vector<pair<int, int>> v;
   for (int i = 1; i < n; i++)
   {
      if (a[i] - a[i - 1] > x)
      {
         v.push_back({a[i - 1], a[i]});
         if (v.size() > 1)
            return false;
      }
   }
   if (v.empty())
      return true;

   int l = v[0].second - x, r = v[0].first + x;
   if (r < l)
      return false;

   for (auto i : d)
   {
      if (i >= r)
         break;
      auto p = lower_bound(f.begin(), f.end(), l - i);
      if (p != f.end() && *p + i <= r)
         return true;
   }
   return false;
}

void solve()
{
   cin >> n >> m >> k;
   a.resize(n);
   d.resize(m);
   f.resize(k);
   for (auto &it : a)
      cin >> it;
   for (auto &it : d)
      cin >> it;
   for (auto &it : f)
      cin >> it;

   sort(d.begin(), d.end());
   sort(f.begin(), f.end());

   int l = 0, r = 0x7fffffff, ans = 0;
   while (l <= r)
   {
      int mid = r - (r - l) / 2;
      if (check(mid))
         ans = mid, r = mid - 1;
      else
         l = mid + 1;
   }
   cout << ans << '\n';
}

int main()
{
   cin.tie(0)->ios::sync_with_stdio(false);

   int t = 1;
   cin >> t;
   while (t--)
      solve();

   return 0;
}

G

思路

双端队列 \(dq\) 中的 \(d,u,a\) 分别表示到 \(u\) 上一个颜色是 \(a\) 的距离是 \(d\) ，当 \(a=0\) 时 \(d\) 表示从起点到 \(u\) 的距离

如果 \(a\) 有值说明有颜色，则到达同色的节点花费为 \(0\)

如果 \(a=0\)，就通往别的颜色的节点，花费为 \(1\)

为了让花费低的优先搜索，将花费为 \(0\) 的情况放在队首，将花费为 \(1\) 的情况放在队尾

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<map<int, vector<int>>> g(n + 1);

    for (int i = 0; i < m; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        g[u][c].push_back(v);
        g[v][c].push_back(u);
    }

    map<pair<int, int>, int> dis;
    deque<tuple<int, int, int>> dq;
    int b, e;
    cin >> b >> e;
    dq.push_back({0, b, 0});
    while (!dq.empty())
    {
        auto [d, u, a] = dq.front();
        dq.pop_front();

        if (dis.count({u, a}))
            continue;
        dis[{u, a}] = d;

        if (a)
        {
            dq.push_front({d, u, 0});
            for (auto v : g[u][a])
                dq.push_front({d, v, a});
        }
        else
        {
            for (auto [a, _] : g[u])
                dq.push_back({d + 1, u, a});
        }
    }

    cout << dis[{e, 0}] << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

ACM > 题解 > Codeforces

#算法 #Codeforces

Codeforces Round 933 (Div. 3)

http://xiaowhang.github.io/archives/744274538/

作者

Xiaowhang

发布于

2024年3月12日

许可协议

Educational Codeforces Round 163 (Rated for Div. 2) 上一篇

字典树下一篇