第一篇：ACM 筛素数总结
【总结】关于求素数的说【两种筛法】（学习小结，请无视）
素数大家都很熟了，不多说了，这里只想说一下求素数。
当然先是唯一素因子分解定理：合数a仅能以一种方式，写成如下的乘积形式：a=p1e1p2e2…prer 其中pi为素数，p1
对于一个整数n，当其在 小于sqrt（n）范围里有一个约数，那么必然在 大于sqrt（n)的范围里有对应的另一个Eratosthenes（埃拉托斯特尼筛法）都是到 sqrt（n）的范围。①。试除法判素数
对于大于1的正整数a，如果a具有小于或等于sqrt（a）的素因子，则a为合数，否则a为素数。
因此，可用区间[2,sqrt(a)]内的数去试除a，只要有一个数能整除a，则a为合数，否则a为素数。这种判断素复杂度O(sqrt(n)).IsPrime(a)for(i=2;i*i<=a;i++)if(a%i==0)return a为合数
return a为素数
②。Sieve Of Eratosthenes（埃拉托斯特尼筛法）可以筛出2~n 范围里的所有素数。
1)将所有候选数2~n放入筛中;2)找出筛中最小数P，P一定为素数。
3)宣布P为素数，并将P的所有倍数从筛中筛去;4)重复2)至3)直到筛空.其实，当P>sqrt(n)时筛中剩下的数就已经都是素数了。//用数组prime[MAXN]记录是否为素数； //prime[i]为0表示i为素数，否则为合数 int prime[MAXN]={0};for(i=2;i*i<=n;i++){ if(prime[i]==0){ for(j=i+i;j<=n;j+=i)prime[j]=1;} } ③。线性筛法
对于Sieve Of Eratosthenes，普通的筛法如果是一个合数，那么会被多次筛掉，比如6,当2作为素数时筛掉一线性筛法保证所有合数只被筛掉一次
具体详见《ftfish利用积性函数的优化》，讲到了 积性函数（对于正整数n的一个算术函数f(n)，当中f(1)=1且称它为积性函数。）
for(int i = 2;i < maxn;i ++){ if(!fg[i])prim[np++] = i;//如果没被筛掉，那么就是素数
for(int j = 0;j < np && i*prim[j] < maxn;j ++){ //注意i不是素数的时候也筛
fg[i*prim[j]] = 1;if(i % prim[j] == 0)break;//这一步保证了筛法是线性的，这是整个算法的关键
} } 摘：
利用了每个合数必有一个最小素因子。
每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。代码中体现在：
if(i%prime[j]==0)break;prime数组 中的素数是递增的,当 i 能整除 prime[j]，那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。在满足i%pr[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。
第二篇：ACM赛后总结
赛后总结
虽然已经是大二第二学期了，这却是我的第一真正的ACM比赛经历，赛后感觉自己水平很差，感觉很不好，或许只有受到了了打击，才会有成长，也只有在一次次的打击中吸取经验，成为自己前进的动力。
这次比赛总结起来发现了我们的好多不足之处，第一个就是我们经验的缺失，毕竟是我们第一次参加这样的比赛，还有就是对做题顺序的把握不好，对题目难易程度判断不准确，如果做一个题发现思路错了，我们应该要及时改变思路，跳过去，先去做下面容易的题，等回过头来在做，要用尽量短的时间把我们知道做的题做出来，有些题，我们有思路，不敢保证完全做出来，就放到后面再去做，还有就是比赛的时候心态不好，中间做的时候就比较焦急，这样对自己的思路也会有影响，要调节好自己的情绪，还有就是要及时改变策略，多看榜，看到有很多人a的题目，我们肯定要去看一下，一开始我们就应该把题目全部都看一遍，最重要的是我们的实力还是不行，对于有些简单的题目还是不够熟练，思路不够清晰，下阶段要进一步有针对的加强训练！
比赛结束，我们真的是百感交集，有过遗憾，有过不甘心，有过失望，本来这次比赛应该是很好拿奖的，但最终我们还是与奖状擦肩而过，可能与经验的缺乏有关，我想更多的应该还是实力的差距，自己的实力不行，做什么都是白搭。所幸的是，我们明年还有一次机会，再努力一年，我想我们明年再战的时候，一定可以取得一个很好的成绩。
14物联网 贾文彪
第三篇：新筛总结
新生儿疾病筛查工作总结(产科)
新生儿疾病筛查是一项减少婴幼儿死亡和儿童残疾，提高人口素质的公共卫生举措，对提高人口素质、家庭幸福、社会和谐以及经济社会发展都有非常重要的意义。新生儿遗传病筛查以及听力筛查作为了解新生儿的两项重要筛查项目，在产科工作中有着重要的地位。
结合实际工作情况，现将我院新生儿疾病筛查工作的落实以及进展情况作如下总结：
1、疾病筛查工作的学习情况
自2011年5月份起，我院先后组织相关人员参加了由市妇幼保健院组织的新生儿疾病筛查相关知识和技能培训，认真学习，仔细笔记，回来后与全科同事共同学习，分享经验，研究重点，让相关岗位人员对于新生儿疾病筛查工作有了更加全面的认识，并能够进行实际的操作，把自己的本职工作干好。随着理论知识的学习，技术规范的操作以及熟练进行信息录入，每一位产科工作人员从思想上更加重视该项工作，争取做到百分百合格。
2、相关系统的操作要点以及注意事项
具体到实际的新生儿疾病筛查工作内容，可总结如下几个方面：首先，做好疾病筛查的宣教工作。在血片采集前，将新生儿疾病筛查的目的、意义、筛查病种、方法以及费用等情况，如实告之新生儿监护人并获得书面同意。其次，认真填写采血卡片，并由监护人认真核对确保信息真实无误；血片采集时，坚持一人一针一滤纸，严格无菌技术做到血片无污染，无渗血环，确保新生儿出生后72h7天之内，充分哺乳6次以上采集。另外，特殊情况延期采血者，签订延期通知单，并交代具体的注意事项，在规定时间内，送检血片并据实进行信息录入。对可疑阳性病例协助筛查中心及时通知复查，以防延误疾病，同时做好资料备案。
3、疾病筛查的信息化管理与网上录入
自疾病筛查实行网上信息化统一管理后，对我院新生儿逐一进行网上信息录入，以便于全市新生儿信息共享与统一管理。通过全科工作人员的耐心宣教，让每一位新生儿监护人都能够自觉接受疾病筛查，配合相关人员的工作，达到零拒筛的目标。
疾病筛查作为一项十分重要的护理工作，肯定存在这样或者那样的问题。结合我们的具体工作，现就疾病筛查工作遇到的问题以及问题解决方法作如下探讨：
首先，从实际工作来看，存在着“宣教难，全凭嘴”的尴尬，不仅影响效率，也缺乏可信度；对于这个问题，一是加强业务学习，总结宣教方法，改善宣教方式；第二可以依托市妇幼系统，印制简单、精美又便于理解的画册或者挂画，更加直观的宣导给新生儿父母及家人，直至成为人们的常识。
其次，随着网上录入信息的实行，加大了相关医护人员的工作量，如何尽快的完成工作，除了找方法，总结经验外，最起码的网络与硬件配备也应到位，这是更加出色完成工作的基础，也是我院迈向高等级医院的必备设施，对此理应优先投入；
再次，以我院的实力与地位，当依托相关卫生部门，配备更加强大的人员、资源，逐步的壮大我们产科的队伍，增强我院在产科护理这一块的作用，达到全市领先的目标。只有我们每一个科室发展了，我院才能够取得本质的发展与壮大。
随着广大人民群众物质和文化生活水平的不断提高，人们对于儿童的关注与投入进一步增加。新生儿疾病筛查作为一项重要的防护工作，理应取得全社会的关注与支持；同时，也应该作为产科工作中十分重要的一项工作来做。宏伟的目标总归只是一种理论的期望，随着2013年的到来，作为产科的一员，我们首先要做的，还是从最基本的工作入手，多学习，看资料，勤培训，丰富理论知识的同时，加强技术的交流，真正提高岗位技能，做到让千万父母与家人的百分百满意。真诚期待我与产科、与我院的共同成长！
第四篇：ACM程序设计培训总结
C语言篇
学生信息管理系统 #include “stdio.h” #include “stdlib.h” #define LEN sizeof(struct student)struct student
/*结构体类型*/ { int num;float score;struct student *next;};int n=0;
/*记录链表结点个数*/ struct student *head;
/*链表头指针*/ void menu();
/*DOS菜单函数*/ struct student *creat();
/*链表创建函数*/ void prin(struct student *head);
/*链表输出函数*/ struct student *insert(struct student *head);/*链表添加函数*/ struct student *del(struct student *head);
/*链表删除函数*/ struct student * paixu(struct student *head);/*排序函数*/ struct student *xiugai(struct student *head);/*修改函数*/ void seach();
void menu(){
int i;
printf(“n t 1t创建学生表n”);printf(“n t 2t添加学生数据n”);printf(“n t 3t显示学生信息n”);printf(“n t 4t排序学生记录n”);printf(“n t 5t修改学生记录n”);
printf(“n t 6t删除学生记录n”);
printf(“n t 7t查找学生记录n”);printf(“n t 0t退出n”);
printf(“n t 请输入你的选择（0-4）：”);
scanf(“%d”,&i);switch(i){
case 1: head=creat();break;
case 2: head=insert(head);break;
case 3: prin(head);break;
case 4: head=paixu(head);break;
case 5: head=xiugai(head);break;
case 6: head=del(head);break;
case 7: seach();break;
case 0: exit(0);
default:printf(“n选择错误！请按照下面提示选择。”);}
menu();} void main(){
menu();}
struct student *creat()
/*此函数带回一个指向链表头的指针*/ {
struct student *head,*p1,*p2;n=0;head=NULL;p1=(struct student *)malloc(LEN);/*创建第一个结点*/ printf(“请输入第1个学生学号及成绩（学号与成绩以空格隔开，'0 0'结束）:”);scanf(“%d%f”,&p1->num,&p1->score);p1->next=NULL;while(p1->num!=0)
/*应该将结点加入链表*/ { ++n;if(n==1)head=p1;
/*是第一个结点,作表头*/ else p2->next=p1;
/*不是第一个结点,作表尾*/ p2=p1;p1=(struct student*)malloc(LEN);/*开辟下一个结点*/ printf(“请输入第%d个学生学号及成绩（学号与成绩以空格隔开，'0 0'结束）:”,n+1);scanf(“%d%f”,&p1->num,&p1->score);p1->next=NULL;} free(p1);
/*释放最后一个结点所占的内存*/ return(head);/*返回链表的头指针*/ }
void prin(struct student *head)
/*链表输出函数*/ {
struct student *p;
if(head==NULL)
printf(“链表不存在，请先创建！”);
else
{
p=head;
for(;p!=NULL;)
{
printf(“%d号学生成绩：%fn”,p->num,p->score);
p=p->next;
}
} }
struct student *insert(struct student *head){ struct student*p0,*p1,*p2;int i;char ch='y';p1=head;
/*p1指向第一个结点*/
if(head==NULL)printf(“链表不存在，请先创建！”);else
{
while(ch=='Y'||ch=='y'){ p0=(struct student*)malloc(LEN);
printf(“请输入新结点的数据，输入'0 0'放弃插入：”);
scanf(“%d%f”,&p0->num,&p0->score);p0->next=NULL;
if(p0->num==0)
{ free(p0);
}
else
{ printf(“输入结点插入的位置：”);
scanf(“%d”,&i);
if(i==0)
/*作为表头*/
{
p0->next=head;
head=p0;
}
else
{
while(i>1&&(p1!=NULL))
{
p2=p1;
p1=p1->next;
i--;
}
/*找插入点*/
p0->next=p1;
/*插到p2指向的结点之后*/
p2->next=p0;
}
++n;
/*结点数加1*/
}
printf(“n数据添加成功！是否继续（y或Y继续,任意键退出):”);
getchar();
ch=getchar();} } return(head);}
struct student *del(struct student *head)/*形参num为需删除的学号*/ { int i;
char ch='y';struct student *p1,*p2;
while(ch=='Y'||ch=='y'){ if(head==NULL){ printf(“n链表不存在!n”);break;
/*链表为空*/ } else {
p1=head;
/*从头结点开始查找*/
printf(“请输入要删除的学生学号：”);
scanf(“%d”,&i);
getchar();
while(i!=p1->num&&p1->next!=NULL)
/*p1指向的不是所要找的结点,并且没有到表尾*/
{
p2=p1;
p1=p1->next;
/*后移一个结点*/
}
if(i==p1->num)
/*找到了需删除的结点*/
{
if(p1==head)
/*p1指向的是头结点*/
head=p1->next;/*第二个结点成为新的头结点*/
else
p2->next=p1->next;/*后继结点的地址赋给前一结点*/
printf(“%d号学生已经被删除n”,i);
free(p1);
/*释放结点所占的内存*/
n--;
/*链表结点数减1*/
printf(“n数据删除成功！是否继续（y或Y继续,任意键退出):”);
ch=getchar();
}
else
{
printf(“%d 号学生不存在或已经被删除!n”,i);/*找不到删除结点*/
printf(“n是否继续（y或Y继续,任意键退出):”);
ch=getchar();
} }
}
return(head);}
struct student * paixu(struct student *head)
/*排序函数*/ {
struct student *p0,*p1,*p2,*pt;
/*p0代表p1的前个结点*/
/*p1代表当前正排序的结点*/
/*p2用来取p1后面的每个结点来与P1比较*/ int i;
/*i=1表示头结点排序*/ if(head==NULL)
{
printf(“链表不存在，先创建！n”);
}
else if(n>1)
{
p0=p2=p1=head;
for(i=1;p1->next!=NULL;i++)
/*选择法排序算法*/
{
for(;p2->next!=NULL;)
if(p1->num>p2->next->num)
{
pt=p1;
p1=p2->next;
p2->next=p1->next;
p1->next=pt;
}
else p2=p2->next;
/*若不要交换，则p2指针后移*/
if(i==1)p0=head=p1;
/*对第一个结点排序时处理*/
else
/*其他结点排序时处理*/
{ p0->next=p1;
p0=p1;
}
p2=p1->next;
p1=p1->next;
}
prin(head);
/*调用输出函数*/
}
return(head);}
struct student *xiugai(struct student *head)
/*修改函数*/ { struct student *p;
int m;
printf(“n请输入要修改数据的学号(0退出)：”);
scanf(“%d”,&m);
while(m!=0)
{ p=head;
for(;p->num!=m&&p->next!=NULL;)
p=p->next;
if(p->num==m)
{ printf(“n请输入新的数据(学号 成绩)：”);
scanf(“%d%f”,&p->num,&p->score);
printf(“n修改成功！”);
printf(“n若继续修改，请输入学号(0退出)：”);
}
else
printf(“n该学生不存在，请重新输入学号(0退出)：”);
scanf(“%d”,&m);
}
return(head);}
void xuehao(struct student *head)
/*按学号查找函数*/ { struct student *p;
int m,leap;
printf(“n请输入要查找的学号：”);
scanf(“%d”,&m);
while(m!=0)
{ p=head;
leap=0;
for(;p->next!=NULL;)
{
if(p->num==m)
{printf(“n你要查找的学生信息为： 学号 %d 成绩 %fn”,p->num,p->score);
leap=1;
}
p=p->next;
}
if(leap==1)
printf(“n若继续查找，请输入学号(0退出)：”);
else
printf(“n该学生不存在，请重新输入学号(0退出)：”);
scanf(“%d”,&m);
}
}
void chengji(struct student *head)
/*按成绩查找函数*/ { struct student *p;
int leap;
float m;
printf(“n请输入要查找的成绩：”);
scanf(“%f”,&m);
while(m>=0)
{ p=head;
leap=0;
for(;p->next!=NULL;)
{
if(p->num==m)
{printf(“n你要查找的学生信息为： 学号 %d 成绩 %fn”,p->num,p->score);
leap=1;
}
p=p->next;
}
if(leap==1)
printf(“n若继续查找，请输入成绩(负数退出)：”);
else
printf(“n该学生不存在，请重新输入成绩(负数退出)：”);
scanf(“%f”,&m);
}
}
void seach()
/*查找子菜单*/ {
int i;
printf(“n t 1 按学号查找n”);printf(“n t 2 按成绩查找n”);printf(“n t 0 返回上级菜单n”);printf(“n t
请输入你的选择：”);scanf(“%d”,&i);switch(i){
case 1: xuehao(head);break;
case 2: chengji(head);break;
case 0: menu();break;
default:printf(“n选择错误！请按照下面提示选择。”);} seach();}
数据结构篇
//huffman.cpp 求Huffman编码 #define UNIT_MAX 65535
//函数结果状态代码
#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0
#define INFEASIBLE-1 #define OVERFLOW-2
#include
//Status 是函数的类型，其值是函数结果状态代码 typedef int Status;
//Huffman树＆Huffman编码的存储表示
typedef struct{ unsigned int weight;unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储Huffman树 typedef char **HuffmanCode;/* int min(HuffmanTree t,int i){ //函数void select()调用
int j,flag;unsigned int k=UNIT_MAX;for(j=1;j<=i;j++)
if(t[j].weight { k=t[j].weight; flag=j; } t[flag].parent=1; return flag;} void select(HuffmanTree t,int i,int &s1,int &s2){ //s1为最小的两个值中序号小的那个 int j;s1=min(t,i);s2=min(t,i);if(s1>s2){ j=s1; s1=s2; s2=j;} } */ void select(HuffmanTree t,int i,int &s1,int &s2){ int j;s1=0;s2=0; unsigned int small1,small2; small1=UNIT_MAX;small2=UNIT_MAX; for(j=1;j<=i;j++) //选出两个权值最小的根结点 { if(t[j].parent==0) if(t[j].weight { small2=small1; //改变最小权、次小权及对应的位置 small1=t[j].weight; s2=s1; s1=j; } else { if(t[j].weight { small2=t[j].weight;//改变次小权及位置 s2=j; } } } } void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){ // 算法6.12 // w存放n个字符的权值(均>0)，构造哈夫曼树HT，// 并求出n个字符的哈夫曼编码HC int m,i,s1,s2;unsigned c,cdlen; HuffmanTree p;char *cd; if(n<=1)return;m = 2 * n1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs.Every number must be connected to exactly one another.And, no two segments are allowed to intersect.It's still a simple game, isn't it? But after you've written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right? 卡特勒数 import java.math.*;import java.util.*;public class Main{ public static void main(String args[]) { Scanner as=new Scanner(System.in); int n,i; BigDecimal[] a=new BigDecimal[101]; a[0]=BigDecimal.valueOf(1); for(i=1;i<101;i++) { a[i]=a[i-1].multiply(BigDecimal.valueOf(4*i-2)); a[i]=a[i].divide(BigDecimal.valueOf(i+1)); } while(i>0) { n=as.nextInt(); if(n==-1) break; System.out.println(a[n]); } } } 筛选法 七夕节 除了筛选素数外，还能筛选因子（倍数的运用）#include for(j=i+i;j<=max;j+=i) a[j]+=i; scanf(“%d”,&t); while(t--) { scanf(“%d”,&n); printf(“%dn”,a[n]); } return 0;} 母函数 Ignatius and the Princess III “Well, it seems the first problem is too easy.I will let you know how foolish you are later.” feng5166 says.“The second problem is, given an positive integer N, we define an equation like this: N=a[1]+a[2]+a[3]+...+a[m];a[i]>0,1<=m<=N;My question is how many different equations you can find for a given N.For example, assume N is 4, we can find: 4 = 4;4 = 3 + 1;4 = 2 + 2;4 = 2 + 1 + 1;4 = 1 + 1 + 1 + 1;so the result is 5 when N is 4.Note that ”4 = 3 + 1“ and ”4 = 1 + 3“ is the same in this problem.Now, you do it!” Input The input contains several test cases.Each test case contains a positive integer N(1<=N<=120)which is mentioned above.The input is terminated by the end of file.Output For each test case, you have to output a line contains an integer P which indicate the different equations you have found.#include int n,i,j,k; while(cin>>n) { for(i=0;i<=n;i++) { c1[i]=0; c2[i]=0; } for(i=0;i<=n;i++) c1[i]=1; for(i=2;i<=n;i++) { for(j=0;j<=n;j++) for(k=0;k+j<=n;k+=i) { c2[j+k]+=c1[j]; } for(j=0;j<=n;j++) { c1[j]=c2[j]; c2[j]=0; } } cout< } return 0;} 贪心算法（排序函数）#incluide 初期: 一.基本算法: (1)枚举.(poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法.(4)递推.(5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法: (1)图的深度优先遍历和广度优先遍历.(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法)(poj3041,poj3020) (6)最大流的增广路算法(KM算法).(poj1459,poj3436)三.数据结构.(1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排)(poj2388,poj2299) (3)简单并查集的应用.(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树)(poj2513)四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.动态规划 (1)背包问题.(poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书 page149): 1.E[j]=opt{D+w(i,j)}(poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij}(最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)六.数学 (1)组合数学: 1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942) (2)数论.1.素数与整除问题 2.进制位.3.同余模运算.(poj2635, poj3292,poj1845,poj2115) (3)计算方法.1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)七.计算几何学.(1)几何公式.(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等).(poj2031,poj1039) (3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交) (poj1408,poj1584) (4)凸包.(poj2187,poj1113)中级: 一.基本算法: (1)C++的标准模版库的应用.(poj3096,poj3007) (2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)二.图算法: (1)差分约束系统的建立和求解.(poj1201,poj2983) (2)最小费用最大流(poj2516,poj2516,poj2195) (3)双连通分量(poj2942) (4)强连通分支及其缩点.(poj2186) (5)图的割边和割点(poj3352) (6)最小割模型、网络流规约(poj3308,)三.数据结构.(1)线段树.(poj2528,poj2828,poj2777,poj2886,poj2750) (2)静态二叉检索树.(poj2482,poj2352) (3)树状树组(poj1195,poj3321) (4)RMQ.(poj3264,poj3368) (5)并查集的高级应用.(poj1703,2492) (6)KMP算法.(poj1961,poj2406)四.搜索 (1)最优化剪枝和可行性剪枝 (2)搜索的技巧和优化(poj3411,poj1724) (3)记忆化搜索(poj3373,poj1691) 五.动态规划 (1)较为复杂的动态规划(如动态规划解特别的施行商问题等) (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034) (2)记录状态的动态规划.(POJ3254,poj2411,poj1185) (3)树型动态规划(poj2057,poj1947,poj2486,poj3140)六.数学 (1)组合数学: 1.容斥原理.2.抽屉原理.3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数.(2)数学.1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222) 2.概率问题.(poj3071,poj3440) 3.GCD、扩展的欧几里德(中国剩余定理)(poj3101) (3)计算方法.1.0/1分数规划.(poj2976) 2.三分法求解单峰(单谷)的极值.3.矩阵法(poj3150,poj3422,poj3070) 4.迭代逼近(poj3301) (4)随机化算法(poj3318,poj2454) (5)杂题.(poj1870,poj3296,poj3286,poj1095)七.计算几何学.(1)坐标离散化.(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004) (3)多边形的内核(半平面交)(poj3130,poj3335) (4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高级: 一.基本算法要求: (1)代码快速写成,精简但不失风格 (poj2525,poj1684,poj1421,poj1048,poj2050,poj3306) (2)保证正确性和高效性.poj3434 二.图算法: (1)度限制最小生成树和第K最短路.(poj1639) (2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解) (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446 (3)最优比率生成树.(poj2728) (4)最小树形图(poj3164) (5)次小生成树.(6)无向图、有向图的最小环 三.数据结构.(1)trie图的建立和应用.(poj2778) (2)LCA和RMQ问题(LCA(最近公共祖先问题)有离线算法(并查集+dfs)和 在线算法 (RMQ+dfs)).(poj1330) (3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的 目的).(poj2823) (4)左偏树(可合并堆).(5)后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)四.搜索 (1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426) (2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法.(poj1768,poj1184,poj1872,poj1324,poj2046,poj1482) (3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法.(poj3131,poj2870,poj2286)五.动态规划 (1)需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017) (2)四边形不等式理论.(3)较难的状态DP(poj3133)六.数学 (1)组合数学.1.MoBius反演(poj2888,poj2154) 2.偏序关系理论.(2)博奕论.1.极大极小过程(poj3317,poj1085) 2.Nim问题.七.计算几何学.(1)半平面求交(poj3384,poj2540) (2)可视图的建立(poj2966) (3)点集最小圆覆盖.(4)对踵点(poj2079)八.综合题.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263) Dp状态设计与方程总结 1.不完全状态记录 <1>青蛙过河问题 <2>利用区间dp 2.背包类问题 <1> 0-1背包，经典问题 <2>无限背包，经典问题 <3>判定性背包问题 <4>带附属关系的背包问题 <5> +-1背包问题 <6>双背包求最优值 <7>构造三角形问题 <8>带上下界限制的背包问题(012背包) 3.线性的动态规划问题 <1>积木游戏问题 <2>决斗（判定性问题） <3>圆的最大多边形问题 <4>统计单词个数问题 <5>棋盘分割 <6>日程安排问题 <7>最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等) <8>方块消除游戏(某区间可以连续消去求最大效益) <9>资源分配问题 <10>数字三角形问题 <11>漂亮的打印 <12>邮局问题与构造答案 <13>最高积木问题 <14>两段连续和最大 <15>2次幂和问题 <16>N个数的最大M段子段和 <17>交叉最大数问题 4.判定性问题的dp(如判定整除、判定可达性等) <1>模K问题的dp <2>特殊的模K问题，求最大(最小)模K的数 <3>变换数问题 5.单调性优化的动态规划 <1>1-SUM问题 <2>2-SUM问题 <3>序列划分问题(单调队列优化) 6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大) <1>凸多边形的三角剖分问题 <2>乘积最大问题 <3>多边形游戏(多边形边上是操作符,顶点有权值) <4>石子合并(N^3/N^2/NLogN各种优化) 7.贪心的动态规划 <1>最优装载问题 <2>部分背包问题 <3>乘船问题 <4>贪心策略 <5>双机调度问题Johnson算法 8.状态dp <1>牛仔射击问题(博弈类) <2>哈密顿路径的状态dp <3>两支点天平平衡问题 <4>一个有向图的最接近二部图 9.树型dp <1>完美服务器问题(每个节点有3种状态) <2>小胖守皇宫问题 <3>网络收费问题 <4>树中漫游问题 <5>树上的博弈 <6>树的最大独立集问题 <7>树的最大平衡值问题 <8>构造树的最小环第五篇：ACM算法总结——超有用!
点击咨询 