Blog E

USACO 2021 US Open 铂金组 T1 题解

想了挺久

United Cows of Farmer John 题意：给定一个长度为 n 的数列 $a_i$，求符合下列条件的三元组 ${i,j,k}$ 个数： $1\le i < j < k \le n$ $a_i,a_j,a_k$ 的值在 $a_{[i,k]}$ 各只出现一次（即他们自己）。思路：为了方便描述，我们称 $a_i$ 为 i 点的颜色，记 $pre_i$ 表示 $a_i$ 的前驱（即 i 之前与 $a_i$ 相同的最后一个数），记集合 $last$ 表示右端点扫描到 r 时，每个颜色最后一次出现的位置。朴素想法考虑固定右端点 r，然后枚举左...

Posted by ethan-zhou on April 6, 2021

USACO 2021 US Open 金组题解

终于 AK 了！

T1 United Cows of Farmer John 思路这题比较水，记 $pre_i$ 为 i 号奶牛的前驱（即 i 前面最靠后的与 i 号奶牛颜色相同的奶牛）。令这两个奶牛领导中，在序列中靠后的那个为 i，考虑靠前的奶牛领导有几种可能，不难发现其个数为 $[pre_i+1,i-1]$ 这段区间内奶牛的种类数。于是直接上树状数组，用代表元法（将每种种类的最后出现位置加一）即可求出答案。复杂度 $O(n\log n)$ 代码 #include<bits/stdc++.h> using namespace std; #define fi first #def...

Posted by ethan-zhou on April 3, 2021

【题解】P3747 相逢是问候

麻烦得很

题意定义函数 $f(x)=c^x$ 维护给定序列 $a_i$，支持两种操作（p，c 由输入给定）：将数列第 l 到 r 项中的每一项 $a_i$，赋值为 $f(a_i)$ 查询 $\sum_{i=l}^{i\leq r}a_i\ \pmod p$

Posted by ethan-zhou on February 20, 2021

【题解】洛谷二月月赛div2

25%的时间获得了自己100%的得分

这次月赛感觉考的海星，估计是 WC 爆炸时失去的 RP 又回来了吧。前一个小时多点把 abc 都切了，后面都没骗到分（ T1 『MdOI R4』Fun 傻子题，直接模拟即可。 ll n,m,k; ll arr[MXN]; inline void solve(){ //codes cin>>n>>m>>k; for(int i=1;i<=n;i++) cin>>arr[i]; ll cnt=0; for(int i=1;i<=n;i++){ ll tmp; cin>>tmp; cnt+=tm...

Posted by ethan-zhou on February 9, 2021

【题解】P7287魔法

听说有1log做法？

题目在此：P7287 结论所有的 1 操作一定在所有的 2 操作之前进行每个 1 操作的范围一定是 [1,n] 每次 2 操作都是对当前序列的最大字段和那个区间进行的。最终选的区间是最终序列的最大子段和 1，2，4 都很显然，3 结论可感性理解（这个野鸡博主不会证）：如果每次都选那个最大子段和进行操作，那得到的结果一定是最优的。否则一旦在操作过程中有操作的区间不是最大子段和区间的话，在进行同样次操作之后的结果是不优的。算法现在，我们只需要知道 1 操作以及 2 操作的次数，就能算出最终数列的最大最大字段和。接着观察发现2操作的次数是不超过\(...

Posted by ethan-zhou on January 25, 2021

USACO一月月赛金组游记

暴力奇迹

T1 转化上来一看这题蒙了，猜了几个结论，又打了个贪心，结果只过了样例，就先去打 T2 了。打完 T2 回到这题，仔细想想，发现这个答案是很难直接在输入字符串序列上 dp 的，故考虑构造牛文字母表的顺序，使得结果最小。先跳过构造的过程，假设我们目前已经知道，牛文字母表的顺序就是 abcdefg… 我们如何快速的求出输入序列的答案呢？不妨设输入序列为abcba，我们发现这个序列最少需要唱3次才能出现，为什么呢？唱第一次可以出现到abc但是下一项b的字典序比c靠前，所以b就只能再唱一次了，下一项a也是同理，所以这个序列的答案是 3 。总结一下，答案为： $1+\sum_...

Posted by ethan-zhou on January 24, 2021

牛客第三场提高组模拟赛T2题解

队除我炸

队里除了我都炸了 \[n,m \leq 5\times 10^5,q \leq 10^5,c_i\leq 600, 0<w_i,l_i,r_i < 10^9\] 首先不考虑 w（每条边的难度）的数据范围，我们可以得到以下的做法。预处理: 用 spfa 求出 dis[i]，表示：从 x 到每一个点的路径上，最大难度的最小值用 addp[i] （一个 vector）存储：牛半仙的困难接受程度从 i-1 增加到 i 的时候，他能见到的新的妹子们。将 i 号节点 push 到 addp[dis[i]] 里。计算...

Posted by ethan-zhou on October 22, 2020

【题解】[APIO2020]T1粉刷墙壁

第一次参加apio

注：本题解详细讲解了各部分分的得法以及对于正解的启发问题转化理解题意之后我们不难发现，只要我们能算出是否有以 i 块墙壁开始，刷 M 块墙的合法请求，那么这就转化成了一个区间覆盖问题。比如：样例1中，x=1，y=0 是一个合法请求，那么 [0,M-1] 就是一个合法区间（即：一次请求就可以覆盖这个区间）找出这些区间之后，就可以做一个简单的贪心了，贪心代码如下： /* * canpaint[i]表示有没有从第i块开始的合法区间 * lastr表示目前匹配到的右端点 * newl表示下一个合法区间的左端点 */ int lastr=-1,newl=...

Posted by ethan-zhou on August 18, 2020

cf-edu-round-49解题记录

罚时太长

注：这个解题主要详细讲T3，T4 T1 只需要找到每个位置对称的字符，看他们是否相差 +-2 或 0 即可。代码：

Posted by ethan-zhou on July 17, 2020

cf-edu-round-48解题记录

有点难

T1 直接模拟代码： #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int n,m; int cp=0,tmp; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&tmp); cp+=tmp; printf("%d ",cp/m); cp%=m; } re...

Posted by ethan-zhou on July 10, 2020