darren_nizna
- 浏览: 72574 次
- 性别:
- 来自: 长沙
-
最新评论
-
nhy338：
mark,留着以后看
使用MethodInterceptor实现AOP -
爪哇夜未眠：
这个是spring里面的方法拦截
使用MethodInterceptor实现AOP -
sunnylocus：
做下标记，明天有空仔细研究下方法拦截，感觉这是好东西！
使用MethodInterceptor实现AOP -
nwwhbp：
都是些基础的东西，学习了，谢谢LZ的分享。
Kingsoft西山居笔试试题
文章列表
题意为给定一个矩形，矩形中有一些点，要使一个半径为 r 的圆穿过这个矩形而不经过这些点，至少得去掉这些点的几个点。 将上边界看成源，下边界看成汇，点到源距离小于直径，则边一条无穷大边，同样，点到下边界距离小于直径，连一条无穷大边，将点拆成两点，权值为 cost, 对任意两点，距离小于直径则连无穷边，问题就转化成求新图的最小割。
具体建图见代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int const N= 250, ...
题意：给你 n 个单词，求出满足以下条件的单词个数：长度不大于 L 且单词中至少包含一个子串为前面 n 个单词中任意一个。先求出所有单词的数量 26^1+ 26^2+ ... + 26^L，可以用矩阵乘法求出，也可用逆元的方法。然后求出所有不包含 n 个单词的串的数量，这个求法和 pku 2778 相同，只是这里要求出所有长度不大于 L 的字符串数量和，方法参考 pku 3233。两者相减就是答案。对那个 2^64 求余，用unsigned __int64 存储的数据，相乘溢出后剩下的结果，就直接是对2^64取模的结果。
#include <iostream>
#inclu ...
LTC 男人八题之一，解题报告见09看论文。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int const N= 10010, inf= 0x7fffffff;
int n, k, cnt, tot, root, size, nchild, first, last, pre, ans;
int Fnum;
struct ...
这题杯具的写了一下午，真是太菜了。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
int const N= 100010;
int n, m;
struct Node{
int Lx1, Rx1, Ax1;
int Lx0, Rx0, Ax0;
int op1, op2, op3;
int num;
};
Node tb[N ...
先用AC自动机构建一个不含有任何病毒串的 DFA ， dp[i][j] 表示到目标串的第 i 个字符，DFA 状态为 j 时的最小修改数量。则 dp[i][ son[j] ]= min{ dp[i][ son[j] ], dp[i-1][j]+ (tran[j][ son[j] ]!= str[i] ) } tran[j][ son[j] ]表示从 j 到 son[j] 经过的字母边。
代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define min(a ...
利用AC自动机构建一个 DFA， 该 DFA 不经过任何模式串。然后问题转化为在一个图上找经过 n 条边的路径条数。
代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef long long LL;
int n, m, cnt= 0;
LL mat[200][200]= {0};
struct Node{
int next[4];
int fail, flag;
void init(){
for( int i= 0; i< ...
查找多个串是否在目标串中出现，简单的AC自动机应用。。。
代码：
#include <iostream>
using namespace std;
struct Node{
int next[100];
int fail, flag;
void init(){
for( int i= 0; i< 100; ++i ) next[i]= 0;
fail= -1; flag= 0;
}
};
Node tb[100000];
int n, cnt, m;
char str[10010];
int mark[1010];
...
原题链接：http://codeforces.com/contest/12/problem/D
给一系列三维点(x,y,z)。求出满足以下条件的点个数： 对点 (x1,y1,z1 ) , 存在一个点 (x2,y2,z2) 使得 x2> x1, y2> y1, z2> z1。
先按 x 从大到小排序，再将 y 离散化。从前到向扫描，对于点(x,y,z), 在大于 y 的区间内找到最大的 z1，如果 z1> z, 则答案加 1.
代码：
#include <iostream>
#include <cstdio>
#include & ...
问题最终转化为，求出 height 数组后，求 max{ (j- i+ 1)* ( min( height[i..j] ) ) }，相当于找一个最大的矩形。
求F(a^b)% c 因为 c 比较小，可求出其循环节。
代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef __int64 LL;
int const N= 200110;
int wa[N], wb[N], ws[N], wv[N];
int rank[N], height[N], s ...
给你 n 个字符串，求出最长的子串，使得子串在大于一半的字符串中都出现。
先将 n 个字符串用 n 个不同的字符连接起来。求出 height 数组后，二分子串长度 k, 查找是否存在连续的大于 n/ 2+ 1 个后缀的 height 值都大于 k。这里要求这 n/ 2+ 1 都属于不同串，可以用一数组进行标记，具体做法详见代码。
代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
int const N= 200100;
int wa[N], wb[N], wv[N], ...
先将数据按 a_i 从小到大排序，然后直接背包。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
struct Node{
int h_i, a_i, c_i;
};
bool operator<( Node a, Node b ){
return a.a_i< b.a_i; }
Node dat[410];
int dp[4001 ...
题目意思可以归结为给一个字符串，求可重叠的 k 次最长重复子串。
二分 k ，然后在 height 数组中找是否存大连续 k 个数都大于 k。
代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int const N= 1000100;
int wa[N], wb[N], ws[N], wv[N];
int rank[N], sa[N], height[N], r[N], n, k;
int cmp( int* r, int a, int b, int L ...
题意在一个整数序列中求出相邻元素相差不超过 m 的最长子序列。
易得到 dp 方程。 dp[i]= max{ dp[j]+ 1, 1<= j < i 且 d[i] 与 d[j] 相差不超过 m } 方程复杂度为 o(n^2) 。
用线段树对方程进行优化，先将数据离散化，使得数据范围变成 [1,n]。在上述方程求 dp[i] 的值时，对 i 前面的数遍历找出最优值相当于在区间 [ d[i]- m, d[i]+ m ] 内找出最优值，这个可以用线段树优化，使得复杂度达到 nlogn。
代码：
#include <iostream>
#include <c ...
1.给你一棵边带权的树，求出树中每一个点到其它点的最大距离。
2.在一个整数序列中找一个最大的连续序列，使得该序列中最大数和最小数之差不超过 m 。
问题 1 可用树形 DP 解决。对树进行 DFS，DFS 过程中，对根 R，记录他的孩子结点到他是最大距离和次大距离以及相应的结点。然后用一次 BFS 更新。
问题 2 用两个指针 head, tail分别指向连续序列的首尾，如果区间 [head,tail] 满足条件，则 tail++,更新值最大最小值，不满足条件则 head++, 用线段树更新最大最小值。
注意图不能用 STL 的 vector 和 pair 保存，这样会 TLE。 ...
题目意思为有一系列村庄，然后对一些村庄进行破坏或修复。让你求与某村庄直接或间接相连且都没有破坏的村庄数量。
对于每一个区间，用线段树维护从区间左端点开始的最大连续没破坏的村庄数量 Lx 以及以区间右端点结点的最大连续没破坏的村庄数 Rx，很容易更新这两个值及求出要求的数量。
代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace st ...