简单记录, 备忘查找. 考前预习, 考后忘光.

面了个极创, 学长们在搞移动端人工智障的项目. 然后我就得开始系统学人工智障了.

永凯学长给了资料, 本文是参考Victor Zhou的博客Machine Learning for Beginners: An Introduction to Neural Networks学习后的笔记.

之前听科创的学长讲过2h, 所以现在看起来好像挺简单?

终于把这首曲子练完了, 很短, 三段, 重复. 却饱含了一种静谧.

一个洒满阳光的午后, 慵懒地躺在藤椅上, 满眼皆是洁白的云彩, 镶嵌在湛蓝的天空, 像一颗玛瑙. 云也慵懒地自顾自舒展, 变得越来越薄. 阳光穿过, 金色遍身, 尽是温暖. 这一刻, 仿佛就在一瞬, 殊不知分针已经绕过了几个圈.

去留无意, 望天上云卷云舒

闭上眼, 自己就在云端, 蓝天很安静, 只有白云在流行. 忘却了周遭的一切, 只听得见白云慢慢卷起的悉索声. 一个人独处的静谧, 向蓝天祈祷, 同白云分享. 一缕缕清凉的雾气抚摸着面庞, 钻进灵魂深处, 由内而外, 净化浮躁的心灵.

再睁开眼, 就忘记今是何世, 自己是何许人也.

之前没记, 正好最近解决了一个相关问题, 一起记录一下.

给出 $1 \sim n$ 的排列, 开始时A, B各选一个点, 然后轮流移动, 每次移动只能移动到相邻的位置, 且不能碰到另一个人. 并且, A只能走更小的数字, B只能走更大的数字. A先走, 不能走的人输. 问A必胜的选点有多少个.

$2 \le n \le 10^5$

可以发现, 和排列没什么关系. 看成折线图, 发现, A一定要选峰, 否则在坡上, B只需要卡他下坡路, A就无了.

所以现在需要看某个峰是不是必胜.

考虑仅有一个峰, 首先能够发现, 如果AB相对走的话, 距离为奇数, A败; 距离为偶数, A胜. 更多地(当时这么思考的), 如果下落长度为奇数, 那么B只要放在底下(或者离峰距离为奇数的地方), A必败. 所以此时A一定不会走是奇数的一边, 那么他只能走另一边. 如果另一边是奇数, 那无论如何必败.

这启示我们考虑两边的下落距离奇偶性.

还可以发现, 如果有一边很长, 另一边较短, B可以放在较长的边上, 这样A走另一边不能胜利. 走这一边还需要看B放的位置到峰是不是奇数.

这启示我们考虑两边下落的距离差.

所以这样讨论:

1. 2奇: 必败
2. 1奇1偶:
   1. 奇>偶: B放奇边底端, A必败
   2. 偶>奇: B放偶边(长边)等于奇边的位置, A必败
3. 2偶:
   1. 不相等: B放较长边的 (较短边+1) 的位置, A必败
   2. 相等: A必胜

画图即可. 由于重点不在证明而在思考方式, 所以不画(证)了.

有 $q$ 个询问每次询问的 $k$ 不变, 要求找到 $k$ 个非负数的和为 $n$. 如果这 $k$ 个数中某个数位 (个位, 十位, 百位…) 上有 $3, 6, 9$ 那么就会增加幸运值. 具体的数值如下表, $F$ 都会提前给出, 求出最大幸运值.

$1 \le n, k \le 999999, 1 \le F_i \le 10^9, 1 \le q \le 10^5$

能看出来和应该是一个背包(取一些数, 使其和为某值), 但明显不能直接背包, 因为这样复杂度至少 $O(k^2)$

注意到, 不同数字相同位置的数位交换对答案没有影响, 比如 $31, 29$ 和 $39, 21$ 对答案的贡献是一样的. 利用这个性质, 我们可以把 $k - 1$ 个数都构造成**仅由$0, 3, 6, 9$**组成(因为对答案的贡献为$0$, 所以可以含前导零), 而只剩下一个数, 可能有除 $0, 3, 6, 9$ 之外的其他数字. 也就是说, 能够构造出一种解, 使得最多只有一个数字, 每一位不全为 $0$ 或 $3$ 或 $6$ 或 $9$.

二维平面上有 $n$ 个点$(x_i, y_i)$. 有一辆电汽车, 电池容量为 $W$, 要从点 $s$ 到点 $t$. 每个点都可以充电, 充一个单位的电量需要 $c_i$ 点花费. 一个单位的电量能走一个单位距离. 两个点之间的距离是笛卡尔距离. 开始时车在 $s$ 点电量为 $0$, 问在充电次数不超过 $\Delta$ 的情况下, 到达 $t$ 点的最小花费.

$1 \le n \le 1000, 0 \le x_i, y_i \le 10^6, 1 \le c_i \le 10^4, 1 \le W \le 10^5, 1 \le \Delta \le 10$

首先想到经典贪心题. 确定一条路线, 那么一定是两种选择:

1. 充满电往下走
2. 充到刚好到下一个点

根据这两个决策, 我们设计dp.

$dp(i, x, 0)$ 表示已经充了 $i$ 次电, 当前在点 $x$, 从某个点充到刚好能过来, 即现在的电量为 $0$.