poj题目

时间:2022-09-24 07:37:59

poj2965 poj1753:标准的BFS+位运算优化

poj1328:线段覆盖变种,把圆对应到线段上,贪心求解

poj2109:高精度开根,二分+高精度,注意要判断答案的位数,如果按照题目给的范围二分会TLE

poj2586:给十二个月定盈亏(每个月+s或-d),连续5个月总的需要时亏,求12个月的总的最大盈利。枚举或者贪心,贪心的话就尽量把亏损的放在连续五个月的后面,这样使得-d尽可能少

poj3295:枚举所有bool变量的取值,然后带入算

poj3259:裸的spfa判断负还

poj1062:最短路变种。在最短路的前提下定义每个点的等级,等级差>M的两个点无法在一条路径上,求最短路。刚开始考虑把不符合的构造成一个负环,后来发现这样仍然会造成路径上不可能存在的边更新,正确做法是枚举最小等级,把所有等级符合的点和边加进去成为新图,求最短路

poj1860:

poj2253:MST问题。求S到T点的所有路径中的最大值的最小值。典型的求最小生成树的最大边

poj3041:二分图最小点覆盖=最大匹配,匈牙利算法

poj3020:无向图的最小边覆盖。拆点成二分图,ans=|P|-最大匹配/2

Poj3080:求多个字符串的最长公共子串。经典的后缀数组应用

poj3274:题意是要找到满足s[r][0..k-1]与s[l][0..k-1]对应位置差相等的最大的r-l,将问题转化成s[r][i]-s[r][i-1]==s[l][i]-s[l][i-1]这种,然后就能单独处理一个位置的数组信息,问题即要求两个相同数组的最远间距,这个用hash就可以了

poj2151:有T个人参加比赛,共有M道题,第 i 个人通过第 j 题的概率为 p[i][j] 求:所有人都至少做出一道题,而且第一名至少做出N道,求这个结果的概率。f[i][j][k]表示第i个人,前j道题,做出k道的概率,很方便可以递推出。ans=所有人至少做一道题概率-所有人至少做出题但是都小于N道的概率,前面这个直接减,后面这个循环枚举做出几道相减
poj1840:求给定五元三次方程在给定定义域上的解的个数,直接枚举TLE,可以先枚举左边三个,将其值放在HASH表中,再枚举右边两个,和hash表中的配对
poj2020:
poj2513:Trie,然后判断是否为欧拉路,统计每个点度数、并查集判连通(目前仍然RE)
poj3083:每层搜索搜索顺序不同的DFS,搜的过程中保留记录当前方向,并根据当前方向决定不同的搜索顺序
poj1837:固定天平钩子的位置和勾码的数目和重量,求天平平衡的方案数。f[i][j]表示前i个砝码,力臂和为j的方案数,ans=f[n][0],转移的时候平移一下,这里将钩子的位置视为每个物品的数量 
poj1276:
poj3267:区间DP,单词的开头和结尾把S分为连续的若干段区间,所以可以区间DP,注意考虑一段区间全删除的情况(初始值)
poj1159:给你一个字符串,至少加多少字符让其变成回文串。加一个字符等价于删除它对应的字符,所以问题转化成最少删掉多少字符使其变成回文串,也就是在原串中找到最长的可以跳跃的回文串,于是就想到把原串翻转过来,两个串做一个LCS
poj3252:
poj1019:f[i]表示第i组数的尾部在第f[i]个位置,从而对于一个询问就能找到对应的组,在哪个组中继续寻找就行了
poj1942:就是求C(n,m)的问题……然而这题n,m很大,但是没mod,保证结果不需要高精度。n,m达到了2^32,筛选出素数把每项因式分解也办不到……然后看了题解,竟然把当做double类型一项一项除,最后强行转成longlong类型……
poj2635:高精度数取单精度模问题,将高精度数几位压成一位加速除法过程,我是压了9位
poj2115:
poj1905:二分角度判定是否符合题意,注意double类型输出的时候一定要用.f!不能用.lf!
poj1286:Polya定理,这题注意一点就是循环置换的循环个数的计算。
      比如求置换:(  1 ,  2,   3,........... n)
            (i+1,i+2,......1 , n.... i)
     有多少个循环。
     假设从位置x开始,那么依次是x,x+i,x+2*i,...x+t*i,x
       即(x+t*i)%n=x,即t*i%n=0
              所以t=lcm(i,n)/i,循环节长度为t,那么循环个数就是n/t=gcd(n,i)
       此题注意要讨论下奇偶性  
poj3270 置换群,:http://www.cnblogs.com/wmrv587/p/3530506.html
poj3007:主要是字符串判重,用trie判重,用set或者map会TLE
poj1201:差分约束问题,注意这里线段是闭区间,所以对于[ai,bi]要将其表示为[ai,bi+1)
poj2983:

