首页 > 其他分享 >Codeforces Round 956 (Div. 2) 部分题解A~C

Codeforces Round 956 (Div. 2) 部分题解A~C

时间：2024-07-09 19:55:50浏览次数：17  
标签：cout int 题解 ll Codeforces else 蛋糕 need 956

A. Array Divisibility

题目大意

构造长度为n的数组，满足：

  • 所有j的aj之和可以被k整除，其中j是k的倍数，k的取值为1~n。

思路

构造序列1->n即可满足条件。

代码实现
void solve() {
    ll n; cin >> n;
    for (int i = 1; i <= n; i++)cout << i << " ";
    cout << "\n";
}

B. Corner Twist

题目大意

给定a和b两个网格，网格中只存在0、1、2三种值。

给定操作，可以选择一个矩形的一条对角线上的两个端点，让他们加1/2；另一条对角线的端点值加2/1，然后对这些值取模3。问是否存在操作可以让a和b两个网格一致。

思路

考虑网格的边上的值，边上的值的变化会受到其他的影响，所以我们优先去找如何让边上的值相等即可。

正扫一遍，反扫一遍，然后比较数组即可。

代码实现
void solve() {
    ll n, m; cin >> n >> m;
    vector<vector<char>>a(n + 1, vector<char>(m + 1));
    vector<vector<char>>b(n + 1, vector<char>(m + 1));
    for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];
    for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> b[i][j];
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (a[i][j] != b[i][j]) {
                if (a[i][j] == '0') {
                    if (b[i][j] == '1') {
                        a[i][j] += 1;
                        if (a[i][j] == '3')a[i][j] = '0';
                        if (a[i][j] == '4')a[i][j] = '1';
 
                        a[i + 1][j + 1] += 1;
                        if (a[i + 1][j + 1] == '3')a[i + 1][j + 1] = '0';
                        if (a[i + 1][j + 1] == '4')a[i + 1][j + 1] = '1';
 
                        a[i + 1][j] += 2;
                        if (a[i + 1][j] == '3')a[i + 1][j] = '0';
                        if (a[i + 1][j] == '4')a[i + 1][j] = '1';
 
                        a[i][j + 1] += 2;
                        if (a[i][j + 1] == '3')a[i][j + 1] = '0';
                        if (a[i][j + 1] == '4')a[i][j + 1] = '1';
                    }else if(b[i][j]=='2') {
                        a[i][j] += 2;
                        if (a[i][j] == '3')a[i][j] = '0';
                        if (a[i][j] == '4')a[i][j] = '1';
 
                        a[i + 1][j + 1] += 2;
                        if (a[i + 1][j + 1] == '3')a[i + 1][j + 1] = '0';
                        if (a[i + 1][j + 1] == '4')a[i + 1][j + 1] = '1';
 
                        a[i + 1][j] += 1;
                        if (a[i + 1][j] == '3')a[i + 1][j] = '0';
                        if (a[i + 1][j] == '4')a[i + 1][j] = '1';
 
                        a[i][j + 1] += 1;
                        if (a[i][j + 1] == '3')a[i][j + 1] = '0';
                        if (a[i][j + 1] == '4')a[i][j + 1] = '1';
                    }
                }
                else if (a[i][j] == '1') {
                    if (b[i][j] == '2') {
                        a[i][j] += 1;
                        if (a[i][j] == '3')a[i][j] = '0';
                        if (a[i][j] == '4')a[i][j] = '1';
 
                        a[i + 1][j + 1] += 1;
                        if (a[i + 1][j + 1] == '3')a[i + 1][j + 1] = '0';
                        if (a[i + 1][j + 1] == '4')a[i + 1][j + 1] = '1';
 
                        a[i + 1][j] += 2;
                        if (a[i + 1][j] == '3')a[i + 1][j] = '0';
                        if (a[i + 1][j] == '4')a[i + 1][j] = '1';
 
                        a[i][j + 1] += 2;
                        if (a[i][j + 1] == '3')a[i][j + 1] = '0';
                        if (a[i][j + 1] == '4')a[i][j + 1] = '1';
                    }
                    else if (b[i][j] == '0') {
                        a[i][j] += 2;
                        if (a[i][j] == '3')a[i][j] = '0';
                        if (a[i][j] == '4')a[i][j] = '1';
 
                        a[i + 1][j + 1] += 2;
                        if (a[i + 1][j + 1] == '3')a[i + 1][j + 1] = '0';
                        if (a[i + 1][j + 1] == '4')a[i + 1][j + 1] = '1';
 
                        a[i + 1][j] += 1;
                        if (a[i + 1][j] == '3')a[i + 1][j] = '0';
                        if (a[i + 1][j] == '4')a[i + 1][j] = '1';
 
                        a[i][j + 1] += 1;
                        if (a[i][j + 1] == '3')a[i][j + 1] = '0';
                        if (a[i][j + 1] == '4')a[i][j + 1] = '1';
                    }
                }
                else {
                    if (b[i][j] == '0') {
                        a[i][j] += 1;
                        if (a[i][j] == '3')a[i][j] = '0';
                        if (a[i][j] == '4')a[i][j] = '1';
 
                        a[i + 1][j + 1] += 1;
                        if (a[i + 1][j + 1] == '3')a[i + 1][j + 1] = '0';
                        if (a[i + 1][j + 1] == '4')a[i + 1][j + 1] = '1';
 
                        a[i + 1][j] += 2;
                        if (a[i + 1][j] == '3')a[i + 1][j] = '0';
                        if (a[i + 1][j] == '4')a[i + 1][j] = '1';
 
                        a[i][j + 1] += 2;
                        if (a[i][j + 1] == '3')a[i][j + 1] = '0';
                        if (a[i][j + 1] == '4')a[i][j+1] = '1';
                    }
                    else if (b[i][j] == '1') {
                        a[i][j] += 2;
                        if (a[i][j] == '3')a[i][j] = '0';
                        if (a[i][j] == '4')a[i][j] = '1';
 
                        a[i + 1][j + 1] += 2;
                        if (a[i + 1][j + 1] == '3')a[i + 1][j + 1] = '0';
                        if (a[i + 1][j + 1] == '4')a[i + 1][j + 1] = '1';
 
                        a[i + 1][j] += 1;
                        if (a[i + 1][j] == '3')a[i + 1][j] = '0';
                        if (a[i + 1][j] == '4')a[i + 1][j] = '1';
 
                        a[i][j + 1] += 1;
                        if (a[i][j + 1] == '3')a[i][j + 1] = '0';
                        if (a[i][j + 1] == '4')a[i][j + 1] = '1';
                    }
                }
            }
        }
    }
    for (int i = n; i > 1; i--) {
        for (int j = m; j > 1; j--) {
            if (a[i][j] != b[i][j]) {
                if (a[i][j] == '0') {
                    if (b[i][j] == '1') {
                        a[i][j] += 1;
                        if (a[i][j] == '3')a[i][j] = '0';
                        if (a[i][j] == '4')a[i][j] = '1';
 
                        a[i - 1][j - 1] += 1;
                        if (a[i - 1][j - 1] == '3')a[i - 1][j - 1] = '0';
                        if (a[i - 1][j - 1] == '4')a[i - 1][j - 1] = '1';
 
                        a[i - 1][j] += 2;
                        if (a[i - 1][j] == '3')a[i - 1][j] = '0';
                        if (a[i - 1][j] == '4')a[i - 1][j] = '1';
 
                        a[i][j - 1] += 2;
                        if (a[i][j - 1] == '3')a[i][j - 1] = '0';
                        if (a[i][j - 1] == '4')a[i][j - 1] = '1';
                    }
                    else if (b[i][j] == '2') {
                        a[i][j] += 2;
                        if (a[i][j] == '3')a[i][j] = '0';
                        if (a[i][j] == '4')a[i][j] = '1';
 
                        a[i - 1][j - 1] += 2;
                        if (a[i - 1][j - 1] == '3')a[i - 1][j - 1] = '0';
                        if (a[i - 1][j - 1] == '4')a[i - 1][j -1] = '1';
 
                        a[i - 1][j] += 1;
                        if (a[i - 1][j] == '3')a[i - 1][j] = '0';
                        if (a[i - 1][j] == '4')a[i - 1][j] = '1';
 
                        a[i][j - 1] += 1;
                        if (a[i][j - 1] == '3')a[i][j - 1] = '0';
                        if (a[i][j - 1] == '4')a[i][j - 1] = '1';
                    }
                }
                else if (a[i][j] == '1') {
                    if (b[i][j] == '2') {
                        a[i][j] += 1;
                        if (a[i][j] == '3')a[i][j] = '0';
                        if (a[i][j] == '4')a[i][j] = '1';
 
                        a[i - 1][j - 1] += 1;
                        if (a[i - 1][j - 1] == '3')a[i - 1][j - 1] = '0';
                        if (a[i - 1][j - 1] == '4')a[i - 1][j - 1] = '1';
 
                        a[i - 1][j] += 2;
                        if (a[i - 1][j] == '3')a[i - 1][j] = '0';
                        if (a[i - 1][j] == '4')a[i - 1][j] = '1';
 
                        a[i][j - 1] += 2;
                        if (a[i][j - 1] == '3')a[i - 1][j] = '0';
                        if (a[i][j - 1] == '4')a[i - 1][j] = '1';
                    }
                    else if (b[i][j] == '0') {
                        a[i][j] += 2;
                        if (a[i][j] == '3')a[i][j] = '0';
                        if (a[i][j] == '4')a[i][j] = '1';
 
                        a[i - 1][j - 1] += 2;
                        if (a[i - 1][j - 1] == '3')a[i - 1][j - 1] = '0';
                        if (a[i - 1][j - 1] == '4')a[i - 1][j - 1] = '1';
 
                        a[i - 1][j] += 1;
                        if (a[i - 1][j] == '3')a[i - 1][j] = '0';
                        if (a[i - 1][j] == '4')a[i - 1][j] = '1';
 
                        a[i][j - 1] += 1;
                        if (a[i][j - 1] == '3')a[i][j - 1] = '0';
                        if (a[i][j - 1] == '4')a[i][j - 1] = '1';
                    }
                }
                else {
                    if (b[i][j] == '0') {
                        a[i][j] += 1;
                        if (a[i][j] == '3')a[i][j] = '0';
                        if (a[i][j] == '4')a[i][j] = '1';
 
                        a[i - 1][j - 1] += 1;
                        if (a[i - 1][j - 1] == '3')a[i - 1][j - 1] = '0';
                        if (a[i - 1][j - 1] == '4')a[i - 1][j - 1] = '1';
 
                        a[i - 1][j] += 2;
                        if (a[i - 1][j] == '3')a[i - 1][j] = '0';
                        if (a[i - 1][j] == '4')a[i - 1][j] = '1';
 
                        a[i][j - 1] += 2;
                        if (a[i][j - 1] == '3')a[i][j - 1] = '0';
                        if (a[i][j - 1] == '4')a[i][j-1] = '1';
                    }
                    else if (b[i][j] == '1') {
                        a[i][j] += 2;
                        if (a[i][j] == '3')a[i][j] = '0';
                        if (a[i][j] == '4')a[i][j] = '1';
 
                        a[i - 1][j - 1] += 2;
                        if (a[i - 1][j - 1] == '3')a[i - 1][j - 1] = '0';
                        if (a[i - 1][j - 1] == '4')a[i - 1][j-1] = '1';
 
                        a[i - 1][j] += 1;
                        if (a[i - 1][j] == '3')a[i - 1][j] = '0';
                        if (a[i - 1][j] == '4')a[i - 1][j] = '1';
 
                        a[i][j - 1] += 1;
                        if (a[i][j - 1] == '3')a[i][j - 1] = '0';
                        if (a[i][j - 1] == '4')a[i][j-1] = '1';
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] != b[i][j]) {
                cout << "NO\n"; return;
            }
        }
    }
    cout << "YES\n";
}

