【前缀和】csustoj 3019题解&记录

发布于 2020-10-24  141 次阅读


前言

pc大佬说,做出来发红包,我就去做了。(虽然最后只有三块钱图个乐)一做就是4天,还是在几个大佬提示下才做出来的,而且代码过于冗长。大佬们安慰我说,这种题做一道剩下的都会了,也暗示了这道题可以作为母题来记录前缀和的用法。总而言之,我认为这道题揭示了前缀和查询高效的特点。

预备知识——前缀和

定义

前缀和是一种重要的预处理,能大大降低查询的时间复杂度。前缀和相当于数列中前n项和的概念,对于数组a[n]={1,2,3,4,5},他的前缀和数组就是sum[n]={1,3,6,10,15}。

定义式 递推式
一维前缀和 b[i]=\sum_{j=0}^{i}a[j] b[i]=b[i-1]+a[i]
二维前缀和 b[x][y]=\sum_{i=0}^{x}\sum_{j=0}^{y}a[i][j] b[x][y]=b[x-1][y]+b[x][y-1]-b[x-1][y-1]+a[x][y]

用途

有了前缀和,就可以用O(1)查询一段区间的和,而不用O(n)的逐个相加。如何查询?

比如要查a[i]~a[j]之间的元素之和,这个和就是sum[j]-sum[i-1]。这个结论容易证明。【显而易见.jpg】

题目

DARLING in the FRANXX

描述

没学过前缀和的可以先去学一下前缀和再写这题

“呐,darling,让我们快点结束这场战斗吧”02如此说道。

9102年10月10日,13号城市遭到了前所未有的危机,由于过度开采岩浆能源,

13号城市被n只叫龙包围了,n只叫龙分别站在一特定的位置上,每只叫龙都有一个等级划分:古登堡级、康德拉级和莫霍级

由于13号城市是个圆形,所以n只叫龙围成了一个环,用a1,a2,a3,...an表示, a2和a1,a3相邻,a3和a2,a4相邻,a1和an,a2相邻,其余同理

众所周知,要度过危机必需依靠02和pc所驾驶的鹤望兰的力量,若是放在以前,鹤望兰只要绕着基地

飞一圈便可消灭所有叫龙,但是今天很不走运,02sama的心情不是很好

她想要一次性解决所有同一级别的叫龙再解决下一等级的(换句话说就是同一级的叫龙全部站在一起)

于是她对pc说:“呐,darling,你能帮我把叫龙引导成我想要的排列吗?”

pc当然义不容辞,众所周知(wo xia bian de),13部队的成员经过训练后可以引导叫龙走到特定的

位置,所以我们可以把叫龙引导成02想要的排列,但是时间紧急,我们必须在最小的时间内完成这项任务,

也就是说我们要让最少的叫龙改变位置,变成02想要的排列,可这对pc来说太难了,于是他求助于隶属于

13部队的ACMer,请你们帮他计算出最少的需要改变位置的叫龙。

用A代表古登堡级,B代表康德拉级,C代表莫霍级

举例:ACAABB就不是02想要的排列,但我们可以将它变成CAAABB就是02想要的序列了

注:被引导的叫龙只能移动到之前有叫龙站的位置,同一个位置不能站两只以上叫龙

输入

第一行一个n,1 <= n <= 1e5

第二行一个字符串,代表叫龙一开始的排列

输出

一个数,代表最少需要引导的叫龙数量

输入样例 1

5 
ABABC

输出样例 1

2

输入样例 2

12 
ABCABCABCABC

输出样例 2

6

输入样例 3

4
ACBA

输出样例 3

0

输入样例 4

6 
BABABA

输出样例 4

2

输入样例 5

9 
ABABCBCAC

输出样例 5

3

提示

样例一解释:我们可以把原来a2移到a3,原来的a3移到a2,是序列变成AABBC

样例四解释:我们可以把a2和a5换一下,是序列变成BBBAAA

题解

由于这个毒瘤题面,要读懂题目就很费力。(反正我读了好几个小时)简单来说就是一个环,把相同的字母放在一起,求最少移动次数。经过几次三番的思考,一开始是想把环拆开但是得到的和原来的不等价。

后来得到结论,原字符串与答案字符串字符位置不同的个数就是所需要的移动次数,因此容易想到穷举答案字符串,每次与原字符串比较,最小的差就是答案。但是显然(又显然了?)穷举需要O(n),如果与原字符串比较使用的是线性扫描,那又需要O(n),总的时间复杂度就是O(n^2)。这对于题目范围1e5是无法接受的。

进一步思考,答案字符串的穷举是必须的。能改进的只有内层的查找。你想到了什么?没错,O(1)的前缀和。那么问题就变成了如何用前缀和查找不同的字符个数?

为使实现过程简化,我们将三种字母分开考虑。我们知道,在答案字符串中,一种字母必然是连续的(头尾相连也算),因此知道开始位置就能得到终点位置,就能得到这个区间。这个区间就是我们要用前缀和查询的区间。

