Codeforces Round #791 (Div. 2)(A-D)

这篇具有很好参考价值的文章主要介绍了Codeforces Round #791 (Div. 2)(A-D)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Codeforces Round #791 (Div. 2)(A-D)

A. AvtoBus

题意:

给你 n, 问满足 4 x + 6 y = n 4x+6y=n 4x+6y=n x + y x+y x+y的最小值和最大值是多少? x , y x,y x,y 都是非负整数。

题解:

n如果是奇数,无解。如果是偶数,等式除以2,考虑 2 x + 3 y = n 2x+3y=n 2x+3y=n

要想使得 x + y x+y x+y尽可能大,那么x要尽量多,就需要找最小的y满足 n − 3 y n-3y n3y是偶数,分别讨论摸3的各种情况。反之同理。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    ll n;

    cin >> t;
    while (t--) {
        cin >> n;
        if (n & 1 || n == 2) {
            cout << -1 << endl;
            continue;
        }

        n /= 2;

        ll mi = 1e9, mx = 0;

        if (n < 4) {
            cout << "1 1" << endl;
            continue;
        }

        switch (n % 3) {
        case 0:
            mi = n / 3;
            break;
        case 1:
            mi = (n - 4) / 3 + 2;
            break;
        case 2:
            mi = (n - 2) / 3 + 1;
            break;
        default:
            break;
        }

        if (n & 1) {
            mx = max(mi, 1 + (n - 3) / 2);
        }
        else {
            mx = max(mi, n / 2);
        }


        cout << mi << ' ' << mx << endl;
    }
    return 0;
}

B. Stone Age Problem

题意:

给你 长度为 n n n的数组 a a a, 有两种操作:

  1. a i a_i ai改成 x x x
  2. 把所有数改成 x x x

输出每次操作后

题解:

单点更新,区间更新,维护区间和,这不就是线段树吗,练板子了。。。。当然,这里是区间赋值

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;


int n, q, a[MAXN];

struct node {
    int l, r;
    ll lazy;
    ll sum;
} tr[MAXN << 2];

inline int lson(int x) {
    return x << 1;
}
inline int rson(int x) {
    return x << 1 | 1;
}

void pushup(int x) {
    tr[x].sum = tr[lson(x)].sum + tr[rson(x)].sum;
}

void pushdown(int x) {
    if (tr[x].lazy) {
        tr[lson(x)].lazy = tr[x].lazy;
        tr[rson(x)].lazy = tr[x].lazy;
        tr[lson(x)].sum = (tr[lson(x)].r - tr[lson(x)].l + 1) * tr[x].lazy;
        tr[rson(x)].sum = (tr[rson(x)].r - tr[rson(x)].l + 1) * tr[x].lazy;
        tr[x].lazy = 0;
    }
}

void build(int x, int l, int r) {
    tr[x].l = l, tr[x].r = r, tr[x].lazy = 0;
    if (l == r) {
        return;
    }

    int mid = l + r >> 1;
    build(lson(x), l, mid);
    build(rson(x), mid + 1, r);
    pushup(x);
}

ll query(int x, int l, int r) {
    if (tr[x].l >= l && tr[x].r <= r)
        return tr[x].sum;

    if (tr[x].l > r || tr[x].r < l)
        return 0;

    pushdown(x);
    return query(lson(x), l, r) + query(rson(x), l, r);
}

void update(int x, int l, int r, ll k) {
    if (tr[x].l >= l && tr[x].r <= r) {
        tr[x].lazy = k;
        tr[x].sum = (tr[x].r - tr[x].l + 1) * k;
        return;
    }

    if (tr[x].l > r || tr[x].r < l)
        return;

    pushdown(x);
    update(lson(x), l, r, k);
    update(rson(x), l, r, k);
    pushup(x);
}


int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> q;
    build(1, 1, n);

    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        update(1, i, i, a);
    }

    while (q--) {
        int t, x, i;
        cin >> t;
        if (t == 1) {
            cin >> i >> x;
            update(1, i, i, x);
        }
        else {
            cin >> x;
            update(1, 1, n, x);
        }
        cout << query(1, 1, n) << endl;
    }
    return 0;
}

C. Rooks Defenders

题意:

给你 n*n的国际象棋棋盘,有3种操作:

  1. ( i , j ) (i,j) (i,j)处放一个车
  2. 移除 ( i , j ) (i,j) (i,j)处的车
  3. 查询矩形 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1), (x_2,y_2) (x1,y1),(x2,y2)的所有点是不是都被车攻击到
