点击打开链接
无向图求欧拉回路：
1、图连通
2、所有顶点的度数位偶数
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
const int mt = 2000;
const int ms = 50;
bool vis[mt+5];
int g[ms][mt+5];
int deg[ms+5];
int f[ms+5];
stack<int> s;
int street, startv;
int findset(int x){
return f[x]==x?f...
阅读全文
点击打开链接
无向图点双联通，二分图判定
<span style="font-size:18px;">#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
struct Edge{
int u, v;
};
const int maxn = 1005;
int pre[maxn], iscut[maxn], bccno[maxn],dfs_clock, bcc_cnt;
vector<int> G[maxn], bcc[maxn];
stack<Edge> S;...
阅读全文
http://poj.org/problem?id=3468
整段更新，整段查询
PushUp（int rt) 是把当前结点的信息更新到父结点
PushDown（int rt) 是把当前结点的信息更新到儿子结点
延迟标记：
简单来说就是每次更新的时候不要更新到底，用延迟标记
使得更新延迟到下次需要更新or询问到的时候
/*
* 整段更新，整段查询
* PushUp（int rt) 是把当前结点的信息更新到父结点
* PushDown（int rt) 是把当前结点的信息更新到儿子结点
* 延迟标记：
...
阅读全文
题目链接：点击打开链接
题意：有两种操作，合并集合，查询第K大集合的元素个数。(总操作次数为2*10^5)
解法：
1、Treap
2、树状数组
|-二分找第K大数
|-二进制思想，逼近第K大数
3、线段树
4、。。。
Treap模板（静态数组）
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
const int maxNode = 500000 + 100;
const int inf =...
阅读全文
提交地址：点击打开链接
题意： N(N<=10^5)只猴子，初始每只猴子为自己猴群的猴王，每只猴子有一个初始的力量值。这些猴子会有M次会面。每次两只猴子x,y会面，若x,y属于同一个猴群输出-1，否则将x,y所在猴群的猴王的力量值减半，然后合并这两个猴群。新猴群中力量值最高的为猴王。输出新猴王的力量值。
分析：涉及集合的查询，合并，取最值。 利用并查集和左偏树即可解决。
#include <cstdio>
#include <cstri...
阅读全文
题意：
给定一些木棒，木棒两端都涂上颜色，求是否能将所有木棒首尾相接，连成一条直线，要求不同木棒相接的一边必须是相同颜色的。
无向欧拉图：不存在或只存在两个奇度顶点
用并查集判断图的连通性 //判断是否只有一个根结点
用Trie或者hash给每种颜色编号
静态数组Trie
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<algorithm&...
阅读全文
sum[i][j] 表示从第1到第i头cow属性j的出现次数
所以题目要求等价为:
求满足
sum[i][0]-sum[j][0]=sum[i][1]-sum[j][1]=.....=sum[i][k-1]-sum[j][k-1] (j<i)
中最大的i-j
将上式变换可得到
sum[i][1]-sum[i][0] = sum[j][1]-sum[j][0]
sum[i][2]-sum[i][0] = sum[j][2]-sum[j][0]
......
sum[i][k-1]-sum[i][0] = sum[j][k-1]-sum[j][0]
令C[i][y]=sum[i][y]-sum[i][0] (0<y<k)
初始条件C[0][0~k-1]=0
所以只需求...
阅读全文
a1x13+ a2x23+
a3x33+ a4x43+
a5x53=0
所有数的范围[-50,50]
给出 a1, a2, a3, a4, a5的值，x1, x2, x3, x4, x5为变量，求这个方程有多少组解。
可以先三重循环枚举x1,x2,x3计算前面三项的值sum1, count[sum1]++;
然后二重循环枚举x4,x5计算后面二项的值sum2, answer += count[-sum2];
这里要注意，sum1, sum2的值可以为负数，所以要加上一个合适的值，同时也要考虑count[]数组的大小。
当然也可以用STL_map 代替count...
阅读全文
poj 2002 Squares
给出n个点，问能组成多少个正方形？
题解：
先把每个点hash
然后枚举两点（即枚举正方形的一条边），然后通过三角形全等，可以推出正方形的另外两点，在hash表里查找这两点看是存在，存在则 Cnt +1。
最后 answer = Cnt/4 //因为同一正方形都统计了4次。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1005;
const int MOD = 100...
阅读全文
http://poj.org/problem?id=2431
题意：
你需要驾驶一辆卡车行驶L单位距离。最开始时，卡车上有P单位的汽油。卡车每开1单位距离需要消耗1单位的汽油。如果在途中车上的汽油耗尽，卡车就无法继续前行，因而无法到达终点。在途中一共有N个加油站。第i个加油站在距离终点Ai单位距离的地方，最多可以给卡车加Bi单位汽油。假设卡车的燃料箱的容量是无限大的，无论加多少油都没有问题。那么请问卡车是否能到达终点？如果可...
阅读全文