首页 > 其他分享 >Codeforces Round 938 (Div. 3) A-H 题解

Codeforces Round 938 (Div. 3) A-H 题解

时间：2024-04-10 20:45:57浏览次数：20  
标签：vector int 题解 ++ -- while 938 solve Div

A - Yogurt Sale

Solution

当 \(2a>b\) 时，显然用 \(a\) 来买两个比较好，否则就用 \(b\) 来买两个比较好

Code

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

void solve() {
    int n; cin >> n;
    int a, b; cin >> a >> b;
    b = min(b, a * 2);
    int ans = n / 2 * b + (n % 2) * a;
    cout << ans << '\n';
}

int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

B - Progressive Square

Solution

取最小的元素为 \(a[1][1]\) 然后构造 \(a\) 数组，排序后和 \(b\) 排序后查看是否相同

Code

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

void solve() {
    ll n, c, d; cin >> n >> c >> d;
    vector<ll> a(n * n);
    for (int i = 0; i < n * n; i++) cin >> a[i];
    vector<vector<ll> > b(n, vector<ll>(n));
    sort (a.begin(), a.end());
    b[0][0] = a[0];
    vector<ll> p;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            if (i == 0) {
                b[i][j] = b[i][j - 1] + d;
                continue;
            }
            b[i][j] = b[i - 1][j] + c;
        }
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            p.push_back(b[i][j]);
    sort (p.begin(), p.end());
    if (p == a)
        cout << "YES\n";
    else 
        cout << "NO\n";
}