题解:

用两个树状数组维护行和列能不能被车吃到,放子的时候,注意幂等,也就是说,这一行/列如果已经被车吃到了,就不用放了。

也可以用线段树做,维护区间最小值。

#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef pair<int, int> pii;

const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;

int n, q;

int tr1[MAXN], tr2[MAXN];
int r[MAXN], c[MAXN];
inline int lowbit(int x) {
    return x & (-x);
}

void add(int* tr, int i, int d) {
    while (i <= n) {
        tr[i] += d;
        i += lowbit(i);
    }
}

int sum(int* tr, int i) {
    int res = 0;
    while (i > 0) {
        res += tr[i];
        i -= lowbit(i);
    }
    return res;
}


signed main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    int x, y, x1, x2, y1, y2;

    cin >> n >> q;
    while (q--) {
        cin >> t;
        if (t == 1) {
            cin >> x >> y;
            r[x]++, c[y]++;
            if (r[x] == 1) add(tr1, x, 1);
            if (c[y] == 1) add(tr2, y, 1);
        }
        else if (t == 2) {
            cin >> x >> y;
            r[x]--, c[y]--;
            if (r[x] == 0) add(tr1, x, -1);
            if (c[y] == 0) add(tr2, y, -1);
        }
        else {
            cin >> x1 >> y1 >> x2 >> y2;

            bool row = sum(tr1, x2) - sum(tr1, x1 - 1) >= x2 - x1 + 1;
            bool col = sum(tr2, y2) - sum(tr2, y1 - 1) >= y2 - y1 + 1;

            puts((row || col) ? "Yes" : "No");
        }
    }
    return 0;
}

D.Toss a Coin to Your Graph…

题意:

给你一个图,选择一条长度为 k − 1 k-1 k1的路径,使得沿路k个点的点权的最大值最小

题解:

看到最X值最X,刻在DNA里就是“二分答案“,那么我们可以看出答案最大值为点权最大值1e9,最小值为0,二分答案记为mid,则问题转化为:

是否存在一条长度为 k − 1 k-1 k1 的路径,使得沿路k个点的点权不超过 m i d mid mid ?

可以想到,如果存在,那么这条路径经过的点的点权都不超过mid,那就一定在原图里面点权小于mid的子图里面,则问题可以进一步转化为:

给你一个图,是否存在长度为 k − 1 k-1 k1的路径?

这样问题就变得容易解决了,首先如果有环,一定存在任意长度的路径。

否则是个dag图,拓扑排序的时候记录dp[i]表示从入度为0的点走到i点的最长路径,如果走到了k,则直接返回true,否则拓扑排序出来之后判断是否仍有入度不为0的点,如果有,说明一定存在环,若存在环,就说明任意长度的路径都存在,返回true,否则为false。文章来源地址https://www.toymoban.com/news/detail-451467.html

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;

int n, m;
ll k;
ll a[MAXN];

vector<int> g[MAXN];

int in[MAXN];
bool vis[MAXN];
int dp[MAXN];
// 建一个新图
vector<int> g2[MAXN];
unordered_set<int> s;


