Codeforces Edu R40

手残比赛系列 +3 +3 +3 +3 +3……

话不多说进入正题

A. Diagonal Walking

瞎dp一波即可 贪心也对(当时没仔细想直接开始敲dp)

B. String Typing

枚举终点然后判断能不能复制即可。

记得倒序,要不会被aaaaaaaaa这种卡掉

C. Matrix Walk

尝试能不能通过上下的移动确定一行的宽度y

然后fixed宽度,把不合法的上下移动,左右移动判掉即可

特判不动的情况和没有上下移动的情况

x轴直接设置10^9

D. Fight Against Traffic

两遍SPFA然后枚举左右端点判定距离即可

注意有两种情况,还有就是ans要除2

E. Water Taps

把式子移一下就会发现是贪心

还没写出来,写出来再说

F. Runner’s Problem

时间不够了,没看题目

G. Castle Defense

先差分一遍把初始的\rm defense指数算出来

然后二分最小值,用贪心的方法判定

区间影响那就差分一下,假设判定的时候当前不足,还要让i+1加上补充的数目,i+2 \times \rm Range -1减去数目,然后从左到右扫就行

H. Path Counting

留坑

I. Yet Another String Matching Problem

留坑

乱写点线代

UPD:刚买了本线代,感觉还挺好的,学几页之后会在这里补充一些想法和笔记。

 

矩阵都会吧……基础的加减法

矩阵转置满足:

\begin{array}{l} \left( A^T \right) ^T=A \\\\ \left( \lambda A \right) ^T=\lambda A^T \\\\ \left( AB \right) ^T=B^TA^T \\\\ \end{array}


矩阵乘法(提高组内容)

\begin{array}{l} C_{mn}=A_{mp}\times B_{pn} \\ C_{ij}=\sum_{k=1}^p{a_{ik}b_{kj}} \\ \end{array}


一些常见的规律

\begin{array}{l} A\left( BC \right) =\left( AB \right) C \\ \left( A+B \right) C=AC+BC \\ C\left( A+B \right) =CA+CB \\ \lambda \left( AB \right) =\left( \lambda A \right) B=A\left( \lambda B \right) \\ \end{array}


Hadamard积

没见过这玩意

以下是运算定义

\left( A\ast B \right) _{ij}=a_{ij}b_{ij}


Kronecker积

神奇。

\left( \begin{matrix} 1& 2\\ 3& 4 \end{matrix} \right) \otimes \left( \begin{matrix} 5& 6\\ 7& 8 \end{matrix} \right) =\left( \begin{matrix} 1\cdot 5& 1\cdot 6& 2\cdot 5& 2\cdot 6\\ 1\cdot 7& 1\cdot 8& 2\cdot 7& 2\cdot 8\\ 3\cdot 5& 3\cdot 6& 4\cdot 5& 4\cdot 6\\ 3\cdot 7& 3\cdot 8& 4\cdot 7& 4\cdot 8 \end{matrix} \right)


一个n阶的行列式的定义是这样的

\det \left( A \right) =\sum_{\left( i_1i_2i_3\cdots i_n \right)}{\delta \left( i_1i_2i_3\cdots i_n \right) a_{1i_i}a_{2i_2}a_{3i_3}\cdots a_{ni_n}=|A|}

其中\delta \left( i_1i_2i_3\cdots i_n \right)

表示排列\left( i_1i_2i_3\cdots i_n \right)中当逆序对个数为t\left(-1\right)^{t}的值


好了,我们考虑一些性质

1.\det \left( A \right) =\det \left( A^T \right)

2.两行互换,行列式变号

3.一行乘上k , 行列式乘上k

4.两个行列式只有一行不同,他们的行列式和等于不同的行相加后的行列式

也记为:若行列式的某一列(行)的元素都是两数之和,则这个行列式是对应两个行列式的和

推论:将行列式的任意行乘以实数k,再相应地加到另一行上去,行列式的值不变

证明推论:拆成两个行列式的和,一个有两行成比例…

5.每行每列和均为0的矩阵行列式为0

·   ·   ·   ·   ·

\det \left( AA^T \right) =\left( \det \left( A \right) \right) ^2


Binet-Cauchy公式

A,B分别为n\times ss\times n矩阵

则有\det \left( AB \right)=

\begin{cases} \text{0\ ,\ }n>s\\ \det \left( A \right) \cdot \det \left( B \right) \ ,\ n=s\\ \sum{\det \left( A_s \right) \det \left( B_s \right)}\ ,n<s \end{cases}