int main() {
    freopen ("B.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
}

C - Inhabitant of the Deep Sea

Solution

每次取开头和结尾两个字符，分类讨论哪个字符先取完

最后把没有取完的那个修改后塞回队列即可

具体实现时用 deque

Code

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

typedef long long ll;

void solve() {
    ll n, k; cin >> n >> k;
    deque<ll> a;
    for (int i = 1; i <= n; i++) {
        ll x; cin >> x;
        a.push_back(x);
    }
    int now = 0; // 表示此次攻击的是头还是尾
    int p[2];
    int ans = 0;
    while (k > 0) {
        if (a.size() == 1) {
            if (a[0] <= k) 
                ans ++;
            break;
        }
        p[0] = a.front(); a.pop_front();
        p[1] = a.back(); a.pop_back();
        if (p[now] <= p[now ^ 1]) {
            k -= p[now] * 2 - 1;
            if (k < 0) break;
            ans ++;
            p[now ^ 1] -= p[now] - 1;
            now ^= 1;
            if (now == 0) a.push_front(p[now]);
            else a.push_back(p[now]);
        }
        else {
            k -= p[now ^ 1] * 2;
            if (k < 0) break;
            ans ++;
            p[now] -= p[now ^ 1];
            if (now == 0) a.push_front(p[now]);
            else a.push_back(p[now]);
        }
    }
    cout << ans << '\n';
}

int main() {
    freopen ("C.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
}

D - Inaccurate Subsequence Search

Solution

利用类似于莫队的思想方法

当从区间 \([i,i+L)\) 转移到 \([i+1,i+1+L)\) 时，可以删去一个 \(i\) 位置的数，假设 \(i+L\) 位置的数

我们定义 \(cnt[x]\) 表示在这段区间内 \(x\) 出现的个数，\(tot\) 表示这段区间和 \(b\) 相同的字母个数

当 \(cnt[x]\) 在修改后小于 \(x\) 在 \(b\) 中出现的个数，那么 \(tot++\)

删除同理

Code

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


const int maxn = 1e6 + 5;
int cnt_a[maxn], cnt_b[maxn];

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

    auto insert = [&] (int x) {
        cnt_b[x] ++;
        if (cnt_b[x] <= cnt_a[x]) now_k ++;
    };

    auto del = [&] (int x) {
        if (cnt_b[x] <= cnt_a[x]) now_k --;
        cnt_b[x] --;
    };

    for (int i = 1; i <= m; i++) 
        insert(b[i]);
    int ans = now_k >= k;
    for (int i = m + 1; i <= n; i++) {
        del(b[i - m]);
        insert(b[i]);
        ans += now_k >= k;
    }
    cout << ans << '\n';
    for (int i = 1; i <= n; i++) cnt_b[b[i]] = 0;
    for (int i = 1; i <= m; i++) cnt_a[a[i]] = 0;
}

int main() {
    freopen ("D.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
}

E - Long Inversions

Solution

发现 \(n\) 特别小，考虑暴力

如何 \(check(L)\) 一个长度是否合法

当长度固定时，我们从 \(1\) 开始枚举，左边已经处理完了，此时处理到 \(i\)

当 \(s[i]=0\) 时，我们要以 \(i\) 为左端点执行一次翻转操作来把 \(s[i]\) 变成 \(1\)

此时 \(s[i\sim i+L-1]\) 都需要翻转，但不可能暴力去翻转，使用树状数组给区间加 \(1\)，之后就可以快速查询一个点被翻转了几次了

Code


#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;


void solve() {
    int n; string s; cin >> n >> s;
    s = " " + s;

    vector<int> c(n + 5, 0);
    
    auto add_x = [&] (int x, int data) {
        for (int i = x; i <= n; i += i & -i) 
            c[i] += data;
    };

    auto get_x = [&] (int x) {
        int res = 0;
        for (int i = x; i; i -= i & -i) 
            res += c[i];
        return res;
    };

    auto check = [&] (int L) {
        fill (c.begin(), c.end(), 0);
        for (int i = 1; i + L - 1 <= n; i++) {
            int now = s[i] - '0';
            now ^= (get_x(i) & 1);
            if (now == 0) {
                add_x (i, 1);
                add_x (i + L, -1);
            }
        }
        for (int i = n - L + 1; i <= n; i++) {
            int now = s[i] - '0';
            now ^= (get_x(i) & 1);
            if (now == 0) return false;
        } 
        return true;
    };

    for (int L = n; L >= 1; L--) {
        if (check(L)) {
            cout << L << '\n';
            return;
        }
    }
}

int main() {
    freopen ("E.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
}

F - Unfair Game

Solution

\(4\) 是在单独高位的，所以 \(4\) 对答案的贡献是 \(a_4/2\)

考虑如果 \(a_1,a_2,a_3\) 都为奇数的话，那么异或起来也是零，对答案的贡献就是 \(a_1/2+a_2/2+a_3/2+ 1\)

如果 \(a_1,a_2,a_3\) 都为偶数，对答案的贡献就是 \(a_1/2+a_2/2+a_3/2\)

如果 \(a_1,a_2,a_3\) 不全都是奇数，那么就减少一个，变成偶数的情况，因为在变成偶数的过程中不会产生新的贡献，所以此时对答案的贡献就是 \(a_1/2+a_2/2+a_3/2\)

Code

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

void solve() {
    vector<int> a(5);
    for (int i = 1; i <= 4; i++)
        cin >> a[i];
    int ans = 0;
    if ((a[1] & 1) && (a[2] & 1) && (a[3] & 1)) 
        ans = 1;
    for (int i = 1; i <= 4; i++)
        ans += a[i] / 2;
    cout << ans << '\n';
}

int main() {
    int t; cin >> t;
    while (t--) solve();
}

G - GCD on a grid

Solution

显然，最后的答案肯定是 \(a[1][1]\) 的因子

所以枚举 \(a[1][1]\) 的因子，然后看这个因子是否能跑通全图，能经过一个点的条件是因子能整除这个点的数

还有一点点卡常

Code

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
const int flg[2][2] = {{1, 0}, {0, 1}};


inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void print (int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

const int maxn = 104;
int dp[maxn][maxn];

void solve() {
    int n, m;
    n = read(), m = read();
    vector<vector<int> > a(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            a[i][j] = read();
        }
    
    auto check = [&] (int g) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] = 0;
        dp[1][1] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (a[i][j] % g) dp[i][j] = 0;
                if (dp[i][j]) 
                    dp[i + 1][j] = dp[i][j + 1] = 1;
            }
        if (dp[n][m] == 1) return true;
        else return false;
    };

    int ans = 1;

    auto get_fac = [&] (int x) {
        vector<int> res;
        for (int i = 1; i <= sqrt(x); i++) {
            if (x % i == 0) {
                res.push_back(i);
                if (i * i != x) res.push_back(x / i);
            }
        }
        return res;
    };

    auto g = __gcd(a[1][1], a[n][m]);

    auto fac = get_fac(g);

    sort (fac.begin(), fac.end(), greater<int>());

    for (auto &x : fac) {
        if (check(x) == 1) {
            print(x);
            putchar('\n');
            return;
        }
    }
}

int main() {
    freopen ("G.in", "r", stdin);
    freopen ("G.out", "w", stdout);
    int t; t = read();
    while (t--) solve();
}

H - The Most Reckless Defense

Solution

由于每个 \(r\) 只能给一个塔，所以 \(r\) 就不会太大

\(r<\log_3 nmp\)

所以说 \(r\) 最大值大概在 \(15\) 左右

考虑状压，定义 \(dp[S]\) 表示状态为 \(S\) 时的最大值

先预处理出在每个位置放置半径为 \(r\) 的塔的代价

然后先枚举塔 \(k\)，再枚举状态，最后枚举 \(r\)

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;

int pw3[35];

void init() {
    pw3[0] = 1;
    for (int i = 1; i <= 30; i++) {
        pw3[i] = pw3[i - 1] * 3;
    }
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<char> > mp(n + 1, vector<char>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
        }
    vector<array<int, 3> > tow(k);
    for (int i = 0; i < k; i++) {
        auto &[x, y, p] = tow[i];
        cin >> x >> y >> p;
    }

    auto calc = [&](int id, int r) -> int {
        auto &[x, y, p] = tow[id];
        int ret = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (mp[i][j] == '.') continue;
                if ((x - i) * (x - i) + (y - j) * (y - j) <= r * r) {
                    ret += p;
                }
            }
        return ret;
    };

    int top = 0;
    while (pw3[top] <= n * m * 500)
        top++;
    vector<vector<pii> > ok_tow(k);
    for (int i = 0; i < k; i++)
        for (int r = 1; r < top; r++) {
            int d = calc (i, r);
            d -= pw3[r];
            if (d > 0) {
                ok_tow[i].push_back({r, d});
            }
        }

    vector<int> dp(1 << top, 0);
    for (int j = 0; j < k; j++) { // 枚举位置
        for (int S = (1 << top) - 1; S >= 1; S--) { //枚举状态
            for (auto [x, d] : ok_tow[j]) { //枚举用那个r
                if (! (S >> x & 1)) continue;
                dp[S] = max(dp[S], dp[S ^ (1 << x)] + d);
            }
        }
    }
    int ans = *max_element(dp.begin(), dp.end());
    cout << ans << '\n';
}

