zxp扶摇直上九万里

未归档

学习笔记(4) 比赛题解(3) 题解(2)

/ 注册

全部文章 / 未归档（共65篇）

[ZJOI2014]力题解

题目地址洛谷P3338 Solution 第一道FFT的应用AC祭！我们要求: （直接在除法的时候消掉了qwq） Step 0 卷积是什么？首先我们要有明确的目标，我们要把上面的式子推成卷积的形式，我们就要来回顾一下卷积是什么。卷积的形式如下： Step 1 直接推式子有了目标...

2020-01-02

0 462

[算进] 数据备份

Problem Luogu 题目地址 ACwing 题目地址 Sulotion 代码短，思维强，实现妙（就算猜出性质也不一定会实现），神仙题啊，科科（我太菜了而已）。首先有一个显然的性质：选出来的这 \(k\) 对点一定相邻。根据这个性质，我们做第一步问题转换：记两个点...

2019-12-30

0 386

[算进] 双端队列题解

Problem ACwing 题目地址 Solution 好题，代码短，思维性强，细节多。我们应该推导出以下两条性质：让我们来手玩一下样例，样例排序后应该是这样子的：0 3 3 6 6 9，其中相同的数在排序后的序列是连续的一段，而双端队列中元素应该是序列中连续的一段。（并没有用...

2019-12-24

0 365

[算进] 蚯蚓题解

Problem 洛谷P2827 题目地址 Solution 直接用优先队列模拟可以得到不少的分数，时间复杂度 \(O(m \log m),m<=7*10^6\) ，但是并不能通过此题，我们要考虑挖掘一些性质优化时间复杂度。假设现在有两条蚯蚓，长度分别记为 \(x_1,x_2\)，且满...

2019-12-24

0 475

[算进] 赶牛入圈题解

Problem ACwing 题目地址 Solution 低级套路题。二分边长，二维离散化前缀和预处理，贪心双指针判定即可。时间复杂度 \(O(n^2 \log n)\)，因为离散化了，\(n<=500\) Code Talk is cheap.Show me the cod...

2019-12-23

0 365

[算进] 防线题解

题目地址 ACwing题目地址 Solution 套路题。不会做只是我没见过这个套路而已突破口：但是整条防线上也最多只有一个位置有奇数个防具我们知道一个原理：偶+偶=偶，奇+偶=奇。又因为我们可以快速算出一个前缀和，比如说算出 \(x\) 之前有多少个防具，（用等差数列的一些公...

2019-12-22

0 355

约数之和（数论）

前言失恋了跑过来写这题，想当年这题咕了好久，现在分分钟切了。 ACwing题目地址 Solution 通过唯一分解定理： \[A=p^{\alpha_1}_1*p^{\alpha_2}_2*...*p^{\alpha_n}_n\] 所以： \[A^B=p^{\alpha_1*B}_1...

2019-12-17

0 358

CF 1272F Two Bracket Sequences （括号dp）

题目地址洛谷CF1272F Solution 首先题目中有两个括号串 \(s\) 和 \(t\) ，考虑先设计两维表示 \(s\) 匹配到的位置和 \(t\) 匹配到的位置。接着根据括号dp的一般套路：设计一维表示当前栈中的左括号数量（ygt大佬喜欢形象地把其称为 “前缀和”），所以...

动态规划----线型dp

2019-12-16

0 432

[ZJOI2014]力题解

题目地址洛谷P3338 Solution 第一道FFT的应用AC祭！我们要求: \[E_j=\frac{F_j}{q_j}=\sum_{i<j}\frac{q_i}{(i-j)^2}-\sum_{i>j}\frac{q_i}{(i-j)^2}\] （\(q_j\) 直接在...

数学----多项式FFT

2019-12-15

0 348

Codeforces Round #606 Div. 2 比赛总结

比赛情况 bq. A题 Wrong Answer on test 2 , E题sb题没切。bqbqbq. 比赛总结 bq. 那就直接上题解吧！^-^ A 数位dp，分类讨论，注意细节。 Talk is cheap.Show me the code. #include<bits/...

比赛总结----Codeforces

2019-12-14

0 287