|
|
题意： 就是求重叠的矩阵轮廓的周长。
总结：理解线段树最好的方法就是利用样例，或者自己利用模型模拟一遍，然后就是边模拟边想代码的实现。
我的写法是比较正规的二叉树的形式，各个节点描述信息如下。
这个程序经典在于涵盖了线段树的基本操作和节点记录的数据，至于求矩阵面积交，只是缺少了扫描线区间个数的记录，这也是求矩阵周长并的关键。
具体cpp代码如下：
//poj1177Pucture线段树
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
using namespace std;
const int root = 0;
struct Node{
int l,r;
int cover,len,lines;//vover记录覆盖次数，len长度，lines记录并区间数
int lf,rf;//记录左右节点是否被覆盖
int lnd,rnd;//记录左右节点
}node[20005];
int cnt,cnty;
int indexy[10010];//离散纵坐标y的数组
struct Cord{
int x,y1,y2;
bool f;
}cord[10005];//竖线
int n;
void Creat(int p,int l,int r)
{
node[p].l = l; node[p].r = r;
node[p].lf = node[p].rf = 0;
node[p].len = node[p].lines = 0;
if (r - l > 1)
{
int mid = (r+l) >> 1;
node[p].lnd = ++cnt;
Creat(cnt,l,mid); //递归创建左子树
node[p].rnd = ++cnt;
Creat(cnt,mid,r);//递归创建右子树
}
else {
node[p].lnd = node[p].rnd = -1;
}
}
void upData(int p) //每次插入或删除后的更新操作
{
if (node[p].cover > 0) //整条线段被覆盖
{
node[p].len = indexy[node[p].r] - indexy[node[p].l];
node[p].lines = 1;
node[p].lf = node[p].rf = 1;
}
else if (node[p].l == node[p].r - 1) //未被覆盖的元线段
{
node[p].lf = node[p].rf = 0;
node[p].len = node[p].lines = 0;
}
else { //未被覆盖的非元线段
int left = node[p].lnd;
int right = node[p].rnd;
node[p].lf = node[left].lf;
node[p].rf = node[right].rf;
node[p].len = node[left].len + node[right].len;
node[p].lines = node[left].lines + node[right].lines - node[left].rf*node[right].lf;
}
}
void Insert(int p,int l,int r) //插入线段
{
if (l <= node[p].l && node[p].r <= r)
node[p].cover ++;
else {
int mid = (node[p].l+node[p].r) >> 1;
if (mid > l)
Insert(node[p].lnd,l,r);
if (mid < r)
Insert(node[p].rnd,l,r);
}
upData(p);
}
void Delete(int p,int l,int r) //删除线段
{
if (l <= node[p].l && node[p].r <= r)
{
node[p].cover --;
}
else {
int mid = (node[p].l+node[p].r) >> 1;
if (mid > l)
Delete(node[p].lnd,l,r);
if (mid < r)
Delete(node[p].rnd,l,r);
}
upData(p);
}
bool cmp(const Cord &a,const Cord &b)
{
return a.x < b.x;
}
void init_index() //对纵坐标离散去重
{
sort(indexy+1,indexy+1+cnty);
int m = 1;
for (int i = 2; i <= cnty; i++)
{
if (indexy[i] != indexy[i-1])
{
m++;
indexy[m] = indexy[i];
}
}
cnty = m;
}
int Bi_search(int key) //二分查找 y 对应的离散坐标
{
int l = 1,r = cnty + 1,mid;
while (l < r)
{
mid = (l + r) >> 1;
if (indexy[mid] == key)
return mid;
if (indexy[mid] < key)
l = mid + 1;
else r = mid;
}
}
int main()
{
int i,j,left,right,prelen,prelines;
int x1,x2,y1,y2;
int ans;
while (scanf("%d",&n) != EOF)
{
for (i = 1;i <= n + n; i+=2)
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
cord[i].x = x1; cord[i].y1 = y1; cord[i].y2 = y2;
cord[i].f = true;
cord[i+1].x = x2; cord[i+1].y1 = y1; cord[i+1].y2 = y2;
cord[i+1].f = false;
indexy[i] = y1;
indexy[i+1] = y2;
}
sort(cord+1,cord+1+n+n,cmp);
cnty = n+n;
init_index();
cnt = 0;
Creat(root,1,cnty);
left = Bi_search(cord[1].y1);
right = Bi_search(cord[1].y2);
Insert(root,left,right);
prelen = node[root].len;
prelines = node[root].lines;
ans = prelen;
for (i = 2; i <= n+n; i++)
{
left = Bi_search(cord[i].y1);
right = Bi_search(cord[i].y2);
if (cord[i].f)
Insert(root,left,right);
else {
Delete(root,left,right);
}
ans += abs(prelen - node[root].len); //纵向周长增长量为前后两次被覆盖线段长度的改变量
ans += prelines*(cord[i].x - cord[i-1].x)*2; //横向周长的增长量为上一次区间个数乘2在乘横向长度
prelen = node[root].len;
prelines = node[root].lines;
}
printf("%d\n",ans);
}
return 0;
}
problem A
水题不解释. problem B
题意还是见： http://codeforces.com/contest/36/problem/B 做法是不断递归白色的区域，直到此区域的len == n。
cpp代码：
#include <cstdio>
#include <stdlib.h>
char a[5][5],mp[300][300];
int n,k;
void Orig(int x,int y)
{
// printf("Orig: x = %d,y = %d\n",x,y);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
mp[x+i][y+j] = a[i][j];
// printf("%d,%d--%c",x+i,y+j,a[i][j]);
}
// printf("\n");
}
}
void Black(int len,int x,int y)
{
// printf("Black:len = %d,x = %d,y = %d\n",len,x,y);
for (int i = x; i < len + x; i++)
for (int j = y; j < len + y; j++)
mp[i][j] = '*';
}
void paint(int len,int i,int j)
{
if (len == n)
Orig(i,j);
else {
int cnt = len / n;
for (int x = 0; x < n; x++)
for (int y = 0; y < n; y++)
if (a[x][y] == '*')
Black(cnt,i+cnt*x,j+cnt*y);
else paint(cnt,i+cnt*x,j+cnt*y);
}
}
int myPow(int n,int k)
{
int m = 1;
while (k > 0)
{
m *= n;
k--;
}
return m;
}
int main()
{
int i,j;
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
while (scanf("%d %d",&n,&k) != EOF)
{
int len = myPow(n,k);
for (i = 0; i < n; i++)
scanf("%s",a[i]);
paint(myPow(n,k),1,1);
for (i = 1; i <= len; i++)
{
for (j = 1; j <= len; j++)
printf("%c",mp[i][j]);
printf("\n");
}
// /*********/printf("----------------\n\n");
}
return 0;
}
problem C
题见：http://codeforces.com/contest/36/problem/C 我觉得这是一个比较好的题。首先，需要必要的数学知识就是相似三角形各边的比例关系。然后，就是判断每来一个碗时它会在哪个碗之上？比赛时我没时间想明白后来看了xpree的代码后猛然发觉，其实可以枚举前面放过的碗中每个碗可以使来的碗 i 有一个 上升的高度up[i]，求up[i] + h[j]最大值即可。枚举O（n*n）的。这给我的收获就是：在不确定的情况下，枚举是最好的方法，类似动态规划很多时候都是用这个思想，然后得到下一个最优子结构。
接下来的问题就是求两碗之间的碗底高度差了，这里 i 代表放过的碗，j 代表要放的碗，情况就是三类：1、r[j] >= R[i] 就是j 在 i 的顶部：2、j 能完全i内，高度差为0：2、j 卡在 i 中间或 i 内部。具体的情况自己画画图就明白了；
CPP代码：
#include <cstdio>
#include <cstdio>
#include <algorithm>
using namespace std;
const double eps = 1e-8;
const int MAX = 3005;
double r[3005],R[3005],h[3005],up[3005],k[3005];
double cmp(int i,int j)
{
if (R[i] <= r[j])// j 在 i 顶部
return h[i];
if (r[i] > r[j]) // j 完全在 i 内部，两者碗底的高度差为 0
{
if (k[j] < k[i] )
return 0;
if (h[i] <= h[j] && (h[i]*(R[j]-r[j])/h[j] + r[j]) <= R[i])
return 0;
if (h[i] >= h[j] && (h[j]*(R[i]-r[i])/h[i] + r[i]) >= R[j])
return 0;
}
if (k[j] > k[i]) // j 卡在 i 中
{
if (R[j] >= R[i])
return h[i] - (R[i]-r[j])*h[j]/(R[j] - r[j]);
else return (R[j]-r[i])*h[i]/(R[i]-r[i]) - h[j];
}
else return h[i]*(r[j]-r[i])/(R[i]-r[i]);
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int n,i,j;
double ans,d;
while (scanf("%d",&n) != EOF)
{
for (i = 1; i <= n; i++)
{
up[i] = 0;
scanf("%lf %lf %lf",&h[i],&r[i],&R[i]);
k[i] = (R[i] - r[i]) / h[i];
}
ans = 0;
for (i = 1; i <= n; i++)
{
//枚举 i 之前的碗，看 i 会在 那个上面
for (j = 1; j < i ; j++)
{
d = cmp(j,i);
// printf("i = %d,j = %d,d = %lf\n",i,j,d);
up[i] = max(up[i],up[j]+d);
}//printf("ans = %lf\n",ans);
ans = max(ans,up[i]+h[i]);
}
printf("%.8lf\n",ans);
}
return 0;
}
题意就不说了，主要是看陈宏的论文和Magicfly的模板终于初步了解了线段树，真是个强大的东西啊。
说点自己写的时候遇到的问题吧：
注意：左右节点的被覆盖的标记和并区间的计算。
教训：Ctrl+C，Ctrl+V害惨我了，把Insert的代码直接贴到Delete那去，后来看了好久才会过神来，代码能力不够啊。
上代码：
//poj1177Pucture线段树
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
using namespace std;
const int root = 0;
struct Node{
int l,r;
int cover,len,lines;//vover记录覆盖次数，len长度，lines记录并区间数
int lf,rf;//记录左右节点是否被覆盖
int lnd,rnd;//记录左右节点
}node[40005];
int cnt,cnty;
int indexy[10010];//离散纵坐标y的数组
struct Cord{
int x,y1,y2;
bool f;
}cord[10005];//竖线
int n;
void Creat(int p,int l,int r)
{
node[p].l = l; node[p].r = r;
node[p].lf = node[p].rf = 0;
node[p].len = node[p].lines = 0;
if (r - l > 1)
{
int mid = (r+l) >> 1;
node[p].lnd = ++cnt;
Creat(cnt,l,mid); //递归创建左子树
node[p].rnd = ++cnt;
Creat(cnt,mid,r);//递归创建右子树
}
else {
node[p].lnd = node[p].rnd = -1;
}
}
void upData(int p) //每次插入或删除后的更新操作
{
if (node[p].cover > 0) //整条线段被覆盖
{
node[p].len = indexy[node[p].r] - indexy[node[p].l];
node[p].lines = 1;
node[p].lf = node[p].rf = 1;
}
else if (node[p].l == node[p].r - 1) //未被覆盖的元线段
{
node[p].lf = node[p].rf = 0;
node[p].len = node[p].lines = 0;
}
else { //未被覆盖的非元线段
int left = node[p].lnd;
int right = node[p].rnd;
node[p].lf = node[left].lf;
node[p].rf = node[right].rf;
node[p].len = node[left].len + node[right].len;
node[p].lines = node[left].lines + node[right].lines - node[left].rf*node[right].lf;
}
}
void Insert(int p,int l,int r) //插入线段
{
if (l <= node[p].l && node[p].r <= r)
node[p].cover ++;
else {
int mid = (node[p].l+node[p].r) >> 1;
if (mid > l)
Insert(node[p].lnd,l,r);
if (mid < r)
Insert(node[p].rnd,l,r);
}
upData(p);
}
void Delete(int p,int l,int r) //删除线段
{
if (l <= node[p].l && node[p].r <= r)
{
node[p].cover --;
}
else {
int mid = (node[p].l+node[p].r) >> 1;
if (mid > l)
Delete(node[p].lnd,l,r);
if (mid < r)
Delete(node[p].rnd,l,r);
}
upData(p);
}
bool cmp(const Cord &a,const Cord &b)
{
return a.x < b.x;
}
void init_index() //对纵坐标离散去重
{
sort(indexy+1,indexy+1+cnty);
int m = 1;
for (int i = 2; i <= cnty; i++)
{
if (indexy[i] != indexy[i-1])
{
m++;
indexy[m] = indexy[i];
}
}
cnty = m;
}
int Bi_search(int key) //二分查找 y 对应的离散坐标
{
int l = 1,r = cnty + 1,mid;
while (l < r)
{
mid = (l + r) >> 1;
if (indexy[mid] == key)
return mid;
if (indexy[mid] < key)
l = mid + 1;
else r = mid;
}
}
int main()
{
int i,j,left,right,prelen,prelines;
int x1,x2,y1,y2;
int ans;
while (scanf("%d",&n) != EOF)
{
for (i = 1;i <= n + n; i+=2)
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
cord[i].x = x1; cord[i].y1 = y1; cord[i].y2 = y2;
cord[i].f = true;
cord[i+1].x = x2; cord[i+1].y1 = y1; cord[i+1].y2 = y2;
cord[i+1].f = false;
indexy[i] = y1;
indexy[i+1] = y2;
}
sort(cord+1,cord+1+n+n,cmp);
cnty = n+n;
init_index();
cnt = 0;
Creat(root,1,cnty);
left = Bi_search(cord[1].y1);
right = Bi_search(cord[1].y2);
Insert(root,left,right);
prelen = node[root].len;
prelines = node[root].lines;
ans = prelen;
for (i = 2; i <= n+n; i++)
{
left = Bi_search(cord[i].y1);
right = Bi_search(cord[i].y2);
if (cord[i].f)
Insert(root,left,right);
else {
Delete(root,left,right);
}
ans += abs(prelen - node[root].len); //纵向周长增长量为前后两次被覆盖线段长度的改变量
ans += prelines*(cord[i].x - cord[i-1].x)*2; //横向周长的增长量为上一次区间个数乘2在乘横向长度
prelen = node[root].len;
prelines = node[root].lines;
}
printf("%d\n",ans);
}
return 0;
}
其他的都不多说了，列出A*X=B方程，找出系数A矩阵和解B，
教训：查了个把小时的错，计算[i,j]为宽w，高h 中第几个数时弄错了，应该每行 w 个。
收获：rt，还有知道了swap（ ，）这个交换两变量数据的函数
#include <cstdio>
#include <iostream>
#include <stdlib.h>
#include <cmath>
using namespace std;
const int M = 105;
double a[M][M],b[M];
double map[15][15];
int w,h,d,len;
/***********************************************************/
/*******len为解的个数，a[][]*X[] = b[],解在b【】中*****************************************************/
void Guass()
{
int id,i,j,k;
double max,temp;
k = 1;
while (k <= len)
{
max = fabs(a[k][k]);
id = k;
//change the max!!!
for (i = k+1; i <= len; i++)
{
if (max < fabs(a[i][k]))
{
max = fabs(a[i][k]);
id = i;
}
}
if (k != id)
{
//新发现，有swap交换函数能用
swap(b[id],b[k]);
for (i = 1; i <= len; i++)
swap(a[id][i],a[k][i]);
}
//to gauss
b[k] /= a[k][k];
temp = a[k][k];
for (i = k; i <= len; i++)
{
a[k][i] /= temp;
}
for (i = 1; i <= len; i++)
if (i != k)
{
temp = a[i][k];
b[i] -= b[k]*temp;
for (j = k; j <= len; j++)
a[i][j] -= a[k][j]*temp;
}
k ++;
}
}
/*************************************************************************/
int main()
{
// freopen("blur.in","r",stdin);
int i,j,p,q,id,count,sum,cas = 1,cnt;
while (scanf("%d %d %d",&w,&h,&d))
{
if (w == 0 && h == 0 && d == 0)
break;
else if (cas != 1)
printf("\n");
cas ++;
len = w * h;
for (i = 1; i <= h; i++)
for (j = 1; j <= w; j ++)
scanf("%lf",&map[i][j]);
for (i = 1; i <= len; i++)
for (j = 1; j <= len; j++)
a[i][j] = 0.0;
for (i = 1; i <= h; i++)
for (j = 1; j <= w; j++)
{
cnt = (i-1) * w + j;
b[cnt] = map[i][j];
count = 0;
for (p = i - d; p <= i + d; p ++)
for (q = j - d; q <= j + d ; q ++)
{
if (abs(p-i) + abs(q-j) <= d && p >= 1 && p <= h && q >= 1 && q <= w)
{
id = (p-1)*w + q;
a[cnt][id] = 1;
count ++;
}
}
b[cnt] *= count;
}
Guass();
for (i = 1; i <= len; i++)
{
printf("%8.2lf",b[i]);
if (i % w == 0)
printf("\n");
}
}
// while (1) ;
return 0;
}
一、最大公倍数 两数的乘积再除以两数的最大公约数法。 这个方法虽然比较复杂，但是使用范围很广。
因为两个数的乘积等于这两个数的最大公约数和最小公倍数的乘积。
例如：4和6的最大公约数是2，最小公倍数是12，那么，4×6=2×12。
为了便于口算，我们可以把两个数中的任意一个数先除以它们的最大公约数，
然后再和另一个数相乘。例如：18和30的最大公约数是6，
要求18和30的最小公倍数时，可以先用18除以6得3，再用3和30相乘得90；
或者先用30除以6得5，再用5和18得90。这90就是18和30的最小公倍数。
二、最大公约数 //辗转相除法--递归 int gcd(int a,int b) { if(b==0) return a; else return gcd(b,a%b); } //辗转相除法--纯循环 int gcd(int a,int b) { int r; while(b!=0) { r=a%b; a=b; b=r; } return a; }
分类一：
基础题：1000、1001、1004、1005、1008、1012、1013、1014、1017、1019、1021、1028、1029、1032、1037、1040、1048、1056、1058、1061、1070、1076、1089、1090、1091、1092、1093、1094、1095、1096、1097、1098、1106、1108、1157、1163、1164、1170、1194、1196、1197、1201、1202、1205、1219、1234、1235、1236、1248、1266、1279、1282、1283、1302、1303、1323、1326、1330、1334、1335、1339、1390、1391、1393、1395、1397、1405、1406、1407、1408、1412、1418、1420、1465、1491、1555、1562、1563、1570、1587、1673、1678、1708、1718、1720、1785、1799、1859、1862、1877、1898、1976、1977、1985、1994、2000、2001、2002、2003、2004、2005、2006、2007、2008、2009、2010、2011、2012、2013、2014、2015、2016、2017、2018、2019、2020、2021、2022、2023、2024、2025、2026、2027、2028、2029、2030、2031、2032、2033、2034、2035、2039、2040、2042、2043、2048、2049、2051、2053、2055、2056、2057、2060、2061、2071、2073、2075、2076、2078、2081、2083、2088、2090、2092、2093、2095、2096、2097、2098、2099、2101、2103、2106、2107、2109、2113、2114、2115、2123、2131、2132、2133、2135、2136、2137、2138、2139、2143、2148、2153、2156、2161、2162、2164、2178、2186、2192、2200、2201、2212、2304、2309、2317、2401、2500、2502、2503、2504、2519、2520、2521、2523、2524、2535、2537、2539、2547、2548、2549、2550、2551、2552、2555、2560、2561、2562、2566、2567、2568、2700、2710、
DP：1003、1024、1029、1069、1074、1087、1114、1159、1160、1171、1176、1203、1231、1257、1260、1284、1421、1789、1978、2059、2084、2159、2191、2544、2571、2602、2709、
搜索：1010、1015、1016、1026、1072、1075、1175、1180、1181、1238、1239、1240、1241、1242、1253、1254、1312、1372、1548、1597、1671、1677、1728、1800、1983、2102、2141、2553、2563、2605、2612、2614、1616、2717
贪心：1009、1045、1049、1050、1051、1052、1257、1800、2037、2111、2124、2187、2391、2570
数学题：1018、1065、1071、1115、1141、1162、1212、1220、1492、1593、1701、1722、1798、1840、1999、2036、2080、2086、2089、2105、2108、2134、2303、2393、2438、2529、2547、2548、2552、2554、2601、2603、2701、
递推：1133、1143、1207、1249、1267、1284、1290、1297、1396、1992、1995、1996、2013、2014、2044、2045、2046、2047、2050、2064、2065、2067、2068、2070、2077、2085、2151、2154、2160、2190、2501、2512、2563、2569、2709、2716、
字符串：1020、1039、1043、1062、1073、1075、1088、1113、1161、1200、1251、1256、1288、1321、1328、1379、1804、1860、1982、1984、2017、2024、2025、2026、2027、2043、2052、2054、2072、2074、2087、2131、2137、2140、2163、2203、2206、2352、2500、2549、2564、2565、2567、2572、2609、2607、2707、2708、2719、2721、2723、
大数：1002、1042、1133、1250、1297、1715、1753、1865、2100、
胡搞：1022、1027、1030、1035、1128、1165、1209、1210、1215、1222、1228、1229、1230、1237、1259、1276、1286、1337、1342、1361、1370、1506、1577、1597、1702、1716、1727、1868、1870、1896、1981、1986、1987、1988、1997、1998、1999、2058、2062、2089、2090、2094、2104、2116、2117、2135、2175、2183、2184、2197、2303、2368、2370、2374、2511、2522、2527、2600、2615、2703、2711、2714、2715、2725、
博弈：1077、1404、1517、1524、1525、1527、1536、1564、1729、1730、1846、1847、1848、1849、1850、2147、2149、2176、2177、2188
母函数：1085、1171、1398、2079、2082、2110、2152、2189、2566、
hash：1264、1280、1425、1496、1800、2522、2600、
分类二：
附：2000-2099全是水题。
1001 这个就不用说了吧
1002 简单的大数
1003 DP经典问题，最大连续子段和
1004 简单题
1005 找规律（循环点）
1006 感觉有点BT的题，我到现在还没过
1007 经典问题，最近点对问题，用分治
1008 简单题
1009 贪心
1010 搜索题，剪枝很关键
1011
1012 简单题
1013 简单题（有个小陷阱）
1014 简单题
1015 可以看作搜索题吧
1016 经典的搜索
1017 简单数学题
1018 简单数学题
1019 简单数学题
1020 简单的字符串处理
1021 找规律的数学题
1022 数据结构的题（栈的应用）
1023 特殊的数（Catalan Number）
1024 经典DP，最大M子段和
1025 经典DP，最长递增子序列（要用NLogN的方法过）
1026 搜索
1027 数学题（或用STL）
1028 经典问题，整数拆分，用母函数做
1029 简单题（一般方法容易超时）
1030 简单题，可用模拟过
1031 简单题
1032 简单题
1033 模拟题
1034 Candy Sharing Game
1035 模拟题
1036 简单题
1037 简单题，不是一般的简单
1038 简单题
1039 字符串处理
1040 简单题，排序
1041 简单题，用大数
1042 大数
1043 经典搜索题，八数码问题
1044 稍微有点麻烦的搜索题
1045 搜索题，可用匹配做
1046 简单题
1047 简单的大数
1048 简单字符串处理
1049 简单题
1050 贪心
1051 经典贪心，也可以用DP
1052 贪心
1053 贪心，关于Huffman编码
1054 二分匹配
1055 二分匹配
1056 简单题
1057 模拟题
1058 经典问题，丑数，DP
1059 经典问题，可以用母函数或DP（不针对题目优化都会超时）
1060 数学题
1061 数学题
1062 简单字符串处理
1063 模拟大数
1064 简单题
1065 简单题
1066 数学题，找规律
1067
1068 经典二分匹配
1069 经典DP
1070 简单题
1071 简单数学题
1072 搜索
1073 字符串处理
1074 DP
1075 字典树
1076 简单题
1077
1078 DP
1079 博弈（DP）
1080 DP
1081 经典DP
1082 简单题
1083 二分匹配
1084 简单题
1085 母函数
1086 简单几何题
1087 简单DP
1088 字符串处理
1089~1096 （练习输入输出的8个题目）
1097 简单数学题
1098 数学题，注意找规律
1099 数学题
模拟题, 枚举
1002 1004 1013 1015 1017 1020 1022 1029 1031 1033 1034 1035 1036 1037 1039 1042 1047 1048 1049 1050 1057 1062 1063 1064 1070 1073 1075 1082 1083 1084 1088 1106 1107 1113 1117 1119 1128 1129 1144 1148 1157 1161 1170 1172 1177 1197 1200 1201 1202 1205 1209 1212(大数取模) 1216（链表）1218 1219 1225 1228 1229 1230 1234 1235 1236 1237 1239 1250
1256 1259 1262 1263 1265 1266 1276 1279 1282 1283 1287 1296 1302 1303 1304 1305 1306 1309 1311 1314
复杂模拟
搜索，递归求解
1010 1016 1026 1043(双广) 1044 (BFS+DFS) 1045 1067 1072 1104 1175 1180 1195 1208 1226 1238 1240 1241 1242 1258 1271 1312 1317
博奕
1079
动态规划
1003 1024 1025 1028 1051 1058 1059 1069 1074 1078 1080 1081 1085 1087 1114 1158 1159 1160 1171 1176 1181 1203 1224 1227 1231 1244 1248 1253 1254 1283 1300
数学，递推，规律
1005 1006 1012 1014 1018 1019 1021 1023 1027 1030 1032 1038 1041 1046 1059 1060 1061 1065 1066 1071(微积分) 1097 1098 1099 1100 1108 1110 1112 1124 1130 1131 1132 1134 1141 1143 1152 1155(物理题) 1163 1165 1178 1194 1196(lowbit) 1210 1214 1200 1221 1223 1249 1261 1267 1273 1290 1291 1292 1294 1297 1313 1316
数论
1164 1211 1215 1222 1286 1299
计算几何
1086 1115 1147
贪心
1009 1052 1055 1257
并查集
1198 1213 1232 1272
线段树,离散化
1199 1255
图论
最短路相关的问题 1142 1162 1217 1301
二分图问题 1054 1068 1150 1151 1281
其他
1053 (huffman) 1102(MST) 1116（欧拉回路） 1233(MST) 1269（强连通）
数据结构
1103（堆+模拟）1166（数状树组）1247 1251 1285（Topol） 1298
汉诺塔系列
1207
最近顶点对 1007
1500 DP
1501 DP
1502 DP or 记忆化
1503 DP
1504 模拟
1505 DP
1506 DP
1507 2分匹配
1508 记忆化容易点
1509 模拟
1510 DP
1511 搜索可以过
1512 左偏树
1513 DP
1514 DP
1515 DFS
1516 DP
1517 博奕
1518 搜索
1519 DP（不确定）
1520 树状DP
1521 数学题，母函数什么的。其实都可以过
1522 稳定婚姻
1523 DP
1524 博弈
1525 博弈
1526 Maxflow
1527 博弈
1528 2分匹配
1529 简单题
1530 最大团
1531 差分约束
1532 Maxflow 入门题
1533 KM Or 最小费用流
1534 差分约束
1535 差分约束
1536 博弈
1537 模拟 加置换群的理论 CODE可以短些，其实没必要。。。
1538 很有意思的题目。据说是Microsoft亚洲总裁面试的题目
1539 搜索
1540 线段树
1541 树状数组
1542 离散，线段树
1543 线段树
1544 简单的
1545 DP http://acm.hdu.edu.cn/forum/htm_data/18/0608/2050.html
1546 搜索
1547 模拟
1548 模拟
1551 2分答案
1553
1554
1555 简单
1556 技巧。数学
1557 搜索
1558 并查 + 线段判交
1559 DP
1560 减支 + 搜索
1561 树状DP
1562 暴力 between 1000 and 9999
1563 简单
1564 博弈。
1565 状态DP
1566 数学
1567 模拟
1568 大数
1569 最小割
1570 数学
1571 最段路
1572 搜索
1573 数学
1574 DP
1575 2分
1576 数论
1577 模拟，处理精度
1579 记忆化
1580 DP
1582 搜索
1583 模拟
1584 搜索
1585
1586
1587 简单题目
1591 模拟
1592 简单
1593 数学
1594 数学
1595 图论
1596 图论
1597 图论
1598 图论
1599 图论
摘要: http://www.cnblogs.com/MiYu/archive/2010/08/22/MiYu.html牛顿法的一个迭代序列：x(n+1)=x(n)－f(x(n))/f'(x(n))。ax^3+bX^2+cx+d=0根的关系:x1 + x2 + x3 = - b / a;x1 * x2 + x1 * x3 + x2 * x3 = c / a;x1 * x2 * x3 = - d / a;f... 阅读全文
|