signed main() {
    freopen("H.in", "r", stdin);
    init();
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

标签：vector,int,题解,++,--,while,938,solve,Div
From： https://www.cnblogs.com/martian148/p/18127361

相关文章

  • AT_agc038_e [AGC038E] Gachapon 题解
    比较基础的一道题。很容易想到Min-Max容斥：\[E(\max(S))=\sum_{T\subeS}(-1)^{|T|-1}\timesE(\min(T))\]然后发现\(E(\min(T))=\sum_{k\ge0}P(\min(T)\gek)\)。考虑dp，记\(f_{i,j,k}\)表示从前\(i\)个数中选出\(T\)，\(\sum_{i\inT}A_i=j,\sum_{i\inT}c_i=k\)且每个......
  • MHY1001. [崩三]椰子树题解
    #include<bits/stdc++.h>usingnamespacestd;constintN=1010,M=20010;intq[M];//s的最大值为20000，v的最小值为1，所以队列里面最多是会有200010个元素的intn,m;intf[M],g[M];intmain(){cin>>n>>m;for(inti=1;i<=n;++i){......
  • CF1804C Pull Your Luck 题解
    题面。翻译清晰，这里就不吐槽了。根据轮盘转动的方法，可以看出这是一个简单的高斯求和。因为这是一个轮盘，在轮盘中转动了\(now\)个格子与转动了\(now\bmodn\)所到达的格子是一样的（这就没必要证明了吧），因此我们很容易就能得到一个最朴素的代码： cin>>T; while(T--) { c......
  • P3891 [GDOI2014] 采集资源 题解
    题面。看到大家都是两个动态规划的写法，来给大家讲一下只用一次动态规划的写法。思路设\(f_{i,j}\)表示工作效率为\(i\)，获取\(j\)点资源所需的最短时间，不以苦工设状态是因为苦工会因为后面购买而改变，不太现实。\(tme\)表示答案，即到达\(t\)点资源所需的最短时间。从\(0......
  • P8661 [蓝桥杯 2018 省 B] 日志统计 题解
    好久没写题解了，水一篇。这里主要想讲的是不同的处理方法，在阅读本篇题解前请确保读完题。详解一，排序这很好理解，题目要求将热帖从小到大输出，同时题目中还有相对的时间这一概念，因此将输入的\(id\)与\(ts\)按照优先\(id\)其次\(ts\)的排序方式从小到大，排序，这样输出时就没......
  • CF133B Unary 题解
    题面。在考虑如何优化程序时，不要忽略了这题的纯暴力做法。对于样例2此处样例2的输入应该是++++[>,.<-]，也许是翻译问题，但并不重要。思路依据题意，将输入的字符串\(s\)转为其对应的二进制串\(str\)，在暴力将\(str\)由二进制转为十进制即可。代码为了防止因为幂运算而......
  • CF1913C Game with Multiset 题解
    翻译初始时你有一个空序列，共\(m\)次操作，每次操作读入两个数\(t_i\)，\(v_i\)，分为以下两种操作：当\(t_i=1\)时，在空序列中加入\(2^{v_i}\)这一元素。（此时\(0\lev_i\le29\)）当\(t_i=2\)时，询问是否存在：取当前序列的某些元素，使它们的的和等于\(v_i\)（此时\(0\lev_i\l......
  • CF1913B Swap and Delete 题解
    翻译给定一个字符串\(s\)，你有两种操作：删除一个字符。（花费一枚金币）交换某两个字符的位置。（不花费金币）假设经过若干次操作后得到的字符串为\(t\)。\(t\)是好的当且仅当对于任意的\(i\)（\(1\lei\le|t|\)，\(|t|\)为字符串\(t\)的长度），均满足\(t_i\nes_i\)。（\(s\)是......
  • CF1907B YetnotherrokenKeoard 题解
    比较简单，建议评橙。题面。思路对于每个给定的字符串，用两个大根堆来分别记录小写字母与大写字母，注意这里记录时不要记录大写的B和小写的b。每当出现一个B时，从记录大写字母的大根堆中取出目前最后录入的大写字母的位置，标记，接着弹出堆顶元素，标记。小写字母同理。以上操作在......
  • CF1891B Deja Vu 题解
    建议凭橙，思路橙，码量红到橙。题面。思路一，暴力直接依照题意模拟，复杂度\(O(tqn^2)\)，看一眼数据范围，妥妥T飞，倒在第三个点。二，逐步优化看一眼数据发现，虽然\(q\)很大，但实际上\(x\)只有三十个值，因此首先预处理出从\(2^1\)到\(2^{30}\)的所有值，摘掉一个\(n\)，复杂度\(O......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99