这里面那个A_s通俗的,不严格的定义就是说从A里面s行选任意n行组成的新的矩阵,然后B_s也是类似,最后那个 \sum 就是枚举全部的这样的组合


高斯消元法求解行列式 (在此强烈安利 ATP学姐的高斯消元 )

高斯消元这玩意都会吧……

这儿有些细节

第一是交换两行的时候要对答案取负

第二是要用第j行去减第i行,所得答案作为新的第j行(也就是这里的减法正好相反)

最后求 \det \left( A \right) ,因为根据行列式的定义,recur下去每行只能选主对角的那个(否则一定有一个0)那么就是主对角的乘积。(记得取负之类的)


矩阵树定理

非常奇妙

我们来定义图G的度数矩阵D为一个n \times n的矩阵,当结点i \ne j时,d_{ij}=0 ;  当i=j时,d_{ij}等于i的度数

G的邻接矩阵A,当结点i,j之间有k条边相连的的时候,a_{i,j}=k

现在定义图G的Kirchhoff矩阵C=D-A,那么Matrix-Tree定理告诉我们,图G的生成树个数为C的任意一个n-1阶主子式的绝对值。

关于所谓的n-1阶主子式,也就是一个n阶矩阵除第n行和列之后形成的子矩阵的行列式。


Vfk有一篇关于轮状病毒的题解写的特别妙,在这里安利 1002: [FJOI2007]轮状病毒

然鹅他写的好长…… 😕 哇emoji好可爱


矩阵初等变换,先坑着

法法塔也先坑着

BZOJ1033 | ZJOI2008 杀蚂蚁 AntBuster

<论一次杀蚂蚁的经历>

<论如何优雅地用工程代码风格写出杀蚂蚁>

引子:

前天(也就是2018-3-18)的时候,刷B站(BZOJ)突然想起要A这题……

于是怂恿WHY一起做……

然鹅种种原因,拖到昨天(2018-3-19)下午才开始做

于是在CYYZ群里开起了校车……

然后

因为巨长的变量名不想手残于是换了VSCode……

然后疯狂盖楼……

 

注意这已经是今天的中午了……,而我交了一遍得了30

下午来了遂调试……发现了几个zz错误

等级没算对啦……sort忘记+1啦……蚂蚁位置忘记更新啦……以及更为严重的,没算点积判断附加攻击到底能不能打到。

晚上开始怀疑人生……此时代码量超过10k

下载了测试数据本地测……开Lemon却不小心点了O2

结果最后半个小时在静态查错,然而并没有什么错,后来的手动测试也证明了这一点

是Lemon开了O2之后,把程序跑错了

我果然花了几乎1h试图卡掉通过开了O2的Lemon……(滑稽)

管他的,进入正题

 

 

 

 


继续阅读“BZOJ1033 | ZJOI2008 杀蚂蚁 AntBuster”

提高调试效率-GNAQ的变量命名规则

GNAQ的变量命名规则分如下部分:

(函数名同样适用)

1.固定且有奇怪含义的变量(尽量不要理会)

at 邻接表存边时的表尾指针

ed (edge_struct) 邻接表结构体的名字

l (LCA_array) 含有LCA算法时用作记录LCA

pointer 巨长的变量名,但在写的时候很少访问它,这是邻接表里每个点的链尾的位置(更常用的貌似是next,推荐使用next,但要按照规则2缩写为nextx)

opt (operation_type) 用作操作次数变量或操作类型变量被读入

2.前(后)缀式与全缩式命名规则 和 常见单词缩写 和 缩写方法

前(后)缀式命名规则

以hsize,wpoint和tstamp为例

hsize=heap_size 堆大小

wpoint=white_point Prim算法的白点

tstamp=time_stamp 时间戳

前缀式命名规则的适用范围是某种结构或某种算法的信息变量

例如结构的大小、算法的步数、树的子节点个数。

