BUAA_Alchemist的博客

原创 训练复盘记录

 前言：我，zwr，qzz三人组成Hard_to_Name临时队从南昌邀请赛回来以后，由于我们Alchemist队学姐无法参加集训，正好前阵子qzz学长也是和自己配合过一段时间，又有意愿再打一年，于是正好加入我们队。于是现在这个队是我，qzz，lpy三人。计划是每周训练一次，假期的话，除了集训时间外每周集训两次。团队配合是十分重要的，每场训练都要依照惯例写复盘，反思，补题。希望我们最后能克服万难，...

原创 曾经遇到的小坑坑，以后要谨记（持续更新）

multiset的删除，如果erase掉值，那么所有的相同值元素都会被删除，只删除一个的话需要删除的是这个位置的迭代器。min_element/max_element的起点和终点不能相同！相同意味着空集，虽然运行时不会出错，但系统不能保证答案就是某个特定的值（比如0），往往这不是你想要的。...

原创 一些我觉得很有价值，但是没有自己见解的题目的列表（持续更新）

https://codeforces.com/contest/1091/problem/F 贪心算法，有思维难度https://buaacoding.cn/problem/1086/index 动态规划https://buaacoding.cn/problem/1111/index 动态规划，很独特的方式https://codeforces.com/problemset/problem/1...

原创 程序设计是一场修行------博客简介

 这个博客主要是为了更新算法内容，一段时间后会有技术性和实战性的开发总结。它属于北航的一支尚且很弱小的ICPC队伍——Alchemist，队员三人，maxdumbledore（我），Hardict，Katherine_LOVER。暂时只有我在更新博客，以下就以我的视角，来讲述一下我眼中的竞赛以及未来的打算。 我参与信息学竞赛（OI）或者ICPC不是一朝一夕的事情了。一直以来，我都觉得自己不是一个...

原创 计蒜客2020蓝桥杯大学A组模拟赛题解

计蒜客2020蓝桥杯大学A组模拟赛题解蓝桥杯的话，去年拿了C++组的国二。今年报名了新成立的Python组，不知道能不能摸到国一的鱼模拟赛链接如下：https://www.jisuanke.com/contest/6510?view=challenges打蓝桥的策略依旧很简单：前面60~70min 搞填空，后面刷大题，注意先看完所有题，不要只按顺序A. 计算周长一个很显然的想法是a和...

原创 如何用分布式Pollard-Rho法对椭圆曲线离散对数问题（ECDLP）进行攻击（下）

 在上一篇中，我主要介绍了对赛题的初步攻击——单机Pollard-Rho。接下来介绍分布式算法。 让多个机子，从点集合G中不同的起点进行出发，用QD法记录的桩点会被记录到一个公共表里，然后每个机子共享数据，也就是说每个机子可以知道一个桩点，是否曾经被自己或者其它机子产生出来过。 这里面有一些隐含的信息。首先，并不是有n台机子，产生答案的时间就会缩短到原来的1/n，事实上，随机产生的Rho图数量...

原创 如何用分布式Pollard-Rho法对椭圆曲线离散对数问题（ECDLP）进行攻击（上）

 上个学期，竞赛因为种种原因没有继续进行而搁浅。这里仅仅分享一下临时成果。 椭圆曲线离散对数问题赛题介绍如下 任何一个熟悉密码学的人基本上都会了解椭圆曲线离散对数问题。它比较普通素数域离散对数问题更具有难解性。因此相当多的公钥密码体制都构建在这个问题的基础上，如EC-Elgamal系统，以及数字签名、密钥交换协议等...

原创 谈一谈Windows子系统Linux(WSL)相关

 身边很多人喜欢在linux下做代码开发工作，但是想做其他事情比如玩游戏或者处理视频之类的，可能还是得回到Win下。我没有在Linux下写代码的必要性，所以一直没想装双系统，不过偶尔必要时需要用到Linux环境。我之前一直用的是Vmware+CentOS。这里介绍另一种比虚拟机更棒的解决方式——WSL。 微软在两年前便已经悄悄上线了Linux子系统功能。它允许在一个命令行窗口中使用Linux命令...

