头像

Eartha

$Love$ $C++$




离线:52分钟前


最近来访(417)
用户头像
嘉然今天刷算法
用户头像
OrderInChaos
用户头像
等雨停
用户头像
南馆潇湘
用户头像
DL爷爷单身
用户头像
Thelittleprince
用户头像
肖肖_123
用户头像
seth
用户头像
1只小牛马
用户头像
acwing_7164
用户头像
周树人之怒
用户头像
Lorling
用户头像
tky
用户头像
SoumaSumire
用户头像
zslj小凡
用户头像
rushhhhh
用户头像
Carney
用户头像
陈睿涵
用户头像
castlecaffe
用户头像
克里斯保罗


Eartha
1小时前

赠送 10 月日历 即可获得两个关注!!!有意者私信!!!



新鲜事 原文

Eartha
2小时前
AcWing【集日历瓜分10000AC币活动】求10月日历!https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/receive/28914/10/ 送我的私信,给两个关注(我和我朋友)


新鲜事 原文

Eartha
7小时前
AcWing【集日历瓜分10000AC币活动】求7月日历!https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/receive/28914/7/


新鲜事 原文

Eartha
7小时前
AcWing【集日历瓜分10000AC币活动】求7月日历!https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/receive/28914/7/



Eartha
9小时前

缺 9 月日历的进来!!!

送我以下任一日历,即可获得 9 月日历!

7 月

10 月

有意者私信!!!谢谢!!!




Eartha
9小时前

缺 9 月日历的进来!!!

送我以下任一日历,即可获得 9 月日历!

7 月

10 月

有意者私信!!!谢谢!!!



新鲜事 原文

Eartha
9小时前
缺 9 月日历的进来!!! 送我以下任一日历,即可获得 9 月日历! 7 月:https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/receive/28914/7/ 10 月:https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/receive/28914/10/ 有意者私信!!!谢谢!!!


活动打卡代码 AcWing 1875. 贝茜的报复

Eartha
21小时前
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
int ans;
map<char, int> mp1, mp2, a;
string s = "BESIGOM";
void dfs(int u, int x) {
    if(u == 7){
        if((a['B'] + a['I']) % 2 && (a['G'] + a['O'] + a['E'] + a['S']) % 2 && a['M'] % 2) return;
        ans += x;
        return;
    }
    char ch = s[u];
    a[ch] = 1, dfs(u + 1, x * mp1[ch]);
    a[ch] = 2, dfs(u + 1, x * mp2[ch]);
}
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        char c;
        int x;
        cin >> c >> x;
        if(x % 2) mp1[c] ++;
        else mp2[c] ++;
    }
    dfs(0, 1);
    printf("%d", ans);
    return 0;
}



Eartha
21小时前

先来念一遍 差分数组 的定义:

这里 $b$ 数组是 $a$ 数组的差分数组。

首先给定一个原数组 $a$:$a_1, a_2, a_3 \ldots a_n$。

然后我们构造一个数组 $b$:$b_1, b_2, b_3 \ldots b_n$。

使得 $a_i = b_1 + b_2+ b_3 + \ldots + b_i$。


我们需要构造差分数组。举个例子:$n$ 等于 $5$,则有:

$a$:$a_1, a_2, a_3, a_4, a_5$。

$b$:$b_1, b_2, b_3, b_4, b_5$。

$a_1 = b_1$
$a_2 = b_1 + b_2$。
$a_3 = b_1 + b_2 + b_3$。
$a_4 = b_1 + b_2 + b_3 + b_4$。
$a_5 = b_1 + b_2 + b_3 + b_4 + b_5$。

是不是很像三角形呢

所以稍微推理一下的:
$b_1 = a_1$
$b_2 = a_2 - b_1 = a_2 - a_1$
$b_3 = a_3 - b_1 - b_2 = a_3 - a_1 - (a_2 - a_1) = a_3 - a_1 - a_2 + a_1 = a_3 - a_2$
$b_4 = a_4 - b_1 - b_2 - b_3 = a_4 - a_1 - (a_2-a_1)-(a_3-a_2)=a_4-a_1- a_2+a_1-a_3+a_2 = a_4 - a_3$
$\ldots$

这里就不给大家枚举了。总感觉有点像分数列项呢 总之,我们总结出规律:$b_i = a_i - a_{i - 1}$。

这就是构造差分数组的方法。


那么,怎么把差分摆在这道题目里呢?

简单:

  • 注:最后的答案就是差分数组 $b$ 的前缀和。

将 $[l,r]$ 中的数加 $c$,核心两句话:

  • b[l] += c;

    既然最后的答案是 $b$ 的前缀和,那么 $b_l$ 加了 $c$,就相当于 $ans_{l \ldots n}$ 都加了 $c$。

  • b[r + 1] -= c;

    既然最后的答案是 $b$ 的前缀和,那么 $b_{r + 1}$ 减了 $c$,就相当于 $ans_{r + 1 \ldots n}$ 都减了 $c$。

其中 $ans_{l \ldots r}$ 加了 $c$,$ans_{r + 1 \ldots n}$ 加了 $c$ 又减了 $c$,等于啥也没发生。我们的目的达到了!


代码:

#include <iostream>
#include <cstdio>
using namespace std;
int n,m;
int a[100010],b[100010];
int main() {
    scanf("%d%d",&n, &m);
    for (int i = 1; i <= n; i ++ ) {
        scanf("%d",&a[i]);
        b[i] = a[i] - a[i-1];//构造差分数组。 
    } 
    while (m -- ) {
        int l, r, c;
        scanf("%d%d%d",&l, &r, &c);
        b[l] += c; b[r + 1] -= c;
    }
    for (int i = 1; i <= n; i ++ )
        b[i] = b[i - 1] + b[i];
    for (int i = 1; i <= n; i ++ )
        printf("%d ",b[i]);
    return 0; 
}

您看得那么认真,点个宝贵的赞👍再走吧!谢谢各位路过的神犇!



新鲜事 原文

Eartha
1天前
小游戏https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/receive/28914/10/