Blog E

路漫漫其修远兮,吾将上下而求索。

【题解】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$

【题解】洛谷二月月赛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...

【题解】P7287魔法

听说有1log做法?

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

USACO一月月赛金组游记

暴力奇迹

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

牛客第三场提高组模拟赛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]] 里。 计算...

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

第一次参加apio

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

cf-edu-round-49解题记录

罚时太长

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

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...

cf-edu-round-47解题记录

水题翻车

T1 直接按照题目要求模拟,复杂度\(O(M+N)\) 代码 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int NR=1005; int n,m; int a[NR],b[NR]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",a+i); for(int i=1;i<...

【题解】P6477 [NOI Online t2 提高组]子序列问题

t1炸了

注:本题解看似很长其实是非常详细,实则思路简单粗暴,容易理解 暴力优化 最暴力的做法即为枚举每一对 \(l\) , \(r\) ,并分别计算其 \(f(l,r)\) 的值。但这样不知道会慢到哪里去了,所以我们考虑只滚动 \(l\) 的值,并每次计算 \(G(l)=\sum_{r=l}^{n} f^2(l,r)\) 的值。 转移 考虑 \(G(l)\) 如何从 \(G(l-1)\) 转移过来,由 \(G\) 的定义: \[\begin{aligned} G(l-1)&=&f^2(l-1,l-1)+&f^2(l-1,l)&&+\cdots +f^2...

icon