原创 【动态规划】lydsy4498 魔法的碰撞 lydsy4664 Count 特殊的序列dp方法

 这是我没有接触过的dp类型。因此记录一下。 先看lydsy4498（这题现在OJ上已经消失了）。 首先容易想到，对于一个布阵方式，我们可以把多余的格子抽掉，还原出一个魔法师紧凑的局面。那么每一个魔法师紧凑的局面，如果长度为lll，往其中填充L−lL-lL−l个格子，通过插板原理，我们知道它对应着Cn+L−lnC_{n+L-l}^nCn+L−ln​个布阵，于是问题转化为求长度为lll的紧凑局面...

原创 北航ICPC集训队第二次春训（2019.4.28）

https://codeforces.com/problemset/problem/626/Cn+m个人用积木搭堆（每个人搭一堆），n个人只能用高度为2的积木， m个人只能用高度为3的积木。两种积木均有无限多个。这些人都不希望自己搭出的堆的高度与其他任何人的相同。请找出在所有人搭出的积木高度都不同的情况下，这些人中搭出的最高的堆的高度最小值。Input第一行输入包含两个用空格隔开的整数n ...

原创 北航ICPC集训队第一次春训（2019.4.27）

#include<cstdio>#define mo 12345678910using namespace std;using LL=long long;int top,n;LL val[200005],ans;char S[200005];int main(){ scanf("%d",&n); for(int i=1,d;i<=n;i++) {...

原创 【树链剖分】【模板】洛谷3384

题目描述如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点...

原创 【动态规划】codeforces1149B Three Religions

B. Three Religionstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputDuring the archaeological research in the Middle East you found the traces ...

原创 【贪心】【动态规划】【数学思维】codeforces1152D Neko and Aki's Prank

D. Neko and Aki’s Pranktime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputNeko is playing with his toys on the backyard of Aki’s house. Aki decid...

原创 【动态规划】codeforces1155D Beautiful Array

D. Beautiful Arraytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a consisting of n integers. Beauty of array is the m...

原创 作业图片链接引用区域

原创 【数学思维】【动态规划】codeforces1153F Serval and Bonus Problem

Getting closer and closer to a mathematician, Serval becomes a university student on math major in Japari University. On the Calculus class, his teacher taught him how to calculate the expected length...

原创 【贪心】【二分答案】codeforces1119E Pavel and Triangles

Pavel has several sticks with lengths equal to powers of two.He has a0 sticks of length 20=1, a1 sticks of length 212^121 2, …, an−1 sticks of length 2n−12^{n−1}2n−1.Pavel wants to make the maximum ...

原创 【递推】codeforces1140E Palindrome-less Arrays

1140E Palindrome-less ArraysLet’s denote that some array b is bad if it contains a subarray bl,bl+1,…,br of odd length more than 1 (l<r and r−l+1 is odd) such that ∀i∈{0,1,…,r−l} bl+i=br−i.If an ...

原创 【并查集】用水填坑

题目链接：https://ac.nowcoder.com/acm/contest/403/A 先想想一维的降雨积水问题。很容易发现可以考虑每个地两侧的高度最大值的最小值，就是这个地方的积水量，只需要把这些积水量累和即可。但是二维的就没法这么做了。继续想想一维的问题，发现可以有一种并查集的解法，进而推广到二维。 我们把所有的高度排序，从小到大添加入原图，用并查集维护连通块，如果新加入的值a[i...

原创 【动态规划】北航程序设计竞赛决赛B题

 决赛那天感觉确实没发挥好。本来有机会逃离三题大队的。结果中途很多人搞了几何构造题，忍不住跟风。事实证明以我的想象力果然搞不出来。还不如专心搞搞B这题。 B的题意很简单，给一个长度不超过5000的字符串，字符集大小不超过5000，求字典序第k小的子串（子串可以不连续），k规模不超过子串总数以及1E18。 先考虑每个字符都不同的情况，很容易想到一个一个把答案的字符定下来。我们每一次求出下一步接字...