C. Have Your Cake and Eat It Too

题目大意

三个人吃蛋糕，每个人对蛋糕不同位置有自己的估价。

问如何分配蛋糕，使三个人获得的蛋糕价值均高于蛋糕价值和的三分之一。

思路

分类讨论：三个人拿蛋糕的顺序

  • abc

  • acb

  • bac

  • bca

  • cab

  • cba

代码实现
ll a[2100000];
ll b[2100000];
ll c[2100000];
void solve() {
    ll n; cin >> n;
    ll need = 0;
    a[0] = b[0] = c[0] = 0;
    for (int i = 1; i <= n; i++)cin >> a[i], need += a[i];
    for (int i = 1; i <= n; i++)cin >> b[i];
    for (int i = 1; i <= n; i++)cin >> c[i];
    need = ceil(need / 3.0);
    for (int i = 1; i <= n; i++)a[i] += a[i - 1];
    for (int i = 1; i <= n; i++)b[i] += b[i - 1];
    for (int i = 1; i <= n; i++)c[i] += c[i - 1];
    a[n + 1] = b[n + 1] = c[n + 1] = 1e22;
    //abc
    ll id = lower_bound(a + 1, a + 1 + n, need) - a;
    ll id2 = lower_bound(b + 1, b + 1 + n, b[id] + need) - b;
    if (c[n] - c[id2] >= need) {
        cout << 1 << " " << id << " " << id + 1 << " " << id2 << " " << id2 + 1 << " " << n << "\n";
        return;
    }
    //acb
    id = lower_bound(a + 1, a + 1 + n, need) - a;
    id2 = lower_bound(c + 1, c + 1 + n, c[id] + need) - c;
    if (b[n] - b[id2] >= need) {
        cout << 1 << " " << id << " " << id2 + 1 << " " << n << " " << id + 1 << " " << id2 << "\n";
        return;
    }
    //bca
    id = lower_bound(b + 1, b + 1 + n, need) - b;
    id2 = lower_bound(c + 1, c + 1 + n, c[id] + need) - c;
    if (a[n] - a[id2] >= need) {
        cout << id2 + 1 << " " << n << " " << 1 << " " << id << " " << id + 1 << " " << id2 << "\n";
        return;
    }
    //bac
    id = lower_bound(b + 1, b + 1 + n, need) - b;
    id2 = lower_bound(a + 1, a + 1 + n, a[id] + need) - a;
    if (c[n] - c[id2] >= need) {
        cout << id + 1 << " " << id2 << " " << 1 << " " << id << " " << id2 + 1 << " " << n << "\n";
        return;
    }
    //cab
    id = lower_bound(c + 1, c + 1 + n, need) - c;
    id2 = lower_bound(a + 1, a + 1 + n, a[id] + need) - a;
    if (b[n] - b[id2] >= need) {
        cout << id + 1 << " " << id2 << " " << id2 + 1 << " " << n <<" " << 1 << " " << id << "\n";
        return;
    }
    //cba
    id = lower_bound(c + 1, c + 1 + n, need) - c;
    id2 = lower_bound(b + 1, b + 1 + n, b[id] + need) - b;
    if (a[n] - a[id2] >= need) {
        cout << id2 + 1 << " " << n << " " << id + 1 << " " << id2 << " " << 1 << " " << id << "\n";
        return;
    }
    cout << "-1\n";
}

