首页 > 其他分享 >abc369 题解

abc369 题解

时间:2024-09-01 10:03:24浏览次数:10  
标签:le 题意 题解 abc369 序列 contests 等差数列

切了 A~F,还挺开心(但是如果上一次把 G 切了的话,我就上青了 QAQ
比赛链接:https://atcoder.jp/contests/abc369

A - 369

题意:

给定正整数 \(a,b\)(\(1\le a,b\le 100\)),请问有多少个整数 \(x\) 满足 \(a,b,x\) 排序后构成等差数列。

思路:

观察到 \(a,b\) 范围很小,直接枚举 \(x\) 即可。

代码:

https://atcoder.jp/contests/abc369/submissions/57274734

B - Piano 3

题意:

给定 2 个序列 \(a,b\),序列长度分别为 \(n,m\),求 \(\sum_{i=2}^n \lvert a_i-a_{i-1}\rvert+\sum_{i=2}^m \lvert b_i-b_{i-1}\rvert\)。

思路:

按题意模拟即可。

C - Count Arithmetic Subarrays

题意:

给定一个长度为 \(n\)(\(1\le n\le 2\times 10^5\))的序列 \(a\),求 \(a\) 有多少个子串 \(b\) 满足 \(b\) 升序排列且为等差数列。

思路:

容易发现一个性质:若 \(a[l\ldots r]\) 为等差数列,且 \(a[l\ldots r+1]\) 不为等差数列,那么 \(a[l+1\ldots r+1]\) 不为等差数列,\(a[l\ldots r+2]\) 也不为等差数列。

那么我们可以双指针,让 \(r\) 从 \(l\) 开始扩展,扩展到 \(a[l\ldots r]\) 为等差数列时,且 \(a[l\ldots r+1]\) 不为等差数列时,计算方案数为 \(\dfrac{(r-l+1)(r-l+2)}{2}\),但是这样计算会把长度为 \(1\) 的子串算重,那么可以将长度为 \(1\) 的子串不在双指针中计算,那么每次计算的方案数为 \(\dfrac{(r-l)(r-l+1)}{2}\),最后再将答案加 \(n\) 即可。

代码:

https://atcoder.jp/contests/abc369/submissions/57289604

D - Bonus EXP

题意:

给定一个长度为 \(n\)(\(1\le n\le 2\times 10^5\))的序列 \(a\),定义 \(\operatorname{f}(b)=\sum_{i=1}^{\lvert b\rvert} b_i\times[(i-1)\bmod 2+1]\)。求 \(a\) 的所有子序列 \(b\),\(\operatorname{f}(b)\) 的最大值。

思路:

选取子序列,可以想到动态规划。设 \(f_{i,0/1}\) 表示选到了第 \(i\) 个数,当前选到新序列中编号模 \(2\) 为 \(0/1\) 所得到的分数的最大值。\(f_{i,0}\) 可以由 \(f_{j,1}(0\le j\lt i)\) 转移过来,但是可以发现 \(f_{i-3,1}\) 一定比 \(f_{i-1,1}\) 更优,因为中间可以在插一个偶数编号。同理,\(f_{i-2,1}\) 也一定比 \(f_{i-4,1}\) 更优,那么 \(f_{i,0}\) 只要从 \(f_{i-1,1}\) 和 \(f_{i-2,1}\) 转移过来即可。

代码:

https://atcoder.jp/contests/abc369/submissions/57296836

E - Sightseeing Tour

题意:

给定一张 \(n\) 个点 \(m\)(\(2\le n\le 400,n-1\le m\le 2\times 10^5\))条边的无向带权图,图中可能会有重边,但不会有自环。给定 \(T\) 次询问,每次询问给出 \(k\)(\(1\le T\le 3000,1\le k\le 5\))条图上的边,求从 \(1\) 到 \(n\) 经过这 \(k\) 条边的最短路。

思路:

经过这 \(k\) 条边相当于每次从到达的点开始往还没经过的边的任意一个端点走,然后再走该边,这样题目就化成选边的顺序了,有观察到 \(1\le k\le 5\),考虑状压 dp。

设 \(f_{i,S}\) 为到达第 \(i\) 个点,已经过给定边集的子集 \(S\) 的最短路径(这里的 \(i\) 数量很有限,只可能是边的端点)。

枚举集合 \(S\),再枚举集合 \(S\) 中的元素 \(i\),设集合 \(T\) 为集合 \(S\) 中除去元素 \(i\) 的集合,再枚举集合 \(T\) 中的元素 \(j\)(若集合 \(S\) 中只有 \(1\) 个及以下的元素,那么会被预处理算出),考虑用 \(f_{u_j/v_j,T}\) 转移得到 \(f_{u_i/v_i,S}\),很显然有 \(f_{u_i,S}\gets f_{u_j,T}+d_{u_j,v_i}+w_i\)(\(d_{u,v}\) 表示图中 \(u\) 到 \(v\) 的最短路径。\(v_i,v_j\) 同理转移)。

考虑初始化,\(f_{u_i/v_i,\varnothing}=d_{1,u_i/v_i},f_{u_i/v_i,\{i\}}=d_{1,u_i/v_i}+w_i\)。

代码:

https://atcoder.jp/contests/abc369/submissions/57335439

F - Gather Coins

题意:

现在有一个 \(h\times w\) 的网格,网格上有 \(n\) 枚金币,第 \(i\) 枚金币在网格 \((x_i,y_j)\) 处,现在你在网格 \((1,1)\) 处,你想走到网格 \((h,w)\) 处且获得最多的金币,你每次只能向下或向右走。请问你做多能获得多少金币,并输出其中的一种路径。

思路:

容易发现路径的横纵坐标是单调不减的,所以所获得到的金币的横纵坐标也都得是单调不减的,且若所获得的金币的横纵坐标都是单调不减的,那么你一定都能获取到。那么其实就是要求金币按照横坐标从小到大排序后,选取子序列最长且满足纵坐标单调不减,那么题目就转化成了二维偏序问题,可以用最长不下降子序列解决。

代码:

https://atcoder.jp/contests/abc369/submissions/57324756

标签:le,题意,题解,abc369,序列,contests,等差数列
From: https://www.cnblogs.com/lrx-blogs/p/18390878

相关文章

  • 题解:洛谷 P10996 【MX-J3-T3】Tuple
    原题链接介绍一种(也许是正解的)卡常做法先说总体思路:对于每个三元组\((x,y,z)\),若有一个\(w\)满足\((x,y,w),(x,z,w),(y,z,w)\)均存在,则找到了一个合法的四元组\((x,y,z,w)\)。\(20\\rm{Pts}\)做法如果暴力搜索,在遍历每一个三元组时,每一次都扫描所有的\(w\in[1,N]\)......
  • 题解:洛谷 P10497 [USACO03Open] Lost Cows
    原题链接思路+算法首先,考虑读入到\(a_i\)时,如果要得到此时的最优解(指所有牛的编号不重不漏地覆盖\([1,i]\)的所有编号),对于第\(i\)头奶牛,因为在它前面有\(a_i\)头奶牛的编号小于它,所以第\(i\)头奶牛的编号应当为\(a_i+1\)。如果有一头新的奶牛\(i+1\)加入到这个......
  • 题解:洛谷 P10878 [JRKSJ R9] 在相思树下 III
    原题链接解析在操作一时,最小值如果在最后一位,其无法更新任何数,会被删除;否则不在最后一位时一定会被其右侧更大的数更新。所以在操作一时,最小值一定会被更新掉。同理,在操作二时,最大值一定会被更新掉。由此,操作一决定了答案的下限,操作二决定了答案的上限。所以可以得出贪心策略......
  • LOJ #6089. 小 Y 的背包计数问题 题解
    Description小Y有一个大小为\(n\)的背包,并且小Y有\(n\)种物品。对于第\(i\)种物品,共有\(i\)个可以使用,并且对于每一个\(i\)物品,体积均为\(i\)。求小Y把该背包装满的方案数为多少,答案对于\(23333333\)取模。定义两种不同的方案为:当且仅当至少存在一种物品的......
  • ABC369
    Alink判断\(A\),\(B\)之间可不可以放一个数,如果可以就是\(3\)个,不行就是\(2\)个(左右),但是如果\(A\),\(B\)相等就只有一个。点击查看代码#include<bits/stdc++.h>usingnamespacestd;signedmain(){ inta,b; cin>>a>>b; intx=b-a; if(x!=0){ if(x%2==0......
  • 学校训练赛的一些题解
    第二十一届宁波大学程序设计竞赛(重现赛链接)C游戏开发部的小游戏(C)赛时并没有写出来,果然dp还得多练)将所有石头视为容量为\(n\)的背包,每堆石头的数量即背包中物品的质量,对于\(a_i\leqf_i\leqb_i\),由于\(f_i\)最终取值唯一,可当作分组背包处理。将大小为\(i\)的\(t\)......
  • CCF-CSP 2024 --重塑矩阵1,2c语言题解
     创作想法是因为像我当初大一时候想参加一些比赛但是奈何只学了c和c相关数据结构,但是对于许多竞赛的题目的题解往往都是c++或者其他面向对象的编程语言,让我们难以在c语言基础上入手这些比较复杂的题目。 创造的目的是为了帮助各位同时提高我对c语言编程的理解和锻炼个人......
  • CSP-J 2020 初赛试题解析(第一部分:单项选择题(5-10))
    ......
  • 【秋招笔试】8.30饿了么秋招(算法岗)-三语言题解
    ......
  • Leetcode 第 408 场周赛题解
    Leetcode第408场周赛题解Leetcode第408场周赛题解题目1:3232.判断是否可以赢得数字游戏思路代码复杂度分析题目2:3233.统计不是特殊数字的数字数量思路代码复杂度分析题目3:3234.统计1显著的字符串的数量思路代码复杂度分析题目4:3235.判断矩形的两个角落是否......