Arn01d's planet

比赛链接：Dashboard - Educational Codeforces Round 163 (Rated for Div. 2) - Codeforces C 题意：有一个 $2\times n$ 的网格，每个格子有一个指向左或右的箭头。有一机器人从 $(1,1)$ 开始，每次的操作如下：先向上下左右走到任一个网格(不能超出地图)，然后根据该格箭头走一步。问能否走到 $(2,n)$ 。 dfs 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include<bits/stdc++.h>using namespace std;int mp[3][200005];int v[3][200005];int n;bool flag=0;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};bool che ...

比赛链接：Dashboard - The 2023 ICPC Asia Shenyang Regional Contest (The 2nd Universal Cup. Stage 13: Shenyang) - Codeforces C 水题 E 题意：有羊 $x$ 只，狼 $y$ 只，有一人用一艘容量为 $p$ 的船要将所有的羊运到对岸，但当人不在的一边中狼严格大于羊的数量加 $q$ ，羊就会被吃掉。在保证羊安全的前提下至少需要运多少次。 考虑设计 $dp$ 状态：$dp[i][j][k]$ ，表示人在 $k $ 岸时，初始岸的羊和狼的数量为 $i,j$ 时的最小次数。 因为求最少次数，用 $bfs$ 更新状态。每次可以转移如下： $$ dp[i][j][1]\rightarrow dp[i-n][j-m][2],n+m=p,i-n\geq j-m+q $$ $$ dp[i][j][2]\rightarrow dp[i][j+m][1] $$ 每次运送到对岸时都把容量排满是最优的； 往回运的时候只把多余的狼运回，保证对岸满足条件即可。 最终的答案就是 $dp[0][y’][ ...

原理 对于特征集合 $\pmb X$ ，预测值 $\hat y$ ，可用矩阵向量乘法表示为： $$ \hat{y}=\pmb Xw+b $$ 其中 $X$ 的每一行代表一条数据。 定义损失函数为： $$ l^{(i)}(w,b)=\frac{1}{2}(\hat y^{(i)}-y^{(i)})^2 $$ 为了降低损失，定义平均损失函数为： $$ L(w,b)=\frac{1}{n}\sum l^{(i)}(w,b)=\frac{1}{n}\sum \frac{1}{2}(w^\mathrm Tx^{(i)}+b-y^{(i)})^2 $$ 要求的即是： $$ w^\ast,b^\ast=\arg \mathop{\min}\limits_{w,b} L(w,b) $$ 求解时利用随机梯度下降法解出 $w,b$ ： $$ w\leftarrow w-\frac{\eta}{|\beta|}\sum\partial_{w}l^{(i)}(w,b)=w-\frac{\eta}{|\beta|}\sum x^{(i)}(w^\mathrm Tx^{(i)}+b-y^{(i)}) $$ { } ...

比赛链接：Dashboard - 3.10 周赛 - Codeforces A 题意：给出两个长为 $n$ 的字符串 $s$ ，$t$ ，找出满足如下的整数对 $(i,j)$ 的个数：子串 $s_is_{i+1}…s_l$ 字典序严格小于 $t_it_{i+1}…t_l$ 。 若在某一位满足 $s_i<t_i$ ，那么以 $i$ 为开头的所有整数对都满足； 若在连续多位 $s_i=t_i$ ，如果往后第一位不同的位上 $s_j<t_j$ ，那么以 $i$ 开头，至少以 $j$ 结尾是可行的。 那么只需要统计 $s_i=t_i$ 是下一个最近的不等位的情况即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<bits/stdc++.h>using namespace std;int p[200005];int nxt[200005];int main(){ int n; char s[200005],t[2000 ...

快读快写，ios。 注意memset中sizeof的用法。可以直接循环数组清零 在set中找元素不能用lower_bound(C.begin(), C.end(), t)，应该用C.lower_bound(t)。 注意数据范围。long long。一定要算清楚。 整数乘法注意int会不会溢出，可以改成 LL ans=1LL*a*b

比赛链接：Dashboard - The 2023 ICPC Asia Nanjing Regional Contest (The 2nd Universal Cup. Stage 11: Nanjing) - Codeforces SUA牛逼 A 题意：在一个 $n\times m$ 的网格中有很多洞，没有洞的位置上都有一只袋鼠，现在控制所有袋鼠上下左右移动，移出网格或到洞里就会淘汰，问对每一只袋鼠，能否存在一种操作序列使其成为最后一只袋鼠，求这样的袋鼠的数量。$n\times m\leq1000$ 一个比较难写的bfs。 对每个袋鼠，考虑它是否能将其他所有袋鼠都带进坑里，可用 $(i,j,i’,j’)$ 表示，在存储状态时将其哈希处理为 $S=n\times m\times n\times i+n\times m\times j+m\times i’+j’$ 。在bfs时，将某一初始状态能到达的所有位置都记录下初始位置进行剪枝，若以后的初始状态遍历过，那么就直接跳过。复杂度 $O(n^2\times m^2)$ 。 1234567891011121314151617181920 ...

比赛链接：Dashboard - Codeforces Round 932 (Div. 2) - Codeforces C 题意：给出一个数组包含 $n$ 个元素，每个元素包含 $a$、$b$ 两个元素，在这个数组中找出最多的元素并令其下标为 $p_1,…,p_k$ ，使得： 不超过 $l$ 。$n^2\leq 2 \times 10^6$ 把数组按照 $b$ 从大到小排序后，$n^2$ 遍历 $b$ 项的开头 $st$ 与结尾 $ed$ ，可以证得当 $b$ 降序排列时得到的和最小。 用 $multiset$ 维护 $st$ 与 $ed$ 之间的 $a$ 的最大值。 不用担心在multiset中将ed元素的a值删除，因为删除后等效于ed位置提前，且b项的值还变大了，故不会影响答案统计 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<bits/stdc++.h>using namespace std;// ...

比赛链接：Dashboard - 2024.3.3 周赛 - Codeforces C 题意：给出$p$，求整数对 $(a,b)$ 使得 $\frac{a}{b}=p$ 且 $\frac{a}{b},\frac{a+1}{b+1},\frac{a+2}{b+2}$ 均为整数。$p\leq10^{18}$ 通过数学化简后即为求满足以下条件的 $b$ ：$k\times(b+1)\times(b+2)=2\times(p-1),b+1|p-1$ 关于求 $a\times b\times f(b)=p,p\leq10^{18}$ 时，可采用如下的方法： 枚举 $a\in[1,\sqrt[3]p]$，使 $a$ 成为最小的值，然后手算出 $b$ 的值并判断是否满足条件。 枚举 $b\in[1,\sqrt[3]p]$， 使 $b$ 成为最小的值，然后判断 $a$ 是否满足条件。 这种方法可以使时间复杂度为 $O(\sqrt[3]p)$。 123456789101112131415161718192021222324252627282930313233343536373839404142 ...

踩了好多坑。。。 服了。。。 在文档中引用图片 在source文件夹下单独建文件夹image存放图片，引用图片时用如下格式 1 在markdown中编译不出来，但能在hexo上显示 编译时根目录在source文件夹，故直接在source下新建images文件夹，用相对路径引用即可。 建立图库 建立gallery group 建立图库时把图库当一个页面就行 1hexo n page gallery 在gallery文件夹的index中先把type、top_img等改掉 在md文件下插入html代码块，格式如下： 1234<div class="gallery-group-main">{% galleryGroup name description link img-url %}{% galleryGroup name description link img-url %}</div> 即： 123<div c ...