首页 > 其他分享 >Codeforces Round 877 (Div.2) 题解 A - D

Codeforces Round 877 (Div.2) 题解 A - D

时间:2023-06-12 18:34:27浏览次数:61  
标签:const cout int 题解 nullptr cin 877 Div.2 include

A. Blackboard List

题目大意

起初黑板上有两个数,现在不断选取两个数作出他们俩差的绝对值并写在黑板上,如此往复直到黑板上有 \(n\) 个数。现在给定这 \(n\) 个数,问起初两数的其中一个数是多少。

解题思路

我们分两种可能:要么这两个数有负数,要么没有。

  1. 有负数的情况,因为每次写下的都是绝对值,那么这些数中的负数一定是起初两数之一。
  2. 没有负数的情况,没有负数可以保证每次的差值一定比原来两数的最大值要小,因为最小情况下也是减去 \(0\),得到的结果不会比原数大。那么全部数的最大值就是原来两数的最大值。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

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

void solve() {
    LL n, x;
    cin >> n;
    LL min_ = 0x3f3f3f3f, max_ = -0x3f3f3f3f;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        min_ = min(min_, x);
        max_ = max(max_, x);
    }
    cout << (min_ < 0 ? min_ : max_) << endl;
}

signed main() {
    ios;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

B. Minimize Permutation Subarrays

题目大意

给定 \(1\sim n\) 的一个排列,现在我们只允许做一次交换,使得交换后的排列的所有子数列中的排列数最少。

这里排列指的是数组中恰好有 \(1,2,\dots,subarray.\text{length}\) 这些数.

解题思路

我们的排列一定是 \(1, 2,\dots\) 这样的,我们只需要阻断 \(1\) 和 \(2\),并且塞进去最不可能出现在这里元素 \(n\) 即可。这时我们的子数组中的排列就只有两个,单独的 \(1\) 和整个排列。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e6 + 10;
const int MOD = 998244353;

int a[N];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        a[x] = i;
    }
    if ((a[n] - a[1]) * (a[n] - a[2]) < 0) {
        cout << 1 << ' ' << 1 << endl;
    } else if (a[n] > a[1] && a[n] > a[2]) {
        cout << a[n] << ' ' << max(a[1], a[2]) << endl;
    } else {
        cout << a[n] << ' ' << min(a[1], a[2]) << endl;
    }
}

signed main() {
    ios;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

C. No Prime Differences

题目大意

需要构造一个 \(n\times m\) 的矩阵,需要满足其中的元素恰好为 \(1\sim nm\),同时任意相邻两项的差的绝对值不为质数。

解题思路

相邻两项无非就是横着俩以及竖着俩都满足差值不是质数。我们可以考虑构造差值满足以下关系:

  1. 差值为 \(1\)。
  2. 差值为 \(2\) 的非一次倍。
  3. 差值为 \(n\) 的整数倍。

如果 \(n\) 是偶数的话,那么很容易看出来,只需要按照如下情形即可:

 1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24

如果 \(n\) 是奇数的话,我们可以调换输出顺序,把偶数行先输出,奇数行后输出:

 6  7  8  9 10
16 17 18 19 20
 1  2  3  4  5
11 12 13 14 15

奇数行和偶数行内部满足上面对 \(n\) 为偶数情况的讨论,两者交界处的差值是 \(n\) 的整数倍非质数,故可如此构造。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e6 + 10;
const int MOD = 998244353;

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i < n; i += 2) {
        for (int j = 1; j <= m; ++j) {
            cout << i * m + j << ' ';
        }
        cout << endl;
    }
    for (int i = 0; i < n; i += 2) {
        for (int j = 1; j <= m; ++j) {
            cout << i * m + j << ' ';
        }
        cout << endl;
    }
    cout << endl;
}

