Mental's Blog

「每一个不曾起舞的日子 都是对生命的辜负」

CUHK CSE PhD/MPhil Early Admission

港中文提前批面试

大概四月份就在官网填了 early admission 的申请,不过在第二轮才收到了面试邀请…… 具体的面试时间是 6 月 21 号,地点在深圳的香格里拉酒店……19 号一考完试就溜回深圳准备面试了 早上很早(8 点 orz)就到了香格里拉,不过由于太早了现场一个人也没有( 后边陆陆续续来了两位华科和电科的老哥,跟他们随便聊了一下 233 然后发现他们面试完还要赶回学校考试 来深...

训练日志

记录个人和团队的训练情况

决定维护一个类似训练日志的东西,方便补题以及未来调整训练的方向和进度 Todolist 很遗憾西安邀请赛没能发挥出最好的表现 算法生涯可能就结束了啊( 有机会还是希望能再重回 icpc 的舞台吧 该启程前往下一个终点了 Online Name Solved Rank A B ...

2012-2013 ACM-ICPC, Asia Tokyo Regional Contest I

二分 + 动态规划

Description 题目链接: https://codeforces.com/gym/101412 打训练赛时遇到的题目,感觉做法十分的优雅~ 题意是给了 $n$ 个字符串,希望把它们有序地放进一个宽为 $w$ 的矩形方格中,相邻的两个字符串之间必须存在空格,除最后一行外,其余每行开头和末尾的格子都必须填有字符串,问字符串之间间隔的最大值最小能是多少? $(3 \le w ...

Codeforces 1151 F

动态规划 + 矩阵快速幂

Description 题目链接: https://codeforces.com/contest/1151/problem/F 题意是说给一个长度为 $n$ 且只由 01 组成的序列(例如 100110),问 $k$ 次操作后有多大概率将原序列变为 000…111 这样的新序列,每次操作是随机选两个位置并对位置上的数进行交换. 题目限制: $2 \le n \le 100, 1 \l...

HDU 5306

吉如一线段树

Description 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5306 题目给定一个长度为 $n$ 的数组 $a_i$,并进行 $m$ 次操作: 操作 $0$ $l$ $r$ $t$ : 将 $[l, r]$ 区间上比 $t$ 大的数用 $t$ 进行替换; 操作 $1$ $l$ $r$ : 查询 $[l, r]$ 区间上的最大...

矩阵乘法递推的优化

叉姐太强辣 orz

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

一些瞎想

希望岁月静好吧

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

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

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

Asia Yokohama Regional Contest 2018 K

贪心 + 二分

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