文章

发布于

JetBrains Quest 免费领取三个月全家桶 解密

首先看官推给出的这串代码

48 61 76 65 20 79 6f 75 20 73 65 65 6e 20 74 68 65 20 73 6f 75 72 63 65 20 63 6f 64 65 20 6f 66 20 74 68 65 20 4a 65 74 42 72 61 69 6e 73 20 77 65 62 73 69 74 65 3f

看上去是十六进制，猜测是ASCII，转码一下试试

得到了

Have you seen the source code of the JetBrains website?

那么根据提示我们来到jetBrains的官网看源代码，就找到了如下注释：

      O
{o)xxx|===============-
      O

Welcome to the JetBrains Quest.

What awaits ahead is a series of challenges. Each one will require a little initiative, a little thinking, and a whole lot of JetBrains to get to the end. Cheating is allowed and in some places encouraged. You have until the 15th of March at 12:00 CET to finish all the quests.
Getting to the end of each quest will earn you a reward.
Let the quest commence!

JetBrains has a lot of products, but there is one that looks like a joke on our Products page, you should start there... (hint: use Chrome Incognito mode)
It’s dangerous to go alone take this key: Good luck! == Jrrg#oxfn$

                 O
-===============|xxx(o}
                 O

看到了hint说使用Chrome的无痕模式，那我们无痕模式打开一下Products 页面。顺便，注意他的一句话：带上这个key Good luck! == Jrrg#oxfn$
继续阅读“JetBrains Quest 免费领取三个月全家桶 解密”

发布于

[思维][贪心][贡献拆分] codeforces 1255 E2 Send Boxes to Alice (Hard Version)

题目链接

题意：

给定一个长度为 $n$ 的序列 $a$ ，$n \le 10^6$ ，每个数字 $a_i$ ，满足 $0 \le a_i \le 10^6$ .

可以对这个序列进行一种操作，把第 $i$ 个数字中的一份移动到 $i-1$ 或者 $i+1$ .即操作过后 $i$ 处变为 $a_i-1 , a_{i+1}$ 或者 $a_{i-1}$变为 原来的数字+1.

问最少需要多少次操作使得存在某个数字 $k>1$ 满足所有的 $a_i$ 都可以被k整除（$0$可以被任何数整除），操作过程要满足所有的 $0\le a_i$ 。

题解：

考虑操作完成之后的结果，如果每一个数字都能被 $k$ 整除，那么显然 $S = \sum_{i=1}^{n} a_i$ 也可以被k整除。所以 $k$ 一定是 $S$ 的一个因数。

然后显然 $k$ 为合数时的情况，要么被 $k=其质因子$ 的情况包括，要么就劣于这种情况。所以我们只需要考虑 $k$ 为质数的情况，也就是 $S$ 的所有质因子。

由 $S$ 最大为 $10^{12}$ 可知，其质因子最多应该只有$10-20$种，而且分解出质因子可以用时间复杂度 $O(\sqrt{n})$ 的算法，也就是约 $10^6$ 。

继续阅读“[思维][贪心][贡献拆分] codeforces 1255 E2 Send Boxes to Alice (Hard Version)”

发布于

[数学] 向量函数的雅可比矩阵与链式法则

复习一下我的数学知识T_T

1. 回顾高等数学：多元数量函数的梯度

回想高等数学中常见的多元数量函数$f:\mathbb{R}^{n}\rightarrow \mathbb{R}^{1}$，我们可以把他的输入当作一个向量 $\bf{x}\in \mathbb{R}^{n}$，输出$y=f(\bf{x})\in \mathbb{R}^{1}$是一个数字。那么由高数的知识我们知道$f$的梯度定义为
$$
\nabla f_{\boldsymbol{x}} \overset{\underset{\mathrm{def}}{}}{=} \left[ \frac{\partial f }{\partial x_1}, \frac{\partial f }{\partial x_2},\cdots,\frac{\partial f }{\partial x_n} \right]=\frac{\partial f }{\partial \boldsymbol{x}}
$$

有了上式，我们还可以写出全微分的向量化表示

\[
\begin{aligned}
df &= \frac{\partial f}{\partial x_1}dx_1+\frac{\partial f}{\partial x_2}dx_2+\cdots+\frac{\partial f}{\partial x_n}dx_n \\
&=\left[ \frac{\partial f }{\partial x_1}, \frac{\partial f }{\partial x_2},\cdots,\frac{\partial f }{\partial x_n} \right] \left[dx_1, dx_2,\cdots,dx_n \right]^T \\
&=\frac{\partial f }{\partial \boldsymbol{x}} d\boldsymbol{x}
\end{aligned}
\]

接下来我们将其推广到向量函数。向量函数的“梯度”其实就是雅可比矩阵。
继续阅读“[数学] 向量函数的雅可比矩阵与链式法则”

发布于

2019 kali 笔记本电脑 双系统 双显卡 配置nvidia显卡支持外接hdmi显示器

