首页 > 其他分享 >题解:AT_abc369_c [ABC369C] Count Arithmetic Subarrays

题解:AT_abc369_c [ABC369C] Count Arithmetic Subarrays

时间:2024-09-08 21:50:07浏览次数:9  
标签:Count 题解 abc369 答案 Subarrays ABC369C 等差数列 指针

很水的一道题,但是硬控我半个小时呜呜呜。

它问等差数列的数量,我们发现只要找到所有的等差数列,那么答案一定包含在这些数列的连续子序列中。

求所有等差数列显然可以线性,我们求出每个等差数列的长度 \(n\),那么连续子序列个数即为 \(n(n+1)\over 2\)。

至于求的话我定义了两个指针,每次满足差相等的话右指针右移,否则统计答案,重新赋值指针即可。

给出我的代码:

for(int i=2;i<=n;i++)
	{
		if(a[i]-a[i-1]==cha)r++;
		else
		{
			num=r-l+1;
			ans=ans+pre[num];
			l=i-1;
			r=i;
			cha=a[i]-a[i-1];
		}
	}

但是单纯做的话答案不是正确的,因为指针重新赋值的话计算答案时当前等差数列末尾元素会重复计算,所以需要统计累加答案的次数最后减去消除影响。

还有一点细节,上面的循环做完以后最后需要再操作一次计算最后一个等差数列的贡献。

然后就做完了。

提交记录

标签:Count,题解,abc369,答案,Subarrays,ABC369C,等差数列,指针
From: https://www.cnblogs.com/Lydic/p/18403544

相关文章

  • AtCoder Beginner Contest 253 A~E 题解
    A-Median?题目大意给定正整数\(a,b,c\),判断\(b\)是否为三个数中的中位数(即从小到大排序后是第二个,不是平均数)。\(1\lea,b,c\le100\)输入格式\(a~b~c\)输出格式如果\(b\)是三个数中的中位数,输出Yes;否则,输出No。样例\(a\)\(b\)\(c\)输出\(5\)\(3\)\(2\)Y......
  • AtCoder Beginner Contest 241 (Sponsored by Panasonic) D~F 题解
    D-SequenceQuery题目大意我们有一个空序列\(A\)。请依次处理\(Q\)个命令,每个命令有三种类型,每种类型的格式如下:1x:将\(x\)加入\(A\)(不去重)2xk:求在\(A\)的\(\lex\)的元素中,第\(k\)大的值。3xk:求在\(A\)的\(\gex\)的元素中,第\(k\)小的值。\(1\leQ\le2\times10^5......
  • AtCoder Beginner Contest 242 C~E 题解
    C-1111galpassword题目大意给定正整数\(N\),求符合下列条件的整数\(X\)的个数,对\(998244353\)取模:\(X\)是\(N\)位的正整数\(X\)的每一位数都在\([1,9]\)之间(0不行);\(X\)的相邻两位数之差的绝对值不超过\(1\)。\(2\leN\le10^6\)输入格式\(N\)输出格式输出答案。样......
  • AtCoder Beginner Contest 245 A~E 题解
    A-Goodmorning题目大意在同一天里,Takahashi在\(A\)时\(B\)分起床,Aoki在\(C\)时\(D\)分\(1\)秒起床,请问谁起床更早?\(0\leA,C<24\)\(0\leB,D<60\)输入格式\(A~B~C~D\)输出格式输出起得更早的人的名字(Takahashi或Aoki)。样例\(A\)\(B\)\(C\)\(D\)输出\(7\)......
  • AtCoder Beginner Contest 244 D~F 题解
    D-SwapHats题目大意有\(3\)个Takahashi,他们帽子的颜色分别为\(S_1,S_2,S_3\)。我们现在想通过正好\(10^{18}\)次操作,使得\(S_i=T_i\)。每次操作如下:选择\((i,j)\),交换\(S_i\)和\(S_j\)。试问能否达成目标?输入格式\(S_1~S_2~S_3\)\(T_1~T_2~T_3\)输出格式如果能达......
  • ARC138 B - 01 Generation 题解
    ARC138B-01Generation思路考虑逆向思维,很容易想到可以优先从后面删掉0(操作B的逆向操作),然后如果前面是0则删掉它并将序列翻转(操作A的逆向操作),一直重复这两个步骤直到字符串为空。如果中途无法操作,输出No,否则输出Yes。下面我们来证明这个方法的正确性:首先,假设有一个序列\(A......
  • AtCoder题解集锦
    注:本文原发表于CSDN,现已停止更新。原文如下:AtCoder题解集锦自己从全网整理的一些优质AtCoder题解,目前只有ABC(AtCoderBeginnerContest)的C~F。不定期更新。如您有更多需求,欢迎私信我或在评论区留言!\(\rarr\)题解列表传送门用法表格查找找到对应比赛的行找到对应......
  • AtCoder Beginner Contest 250 C~E 题解
    C-AdjacentSwaps题目大意\(N\)个球从左到右排成一列。开始时,从左往右的第\(i\)个球上写着数字\(i\)。请执行\(Q\)个操作,第\(i\)个操作如下:令\(j=~N\)个球中写着数字\(x_i\)的球的位置如果\(j=N\),将其与第\(j-1\)个球交换;否则,与第\(j+1\)个球交换。求所有操作后的球上分......
  • UNIQUE VISION Programming Contest 2022(AtCoder Beginner Contest 248)C~D 题解
    C-DiceSum题目大意有多少个整数序列\(A=(A_1,\dots,A_N)\)符合如下条件:\(1\leA_i\leM\)\(\sum\limits_{i=1}^NA_i\leK\)输出答案,对\(998244353\)取模。\(1\leN,M\le50\)\(N\leK\leNM\)输入格式\(N~M~K\)输出格式输出答案,对\(998244353\)取模。分析艹C题......
  • AtCoder Beginner Contest 252 A~G 题解
    前言这是我第一次写7题(A~G)的ABC题解,若有写得不好或者不到位的地方请多多指教,我将万分感激,感谢大家的支持!A-ASCIIcode题目大意给定正整数\(N\),输出ASCII码是\(N\)的字母。\(97\leN\le122\)输入格式\(N\)输出格式输出ASCII码是\(N\)的字母。分析注意a对应\(97\)......