原创 第十四届北航程序设计竞赛预赛题解（非官方）

 最近沙河好多人生病了，我也不能幸免，今天终于舒服了。补一补上周的老坑吧。 接下来尽量每天刷题。另外要加油学习汇编语言，优化我们的密码学竞赛程序。官方题解参见：http://clatisus.com/BCPC2018_qualification_roundA 两等分的Alicehttps://buaacoding.cn/problem/1914/index 非常容易设计出粗暴的dp。考虑...

原创 【费用流】洛谷1251 餐巾计划问题

 今年参加BCPC暨ACM选拔的同学非常多。看了下预赛榜单，my和ljy率领一大批18级dalao，tky等buaacoding刷题狂魔也都参加了，更可怕的是还有一堆CF黄名橙名故意只写了一点点题隐藏实力。这对于你航ACM事业当然是好事，但对于我们这些菜鸡就很黑暗了。希望明天能加油，Alchemist加油~ 不废话了，来看这题。如果不告诉我是网络流，我估计还真的很难想到它的算法。但告诉我是...

原创 【数学思维】【枚举】codeforces1138B Circus

B. Circustime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputPolycarp is a head of a circus troupe. There are n — an even number — artists in the ...

原创 北邮新生赛题目回忆

 昨天下午在沙邮参加了北邮的新生赛，作为隔壁大二的老年人也跑去玩玩，侥幸拿了rank1，拿了个小米手环（感谢这次没有真的大佬参赛） 有意思的题还是不少的。一道题本身没有难点但是答案的组数要求输出1st，2nd之类的，好多人没考虑模100余11，12，13的分类，卡了很久，还好之前被坑过一遍，不会再入坑了。 有一题是给了一串抹去间隔的某进制数，要求这个数转换成十进制下的最小值，例如11311在1...

原创 【线段树】【区间修改】codeforces1136E Nastya Hasn't Written a Legend

E. Nastya Hasn’t Written a Legendtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputIn this task, Nastya asked us to write a formal statement.A...

原创 【模板】【FWT】简单数学题

 最近因为忙于搞密码学竞赛，做题懈怠了。需要努力。 刚刚学习了FWT，其实不陌生了，去年暑期ACM集训的时候就碰到过两次，但当时补题习惯差一直没有学习。如果了解FFT，那么FWT要解决的问题就比较容易理解了。实际上就是把FFT的多项式乘法求系数修改成多项式位运算求系数。思路和结构基本相似，也有不同之处，例如没有用到原根以及蝴蝶变换。数学证明不作罗列了，参见：https://www.cnblogs...

原创 【数学思维】【树状数组】lydsy1106 [POI2007]立方体大作战tet

1106: [POI2007]立方体大作战tetTime Limit: 10 Sec Memory Limit: 162 MBSubmit: 1046 Solved: 762[Submit][Status][Discuss]Description　　一个叫做立方体大作战的游戏风靡整个Byteotia。这个游戏的规则是相当复杂的，所以我们只介绍他的简单规则：给定玩家一个有2n个元素的...

原创 【线段树】【扫描线】小睿睿的方案

 很精彩的一道题！题意还是很清晰的。自己想了半天没有思路，最后参考了题解。 首先问题可以变成所有方案数（n∗(n−1)2\frac{n*(n-1)}{2}2n∗(n−1)​）减去非法方案数。 考虑每对情侣对方案的负贡献： 当不考虑重复时， 当两个结点非祖先-后代关系时，贡献也就是两个子树的大小的乘积。 当两个结点为祖先-后代关系时，贡献为后代的子树与（所有点，除了祖先指向后代的儿子的子...

原创 【最小生成树】【LCA】【模板】lydsy1977 [BeiJing2010组队]次小生成树 Tree

1977: [BeiJing2010组队]次小生成树 TreeTime Limit: 10 Sec Memory Limit: 512 MBSubmit: 4776 Solved: 1520[Submit][Status][Discuss]Description小 C 最近学了很多最小生成树的算法，Prim 算法、Kurskal 算法、消圈算法等等。 正当小 C 洋洋得意之时，小 P...