signed main() {
    ios;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

D. Bracket Walk

题目大意

给定一个括号序列,起初时人站在第一个字符上面,每次可以向左或者向右走。同时给定 \(q\) 个询问,每次询问会将括号序列第 \(x\) 个括号倒转方向,问能否使得走到的字符拼接起来成为一个匹配的括号序列。

解题思路

首先确定一定不可能的情况,我们向左走一次,就必须向右走回来,所以最终步数的奇偶性和 \(n\) 一致,所以 \(n\) 为奇数的时候肯定不能组成匹配的括号序列。

我们考虑原串已经含有了 (),那么可以直接走过这两个字符,如果出现不匹配部分,我们就将多走一次少的那种括号,我们期望获得 ()() 这样的括号序列,那么可以记录有多少括号不满足这一条,存到我们的set中,随后针对翻转修改,我们通过修改set的元素就可以达到组件的删改,最后只需要判断set的头元素和尾元素,实际上就是最大最小值的奇偶关系即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e6 + 10;
const int MOD = 998244353;

set<LL> st;

void solve() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    for (int i = 0; i < n; ++i) {
        if (s[i] == (i & 1 ? '(' : ')')) {
            st.insert(i + 1);
        }
    }
    while (m--) {
        int x;
        cin >> x;
        if (st.contains(x)) {
            st.erase(x);
        } else {
            st.insert(x);
        }
        cout << (n & 1 || (!st.empty() && (*st.begin() & 1 || !(*st.rbegin() & 1))) ? "NO" : "YES") << endl;
    }
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

标签:const,cout,int,题解,nullptr,cin,877,Div.2,include
From: https://www.cnblogs.com/SanCai-Newbie/p/17475808.html

相关文章

  • P1707 刷题比赛 题解
    多少有点混乱邪恶。题意:给出递推式:\[a_1=b_1=c_1=1\\a_2=b_2=c_2=3\\\begin{aligned}a_k&=p\timesa_{k-1}+q\timesa_{k-2}&+b_{k-1}+c_{k-1}&+r(k-2)^2+t(k-2)+1\\b_k&=u\timesb_{k-1}+v\timesb_{k-2}&+a_{k-1}+c_{k-1}&+w^{k-2}\\c......
  • BestCoder Round #71 (div.2)1001KK's Steel
    题意:中文题思路:其实我们不去考虑N,我们只考虑最优切割策略:     首先肯定是尽量的小即1、2     既要不相等,又不能构成三角形,即每次为当前数列中最大的两项的和     那么,构成的数列为1,2,3,5,8,......     这样我们只要求最接近且小于等于N的......
  • P1306 斐波那契公约数 题解
    请求出\(f_n\)与\(f_m\)的最大公约数,即\(\gcd(f_n,f_m)\),答案对\(10^8\)取模。结论:\(\gcd(f_n,f_m)=f_{\gcd(n,m)}\)证明如下:首先引理1:\[f_{n+m}=f_{n-1}\timesf_{m}+f_{n}\timesf_{m+1}\]运用归纳法,可以简单证明,此处略去。引理2:\[\gcd(f_n,f_......
  • AtCoder Beginner Contest 305 题解
    https://atcoder.jp/contests/abc305/tasks_printE-ArtGalleryonGraph冷知识:md这题赛时没做出来/cy刚看到题:这是什么题啊,\(K,h\)都\(1e5\)能做吗/fn确实能做。考虑类似SPFA的操作。设\(a_x\)表示\(x\)还可以对距离最多为\(a_x\)的点产生贡献,然后就直接......
  • Codeforces Round 877 (Div. 2)
    Preface补题这场补题的时候直接成腐乳了,A题挂两发,B题挂两发,C题挂一发是真的抽象虽然D是个套路题看一眼就秒了,但如果真的比赛时候打真要罚时爆炸了的说后面的EF还是做不来啊岂可修,不过都很有启发性让人感觉神清气爽,不像傻逼蓝桥杯花钱买罪受A.BlackboardList刚开始想错方......
  • Codeforces Round 876 Div2 A-D题解
    CodeforcesRound876Div2A-D题解A.TheGoodArray这个题就是问你对于\(i\leqn\),要求前面后面至少\(ceil(\frac{i}{k})\)个1那我们就贪心的每k个放一个1,或者直接用数学算一下就好了AC代码#include<bits/stdc++.h>usingnamespacestd;constexprintlimit=(......
  • Java8新特性Stream之list转map及问题解决
    List集合转Map,用到的是Stream中Collectors的toMap方法:Collectors.toMap具体用法实例如下://声明一个List集合Listlist=newArrayList();list.add(newPerson("1001","小A"));list.add(newPerson("1002","小B"));list.add(......
  • 杂题题解
    序列变化(exchange)只要第一位确定,后面的\(n-1\)位都是唯一确定的。因为具体是B还是C只取决于两侧字母是否一样,所以两种变化方案其中一种是另一种每一位取反,要么都合法,要么都不合法。但变化出的方案可能不能继续变化下去,比如CCC变化到BBB之后就不能再变化了,但变化到CCC......
  • permu题解(树上莫队)(非正解)
    题目传送门题意给出一个长度为$n$的排列$P(P1,P2,...Pn)$,以及$m$个询问。每次询问某个区间$[l,r]$中,最长的值域连续段长度。思路首先这道题事求连续段的长度,打个莫队先#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;namespaceTestify{ inlineint......
  • mysql运行sql文件时,timestamp默认值出错问题解决
    出现了---Invaliddefaultvaluefor'reward_time' 直接打开sql文件,将字段reward_time类型值替换成NULL即可 ......