可以简单的用前缀和算出答案字符串在此区间中某一字母的数量,也可以算出原字符串中对应区间中某一字母的数量。相减,得到的就是所需要的那个不同字符的个数。剩下的问题就是计算这样的区间了,边界条件(即头尾相连)要特别考虑。(反正这里我就写了一天)

还需要特别注意的是,答案字符串的那个环,顺时针读取和逆时针读取得到的是不同的情况,如abc,bca,cab三种可顺时针得到,cba,bac,acb则是逆时针。所以,穷举起点的时候要考虑这两种情况。

以上。

代码

贴两段代码,一段是我自己的(再难看也是自己写的嘛),一段是大佬HF学姐的

,可以欣赏。

我的代码:

#include<bits/stdc++.h>
using namespace std;
int sumA[200000] = {}, sumB[200000] = {}, sumC[200000] = {};//原字符串前缀和
int d1sumA[400000] = {}, d1sumB[400000] = {}, d1sumC[400000] = {};
int d2sumA[400000] = {}, d2sumB[400000] = {}, d2sumC[400000] = {};
string str, nstr1, nstr2;
int main()
{
    int n;
    cin >> n >> str;
    nstr1 = nstr2 = str;
    sort(nstr1.begin(), nstr1.end());//ABC
    for (int i = n - 1, j = 0; i >= 0; i--, j++) {
        nstr2[j] = nstr1[i];//CBA
    }
    for (int i = 0; i < n; i++) {
        sumA[i + 1] = sumA[i] + (str[i] == 'A');
        sumB[i + 1] = sumB[i] + (str[i] == 'B');
        sumC[i + 1] = sumC[i] + (str[i] == 'C');
    }
    for (int i = 0; i < n; i++) {
        d1sumA[i + 1] = d1sumA[i] + (nstr1[i] == 'A');
        d1sumB[i + 1] = d1sumB[i] + (nstr1[i] == 'B');
        d1sumC[i + 1] = d1sumC[i] + (nstr1[i] == 'C');
        d2sumA[i + 1] = d2sumA[i] + (nstr2[i] == 'A');
        d2sumB[i + 1] = d2sumB[i] + (nstr2[i] == 'B');
        d2sumC[i + 1] = d2sumC[i] + (nstr2[i] == 'C');
    }
    int amountA = sumA[n], amountB = sumB[n], amountC = sumC[n];//ABC总数用于计算区间端点
    //要查询某一区间的和,sum[终点]-sum[起点-1]
    //一次循环查一次字符串,每次循环查ABC的差
    int ans = 0x3f3f3f3f, dis = 0;//存差多少
    //注意0
    //ABC
    for (int i = 0; i < n; i++) {//i枚举起点
        //判断边界条件
        dis = 0;
        int frontA = d1sumA[amountA] - d1sumA[0], frontB = d1sumB[amountA + amountB] - d1sumB[amountA], frontC = d1sumC[amountA + amountB + amountC] - d1sumC[amountA + amountB];
        int lastA = 0, lastB = 0, lastC = 0;
        //终点和起点都在n左边,终点和起点一个在n左边一个在n右边,终点和起点都在n右边
        if (i + 1 <= n && i + amountA <= n) {
            lastA = sumA[i + amountA] - sumA[i];
        }
        else if (i + 1 <= n && i + amountA > n) {
            lastA = (sumA[n] - sumA[i]) + (sumA[i + amountA - n] - sumA[0]);
        }
        else if (i + 1 > n && i + amountA > n) {
            lastA = sumA[i + amountA - n] - sumA[i - n];
        }
        //A起点在i+1,终点在i+amountA,算的时候sum[i+amountA]-sum[i]
        if (i + amountA + 1 <= n && i + amountA + amountB <= n) {
            lastB = sumB[i + amountA + amountB] - sumB[i + amountA];
        }
        else if (i + amountA + 1 <= n && i + amountA + amountB > n) {
            lastB = (sumB[n] - sumB[i + amountA]) + (sumB[i + amountA + amountB - n] - sumB[0]);
        }
        else if (i + amountA + 1 > n && i + amountA + amountB > n) {
            lastB = sumB[i + amountA + amountB - n] - sumB[i + amountA - n];
        }
        //B起点在i+amountA+1,终点在i+amountA+amountB,算的时候sum[i+amountA+amountB]-sum[i+amountA]
        if (i + amountA + amountB + 1 <= n && i + amountA + amountB + amountC <= n) {
            lastC = sumC[i + amountA + amountB + amountC] - sumC[i + amountA + amountB];
        }
        else if (i + amountA + amountB + 1 <= n && i + amountA + amountB + amountC > n) {
            lastC = (sumC[n] - sumC[i + amountA + amountB]) + (sumC[i + amountA + amountB + amountC - n] - sumC[0]);
        }
        else if (i + amountA + amountB + 1 > n && i + amountA + amountB + amountC > n) {
            lastC = sumC[i + amountA + amountB + amountC - n] - sumC[i + amountA + amountB - n];
        }
        //C起点在i+amountA+amountB+1,终点在i+amountA+amountB+amountC,算的时候sum[i+amountA+amountB+amountC]-sum[i+amountA+amountB]
        dis += frontA - lastA;
        dis += frontB - lastB;
        dis += frontC - lastC;
        if (dis < ans) {
            ans = dis;
        }
    }
    //CBA
    for (int i = 0; i < n; i++) {//i枚举起点
    //判断边界条件
        dis = 0;
        int frontC = d2sumC[amountC] - d2sumC[0], frontB = d2sumB[amountC + amountB] - d2sumB[amountC], frontA = d2sumA[amountA + amountB + amountC] - d2sumA[amountC + amountB];
        int lastA = 0, lastB = 0, lastC = 0;
        //终点和起点都在n左边,终点和起点一个在n左边一个在n右边,终点和起点都在n右边
        if (i + 1 <= n && i + amountC <= n) {
            lastC = sumC[i + amountC] - sumC[i];
        }
        else if (i + 1 <= n && i + amountC > n) {
            lastC = sumC[n] - sumC[i] + sumC[i + amountC - n] - sumC[0];
        }
        else if (i + 1 > n && i + amountC > n) {
            lastC = sumC[i + amountC - n] - sumC[i - n];
        }
        //C起点在i+1,终点在i+amountC,算的时候sum[i+amountC]-sum[i]
        if (i + amountC + 1 <= n && i + amountC + amountB <= n) {
            lastB = sumB[i + amountC + amountB] - sumB[i + amountC];
        }
        else if (i + amountC + 1 <= n && i + amountC + amountB > n) {
            lastB = sumB[n] - sumB[i + amountC] + sumB[i + amountC + amountB - n] - sumB[0];
        }
        else if (i + amountC + 1 > n && i + amountC + amountB > n) {
            lastB = sumB[i + amountC + amountB - n] - sumB[i + amountC - n];
        }
        //B起点在i+amountC+1,终点在i+amountC+amountB,算的时候sum[i+amountC+amountB]-sum[i+amountC]
        if (i + amountC + amountB + 1 <= n && i + amountC + amountB + amountA <= n) {
            lastA = sumA[i + amountC + amountB + amountA] - sumA[i + amountC + amountB];
        }
        else if (i + amountC + amountB + 1 <= n && i + amountC + amountB + amountA > n) {
            lastA = sumA[n] - sumA[i + amountC + amountB] + sumA[i + amountC + amountB + amountA - n] - sumA[0];
        }
        else if (i + amountC + amountB + 1 > n && i + amountC + amountB + amountA > n) {
            lastA = sumA[i + amountC + amountB + amountA - n] - sumA[i + amountC + amountB - n];
        }
        //A起点在i+amountC+amountB+1,终点在i+amountC+amountB+amountA,算的时候sum[i+amountC+amountB+amountA]-sum[i+amountC+amountB]
        dis += frontC - lastC;
        dis += frontB - lastB;
        dis += frontA - lastA;
        if (dis < ans) {
            ans = dis;
        }
    }

    cout << ans;
    return 0;
}

