首页 > 其他分享 >abc370

abc370

时间:2024-09-10 19:14:59浏览次数:7  
标签:map 结尾 int mp 数组 abc370

A.

B.

模拟

C.

贪心,顺序枚举,若 \(s_i < t_i\),将 \(i\) 存到数组中,否则直接令 \(s_i = t_i\),输出 \(s\)。

然后从后往前的枚举数组,依次修改并输出即可。

D.

一开始看错数据范围,虚空想了好久。。

用 用 \(set\) 找每一列,每一行的第一个没被摧毁的墙壁即可。

E.

给一个数组 \(a\) 和整数 \(k\),把 \(a\) 分割成若干个子数组,使得没有一个子数组的和为 \(k\) 的方案数。

设 \(f_i\) 表示 \(i\) 个中,以 \(i\) 结尾,没有一个子数组的和为 \(k\) 的分割方案数。

对于每个数 \(a_i\),统计以 \(i\) 结尾的子数组的和为 \(k\) 的方案数之和,可以用 前缀和与 map 维护,然后把以 \(i\) 结尾的方案数加进 map 中。


#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 7;
const int mod = 998244353;
int a[N], f[N];
signed main() {
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    int now = 0;
    map<int, int> mp;
    mp[0] = 1, now = 1;
    for(int i = 1; i <= n; i ++) a[i] += a[i - 1];
    for(int i = 1; i <= n; i ++) {
        f[i] = now % mod;
        f[i] = (f[i] % mod - mp[a[i] - k] % mod + mod) % mod;
        mp[a[i]] = (mp[a[i]] + f[i] % mod) % mod;
        now = (now + f[i]) % mod;
    }
    cout << f[n] % mod << endl;
}

F.

标签:map,结尾,int,mp,数组,abc370
From: https://www.cnblogs.com/wyyqwq/p/18406986

相关文章

  • ABC370 Review
    ABC370ReviewA模拟题,过B模拟题,过C很明显的贪心思路是把需要更改的字母分为两类:改大和改小。首先我们要明确的是要让输出的串尽量拥有小的字典序,且字典序比较的第一关键字是位置,第二是长度所以对于改小的部分,改的位置越靠前我们就放在越前面操作;对于改大的部分,改的位置......
  • トヨタ自動車プログラミングコンテスト2024#9(ABC370)
    A.RaiseBothHands\(\texttt{Diff}11\)#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'#definevoidinlinevoid//#defineONLINE_JUDGE#ifndefONLINE_JUDGE#definetest(i)cout<<"test:"<<i<<......
  • [ABC370C] Word Ladder 题解
    题目描述:给予两个相等长度的序列,\(S\)与\(T\),以及一个空数组\(X\),每在\(S\)上修改一个字符,便将修改后的\(S\)加入\(X\)中,直到\(S\)与\(T\)相同。(输出字典序最小的\(X\)数组)拿过题一看,感觉还是蛮简单的,本题主要的难点在字符串的字典序上。字符串字典序的定义......
  • 题解:AT_abc370_c [ABC370C] Word Ladder
    说句闲话并不会有更好的阅读体验。这题是一个比较奇葩的贪心、构造。也可以认为是一个数据结构略有难度的练习题。理论部分?>注:使用\(N\)表示字符串长度。一句段话题意:三个字符串\(S\)、\(T\)、\(X\),其中\(S\)和\(T\)仅包含小写字母且等长,\(X\)为空。每一个操作可以......
  • abc370 A-E题解 (AtCoder Beginner Contest 370)
     A这类简单题,看清楚:OutputPrint Yes, No,or Invalid accordingtotheinstructionsintheproblemstatement. B Cstd,这样写(0->n-1,n-1->0),可以少写一个vector1#include<bits/stdc++.h>2usingnamespacestd;34intmain(){5strings,......
  • ABC370掉分寄
    在数月不打ABC后,我为了找回打比赛的手感开始打ABC,结果挂得不堪入目。开场前15min,在360的可爱操作下我的AtcoderBetter被卸了,我就重装,然后在油叉里一不小心点了两遍,重装了俩,一登界面发现两个还一块使,导致交替的时候完全找不到提交按钮,极速换浏览器,可是看不了中文题面了。......