Rewinner

未归档

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 图论(24) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16)

/ 注册

全部文章 / 未归档（共69篇）

POJ - 1177 矩形周长并

参考博客：http://www.cnblogs.com/scau20110726/archive/2013/04/13/3018687.html 方法：把矩形分成横线和竖线去处理，可知是完全相同的操作，我们来讲下怎么算出横线部分，竖线部分就是照搬即可。将横线保存在一个表中，按横线所处的竖直位...

2019-01-21

0 593

HDU 4419 扫描线+线段树

自己的思路：题目给了三种颜色 R G B，能够组成7种颜色，我想到用状态压缩（R =1,G=2,B=4），因为他的颜色是由他的种类数决定的，所以我用异或来表示他的覆盖情况（这是我***的地方，我没理解基础的 +1，-1 为什么），后面debug发现我的覆盖情况出现的负值的情况，然后就没有思路了。 ...

2019-01-21

0 374

数位DP HDU 4507 求满足条件的平方和

这跟我的上一篇数位DP博客，有点相似，仔细想一下就能明白：博客：https://blog.csdn.net/qq_42211531/article/details/86307936 ///#include<bits/stdc++.h> ///#include<unorder...

2019-01-21

0 465

线段树+扫描线

看了一天才明白了参考博客：https://blog.csdn.net/otowa/article/details/50695401 看完参考博客在看看我对这个的理解。我的理解：扫描线是一种想法，方便我们去理解，线段的作用：维护我们所需要的值。比我们要求上图的面积，我们可以将图...

2019-01-20

0 603

POJ 1185 炮兵阵地状压DP

解题方法：第一个巧妙之处：第一步先预处理炮车能够放置的位置（其实只有几十种），如果暴力枚举的话，时间空间都不够的。第二个巧妙之处：将地图的每一行状压成一个数，山地位置为1，平原为0。为什么这么状压？我们预处理的炮车放置情况，能放炮车的地方为1，不能放置炮车的地方为0，假如炮车放置情况...

2019-01-09

0 524

HDU 2157 矩阵快速幂

在打牛客的时候碰到一道类似的题，我以为是图论题，结果看了题解，居然是一道矩阵快速幂的经典题。哪个地方会直接用到矩阵快速幂，对，就是图论中求对应两个点长度为n的路径数，这是矩阵乘法在图论中的经典应用，其实就是用到了矩阵乘法的特殊性，因为矩阵乘法有三重循环，最里面的一层循环就是在枚举一个点k，i -...

2019-01-04

0 522

HDU 4334 尺取+思维

题意：在5个数组中，每个数组中取一个数，5个数之和是否为0；第一次我是用map标记前3个数组的和，然后暴力跑后两个数组的循环，果然T了。。网上又两种做法： ① 处理前三个数组的和，后两个数组的和，排序+枚举+二分。我自己没试过不知道能过不 t *（n^3+n^2+log（n^3）+...

2018-12-19

0 491

匈牙利算法，KM算法

匈牙利算法博客原址：https://blog.csdn.net/dark_scope/article/details/8880547 KM算法博客地址：http://www.cnblogs.com/wenruo/p/5264235.html 匈牙利模板： bool fin...

2018-11-29

0 585

“东信杯”广西大学第一届程序设计竞赛 J 【RMQ】

题目链接：传送门题意：题意很简单，两种操作，一：区间每一个数或上x，二：求区间每个数或上x的总和。（或 ' | '）做法：最开始我想的就是单点更新，果断队友T了，然后队友用位来储存数字，然后延迟标记区间更新就过了，虽然找了很久bug。 ///#include<b...

2018-11-28

0 560

51nod 1228 序列求和【伯努利数与自然数幂和】

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1228 这道题需要用到伯努利数，我也是去现学的，因为是数学，有些东西也不是很懂。大佬博客：https://blog.csdn.net/ACdreamer...

2018-11-26

0 450