。。。绝大多数人都会照着官方的教程做，但是这个操作是针对只有一张nvidia显卡的台式机来说的，而不是笔记本的双显卡。。。。按照这个教程，装完之后是可以用这个gpu做运算的，但是不能用来做显示。。。插上外接显示器没有任何反应，用xrandr根本检测不到有外界显示器存在。

出现这个问题的原因是官方的配置里缺少了一步配置显示的操作。。。如果只有一张卡的话装系统的时候显示设置就配置好了，双显卡的话默认的显示用的是核显，独显根本没管，所以我们要手动操作一下。

注意：在参考本配置之前请务必先按照官网Doc走一遍，确保gpu驱动已经装好，可以进行运算测试之后再进行。

我的kali版本

Linux 5.3.0-kali2-amd64 #1 SMP Debian 5.3.9-3kali1 (2019-11-20) x86_64 GNU/Linux
  1. 首先安装kernel headers，不然驱动编译可能会出问题
apt install linux-headers-$(uname -r)

继续阅读“2019 kali 笔记本电脑 双系统 双显卡 配置nvidia显卡支持外接hdmi显示器”

发布于

UEFI双系统下手动删除Ubuntu引导

准备换电脑，把手上这台给我爸玩了，然后想着把Ubuntu删除掉只留个windows。删除双系统里的ubuntu，肯定要先解决引导的问题，然后再在磁盘管理里删除该系统所在卷了，但是操作过程中发现我的ubuntu引导的删除有问题，记录一下操作方法防止自己以后再乱搞。

首先确认本机是UFEI引导的,以管理员身份打开cmd然后输入 bcdedit /enum {current}，如果显示结果如下，path的值为winload.efi则为uefi引导。

