人生难得糊涂
- 浏览: 114696 次
-
最新评论
-
witcheryne：
apache commons http client 很重.推 ...
HTTPClient模块的HttpGet和HttpPost -
jun4997：
JAVA如何自己写方法读取BMP文件 -
肆无忌惮_：
人生难得糊涂 写道肆无忌惮_ 写道注释好少啊，看不懂 写了个五 ...
人工智能原来如此简单——你所见过的最好的五子棋 -
人生难得糊涂：
肆无忌惮_ 写道注释好少啊，看不懂 写了个五子棋人机算法的PP ...
人工智能原来如此简单——你所见过的最好的五子棋 -
肆无忌惮_：
注释好少啊，看不懂
人工智能原来如此简单——你所见过的最好的五子棋
文章列表
poj2586--求公司盈利
- 博客分类：
- 贪心
题目比较难懂
对于每一个月来说，是盈利如果则盈利S，如果亏空则亏d。
每五个月进行一次统计，共统计八次（1-5月一次，2-6月一次.......）
统计的结果是这八次都是亏空。
问题：判断全年是否能盈利，如果能则求出最大的盈利。
如果不能盈利则输出Deficit
明白题目后1A了
这道题用贪心法解，其实也很容易想到，首先用一个数组记录每个月的盈亏，初始化全部为s,又每五个月统计一次一共统计8次, 所以扫描8次，每次求出五个月的和，如果大于等于0 则从后往前将一个月由s改为d（一定要从后往前，想想为什么）。
代码如下
#include "iostream& ...
poj3080-kmp+枚举子串 求最长公共子串
- 博客分类：
- KMP
因为一直有事这道题又有点繁琐， 所以写了好多天今天才AC，不过1A还是很爽的。
思路还是很简单的，对第一个主串枚举其所有子串，然后将每个子串都与其他的所以主串KMP匹配，如果是所有主串的公共子串则记录 并选出最大的一个 注意这道题要字典序最小
代码：
#include "iostream"
using namespace std;
#define maxsize 80
char c[11][maxsize];
char substring[maxsize];
int next[11][maxsize];
char cans[maxsize]; ...
题意：求既是前缀又是后缀的前缀的可能的长度
忙着考试，好几天没做题了，今天做了几道KMP都是1A，但这道题Output Limit Exceeded 了一次 原因是循环输入的时候没有判断是否遇到了文件末尾
思路比较简单：一直用next下去即可 最后逆序输出
#include "iostream"
using namespace std;
#define maxsize 400010
char c[maxsize];
int next[maxsize];
int len;
int prin[maxsize];
void get_nex ...
poj2406-求主串的周期子串
- 博客分类：
- KMP
题目大意：给出一个字符串，将其分解为若干子串的和，求可分解的最多子串的个数。
做题之前就知道这是一道KMP的题目，但一直没想到怎么写 后面看了下别人的思路（最近写题总是会忍不住看别人的思路 惭愧。。） 得出结论： 一个串的周期子串长度=主串长-next[主串长度]. 然后再用主串长除以周期子串长度就得到了子串周期长度。
下面贴代码
#include "iostream"
using namespace std;
#define len 1000020
char c[len];
int next[len];
int clen;
void getne ...
求一个主串中有多少个给定的子串
直接KMP模板就OK了
#include<iostream>
using namespace std;
#define len 1000100
char s[len];
char t[len];
int next[len];
void getnext()
{
int i=0;
int j=-1;
next[0]=-1;
int lent=strlen(t);
while(i<lent)
{
if (j==-1||t[i]==t[j])
{
i++;
j++;
...
题目大意：一个农夫抓牛，农夫坐标为n，牛坐标为p，农夫有三种移动方式，1.从x到x-1 .2.从x到x+1 3.从x到2*x; 求农夫抓到牛所需移动最少的步数。
思路：做题的时候知道是属于分支限界法这类的题，于是采用BFS ，如果事先不知道的话 可能会用DFS递归搜索。。 重点是在剪枝上，要注意两个方面的剪枝，1是当前节点的值如果大于牛的坐标的话 ，那 x+1 x*2 的移动方式就不入队列（即剪枝）。2是记录走过的节点，走过的节点不再走（这个我很惭愧的没想到，一直TLE后老师说了以后再AC的）。
具体看代码
#include<iostream>
#include& ...
题目大意：
就是给一个 p*q的棋盘，一个骑士从任意位置出发，要求遍历棋盘所有的位置（骑士按‘日’字走）。
思路：
把A1这个位置当做起点，然后按字母表方向（题目要求）搜索，如果位置可以走则再从新位置往下走（其实就是深度搜索）。
注意每种情况输出完以后还要输出一个空格。
#include<iostream>
using namespace std;
#define len 30
int p,q;
int tot;
int map[len][len];
int movx[]={-2,-2,-1,-1,+1,+1,+2,+2};
int movy[]={-1,+ ...
题目大意：有f朵花要插到v个花瓶里面去。。。不同的花插到不同的花瓶有不同的美观程度，求最大的美观程度，，还有一个限制条件，如i>j，则编号为i的花能插的花瓶编号也必须大于 编号为j的花所插花瓶的编号。（因为没有注意到这个条件，我想了n久~）。
好的我们说思路
理解题意后还是比较好写的，这里又有花又有花瓶的，肯定是用二维dp啦。假设dp[i][j],为第i朵花插到第j个瓶子中能获得的最大美观程度，dp[i][j]=max(dp[i-1][k]+a[i][j]),k>=i-1&& k<j ,a[i][j]为给出的每朵花对应花瓶的美观程度.
#i ...
poj1042贪心钓鱼
- 博客分类：
- 贪心
题目大意：
一个人去钓鱼 ，有n个湖排成一行，他以第一个湖为起点，从一个湖到下一个湖需要 时间t[i]。第i个湖的鱼一开始每单位时间（以5分钟为单位）能钓上的鱼为f[i],每掉5分钟，则每个单位时间能掉上的鱼减少d[i]。求能掉上的最大的鱼的数目。以及在每个湖所呆的时间（可能有多个情况，要求的是尽量在一个湖呆长一点时间的情况）。
解题思路：假如我们走路不需要时间的话，那么这道题就变的简单了，直接用贪心策略，哪个湖现在每单位时间能钓的鱼数目最多，则在哪个湖钓。
我们假设只在前i个湖钓鱼，那么我们走路的时间是不是可以求出来了。那么求出这个时间以后，用总时间减去走路时间就得到了能用与钓鱼的时 ...
POJ1651-类似矩阵连乘问题
- 博客分类：
- 动态规划
题意：给定n个数，每次取其中一个数（第一个数和最后一个数不能取），得分+=这个数乘以它左边的数和右边的数。要求最后的得分最小。
思路：因为开始知道这个题的DP方程和矩阵连乘的DP方程一样，所以一直根据方程想思路，结果想了很久都没想出来，最后看了评论区的大神提示，瞬间想通。看来自己实力还是很渣渣啊。。唉
我们假设只有a1,a2,a3三个数，那我们只能取a2，那最后的得分=a1*a2*a3; 假如有n个数，设k为最后一个取出来的数，那么，最后一次的得分只与a1,an,ak有关，那么我们把整个区间以k分成两段，左边一段的最后一次得分必然为a1*ak*ai(i>1 &&i ...
正在学习五子棋的开发，现在是第一步，一切都还是渣渣，给新手看看。
简陋的界面。。
代码没什么难度，唯一需要注意的地方就是判断鼠标点击屏幕，需要在哪里出现棋子。
package data0609_五子棋;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener; ...
题意就不说了很容易懂，说一下思路。 这道题问的是怎样放雷达使其放的雷达数目最少而能够探测到所有的岛屿，这里需要转换为求每个岛屿的能放雷达的区间的问题，。如下图
然后我们以每个区间的最右端排序，排完以 ...
BMP图像解析
BMP是一种与硬件设备无关的图像文件格式，使用非常广。它采用位映射存储格式，除了图像深度可选以外，不采用其他任何压缩，因此， BMP 文件所占用的空间很大。 BMP 文件的图像深度可选 lbit 、 4bit 、 8 ...
POJ3624-01背包问题
- 博客分类：
- 动态规划
该题就是原版的01背包问题，没有任何改变，唯一需要注意的是需要用到滚动数组，（因为开不了那么大的二维数组），做完这个后在discuss中看到有人贴出的代码只需要一个数组就可以完成，很是有趣，学习了
先贴我自己写的滚动数组的代码
#include<iostream>
using namespace std;
#define len 3500
#define maxw 14000
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n,tot,i,j,w[len],d[len ...
定义于字母表∑{a,b,c)上的乘法表如表1所示
a
b
c
a
b
b
a
b
c
b
a
c
a
c
c
依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。例如,对于字符串x=bbbba,它的一个加括号表达式为 i(b(bb))(ba)。依乘法表,该表达式的值为a。试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括 号方式,使由x导出的加括号表达式的值为a要求： 输入：输入一个以a,b,c组成的任意一个字符串。 输出：计算出的加括号方式数。
...