poj题目的更多相关文章

  1. (转)POJ题目分类

    初期:一.基本算法:     (1)枚举. (poj1753,poj2965)     (2)贪心(poj1328,poj2109,poj2586)     (3)递归和分治法.     (4)递推. ...

  2. poj 题目分类(1)

    poj 题目分类 按照ac的代码长度分类(主要参考最短代码和自己写的代码) 短代码:0.01K--0.50K:中短代码:0.51K--1.00K:中等代码量:1.01K--2.00K:长代码:2.01 ...

  3. POJ题目(转)

    http://www.cnblogs.com/kuangbin/archive/2011/07/29/2120667.html 初期:一.基本算法:     (1)枚举. (poj1753,poj29 ...

  4. [POJ题目分类][转]

    Hint:补补基础... 初期:一.基本算法:     (1)枚举. (poj1753,poj2965)     (2)贪心(poj1328,poj2109,poj2586)     (3)递归和分治 ...

  5. Poj 题目分类

    初期:一.基本算法:     (1)枚举. (poj1753,poj2965)     (2)贪心(poj1328,poj2109,poj2586)     (3)递归和分治法.     (4)递推. ...

  6. POJ题目排序的Java程序

    POJ 排序的思想就是根据选取范围的题目的totalSubmittedNumber和totalAcceptedNumber计算一个avgAcceptRate. 每一道题都有一个value,value ...

  7. POJ 题目分类(转载)

    Log 2016-3-21 网上找的POJ分类,来源已经不清楚了.百度能百度到一大把.贴一份在博客上,鞭策自己刷题,不能偷懒!! 初期: 一.基本算法: (1)枚举. (poj1753,poj2965 ...

  8. POJ题目分类(按初级\中级\高级等分类,有助于大家根据个人情况学习)

    本文来自:http://www.cppblog.com/snowshine09/archive/2011/08/02/152272.spx 多版本的POJ分类 流传最广的一种分类: 初期: 一.基本算 ...

  9. POJ题目分类

    POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)初期: 一 ...

  10. POJ题目分类(转)

    初期:一.基本算法:     (1)枚举. (poj1753,poj2965)     (2)贪心(poj1328,poj2109,poj2586)     (3)递归和分治法.     (4)递推. ...

随机推荐

  1. (转载)python2+selenium自动化测试系列(一)

    1.Selenium2+python自动化1-环境搭建 2.Selenium2+python自动化2-pip降级selenium3.0 3.Selenium2+python自动化3-解决pip使用异常 ...

  2. killall 根据名称终止进程

    根据名称终止进程 killall [option] name-list killall 将信号发送到一个或多个进程用来终止它.除超级用户外,只有进程的所有者才可以对进程执行killall,超级用户可以 ...

  3. PHP环境下Memcache的使用方法

    原文:PHP环境下Memcache的使用方法 原文地址:http://www.2cto.com/kf/201503/384967.html 如今互联网崛起的时代,各大网站都面临着一个大数据流问题,怎么 ...

  4. Linux在目录中查找某个函数

    1,在某个路径下查文件. 在/etc下查找“*.log”的文件 find /etc -name “*.log” 2,扩展,列出某个路径下所有文件,包括子目录. find /etc -name “*” ...

  5. poj2154-color-polyan次二面体+欧拉函数优化

    N<=1e9,O(nlogn)的做法会超时.从枚举置换转变为枚举轮换长度,然后可以利用欧拉函数,把复杂度变为O(√n * logn) /*---------------------------- ...

  6. sqlserver2012相关资源下载

    1.输入网址http://www.codeplex.com 2.找到Microsoft SqlServer Product Samples选项 3.进入之后显示如下页面 4.选择SQL Server ...

  7. hdu-5683 zxa and xor &lpar;位运算&rpar;

    题目链接: zxa and xor Time Limit: 16000/8000 MS (Java/Others)     Memory Limit: 65536/65536 K (Java/Othe ...

  8. android 分享到新浪微博

    分享到新浪微博,折腾了大半个月,现在终于弄出来了,心里的那个爽呀,太痛快了,哈哈!! 废话少说,首先是认证, 1.进入新浪微博提供的开放平台注册新浪账号. 2.点击’我是开发者‘,创建一个应用,得到C ...

  9. Android 查看通讯录Contacts是否发生变化

    目的:确定通讯录是否发生变化 根据:參见ContactsContract.RawContacts类中的VERSION常量,该值是仅仅读的,当通讯录发生变化时,都会使该值变化 方法:version值是相 ...

  10. 【C语言探索之旅】 第一部分第九课:函数

    内容简介 1.课程大纲 2.第一部分第九课:函数 3.第一部分第十课预告: 练习题+习作 课程大纲 我们的课程分为四大部分,每一个部分结束后都会有练习题,并会公布答案.还会带大家用C语言编写三个游戏. ...