此时网络上流行的通用做法是在win10下用EasyUEFI软件中的管理EFI启动项功能来删除ubuntu引导，但是我自己的电脑用这个方法在软件里删除之后重启发现引导还在那儿没动，想了下可能是因为之前某次沙雕的 rm -rf /* 把引导搞坏了。。。当时只是修复了下Windows的引导，ubuntu直接重装了，可能留下了某些隐患现在暴露出来了emmmmm

那借助软件删除不了的话只能自己暴力手动操作了，首先可以想想，这个EasyUFEI软件本身也只是删除了引导文件而已，只要我自己手动的删除这些文件也可以达到相同的效果。利用这个软件的时候可以看到，在ubuntu选项的旁边会给出来 文件路径 这一行，长得类似于 继续阅读“UEFI双系统下手动删除Ubuntu引导”

发布于

[类欧几里得][位运算] 2019牛客暑期多校训练营（第九场）I KM and M

题目链接

题意：

求 $$\sum_{k=1}^{N}((kM)\& M)mod(10^9+7)$$

其中 $1 \le N \le 10^{18}$ , $1 \le M \le 10^{11}$

题解：

按位来做，考虑每一个二进制位i, 假设pi是 M 中从小到大第i位上的0/1), 然后我们又可以用取模和取整来取代某一位上的运算，比如当前处理的是第i位 ，就可以写成 $$\sum_{k=1}^{N}(\lfloor \frac{k*M}{2^i} \rfloor)-2*\sum_{k=1}^{N}(\lfloor \frac{k*M}{2^{i+1}} \rfloor)$$
这显然是一个类欧几里得的模板式子，我们只需要套用一下模板即可。最后把所有位的答案累加起来即可。
继续阅读“[类欧几里得][位运算] 2019牛客暑期多校训练营（第九场）I KM and M”

发布于

[DP][后效性处理] codeforces 1247 E Rock Is Push

题目链接

题意：

给定一个 $n*m$ 的棋盘，每次你只能向右走或者向下走，要求从左上角 $(1,1)$ 走到右下角 $(n,m)$ ，问有多少种走法。
有一个限制因素是棋盘的格子里可能有石头，然后走到一个地方就会把这里的石头按照来的方向推出去，如果有多个石头就会连带着一起推过去。
数据范围 $1\le n,m\le 2000$ ，答案对 $10^9+7$ 取模。

题解：

直接DP会有后效性的问题，我们可以给状态加上约束：令 $D_{i,j} R_{i,j}$ 分别表示一个点改变原方向后向下走/向右走有多少种走法。
这样的话dp转移可以写成类似于 $D_{i,j}=\sum_{i=1}^{n-k-i}R_{i+t,j}$ 的形式，然后这样可以得到一个复杂度 $\mathcal{O}(n^3)$ 的算法，
观察这个式子发现他是线性的，当一个维度发生变化是等式右边只有一到两项会发生变化，就把复杂度降到了 $\mathcal{O}(n^2)$ ,就可以通过本题了。
继续阅读“[DP][后效性处理] codeforces 1247 E Rock Is Push”

发布于

[博弈论][组合游戏][组合计数] codeforces 812E Sagheer and Apple Tree

题目链接

题意：

给定一棵树，每个节点上有 $a_i$ 个苹果，两个人轮流操作，每次把一个节点的一部分(或全部)苹果移到他的某个儿子中(如果是叶子节点没有儿子那么就吃掉这些苹果)，最后不能走的人输。现在在游戏开始前先手可以选取两个不同的节点交换他们之间的苹果数，问有多少种交换方式可以使得先手必胜。
数据范围： $1\le n \le 10^5,\;1\le a_i \le 10^7$

题解：

博弈本身是很简单的阶梯博弈。由阶梯博弈的知识，求胜负只需要计算奇数位上的SG函数异或和即可，这题只不过把阶梯转移到了树上，但是略微分析就可以发现和链状的阶梯是没有区别的，都是奇数往偶数转移当作拿走，偶数往奇数转移就对称操作。

  • 然后考虑计数:
    • 假设初始状态是必胜态，那么可以先计入奇数层自己内部交换和偶数层自己内部交换的对数，分别为 $C_{num\;of\;odd\;level}^2$ 和 $C_{num\;of\;even\;level}^2$；
    • 然后计算奇偶层之间互换的对数，设异或和结果为 $ans$ ，假设一对数 $a_u$ $a_v$ 交换之后可以使得 $ans=0$ ,那么由亦或的性质可得 $a_v=ans\oplus a_u$，那么我们就可以枚举 $a_u$ 的值，找 $a_v$ 有多少个，而后者利用 $map$ 可以很容易的预处理出来。
      继续阅读“[博弈论][组合游戏][组合计数] codeforces 812E Sagheer and Apple Tree”
发布于

[DP][CDQ分治][树状数组] bzoj2244 SDOI2011 拦截导弹

题目链接

题意：

给定一个序列，每个元素有两个属性 $h$ 和 $v$ ，是导弹的高度和速度，发射的拦截炮弹第一发可以是任意的高度和速度，但是要求每一发炮弹的高度和速度都不能大于前一发。问：
1. 选取最优的发射方案的时候最多能拦截多少发导弹
2. 当有多个拦截导弹数目相同的最优方案的时候，我方会从中随机选取一种方案，现在问在这种策略下，每发炮弹能拦截到导弹的概率是多少

题解：

第一问很明显使用cdq分治加速dp转移算LIS，难点在于第二问。把LIS各个节点的转移看成图上的连边的话，可以得到一个dag，而后可以想见使用dp求出到每个点的在LIS上的路径有多少条，便可以确定随机选取的情况下每个节点被选取到的概率为 经过该点的在LIS上的路径数/所有的在LIS上的路径数 。判断一个点是否在LIS上，我们可以两端各求一次LIS，分别记为 $dpl[i] dpr[i]$ ,则如果当前节点满足 $dpl[i]+dpr[i]=\max\limits_{1\le j\le n} dpl[j]+1$ 则说明其属于某个LIS，+1是为了去除节点本身的重复计算。 为了求出经过某个点的路径数，我们可以用之前 dp求最短路必经边的方法 ，从两端分别跑一次dp，分别记录两端到某个节点的属于LIS的路径数为 $gl[i]\;gr[i]$ ，这样的话经过节点i的路径数就可以表示为 $gl[i]*gr[i]$ ，则每个点被选中的概率就可以被表示为

$$\frac{gl[i]*gr[i}{\sum_{[dpl[k]=LIS]}gl[k]}$$

这就是第二问的答案了。因为分治中每次需要对 $[l,r]$ 之间的元素暴力排序，所以复杂度会多一个 $log$ ，也就是 $\mathcal{O}(n\log{}n)$
继续阅读“[DP][CDQ分治][树状数组] bzoj2244 SDOI2011 拦截导弹”

发布于

[KM][二分图带权匹配][优秀模板][比赛补题] codeforces gym 101635 G Cordon Bleu

题目链接

题意：

题解：

KM最大权二分图匹配。然后权值的话，左侧原来的 m 个点代表送货员的家，与右侧表示红酒地点的 n 个点之间连边，权值为送货员的家 ni 与红酒处 mi 之间的距离与 mi 到 饭店之间距离的和，选中这条边的话表示这个人直接从家里到红酒处然后把酒送到了饭店。之后在左侧新建 n-1 个点表示走到店里又出来的送货员，其与右侧n个点的权值设为2倍红酒到饭店的距离，因为回到店里之后所有的送货员就没差别了，而且一个人可以被重复利用，没有什么先后的时间限制。n-1 是因为最多就只有 n-1 瓶红酒会被从店里又出来的人送到（至少有 1 个人是直接从家里到红酒处的）。这样直接跑KM就可以了，但是有个问题是原来的KM板子太慢了，到UOJ#80找了个新的板子，能1s跑2000个点的KM。。。
继续阅读“[KM][二分图带权匹配][优秀模板][比赛补题] codeforces gym 101635 G Cordon Bleu”