题目链接：poj 1625 Censored!
题目大意：给定N，M，K，然后给定一个N字符的字符集和，现在要用这些字符组成一个长度为M的字符串，要求不包
括K个子字符串。
解题思路：AC自动机+DP+高精度。这题恶心的要死，给定的不能匹配字符串里面有负数的字符情况，也算是涨姿势
了，对应每个字符固定偏移128单位。
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <...
阅读全文
题目连接：zoj 3228 Searching the String
题目大意：给定一个字符串，然后现在有N次询问，每次有一个type和一个子串，问说子串在字符串中出现几次，type
为0时为可重叠，为1时为不可重叠。
解题思路：不过没有type=1的限制，那么就是普通的AC自动机匹配问题，对于不可重叠问题，可以对于每个节点记录
一下上一次匹配到的pos，用当前匹配的i减掉pos看有没有超过长度，有超过即为合法匹配，否则忽略。
题目中有很多相同的...
阅读全文
题目链接：poj 1699 Best Sequence
题目大意；给定N个DNA序列，问说最少多长的字符串包含所有序列。
解题思路：AC自动机+状压DP，先对字符串构造AC自动机，然后在dp[s][i]表示匹配了s，移动到节点i时候的最短步数。
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,i...
阅读全文
题目链接：zoj 3494 BCD Code
题目大意：给定n个2进制串，然后有一个区间l，r，问说l，r之间有多少个数转换成BCD二进制后不包含上面的2进制串。
解题思路：AC自动机+数位dp。先对禁止串建立AC自动机，所有的单词节点即为禁止通行的节点。接着进行数位dp，
用solve(r) - solve(l-1), 这里的l需要用到大数减法。dp[i][j]表示第i为移动到节点j的可行方案数，每次枚举下一位数字，因
为是BCD二进制，所以每位数要一次性移动4...
阅读全文
题目链接：http://poj.org/problem?id=1661
标准的DP，首先将输入数据按高度进行排序,将开始下落的位置初始化为左右坐标均为x,高度为y的平台(方便统一处理)，然后从上至下搜寻最短路径。。
DP的思想已经掌握了，但是各种细节的处理还是远远达不到，这里贴出大神的代码，以示参考
#include<stdio.h>
#include<string.h>
#include<memory.h>
#include<stdlib.h>
#define INF 1000000
st...
阅读全文
重点：
（1）函数式编程建议的是：对象的状态在发生变化是创建一个新的对象，而不是修改现有对象的内部状态，这样有利于并发安全
（2）在scala中一切都是对象，就我们看到的+，-，×，%都是对象
Java中类的定义：
public class JavaPerson
{
public JavaPerson(String firstName, String lastName, int age)
{
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
...
阅读全文
一道递推
#include<iostream>
using namespace std;
__int64 Gcd(__int64 x,__int64 y)
{
if(x==y)return x;
if(x==1||y==1)return 1;
__int64 r;
if(x<y)
{
r=x;
x=y;
y=r;
}
while(y!=0)
{
r=x%y;
x=y;
y=r;
}
return x;
}
int main()
{
char mark[51][101];
__int64 sum[51][101];
__int64 finalsum;
int i,j;
int n,n1,m;
int colnum;
int spoint;
int epoint;
int count;
__int...
阅读全文
在已有的边上做Prim
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
#define infinity 1000000
class Point2D
{
public:
double x,y;
};
Point2D point[1001];
double map[1001][1001];
double dis[1001];
bool flag[1001];
int n,m;
int main()
{
memset(flag,false,sizeof(flag));
int c,i,j,k;
double len;
double minone;
scanf("%d%d",&n,&m);
for(...
阅读全文
重构二叉树，已知前序和中序，输出后序。
#include <iostream>#include <cstring>using namespace std;
struct treeNode{ treeNode(); char letter; treeNode* left; treeNode* right;};treeNode::treeNode(){ left=NULL; right=NULL;}void AddNode(treeNode* node,bool left,bool right,char ch){ treeNode* tmpNode=new treeNode; tmpNode->letter=ch;
if(true==left) { node->left=tmpNode; } else { ...
阅读全文
因为最近想做的一个东西和区间统计有关，心血来潮玩了下线段树。
#include<iostream>
using namespace std;
#define MAXNUMBER 1<<30
class TreeNode
{
public:TreeNode();int leftIndex;int rightIndex;int maxHeight;int minHeight;TreeNode* leftNode;TreeNode* rightNode;
};
TreeNode::TreeNode()
{leftIndex=0;rightIndex=0;maxHeight=-1;minHeight=MAXNUMBER;leftNode=NULL;rightNode=NULL;
}
...
阅读全文