whix

分类

acm(1) codeforces(13) dp(1) java(1) 区域赛真题(2) 图论(20) 字符串(3) 数据结构(4) 数论(37) 未归档(32) 牛客(8) 组合数学(7) 计算几何(1) 题解(9)

/ 注册

全部文章（共139篇）

Stars HDU - 1541

本题对于我而言，一开始不知道如何把树状数组建立在问题上，其实对于一个问题，经过一定的处理后，可以直接套用树状数组，只要满足其性质，可以通过树状数组的操作解决即可。因为题目的数据是已经有顺序的，所以只要以star 的横坐标为数组的下标建立树状数组即可，同时因为x>=0,所以在操作前，x++。 ...

2019-07-16

0 349

树状数组总结

1 一、一维树状数组 1、单点修改+区间查询（应用：求逆序对，求区间最大值） lowbit()函数：求x的补码（x&-x）意义:得到的是x的二进制表示中，最低位的1表示的数如 5 二进制表示为101，所以最低位的1所在的位置是0，所以lowbit(5)=2^0=1; 后缀数组： sum[...

2019-07-16

0 484

poj1703----种类并查集

首先看题意，可知本题中一共有两个种类。因此根据种类并查集的思想对group[x]数组进行定义： group[x]=0表示x与pre[x]为同类，group[x]=1表示x与pre[x]为不同类。一开始对group[x]=0; 由种类并查集的思想，在find（）中对group进行更新（利用x与之前p...

2019-07-16

0 353

Silver Cow Party POJ - 3268

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1…N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total ...

2019-07-15

0 585

poj3087

#include <cstdio> #include <algorithm> #include <string> #include <iostream> using namespace std; int n,c; string s1,s2,aim; v...

2019-07-15

0 377

树状数组求逆序对 poj2299

树状数组求逆序对；对于一组任意顺序的数，记下他们的初位置，再进行排序，记下他们本来应该在的位置。然后，按最初位置从前往后，进行处理。基本思想：对于一个数要求它对应得逆序对，可以通过求前面小于等于它的数的个数，然后用当前已处理的数的个数-前面小于等于当前的数的个数得到。如： 4 3 5 2 1...

2019-07-14

0 401

hdu3038

#include <cstdio> #include <algorithm> using namespace std; const int N=200010; int n,m; int pre[N],value[N];//value[]表示改点到其更节点的距离，对value含...

2019-07-14

0 388

并查集

1.普通并查集用于记录节点之间的连接关系，使得相互连通关系的点可以用他们共同的父节点来表示。对于父节点不同的点可以通过父节点的合并来改成相互连通。主要用于判断图的连通性（如kruskal算法中）。 int find(int x) { if(x!=pre[x])//包括路径压缩 ...

2019-07-14

0 424

HDU3371题解

此题为最小生成树的基础题，一开始用Prim算法发现超时，当时想的是把已联通的城市当作一个城市，但发现用了太多的时间去处理。最后发现适合用kruskal求解，利用并查集的思想，对于n个点，全部连通需要ee=n-1条边，对于那些已联通的点，输入时进行处理，把他们并起来，使得在使用kruskal算法进行处...

2019-07-14

0 550