原创 【线段树】【LCA的RMQ求法】【树上路径求交】车站

链接：https://ac.nowcoder.com/acm/contest/368/E来源：牛客网 很好的一道题，一开始没有想到从路径来建立线段树，总想着从原树上搞，还觉得和树链剖分有点相似，后来看了题解才知道自己完全想错了。车站线段树+倍增+LCA。首先车站一定在所有铁路的经过的点的交集上，所以可以用线段树求出区间路径的交集，同时维护离路径交的两个端点最远的点。找到出了最远的两个点...

原创 【概率与期望】流星雨

链接：https://ac.nowcoder.com/acm/contest/368/C来源：牛客网 题目比较简单，但因为比较典型所以记录一下。 另外，这种题一定要分清事件的概率，否则容易全盘皆错。 这题中，某一天是否发生流星雨的概率，不仅和当天有关，还和之前的情况有关。假设这个事件发生的概率为dp[i]dp[i]dp[i]，则dp[i]=dp[i−1]∗(pi+P)+(1−dp[i−...

原创 【数学思维】codeforces1117E Decypher the String

E. Decypher the Stringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis is an interactive problem. Remember to flush your output while com...

原创 【二分答案】【数学思维】codeforces1117C Magic Ship

C. Magic Shiptime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou a captain of a ship. Initially you are standing in a point (x1,y1) (obviousl...

原创 【并查集】lydsy1104 [POI2007]洪水pow

Description　　AKD市处在一个四面环山的谷地里。最近一场大暴雨引发了洪水，AKD市全被水淹没了。Blue Mary，AKD市的市长，召集了他的所有顾问（包括你）参加一个紧急会议。经过细致的商议之后，会议决定，调集若干巨型抽水机，将它们放在某些被水淹的区域，而后抽干洪水。你手头有一张AKD市的地图。这张地图是边长为mn的矩形，被划分为mn个11的小正方形。对于每个小正方形，地图上...

原创 【动态规划】【四边形不等式】合并石子

 传送门：http://lx.lanqiao.cn/detail.page?submitid=3262677问题描述　　在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。输入格式　　输入第一行包含一个整数n，表示石子的堆数。　　接下来一行，包含n个整数，按顺序给出每堆石子的大小 ...

原创 【计算几何】【圆的交点】Navigation

 传送门：http://lx.lanqiao.cn/problem.page?gpid=T472问题描述　　全球定位系统（GPS）是一个导航系统，根据一些在距地表大约20,000千米的轨道运行的卫星。每个卫星在一个已知的轨道上运行，发射编码着当前时间的无线电信号。如果一个装有全球定位系统的交通工具有一个非常精确的时钟，它就可以比较它自己的当地时间和从卫星上接受到的编码成信号的时间。因为无线电信...

原创 【计算几何】【扫描法】The Sky is the Limit

 传送门: http://lx.lanqiao.cn/problem.page?gpid=T483问题描述　　Banff城雇用了一家广告公司来提升这座城市对潜在的游客的吸引力。其中一个计划中的口号声称延伸在这座城市周围的山脉组成了加拿大最美丽的天际线。但是加拿大消费者保护协会认为“最美丽的天际线”是一种主观的，无法证实的声称，而且可能因此让人误解。　　然后那个广告公司就想出了一个口号“Ban...

原创 【交互题】【概率】codeforces1114E Arithmetic Progression

This is an interactive problem!An arithmetic progression or arithmetic sequence is a sequence of integers such that the subtraction of element with its previous element (xi−xi−1, where i≥2) is consta...

原创 【动态规划】Stacking Plates

 传送门:http://lx.lanqiao.cn/problem.page?gpid=T507问题描述　　盘子装运公司是一家网络零售商，顾名思义，是一家只销售盘子的公司。该公司销售的盘子由不计其数的生产厂商提供，品种是全宇宙最多的，为此公司的员工倍感自豪。　　在最近的一次成本分析中，公司员工发现，他们花费了大量金钱在盘子的装箱环节。一部分原因是盘子在被运输工具运走前，需要被堆成一堆。很显然...