Educational Codeforces Round 72 Div. 2 解题报告 (CF1217)

C – The Number Of Good Substrings

这道题比较傻逼。

考虑记录上一个最近的\(1\)的位置\(nxt_i\),然后显然的是:如果在\( O(n \log n) \)时间的扫描中扫描到\([l, r]\)大于当前区间,那么就考虑\(l\)左边是否有足够的零来补足长度。然后这道题就可以愉快的 AC 了。

继续阅读Educational Codeforces Round 72 Div. 2 解题报告 (CF1217)

Codeforces Round #551 (Div. 2) 解题报告 (CF1153)

C – Serval and Parenthesis Sequence

这道题主要是运用贪心。首先我们可以确定以下几种情况是肯定无解的:

  • 第一个字符是 ‘)’,最后一个字符是 ‘(‘。
  • 字符串长度为奇数。

我们发现整个字符串\(s[1 \dots n]\)中,第一个和最后一个字符一定要是 ‘(‘ 和 ‘)’。所以我们只用关心\(s[2 \dots n-1]\)就好。统计需要补充的括号个数:也就是\((n-2)\)减去现已确定的括号个数,分\(remL\)为左括号需要补充的个数、\(remR\)为右括号需要补充的个数。

继续阅读Codeforces Round #551 (Div. 2) 解题报告 (CF1153)

Codeforces Round #549 (Div. 2) 解题报告 (CF1143)

E – Lynyrd Skynyrd

题目大意

给一个排列\(p[1-n]\)和取值范围在\([1,n]\)内的数组\(a[]\),处理\(q\)个询问:在数组的字段\([l,r]\)内是否存在排列的环形偏移。

解法

考虑正向扫描,处理出每一个位置上的数到左边「最近的上一个环形偏移数」的位置,并同时更新自己所在的位置供下一次循环进行使用:

继续阅读Codeforces Round #549 (Div. 2) 解题报告 (CF1143)

Codeforces 1136D:Nastya Is Buying Lunch 题解

主要思路

这道题的主要做法就是贪心了。我们枚举\(i\)从\(n-1\)到\(1\),记\(vis[i]\)为编号为\(i\)的节点是否可以转移、\(arr[i]\)为\(i\)位置上的数,在转移关系集中寻找\((i,j), vis[j]=true\)的\(j\)。由于我们是从后向前转移,所以我们找到的这些\(j\)的位置都是在\(i\)之后的,符合转移要求。之后我们验证目前已转移的答案\(ans\)与满足条件的关系个数\(cnt\)与\(i\)的和是否为\(n\),如果符合意味着转移符合条件,便直接进行转移;如果不符合,那么我们把该点的标记打上,意味着可以从此被转移。

继续阅读Codeforces 1136D:Nastya Is Buying Lunch 题解

Codeforces Round #548 (Div. 2) 解题报告 (CF1139)

A – Even Substrings

很简单,扫描的时候如果所在数位为偶数位,向答案添加当前数位即可。

// A.cpp
#include <bits/stdc++.h>
using namespace std;
char str[66000];
int main()
{
    int ans = 0, len;
    scanf("%d", &len), scanf("%s", str + 1);
    for (int i = 1; i <= len; i++)
        if (((str[i] - '0') & 1) == 0)
            ans += i;
    printf("%d", ans);
    return 0;
}

继续阅读Codeforces Round #548 (Div. 2) 解题报告 (CF1139)