poj3358 Period of an Infinite Binary Expansion 数论有难度
这道题目感觉好难，根本就是无从下手的感觉，尝试了以前的所有方法，都没有思路，毫无进展，参考了一下别人的思路，感觉学到了新的知识接下来开始分析观察1/10这组数据，按照二进制转化法可以得到： 1/10 2/104/108/1016/1032/10.……对于每一个分子进行模10处理 可以相应的得到： ...
poj 3358 Period of an Infinite Binary Expansion
由乘2取整得到分数的小数位，可以找到规律！！！例如：1/10，2/10，4/10，8/10，16/10，32/10，64/10……取整后：1/10，2/10，4/10，8/10，6/10，2/10，4/10……这样我们就发现规律了！！！也就是对于p/q而言，要满足2^x=2^y mod q (gcd...
poj 2074 Line of Sight 计算几何
/** 大意：给定一个建筑--水平放置，给定n个障碍物， 给定一条街道，从街道上能看到整个建筑的最长的连续的区域 思路： 分别确定每一个障碍物所确立的盲区，即----建筑物的终点与障碍物的起点的连线，建筑物的起点与障碍物的终点的连线。。这段区域即为盲区，，，有多个盲区，需要去重。。 学习之处： 1...
ST表poj3264
/*ST表多次查询区间最小值设 g[j][i] 表示从第 i 个数到第 i + 2 ^ j - 1 个数之间的最小值类似DP的说 ans[i][j]=min (ans[i][mid],ans[mid+1][r])mid=(l+r)/2but 数太大装不下 所以改一个g数组出来就好了接下来考虑 g[...
Jury Compromise POJ - 1015 dp （标答有误）背包思想
题意:从 n个人里面找到m个人 每个人有两个值 d p 满足在abs(sum(d)-sum(p)) 最小的前提下sum(d)+sum(p)最大思路：dp[i][j] i个人中 和是 j 运用背包的思想 二维背包 i是人数容量，人数要符合背包思想，每次只插入一个，逆序...
POJ - 2528 Mayor's posters （离散化+线段树区间修改）
https://cn.vjudge.net/problem/POJ-2528题意给定一些海报，可能相互重叠，告诉你每个海报的宽度（高度都一样的）和先后叠放顺序，问没有被完全盖住的有多少张？分析海报最多10000张，但是墙有10000000块瓷砖长，海报不会落在瓷砖中间。如果直接建树，就算不TLE,也...
HDU 1513 && POJ 1159 Palindrome (DP+LCS+滚动数组)
题意：给定一个字符串，让你把它变成回文串，求添加最少的字符数。析：动态规划是很明显的，就是没有了现思路，还是问的别人才知道，哦，原来要么写，既然是回文串，那么最后正反都得是一样的，所以我们就正反求LCS，这样公共的就求出来了，那么再用总数减掉这个LCS，那么剩下的肯定就是没有配对的了，就得必须加上了...
数论-质数 poj2689,阶乘分解，求阶乘的尾零hdu1124, 求尾零为x的最小阶乘
/*要求出[1,R]之间的质数会超时，但是要判断[L,R]之间的数是否是素数却不用筛到R因为要一个合数n的最大质因子不会超过sqrt(n)所以只要将[2,sqrt(R)]之间的素数筛出来，再用这些素数去筛[L,R]之间的合数即可*/#include<iostream>#include&l...
poj 1159 Palindrome 【LCS】
任意门：http://poj.org/problem?id=1159解题思路：LCS + 滚动数组AC code：#include <cstdio>#include <iostream>#include <algorithm>#define INF 0x3f3f3...
动态规划+滚动数组 -- POJ 1159 Palindrome
给一字符串，问最少加几个字符能够让它成为回文串。比方 Ab3bd 最少须要两个字符能够成为回文串 dAb3bAd思路：动态规划 DP[i][j] 意味着从 i 到 j 这段字符变为回文串最少要几个字符，枚举子串长。if str[i] == str[j]:DP[i][j] = DP[i + 1][j ...
POJ 1159 Palindrome(字符串变回文:LCS)
POJ 1159 Palindrome(字符串变回文:LCS)id=1159">http://poj.org/problem?id=1159题意:给你一个字符串, 问你做少须要在该字符串中插入几个字符能是的它变成一个回文串.分析:首先把原字符串和它的逆串进行匹配, 找出最长公共子序列. 那么最...
poj - 1159 - Palindrome（滚动数组dp）
题意：一个长为N的字符串( 3 <= N <= 5000)。问最少插入多少个字符使其变成回文串。题目链接：http://poj.org/problem?id=1159——>>状态：dp[i][j]表示第i个字符到第j个字符组成的字符串变成回文串的最少插入次数。状态转移方程：若...
POJ 1159 Palindrome(区间DP/最长公共子序列+滚动数组)
PalindromeTime Limit: 3000MS Memory Limit: 65536KTotal Submissions: 56150 Accepted: 19398DescriptionA palindrome is a symmetrical string, that is, a s...
POJ 2418 ，ZOJ 1899 Hardwood Species - from lanshui_Yang
Description Hardwoods are the botanical group of trees that have broad leaves, produce a fruit or nut, and generally go dormant in the winter. Americ...
poj1552
DoublesTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 18824 Accepted: 10846DescriptionAs part of an arithmetic competency program, your stu...
POJ 3126 primepath bfs
题目链接：http://poj.org/problem?id=3126题意：1维的坐标轴，给出起点和终点，求从起点到终点变换经历的最短的步数。起点，终点和中间变换的数字都是4位，而且都是质数。思路：普通的广搜、精神状态不佳、找了许久的bug。后来发现是prime函数和pow函数都很丧心病狂的写错了、...
C# ACM poj1007
求逆序数，快排 public static void acm1007(int a, string[] c) { Dictionary<int, string> dic = new Dictionary<int, string>(); ...
暴力求解——POJ 3134Power Calculus
DescriptionStarting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:x2 = xxx, x3 = x2xx, x4 = x3xx, ...
Count Color(线段树+位运算 POJ2777)
Count Color Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 39917 Accepted: 12037Description Chosen Problem Solving and Program...
POJ 1321 棋盘问题（DFS & 状压DP）
用DFS写当然很简单了，8！的复杂度，16MS搞定。在Discuss里看到有同学用状态压缩DP来写，就学习了一下，果然很精妙呀。状态转移分两种，当前行不加棋子，和加棋子。dp[i][j]中，i代表行数，j代表当前行棋子的状态。j的二进制中，1代表有旗子，0代表无棋子。贴代码~状压DP果然快一点。#i...