前缀式命名规则基于英文的全拼(通常是两个或三个单词)缩写第一个单词而全写第二个单词,当且仅当第二个单词较短 , 且第一个单词( 表明变量的从属关系 )的缩写较好辨认 (比如叶子序号 线段树大小 距离

上面的例子均按照此规则缩写。

更多例子: **size **dis (distance太长而使用简写) **pos (position太长而使用简写)

而缩写第二个单词全写第一个单词,当且仅当第一个单词较短而第二个单词的缩写较好辨认。

比如edgenum nodenum nodev (v=value)  ctr* (ctr=counter 计数器)  cache** (表明是某某的缓存变量)

·

全缩式命名规则

若变量名都不符合前缀式命名规则,使用全缩式命名。

如ansf=answer_flow 既不符合前缀式缩写,(ans缩写为大多数人固定搭配,缩写为a则加深了理解难度),也当然不符合后缀式缩写(一个题外话:flow_ans是符合的,但是当时我不知道为啥脑子抽了就是写了个ans_flow)

那就全部缩写。缩写后意义较明显的单词只取首字母,而意义较不明显的单词取部分缩写。

·

缩写方法

  1. 原则是用最少的字母缩写,看到后在众多相似单词中能快速还原到正确的一个。
  2. 单词中发元音的字母尽量加入到缩写,而发辅音的较少添加
  3. 如果这样你还不知道怎么缩写,那就取前三个字母
  4. 缩写主要是给你看的,如果你扫了脑子一圈还没想到有别的常用意义可以如此缩写,那这个缩写就是好用的。你当然也可以使用其他易懂的缩写格式

比如:flow=fo/fl/fw

fo中o也发元音好像比较合适,但fo也可以是for的缩写或者former的缩写,容易产生混淆,尽量避免使用这种缩写(常用含义较多的)。

fl好像比较合适

fw可以是forward的缩写(且w在原词不发音,不应用这个单词缩写)

3.全拼式命名规则

如mapx,edgex,dis

如果变量名原本是一个单词,比较长而有缩写形式,使用缩写。没有就造一个。

如果较短(≤5个字符),使用全拼并在末尾+x

这样做的好处是防止卡关键字(试试prev!!你会被吓到的)

有时候使用缩写后也可以+x,也是为了防卡关键字

4.其他

尽量不要使用单个字母的变量,最佳范围2~5 (6)个字母之间

函数名可以使用下划线,变量名尽量不使用下划线,更好区分。

成员变量应该是一个名词或者偏正短语

函数应该是一个动词或者动宾短语

 

最重要的是有一套自己的常用变量缩写与变量名常用单词

当你写猪国杀 杀蚂蚁 立体图以及其他超过200行的程序,调试效率会非常高,因为在如此多的变量之下不会忘记每一个的含义,这才是最主要的。

这样当你打开屯了一个月的代码,你会用最快的时间进入状态,不需要纠结在变量名

当你请他人帮忙的时候,发代码他也能快速读懂

树链刨分(启发式剖分)

的梗来自于Yveh在SDWC2018上的课件

 

线段树背今晚的大锅

在这里再说一点轶事,据说集训队大爷WZD神犇出过一道带八个操作的LCT

Exciting.

还有我成功拿到了4k的长度,代码更加高清了。

//牺牲一些长度换易读性吧 反正手速快。[滑稽

没错这就是洛谷的板子题.

BZOJ4241 历史研究

Mo’s Algorithm with Roll-Back

回滚莫队算法

对于删除操作难维护答案但添加易维护的或者 添加难维护但是删除易维护的莫队题,可以使用回滚莫队算法。

历史研究是第一种

对于这种,我们选择

1.对于在同一个块内的询问,O\left( \sqrt{n} \right)暴力计算

2.对于不在同一块的询问,莫队排序后,形成了左端点在同一个块内的若干询问,

对于这些询问,我们只维护这个同块的下一个块的起点到这些询问的右端点的答案情况,因为右端点递增,左面固定在一处,所以只有添加。

然后回答每一个询问的时候暴力统计左端点到下一个块左端对答案的影响,统计完再改回去,

还有一个问题就是如果这个询问的左端点和上个的不在一个块,那直接重置答案统计变量和答案统计数组,暴力重新统计。

这样把复杂度压回了O\left( n\sqrt{n} \right)的级别

·

下一点是添加难维护但是删除易维护的莫队题

对于这类我们采取和上面相同的思想,但是我没见过任何这样的题,属于有解法无题的东西。

对于同块询问当然还是暴力

非同块询问你需要这么做,莫队思想排序完后倒序处理。

对于左端点同块的若干询问,维护这个同块的起点到目前询问右端点的答案情况。倒序处理只有删除操作。

每次回答时暴力删除到询问的左端点,然后改回去。

对于目前询问和上一个询问左端点不同块的情况,做法和第一类问题一样。

·

最后是这个题的代码,全开longlong结果跑了大概20s……大概是ll太慢了。你可以少开几个ll

Codeforces R470 (Based on VKcup R1)

和dkw组队 敲开心!

明天早自习请假了但是还要七点半起床 好痛苦QAQ

大概上午要睡过去

A. Protect Sheep

送分(ming)构造题(?)

把羊四周全围上狗就行

别像我一样没判羊挨着羊的情况然后连WA两发QAQ

B. Primal Sport

留坑

C. Producing Snow

对于每个雪堆二分哪一天最早化到负数

对温度做个前缀和,每次二分,假设cac天化到负数,当前是第i天

差分答案,化的=温度的区间,也就是i~cac-1差分一下,最后可以得知每天化了多少雪

加上化的小于温度的那一天,这个单独统计

最后加起来就ok

D. Perfect Security

一颗Trie树题,挺好玩的

带删除Trie树,每个结点记录有多少个数在这上面

递归删除并且贪心就行了

如果还不明白:

尽量让密钥和文本不匹配的那几位在低位上,这样才能字典序小,

也就是把数看成一个二进制字符串,带权匹配。

对于询问Trie树,如果能走同0或同1的当然好,那就贪心的走就是了,递归回来删除

E. Picking Strings

留坑

Codeforces R469

临时改时间了结果我失了智打了后半场……rk2700全程被碾压

A. Left-handers, Right-handers and Ambidexters

一道略微简单的题

答案讨论下左右撇子哪个多就行,不够就Ambidexters凑,Ambidexters还有剩余就一边分一个

B. Intercepted Message

贪心.两边取,相等就消掉,不相等继续取

C. Zebras

从前往后扫,vector维护序列们

每次维护两个集合,末尾是0的序列的集合,和末尾是1的,如果空了就新建序列

但是如果末尾是0的序列的集合空了而还有1的话不就无解了嘛

D. A Leapfrog in the Array

留坑

Codeforces Edu R39

居然Rated!

哇我明天早自习怕不是要被查水表了QAQ

不管了先补下题解

A. Partition

这题很zz你就把正数划到B负数划到C就行了

代码↓

B. Weird Subtraction Process

这题也很zz,fqk学长推了下式子然而我直接写了个二分

二分(a或b)*2*k可以证明复杂度非常优秀,大概在O(logn)还是怎么着的反正减一次还是减两次就完事了

具体证明等我再补 不一定能记得补

来补

复杂度是O(log2n)

C. String Transformation

贪心。忽略掉z即可

别忘记特判,具体看代码

D. Timetable

前三题都是热身题,这才是个正经题

dp。

先设dx[i][j]是第i天逃课j次后的最小度过时间

dp求这个东西,O(nk2) 先枚举每一天,这是显然的

然后枚举用了几次逃课,再meet in the middle,枚举从开头逃了几节然后就能算结尾逃了几节

预处理一下逃了x节之后在第几个小时就可以O(1)算答案了,三层枚举总的是O(nk2)

然后处理出dx就dp,设dp[i][j]是到第i天为止用了j次逃课得到的最短时间

然后枚举i,这也是显然的

枚举一下j,为了更新dp[i][j]你需要枚举当前第i天用了多少次逃课

这样我们就枚举l做为今天逃课数,然后更新dp[i][j]即可。

这题其实长得蛮像新魔法药水

后面三题没做出来 QAQ很惭愧

还是自己太弱了。

#洛谷 P1860 新魔法药水

神奇的DP

大概是用DP预处理要预处理的内容

然后用DP预处理

最后DP背包跑答案

 

卡了我很久有必要详细讲一下

题目描述

商店里有N种药水,每种药水都有一个售价和回收价。小S攒了V元钱,还会M种魔法,可以把一些药水合成另一种药水。他一天可以使用K次魔法,问他一天最多赚多少钱?

输入输出格式

输入格式:

第一行四个数N、M、V、K

接下来N行,每行两个数,表示药水的售价和回收价。

接下来M行,每行若干个数,第一个数表示魔法的成品,第二个数是原料的种数,接下来为各种原料的编号

输出格式:

一个数,表示小S的最大利润

·

N<=60 M<=240

V<=1000

k<=30

我们先考虑这是个背包

然后很自然的只需要求每个物品的min 购买价,然后二位费用xjb转移就可以得出答案

DP求这个部分.

因为有魔法,所以设计状态dx[i][j]表示物品i在当前用了j次魔法的情况下最小的购买价,这样才能当做背包来DP

dx怎么求呢?也不好求,所以这就是卡我的地方,我一开始还以为是DFS求

 

厚颜无耻的看题解……

你需要在枚举每个魔法w的时候都dp处理出 第w个魔法所需的前x个物品 用y次魔法 可以得到的最小购买价

设计状态ori[x][y]表示这样,每次枚举了一个魔法w都要求一次ori,注意y≤枚举的魔法次数

然后DP一波ori,这个很简单,写过几道提高水平的DP就会求

然后用ori[w需要的物品总数][枚举魔法次数-1]更新dx[w产成品][枚举的魔法次数]

·

这样我们就有了dx

xjb背包即可.XXXD