学姐的代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
int sum[maxn][5];
string s;

int main()
{
    int n;
    cin >> n;
    cin >> s;
    for (int i = 0; i < n; i++) {
        sum[i + 1][0] = sum[i][0];
        sum[i + 1][1] = sum[i][1];
        sum[i + 1][2] = sum[i][2];
        sum[i + 1][s[i] - 'A']++;
    }
    for (int i = 0; i < n; i++) {
        sum[n + 1 + i][0] = sum[i + 1][0] + sum[n][0];
        sum[n + 1 + i][1] = sum[i + 1][1] + sum[n][1];
        sum[n + 1 + i][2] = sum[i + 1][2] + sum[n][2];
    }
    int ans = 0x3f3f3f3f;
    int a = sum[n][0], b = sum[n][1], c = sum[n][2];
    for (int i = 1; i <= n; i++) {
        int sta = i, stb = i + a, stc = i + a + b;
        int tmp = a - (sum[sta + a - 1][0] - sum[sta - 1][0]) + b - (sum[stb + b - 1][1] - sum[stb - 1][1]) + c - (sum[stc + c - 1][2] - sum[stc - 1][2]);
        ans = min(ans, tmp);
        stb = i + a + c, stc = i + a;
        tmp = a - (sum[sta + a - 1][0] - sum[sta - 1][0]) + b - (sum[stb + b - 1][1] - sum[stb - 1][1]) + c - (sum[stc + c - 1][2] - sum[stc - 1][2]);
        ans = min(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

不过多解释,学姐的代码非常简洁干练,不像我废话连篇。

Q.E.D.


夢に僕らで帆を張って 来るべき日のために夜を越え。