算法 – 🔭望远镜开启之时

十月（扫描线，分块，点分治）

最近没什么时间更新了，今后更新频率会降低，但同时一次的内容也更多。
这个月的kickstart好可惜啊。。。~~痛失35分~~。。其实就是太菜了。。。
开始在AcWing上打卡，逐步完成《算法竞赛进阶指南》的内容。

1. 重温扫描线写法

窗内的星星

#include<bits/stdc[......]Read More

KickStart 2018 Round D

第一题滑动窗口+multiset的运用
第二题将两个不等式条件转化为两个点的位置关系（一个点在另一个点的右上方），这个转化像整体换元，感觉很巧妙…然后贪心。
第三题四维dp+前缀和处理，参考了【Kickstart】2018 Round D – Funniest Word Search
以下是第三[……]

Transformation HDU – 4578 （延迟标记）

对延迟标记要有深入的理解。。。多个标记同时存在时要考虑顺序

参考：http://www.cfzhao.com/2019/04/03/hdu-4578-transformation/

#include <bits/stdc++.h>

typedef long long ll;

usin[......]Read More

Kick Start 2018 Round B B题

Sherlock and the Bit Strings

构造一个长度为N的只有‘0’和‘1’的串s，满足K个限制（s[A,B]中含有C个1），且这个串在所有满足限制的合法串当中为字典序第P大.

状压dp,f[i][j]：假设前i个字符已固定，且这前i个中最后16个字符为j时的合法方案数（注意j前[……]

SGU385 Highlander

题目来源：SGU 385
图片来自国家集训队论文《浅析竞赛中一类数学期望问题的解决方法》

其中min(j,i-j+1) 更改为min（j-1，i-j）貌似更合适。

#include<bits/stdc++.h>

using namespace std;

double d[105];[......]Read More

[NOI2005]聪聪与可可

聪聪与可可

在一个单位时间内，聪聪根据可可的位置，会先走出最短路中的下一步，然后被抓者可等概率随意走一步，也可原地不动。
在距离一步或者两步的时候，只要一个单位时间就可以抓到了，这是递归基。然后记忆化搜索解决之。

#include <bits/stdc++.h>
using namesp[......]Read More

扫描线(POJ 1151)

在平面坐标系里给出一些矩形,求面积并.
Atlantis

#include<cstdio>
#include<map>
#include<algorithm>
#include<iostream>
using namespace std;

const[......]Read More

线段树延迟标记 (POJ3468)

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int SIZE = 100010;

struct SegmentTree{
    int l[......]Read More

最大连续子段和

RT,线段树单点修改,区间查询.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include[......]Read More

HDU – 6214 Smallest Minimum Cut

HDU 6214

求最小割的最小割边数量.
每边以w*(m+1)+1为边权加入图中,最小割为maxflow/(m+1),最小割的边数为maxflow%(m+1).
精髓在于将已选边数加到了流量信息里.

#include <bits/stdc++.h>

using namespace s[......]Read More