Mental's Blog

矩阵乘法递推的优化

叉姐太强辣 orz

补去年校赛题目的时候，发现了一道线性递推的题目，不过递推式的大小竟然开到了 1000。一般这类题目都是用矩阵快速幂来处理的，但如果在这里用的话肯定妥妥地超时啊 orz 于是学习了一波叉姐的论文，关于如何优化矩阵乘法递推…论文地址: http://www.docin.com/p-724323397.html P.S. 同时意外感受了一波 BM 递推的强大！只需要把序列传进去，就能返回一个...

作者 mental2008，发布于 2019 年 4 月 11 日

一些瞎想

希望岁月静好吧

前天看了 world final 的转播，感觉热血沸腾啊…虽然整个算法生涯都很少有这种超燃的时刻下周就是校赛了，希望能多补点题，调整下状态，不至于校赛被其他队伍吊起来锤啊 QvQ 人生中总是幻想了很多时刻，自己仿佛是个超人，无所不能但现实总是骨感的，没有汗水甚至痛苦浇灌，总感觉不太真实说实在话，自己对于接下来要打的比赛，或是 cuhk 的申请，都没有十足的把握我高中的时候一...

作者 mental2008，发布于 2019 年 4 月 6 日

SCUT OJ P349

欧拉函数

感觉要每天更新一条博客，来证明自己有在学习啊 QvQ Description scut.online 上的一道题给定两个数 $n,m(1 \le m \le n \le 10^{12})$. 求满足 $1 \le x \le n$ 同时 $m \le gcd(x,n)$ 的 $x$ 的个数. Solution 直接考虑枚举 $gcd(x,n)$，设 $gcd(x,n)=...

作者 mental2008，发布于 2019 年 3 月 15 日

Educational Codeforces Round 61 (Rated for Div. 2)

差一点点回紫名啊 QAQ

Educational Codeforces Round 61 (Rated for Div. 2) 比赛链接: https://codeforces.com/contest/1132 比赛情况: 3/7(384) 被 hack 数: 1😔 总的来说，这次 edu 场应该还挺适合自己的，不过还是没怎么打好…做 C 题的时候复杂度没算好，T 了好几次，最后因为细节写岔了还被 hack ...

作者 mental2008，发布于 2019 年 3 月 6 日

Asia Yokohama Regional Contest 2018 K

贪心 + 二分

Desription 题目链接: https://codeforces.com/gym/102082/attachments 周末打训练赛时遇到的一道比较 interesting 的题目题目大意是说有两个玩家 $a$ 和 $b$ 在比赛，$a$ 和 $b$ 各有 $n$ 张有一定数值的卡牌，在 $a$ 出牌方案固定的情况下，问 $b$ 如何调整出牌能使得 $b$ 获胜的次数最大，同时...

作者 mental2008，发布于 2019 年 3 月 5 日

Educational Codeforces Round 60 (Rated for Div. 2)

最近 debug 的速度好慢啊 QAQ

Educational Codeforces Round 60 (Rated for Div. 2) 比赛链接: https://codeforces.com/contest/1117 A 题意是给定一个数组 $a$，问算术平均值 $(\frac{1}{r-l+1}\sum_{i=l}^{r}a_i)$ 最大的最长连续段长度是多少. $(1 \le n \le 10^5)$ 这个连续...

作者 mental2008，发布于 2019 年 2 月 19 日

Codeforces Round #539 (Div. 2)

螺旋炸裂系列 orz

日常打 cf 状态低迷 QAQ 连题目都读不清楚了啊 Codeforces Round #539 (Div. 2) 比赛链接: https://codeforces.com/contest/1113 A 题意是有一条 $1$->$2$->…->$n$ 的道路，Sasha 需要开车从 $1$ 到达 $n$，初始燃料为 $0$，每移动一步需要耗费 $1$ 燃料，...

作者 mental2008，发布于 2019 年 2 月 18 日

Winter Camp Day3 D

状压 dp

写题解的效率好低啊 QvQ 补题的速度好慢啊 Description 题目链接: https://www.zhixincode.com/contest/12/problem/D?problem_id=186 题意是给定一幅无向带权连通图，询问保证连通的前提下，删除一些边使得道路复杂度 $\sum_{i=1}^{n}\sum_{j=i+1}^{n}d(i,j)$ 的值最大（$d(...

作者 mental2008，发布于 2019 年 2 月 1 日

Winter Camp Day3 I

带权并查集

Description 题目链接: https://www.zhixincode.com/contest/12/problem/I?problem_id=191 题意是有一场 $n$ 个选手参加的石头剪刀布比赛，第 $i$ 个选手坐在第 $i$ 个位置，每个选手都有 $3$ 种可能情况接下来有 $m$ 个询问，操作 $1$ $x$ $y$ 表示让 $y$ 位置的选手去挑战 $x$ 位...