标签：cout,int,题解,ll,Codeforces,else,蛋糕,need,956
From： https://blog.csdn.net/ZZZioz/article/details/140255974

相关文章

  • joi2022_yo2_c 国土分割 (Land Division) 题解
    国土分割(LandDivision)推销我的洛谷博客。题意给定一个\(n\timesm\)的矩阵\(a\)，你需要选择在横向或纵向分割至少一次，使得每个分割出来的小矩阵的\(a_{i,j}\)之和相等。数据范围\(1\leqslantn,m\leqslant50\)。\(1\leqslanta_{i,j}\leqslant10^5\)。思......
  • Codeforces Round #956 (Div. 2) and ByteRace 2024
    Preface连着好几天因为熬夜看LOL比赛导致白天精神萎靡，都没精力VP了而且明天就要开始统一训练了，趁着最后一天补一下前两天因为看比赛没打的这场吧这场只能说是战术正确，想了会E没啥思路就马上转头去把F写了，后面回头慢慢想E也想出来了，最后极限2h14min出了EA.ArrayDivisibility......
  • 题解 - 幻象迷宫
    题目in洛谷或题目inCF题目幻象迷宫可以认为是无限大的，不过它由若干个\(N\timesM\)的矩阵重复组成。矩阵中有的地方是道路，用\(\verb!.!\)表示；有的地方是墙，用\(\verb!#!\)表示。起始位置用\(\verb!S!\)表示。也就是对于迷宫中的一个点\((x,y)\)，如果\((x\bmodn,y......
  • codeforces 955 div 2 D
    题目链接D.Beautyofthemountains题目大意解题思路首先记录所有雪山和没有雪山两种山峰的高度差为\(tot\)，然后对于每个可能的子矩，我们可以每次给所有山峰都加一或者减一，因此只要计算出矩阵内两种山峰的个数差的绝对值我们就能得到每次操作该子矩阵对tot的贡献\(z_{i}......
  • UVA12342 Tax Calculator 题解
    题目传送门题目大意题目描述某国所得税计算十分复杂。该国政府指定你制作一个自动计算所得税的程序。以下是该国计算所得税的规则：所得税免征额为180000180000......
  • P10719 的题解
    （一）设\(a_{x,y}\)为从\((1,1)(x,y)\)矩形中的\(1\)的数量。然后通过二位前缀和可以\(O(1)\)算。注意到\(1\len,m\le100\)。先确定矩形右下角，对于左上角，先确定在哪一行，再二分在哪一列。（二）AC代码。#include<bits/stdc++.h>#definepbpush_back#definefifirs......
  • 【Py/Java/C++三种语言OD独家2024D卷真题】20天拿下华为OD笔试之【前缀和/固定滑窗】2
    有LeetCode算法/华为OD考试扣扣交流群可加948025485可上欧弟OJ系统练习华子OD、大厂真题绿色聊天软件戳od1441了解算法冲刺训练（备注【CSDN】否则不通过）文章目录题目描述与示例题目描述输入描述输出描述示例一输入输出说明示例二输入输出说明解题思路贪心思想......
  • Codeforces Round956(div2) A~C
    A.ArrayDivisibility题意:对于所有k=1~n,能被j=1~n整除,要求以这些j作为下标a[j]的和也能够被k整除思路:题目有点绕,但是仔细读懂题目其实会发现,其实就是从1到n按顺序输出一遍...,别被样例忽悠了voidsolve(){ intn; cin>>n; for(inti=1;i<=n;i++){ cout......
  • zxx题单的题解
    https://www.luogu.com.cn/training/168096CF1359ELemma:\(\forallx\in\mathbb{N},\x\bmoda\bmodb=x\bmodb\bmoda\iffa\midb\(a<b)\)Proof:因为\(a<b\)，所以\(x\bmoda\bmodb=x\bmoda\)。设\(x=pb+q\)，其中\(0<q<b......
  • PostgreSQL的AutoVacuum原理及autovacuum不工作问题解析
    1、AutoVacuum概述PostgreSQL数据库是有数据清理的，有人工执行清理，也有自动清理，但是这2种的清理方式对性能是有不同的影响，特别是OLTP环境中，每次不管是人工清理还是自动清理deadtuple，都会对数据库的IO有明显的影响，基于PostgreSQL的原理每个表中的行会存在多个版本的数据，为了完成......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99