// if exists path which max number of it <= x
bool check(int x) {
    s.clear();
    for (int i = 1; i <= n; i++) {
        in[i] = vis[i] = dp[i] = 0;
        g2[i].clear();
        if (a[i] <= x) s.insert(i), dp[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (auto j : g[i]) {
            if (s.find(i) != s.end() && s.find(j) != s.end()) {
                g2[i].push_back(j);
                in[j]++;
            }
        }
    }


    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (s.find(i) != s.end() && !in[i]) q.push(i);
    }

    while (!q.empty()) {
        int j = q.front();
        q.pop();
        vis[j] = true;

        if (dp[j] >= k) return true;
        for (auto u : g2[j]) {
            if (!vis[u]) {
                dp[u] = max(dp[u], dp[j] + 1);
                if (dp[u] >= k) return true;
                in[u]--;
                if (!in[u]) q.push(u);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (s.find(i) != s.end() && in[i]) return true;
    }
    return false;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }

    ll l = 0, r = 1e9;
    while (l < r) {
        ll mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    // cout << l << endl;
    if (check(l))cout << l << endl;
    else cout << -1 << endl;

    return 0;
}

到了这里,关于Codeforces Round #791 (Div. 2)(A-D)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Codeforces Round 912 (Div. 2)

    大等于2依据冒泡排序即可排序,因此判断下1即可 对每一个数字找哪一位肯定为0填0其他的填1 从后往前考虑加到当前集合或新立一个集合 从最高位开始考虑能否为1,计算能否时每个数当前位为1

    2024年02月04日
    浏览(45)
  • Codeforces Round 881 (Div. 3)

    给定一个数组,给每个元素涂色。求最大的代价。 代价为每个颜色的代价和。 每个颜色的代价为涂了该颜色的元素的极差。 因为是极差,每个元素要么对答案有正的贡献,要么有负的贡献,要么无贡献。且正负贡献的个数要相同。 因为要最大值,自然就是想有正贡献的是最

    2024年02月09日
    浏览(44)
  • Codeforces Round 867 (Div. 3)

    从所有a[i]+i-1=t的选择种取个max即可 实际上就是取同符号乘积的最大值 找规律,发现结果与边长n的关系是:res = n * (n + 3) - (n - 2) ①当n为奇数时,除了1其他均无解 ②当n为偶数时,我们可以构造一个形如n,1,n - 2,3,...的数列 首先我们可以发现n必定出现在起始位置。如果n不在起

    2024年02月02日
    浏览(49)
  • Codeforces Round 874 (Div. 3)

    用最少的长度为2的字符串按一定规则拼出s。规则是:前一个字符串的尾与后一个字符串的首相同。 统计s中长度为2的不同字符串数量。 给定数组a[n]和b[n],重排b后,令任意|ai−bi|≤k成立(1≤k≤n)数据保证一定有解。 将a和b分别按从小到大的顺序匹配便是最优的,一定能满足

    2024年02月05日
    浏览(38)
  • Codeforces Round 894 (Div. 3)

    签到题 a数组里,大于等于前一个值的a[i]会被写到b里。直接遍历b,如果b[i]比前一个小就在它前面插一个相等的值 计算反过来的长度,判断是否相等就行 对于没有重复口味的集合,能选出的方案是n*(n-1)/2 (从n个里面选2个的组合数)。二分找出需要多少不同口味的冰淇淋,

    2024年02月11日
    浏览(45)
  • Codeforces Round 926 (Div. 2)

    类似于倍投法,就是在一赔一的情况下,第一次压一块钱,每输一次就押注上一次两倍的金额. 假如资金无限的话,这种方法赢的期望为无穷大.原理类似于二进制,不论你输再多次,只要赢一次总额就增加了1.比如 15 二进制1111,前3把一直输,但是只要第4把赢,就一定可以增加 1

    2024年02月20日
    浏览(45)
  • Codeforces Round 868 Div 2

    要求构造一个仅包含 (1) 和 (-1) 的长度为 (n) 的数组 (a) ,使得存在 (k) 个下标对 ((i, j), i j) 满足 (a_i times a_j = 1) 。 当有 (x) 个 (1) , (y) 个 (-1) 时,其满足条件的下标对数量为 (frac{x (x - 1)}{2} + frac{y (y - 1)}{2}) 。 由于 (n) 只有 (100) ,直接枚举 (x) 即可。

    2024年02月01日
    浏览(45)
  • Codeforces Round 866 (Div. 2)

    给出一个仅由_或^组成的字符串,你可以在任意位置添加_或^字符,使得字符串满足: 任意字符要么属于^_^的一部分,要么属于^^的一部分。求最少添加的字符数量。 对于_我们只需处理没有组成^_^的_: ①如果_在首位置且左边没有^则添加^ ②如果_在尾位置且右边没有^则添加

    2023年04月25日
    浏览(57)
  • Codeforces Round 871 (Div. 4)

    给定n个长度为10的字符串,问其与codeforces字符串的对应下标字母不同的个数。 对于每个字符串从前往后依次和“codeforces”对应字符比较然后统计不同字母数即可 给定长度为n的数组,问连续相邻为0的最大长度 维护一个全局最大长度res,和当前连续序列的长度cnt。从前往后扫

    2024年02月03日
    浏览(53)
  • Codeforces Round 918 (Div. 4)补题

    Odd One Out(Problem - A - Codeforces) 题目大意:有三个数,其中两个相同,找出不同的那个数。 Not Quite Latin Square(Problem - B - Codeforces) 题目大意:有一个3*3的矩阵,每行每列都由1,2,3三个元素构成,且同行同列中的元素不同,先有一个地方出现空缺,要求输出空缺位置的元素

    2024年02月01日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包