下一页 »Current position : 首页 >> 算法
2017″百度之星”程序设计大赛 – 初赛（B）
好气啊突然发现复赛的时候要军训1001.Chessf(i,j)表示最后一个棋放在(i,j)的方案[crayon-5994bb5ea3605918167680/]1002.Factory把集合分为元素个数大于\(m=\sqrt{n}\)，和小等于m的对于元素个数很多的集合，每个集合bfs一次，预处理出到其它集合的距离如果询问的两个集合的元素个数都比较少，建一下虚树dp。。。我不慎误算复杂度把这里写成了记忆化搜索+暴力，结果还过了[crayon-5994bb5ea361c120500280/]1005.度度熊的交易计划预...
2017ACM萧山训练第5场(2016 Pacific Northwest – Division 1)
E.Enclosure做出大小两个凸包，即所有点的凸包和前k个点的凸包按动态凸包的思路，新加入的点会把小凸包上连续的一些点弹出，这些点是一个连续的区间相当于切掉凸包的一个角，加入一个三角形若在大凸包上顺时针枚举一个加入的点，这个区间左右端点也是顺时针转的，类似旋转卡壳切掉部分的面积顺便维护由于坐标范围较大，用double精度会炸[crayon-5994bb5ea52c8408222149/]G.MaximumIslandsL的上下左右直接贪心为W然后剩下的就...
2017ACM萧山训练第4场(CTUO 2015)
D.FalconDive计算左下角的像素移动的距离，直接模拟[crayon-5994bb5ea5dd0239198687/]F.TheFoxandtheOwl贪心如果n是负数，找n最低的非9的位加1考虑在n的某一个高位减1，在之后的低位中加2如果存在多个满足的高位，取最低的一个若不存在，构造一个绝对值最小的负数[crayon-5994bb5ea5de3271631109/]J.JumpingYoshi两个点连边的条件是\(d_y-d_x=a_y+a_x,y>x\)由于点对不超过10^6，扫一遍用map维护，把所有的边用并查集连...
2017ACM萧山训练第3场(World Final 2013)
A.Self-Assembly如果一个正方形有两条边a,b则a->op(b)b->op(a)，判图中是否有环，有环则说明我们能把一些正方形绕成环然后翻折旋转变得无限大[crayon-5994bb5ea69f5778166771/]C.SurelyYouCongest只有最短路相同的会互相影响按最短路分组后跑c次最大流[crayon-5994bb5ea6a06249517784/]D.Factors爆搜前16个素数[crayon-5994bb5ea6a19402872898/]F.LowPower二分答案贪心检验[crayon-5994bb5ea6a23022018144/]H:М...
2017ACM萧山训练第2场(NWERC 2008)
A:EquilibriumMobile最终天平平衡的状态下，每个结点x满足w[x]*(2^dep[x])相等统计所有的w[x]*(2^dep[x])，答案是叶子数减去出现次数最多的个数[crayon-5994bb5ea7c4a676147878/]B:ProvingEquivalences答案是max{入度为0的连通块个数，出度为0的连通块个数}特判连通块为1的情况每个连通块，出度0的点，向其它入度为0的连边，使得形成一个环[crayon-5994bb5ea7c61671041381/]C:Catvs.Dog找出所有相互不兼容的人，将他们连边...
2017ACM萧山训练第1场(NEERC 2016)
队友做的题目我并不是非常懂。。。A.[Neerc2016]Abbreviation字符串模拟E.[Neerc2016]ExpecttoWait如果对于等待的人数维护一个关于时间的前缀和那么我们就得到了一个很长的前缀和序列，我们注意到初始车辆为x，实际上就是询问这个序列大于x的前缀和的和那么对于时间离散化以后，就是询问大于x的段的加权和对所有的段从小到大排序，依次处理[crayon-5994bb5ea8dd4385444115/]G.[Neerc2016]GameonGraph第二个人先手的状态...
《数据结构与算法》编程练习
数据结构与算法（上）百练2746:约瑟夫问题 vector模拟操作[crayon-5994bb5eaa0d3574956024/]多项式加法[crayon-5994bb5eaa0e8356282052/]百练2980:大整数乘法[crayon-5994bb5eaa0f1676867973/]百练2702:密码翻译[crayon-5994bb5eaa0f9707037009/]百练4077:出栈序列统计卡特兰数[crayon-5994bb5eaa101203952222/]POJ1686.等价表达式(LazyMathInstructor)给每个字母一个随机值，对两个式子做表达式计算用一个数字栈+操作栈来实...
程序设计实习实验班2017推荐习题
区间众数问题这题写莫队是最容易的，可以对于每种出现次数的数字维护一个堆，用于删除时维护答案[crayon-5994bb5eacac0560631438/]【BZOJ3659】WhichDreamedIt 神奇钥匙求以1为起点的欧拉回路的个数乘1的度数BESTtheorem[crayon-5994bb5eacada486662290/]【bzoj4031】[HEOI2015]小Z的房间矩阵树定理推荐阅读算法合集之《欧几里得算法的应用》[crayon-5994bb5eacaea907017420/]POJ2373DividingthePath用dp(i)...
程序设计实习实验班2017作业（算法 作业19, 20, 21）
一些以前做过的就不再贴了AFunnyStoneGame发现每一堆的每个石子之间都是相互独立的[crayon-5994bb5eadcac536835995/]nnimn阶nim和，在二进制下，每一位求和后对(n+1)取模[crayon-5994bb5eadcbe802448302/]一个水水的序列在建操作树的过程中就能顺便维护信息每次新加入节点的时候维护一下这个点的倍增数组，询问的时候直接向上倍增[crayon-5994bb5eadcc8026836334/]【poj1523】SPF求割点，并且求删去割点后的连通分量个数[cr...
关于OI 的一次问答记录
A就是我啦。。。OwO感觉自己萌萌哒谈话记录（括号内为整理者添加）高一开始参加信息竞赛，全国信息学竞赛银牌，降至pku本一线Q：当时为什么会接触到竞赛？A：刚上高中的时候，学校宣传说：“你们作为实验班的同学，都要学个竞赛。”然后就去计算机竞赛报了名。当时有一个竞赛宣传讲座，讲座完了之后就填了一个报名表，其实我填的是数学和计算机。Q：选计算机竞赛是因为感兴趣吗？A：因为我小的时候学过（PC）Logo，所以后...
程序设计实习实验班2017作业（算法 作业1,5）
【Bailian4115】鸣人和佐助bfs的时候多一维记录查克拉[crayon-5994bb5eba6b3553126516/]【poj1190】生日蛋糕/泰国佛塔从下往上一层一层搜索，每一层枚举半径和高度（注意范围）根据每一层半径和高度严格递减，进行一些剪枝：1、剩下的若干层都放最小的圆柱，体积也不够2、剩下的若干层都放最小的圆柱，得出的表面积比当前最优解劣3、剩下的体积所需的最小表面积加上当前表面积比当前最优解劣[crayon-5994bb5eba6ce221711120/]【B...
再见，OI
信息学全国赛（NOI2015），疏散日，杭州学军中学，暴雨。我校买的下午的车票，省队几个一起通宵麻将的同学天没亮就坐车去了，只留我在空荡荡的宿舍楼里，开始写退役纪念。回忆时断时续，怎么写都像记流水账，无奈，我笔都不大会握了还写文呢，然而人有时就是会矫情。想象中的回忆录大抵是这样，有点文艺范。能自豪地拿给人看，给没竞赛的朋友看，也留给未来的自己。别人看完说：真他妈热血，感觉灌了一大锅该死的鸡汤。然而我的...
魔兽世界之一：备战 / 魔兽世界之二：装备
魔兽世界之一：备战单看这题很简单，考虑到可扩展性，把司令部，武士，游戏进程设计成三个类[crayon-5994bb5ece480087971633/]魔兽世界之二：装备增加了一个武器类，但我指针用的不是很顺手，希望在司令部中能有个武士的vector和map，所以没有把各个武士设计成子类[crayon-5994bb5ece497260000083/] ...
近期评论