331
CF331A1&CF331A2
不难发现一件事:对于在 \(i\) 之后能跟 \(i\) 匹配的 \(j\),最好的办法显然是使得 \(j\) 最大。则用前缀和统计整个和,并且用前缀和维护负数和,在枚举 \(i\) 统计出最小答案时在后面计算出满足最大答案的条件并输出即可。 ac records #include<bits/std ......
[ABC331F] Palindrome Query 题解
思路 判断一个字符串是否是回文串,可以从它的本质出发:正着读和倒着读是一样的。快速判断它正着和反着是否一样,用字符串哈希即可。又因为涉及单点修改,区间查询,那么使用线段树维护这两个值就行了。 这里讲一下如何 pushup。以正着的哈希值为例:我们要更新 \(p\) 这个点的 \(hash\) 值,已 ......
CodeForces 331E2 Deja Vu
洛谷传送门 CF 传送门 考虑一条好的路径 \(x \to y\) 中一定至少存在一条边 \((u, v)\),满足这条边的序列 \(a\) 存在一个 \(j \in [1, |a| - 1]\),满足 \(a_j = u, a_{j + 1} = v\),就是说 \(a\) 包含一对相邻的 \(( ......
AtCoder Beginner Contest 331 G - Collect Them All【概率期望+容斥+多项式】
题目链接:ABC331_G 写在前面 将来如果回顾这道题,建议自己看完题意一定先重新推一遍。如果还是不够熟练,多去做一些同类型的题目吧。 题意: 盒子里有 \(N\) 张卡片,每张卡片上写着一个数字,数字的范围是 \(1,...,M\),写着数字 \(i\) 的卡片有 \(C_i\) 张\((C_i ......
AtCoder Beginner Contest 331
C - Sum of Numbers Greater Than Me 题意:给定一个长度为n的数组,分别找出比a[i]大的数组里的数的和 思路:用map记录每个数的个数,然后遍历一遍,后面一个项就是数组之和-前面一项-前面的累加 #define int long long using namespa ......
Daiwa Securities Co. Ltd. Programming Contest 2023(AtCoder Beginner Contest 331)
Daiwa Securities Co. Ltd. Programming Contest 2023(AtCoder Beginner Contest 331) A - Tomorrow 解题思路: 模拟。 代码: #include <bits/stdc++.h> using namespace s ......
AtCoder Beginner Contest 331
A - Tomorrow (abc331 A) 题目大意 给定一年的月数和一月的天数,以及当天日期,问次日的日期。 解题思路 一个简单的进制加法运算,超出进制数则向前加一。 神奇的代码 #include <bits/stdc++.h> using namespace std; using LL = ......
ABC331G 题解
盒子里有 \(n\) 张 \(m\) 种卡片,第 \(i\) 种卡片有 \(c_i\) 张。\(\sum c_i=n\)。 每次均匀随机选一张,再放回去。求拿出过的卡片包含全部种类所需要的取出次数的期望。 对 \(998244353\) 取模。 \(1\leq n,m\leq 2e5,c_i\gt0 ......
AtCoder Beginner Contest 331
AtCoder Beginner Contest 331 这场状态好差,下午的校赛也打的好差。 A - Tomorrow #include <bits/stdc++.h> #define int long long #define endl '\n' using namespace std; voi ......
AtCoder Beginner Contest 331 G Collect Them All
洛谷传送门 AtCoder 传送门 设数字 \(i\) 第一次拿到的时间为 \(t_i\),所求即为 \(E(\max\limits_{i = 1}^m t_i)\)。 施 min-max 容斥,有: \[\begin{aligned}E(\max\limits_{i = 1}^m t_i) & = ......
AtCoder Beginner Contest 331
B - Buy One Carton of Milk 难度: ⭐ 题目大意 选择有三种套餐, 6个鸡蛋S元, 8个鸡蛋M元, 12个鸡蛋L元; 问如果要买至少N个鸡蛋, 最少花费多少钱; 解题思路 一道入门级dp; 神秘代码 #include<bits/stdc++.h> #define int l ......
ABC331G题解
ABC331G 日常被bot吊打罢了。 首先注意到一件事是你 需要求一堆max的期望 对吧。所以其实上来就应该试试上 min-max容斥 的。但是鉴于我没有脑子,所以其实没想到也可以理解。 先来复习一下式子: \[Emax(S) = \sum_{T \subset S} Emin(T)(-1)^{\ ......
ABC 331 F - Palindrome Query(字符串哈希,树状数组)
字符串哈希 [OI-Wiki](字符串哈希 - OI Wiki (oi-wiki.org)) 分为两种哈希方式:以左为高位 和 以右为高位 如果只是快速查询每个字串的哈希值,用以左为高位比较简单,即 \[Hash[l...r]=Hash[1...r]-Hash[1...(l-1)]\times ba ......
AtCoder Beginner Contest 331
AtCoder Beginner Contest 331 基本情况 第一次打这个,感觉跟CF有点不一样。 A题秒了。 B题就完全背包变种秒了。 C题简单模拟,秒了。 D题明显是二位前缀和,但是后面处理总感觉有点麻烦,就先调到E。 E题做出来了,但是不如标程,所以贴一下标程。 D - Tile Pat ......
Atcoder Beginner Contest 331 D - Tile Pattern
我最初的想法是把整个正方形切割成九个部分(四个角,四个边上的条条,以及中心的部分),这样是可做的,但是,真的很难调啊(于是我就光荣qs4了) 然后我们通过参考“tr”的代码,发现,其实这又可以转化为一个前缀的计算,用右下角减去左上角。 我能说什么了,以后尽量把问题转换为更优秀和简单的子问题吧。 ......
AtCoder_abc331
AtCoder_abc331 (这次题真的真的真的好难) 比赛链接 A - Tomorrow 题目链接 题目大意 有一个$M$个月,$D$天的日历,请输出$y年m月z日$的下一天。 解题思路 先让天数加一,如果超过了$D$就让月份加一,天数减$D$,然后月份同理 代码 // Problem: A - ......
Daiwa Securities Co. Ltd. Programming Contest 2023(AtCoder Beginner Contest 331)
Daiwa Securities Co. Ltd. Programming Contest 2023(AtCoder Beginner Contest 331) A - Tomorrow int main() { IOS; for (_ = 1; _; --_) { int M, D, y, m, ......
【每日一题】Problem 331C1. The Great Julya Calendar
[原题](https://codeforces.com/problemset/problem/331/C1) #### 解决思路 寻求减到 0 所需的最小次数,即 $Num(n) \Rightarrow Num(n-x)+1$ 当存在一个 x 使得 (n - x)% 10 = 0 时,那么(n - ......
CS331 Programming
CS331 Coursework (MATLAB or Python Programming) Submission Deadline: 31st March 2023 at noon, via Tabula Submission Format:o If you use MALTAB, submit ......