1.位运算
没啥特别重要的东西，只需要知道有符号的整数是用补码来存的,对补码的每一位取反，则数值上 变成-1.
好题：求 (a^b) 对p取模的值，其中(1≤a,b,p≤10^{18})
分析：将 (a^b) 看作b个a相加. b太大怎么办？类似快速幂优化即可.
2.二分and三分
主要用于求特定的答案，即这个答案是能够求出来的，而不是问是否存在，有多少个之类的…… 三分法在使用时需要注意：如果在函数中存在一段值相等的部分，三分法就不再适用,事实上出现这种情况也有解决的方法，如果最后确定了左端点l和右端点r,从l到r枚举一遍所有点判断一下答案即可.
3.平均数问题
如果解题中出现了n个数的平均数T,将这n个数都减去T,以后与0比较即可. 比如要判断一个区间内的数的平均数是否大于x,那么将这n个数都减去x,然后看操作之后的数的和是否大于0即可.
4.中位数问题
如何求中位数？对顶堆！
经典模型：货仓选址问题.
上面两个都是书上涉及到的比较简单的处理方法，有些复杂的问题可能会用到减去偏移量，与中位数比较等方法.
减去偏移量这个方法会在以后提到，与中位数比较则是常用的判定中位数是否存在的一种方法. 二分出中位数x，将比二分出的数大的数标为1，小的数标为-1，求序列的最大连续子段和，若大于0，则x可以是原序列的中位数.接着(l = mid + 1),继续二分.
5.逆序对
归并排序和树状数组都可以求. 一个比较强大的应用是n*m数码的有解性判定.
(N×N)的棋盘，N为奇数时，与八数码问题相同。逆序奇偶同性可互达.
(N)为偶数时，空格每上下移动一次，奇偶性改变。称空格位置所在的行到目标空格所在的行步数为空格的距离（不计左右距离），若两个状态的可相互到达，则有两个状态的逆序奇偶性相同且空格距离为偶数，或者，逆序奇偶性不同且空格距离为奇数数。否则不能。
6.倍增
用来加速枚举，替代二分.
有些题目可以二分，但是在一些极端数据下，二分不如枚举快，这时就可以用倍增来加速枚举，替代二分.举个例子：
给定一个整数T,求出最大的k，满足(Σa_i≤T(1≤i≤k)), 如果T特别小，序列特别长，那么二分就要一步一步缩回来，而倍增则可以从起点一下子找到答案.
7.贪心
收益与代价问题，问题规模一般很大，时间不足以支持dp.
基本策略：在收益最大的前提下让代价尽量最小. 一般涉及到排序，采取决策包容性大的方式排序, 第i次选择时尽量选当前能选到，下一次不一定能选到的.
8.习题
https://ac.nowcoder.com/acm/contest/1004
poj2965 The Pilots Brothers’ refrigerator
枚举 / 位运算 / 搜索
https://www.cnblogs.com/RioTian/p/13461765.html
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main() {
char s[5][5];
int mark[5][5];
int x[20], y[20];
memset(mark, 0, sizeof(mark));
for (int i = 0; i < 4; i++) cin >> s[i];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (s[i][j] == '+') {
mark[i][j] = !mark[i][j];//下面的操作中，i，j这个位置翻转了操作了两次，等于没操作，所以上边这里再操作一次，这样让这个位置 也被操作了
for (int k = 0; k < 4; k++) {
mark[i][k] = !mark[i][k];
mark[k][j] = !mark[k][j];
}
}
}
}
int ans = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (mark[i][j]) {
x[ans] = i + 1;
y[ans] = j + 1;
ans++;
}
}
}
printf("%d
", ans);
for (int i = 0; i < ans; i++) printf("%d %d
", x[i], y[i]);
return 0;
}
poj2083 Fractal
递归 / 分形
#include<iostream>
using namespace std;
const int N=749;
int n;
char a[N][N];
void solve(int n,int x,int y){
if(n==1)a[x][y]='X';
else
if(n>1){
int num=1;
for(int i=2;i<n;i++)
num*=3;
solve(n-1,x,y);
solve(n-1,x,y+num*2);
solve(n-1,x+num,y+num);
solve(n-1,x+num*2,y);
solve(n-1,x+num*2,y+num*2);
}
}
int main(){
while(cin>>n&&n!=-1){
int num=1;
for(int i=1;i<n;i++)
num*=3;
for(int i=0;i<num;i++)
{
for(int j=0;j<num;j++)
a[i][j]=' ';
a[i][num]=' ';
}
solve(n,0,0);
for(int i=0;i<num;i++)
printf("%s
",a[i]);
printf("-
");
}
}
poj3714 Raid
记录一下是哪种类型的点，然后求不同类型的点的最近点对
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n;
struct node {
int x, y;
bool z;
bool operator < (const node w) const {
return x < w.x;
}
}e[N <<1];
node a[N], b[N];
double s(node x, node y) {
if (x.z == y.z) return inf;
return sqrt((ld)(x.x - y.x) * (x.x - y.x) + (ld)(x.y - y.y) * (x.y - y.y));
}
double s(int l, int r) {
if (l == r) return inf;
if (l + 1 == r) return s(e[l], e[r]);
int mid = (l + r) >> 1;
return min(s(l, mid), s(mid, r));
}
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0);
int t; cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; ++i)cin >> e[i].x >> e[i].y, e[i].z = 0;
for (int i = 1; i <= n; ++i)cin >> e[i + n].x >> e[i + n].y, e[i + n].z = 1;
sort(e + 1, e + 2 * n + 1);
printf("%.3f
", s(1, 2 * n));
}
}
poj1723 Soldiers
排序 / 中位数 / 货仓选址问题拓展
问题简述：
有N个士兵，每个士兵开始站的坐标是（x，y），现在使得将N个士兵站在同一个水平线（即所有士兵的y坐标相同）并且x坐标相邻，每个士兵每次可以移动一个位置（分别在x和y方向移动）。求出最少的移动步数。
问题分析：
这是一个最优化问题，可以使用中位数计算来解决。
x方向和y方向可以分别来考虑。
y方向就是一个简单的中位数计算。
x方向是坐标相邻，可以先将x位置排序，然后往中间靠，也是一个中位数计算问题。x方向分别移动到a+i的位置，那么士兵就相邻了，即x[i]=a+i，那么x[i]-i=a。用中位数来算的话，首先将x方向进行排序，然后让x[i]=x[i]-i，再次排序后求中位数即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 10000;
int x[N], y[N];
int main() {
int n; while (cin >> n) {
for (int i = 0; i < n; i++)
cin >> x[i] >> y[i];
sort(x, x + n);
for (int i = 0; i < n; i++) x[i] -= i;
sort(x, x + n);
sort(y, y + n);
int ans = 0, x_median, y_median;
if (n % 2 == 1) {
x_median = x[n / 2];
y_median = y[n / 2];
}
else {
x_median = (x[n / 2 - 1] + x[n / 2]) / 2;
y_median = (y[n / 2 - 1] + y[n / 2]) / 2;
}
for (int i = 0; i < n; i++)
ans += abs(x_median - x[i]) + abs(y_median - y[i]);
cout << ans << endl;
}
}
poj1050 To the Max
贪心 / DP
题目大意：给你一个n*n的矩阵，要求找出其中的子矩阵，使个元素的和最大，输出最大值。
题目分析：
- 分别把第二行加到第一行求最大子段和，再第三行加到第一行求最大子段和，....，第n行...；
- 再把第三行，第四行，....，n行 依次加到第二行，分别求最大子段和。
- 记录过程中的最大值即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int g[N][N], ans = -114514;
int main() {
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0);
int n; scanf("%d", &n);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
scanf("%d", &g[i][j]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
g[i][j] += g[i][j - 1];
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j) {
int sum = 0;
for (int k = 1; k <= n; ++k) {
sum += g[k][j] - g[k][i - 1];
ans = max(ans, sum);
if (sum < 0) sum = 0;
}
}
printf("%d
", ans);
return 0;
}
Hdu4864 Task
贪心
题目不难，就是读题烦
分析：贪心题目，比赛的时候想到贪心。是给机器选工作。工作时间跟小于机器最接近的，然后另一个价值yi。不好贪心。
中间又想到把他们的值放在一个矩阵中贪心，转化为在一个子矩阵中求结果，这个思想也是非常好的，可是大前提没有考虑正确，事实上是给工作选机器。为什么呢？
由于题目求让完毕的任务最多，所以能够把工作和机器都按时间从大到小，然后价值从大到小，然后给每一个工作找机器。首先全部的工作时间比当前任务的工作时间大的都能够选，我们贪心选择当中价值最小的满足条件的一个机器，把大的留给后面的。这样思路就没有错了、
然后是处理，假设直接写的话接近O（n^2),必超时，開始想到的优先队列，可是优先队列返回的是最小的。我们要的是首先要满足大于当前任务价值。所以不行，然后能够用vector，也能够直接用一个数组处理。由于时间都是满足条件的，仅仅要贪心选择一个最优的价值。所以能够用一个哈希数组，非常easy的小处理了。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
struct node{
int x,y;
}ts[101000],mas[101000];
bool cmp(const node &a,const node &b)
{
if(a.x!=b.x)return a.x>b.x;
if(a.y!=b.y)return a.y>b.y;
}
int book[120];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
for(int i=0;i<n;i++)
scanf("%d%d",&mas[i].x,&mas[i].y);
for(int i=0;i<m;i++)
scanf("%d%d",&ts[i].x,&ts[i].y);
sort(mas,mas+n,cmp);
sort(ts,ts+m,cmp);
memset(book,0,sizeof(book));
long long ans=0,count=0;
for(int i=0,j=0;i<m;i++)
{
while(j<n and mas[j].x>=ts[i].x)//满足当前的x,意味着后续的x都可以满足
{
book[mas[j].y]++;
j++;
}
for(int k=ts[i].y;k<=100;k++)
{
if(book[k])
{
book[k]--;
ans++;
count+=ts[i].x*500+ts[i].y*2;
break;
}
}
}
printf("%lld %lld
",ans,count);
}
return 0;
}