whix

未归档

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

/ 注册

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

Farm Tour POJ - 2135

主要是考虑如何转化为网络流问题，要求从起点到终点，再从终点到起点，总的花费最小。相当于从源点到终点走两遍，因为要求每一条边只能走一遍，所以可以以1为每条边的流量，用来限制每一条边只能走一遍，以每条边的路程为花费，再设立一个源点和一个汇点，源点和1号节点之间费用为0，流量为2，n号点和汇点之间的边流量...

2019-08-09

0 504

Max Sum Plus Plus HDU - 1024

经典的dp问题，但自己的dp 水平实在太差。首先定义，dp[i][j]表示把前 j 个数分成 i 组的最大值,可以得到状态转移方程： dp[i][j] =max (dp[i][j-1]+s[j],max(dp[i-1][k]+a[j])) （0<=k<=j-1）前面表示s[j]独立成...

2019-07-23

0 409

Currency Exchange POJ - 1860

BellMan 算法解决一直用迪杰斯特拉算法求最短路问题，一看到最短路就思维固定。要根据不同问题的特点用不同的算法。附上代码，对bellman算法理解的不算深刻。 #include <cstdio>//判断最长路径是否有正环 #include <algorithm> u...

2019-07-23

0 363

Stars HDU - 1541

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

2019-07-16

0 357

树状数组总结

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

2019-07-16

0 486

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 356

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 591

poj3087

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

2019-07-15

0 382

树状数组求逆序对 poj2299

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

2019-07-14

0 410

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 390