信仰 忍耐
darren_nizna · 共 31 篇文章
[LeetCode] Find Minimum in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2 ). Find the minimum element. You may assume no duplicate exists in the array. 代码: class Solution { public: int findMin(vector<int> &num) { int i = 0, j = num.size() - 1; while(…
2014-10-17 17:19 · 程序笔试 · 评论(0)
[LeetCode]Maximum Product Subarray
这题如果没有负数和0,答案就很简单了,所有数的乘积。有负数和0就要复杂一些。 先考虑只有正数和负数而没有 0 的情况: 负数是偶数个。答案也很简单,所有数的乘积。 负数是奇数个。那就要枚举这个负数位置,将序列分成两部分,取乘积大的那部分。 然后再考虑数据中有 0 的情况,这时我们可以将整个序列以 0 进行分割成多个子序列,每个子序列的处理和情况 1 一样。 class Solution { public: int noZero(int A[], int start, int end) { // 没有 0 的子序列 int ans = A[start], left = 1, right = 1…
2014-09-24 13:53 · 程序笔试 · 评论(0)
使用MethodInterceptor实现AOP
1. 先写出业务对象接口及实现业务对象。 public interface Interface { public void hello(); } 这里写俩个实现。 public class InterfaceImpl implements Interface { /** * @see com.alipay.aop.BusinessInterface#hello() */ @Override public void hello() { System.out.println("AOP TEST!!"); } } public class InterfaceImplTest implements …
2011-08-25 11:13 · [JAVA]java语言 · 评论(3)
菜单级联简单例子
<%@ page contentType="text/html; charset=GBK"%> <html> <head> <title>下拉列表联动</title> </head> <body bgcolor="#ffffff"> <table> <tr> <td><select name="s1" onChange="haha()"> <option value="null">请选择 <option value="1">1 <option value="2">2 <option value="3">3 <option value="4">4 </select> </td> <td id=…
2011-05-06 18:19 · javascript · 评论(0)
linux下读取日志文件上传到服务器
日志文件会不断的增加,这个程序能上传这不断增加的日志文件到服务器,以便服务器分析。 #include <sys/socket.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <sys/sendfile.h> #define SA struct sockaddr /** * 如果出现错误,程序返回 0, 错误信息保存在 error 数组中 * server 服务端的 IP, 字符串表示 如 “192.168.1.1…
2011-04-28 14:19 · [Linux] · 评论(0)
[ZJU/ZOJ][2859][Matrix Searching][二维fRMQ]
#include <stdio.h> #include <stdlib.h> #include <string.h> #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) int const N= 302; int mat[N][N], n, q, pos[N]; int dMin[9][9][N][N]; void initRMQ(){ int i, j, u, v, a, b, c, d; for( pos[0]= -1, i= 1; i<= n; ++i ) pos[i]= ( ( i& (i- 1)…
2010-09-17 13:10 · [数据结构]RMQ · 评论(0)
[HNOI2008][玩具装箱toy][斜率优化]
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; int const N= 50010; int n, L; typedef long long LL; LL dp[N], sum[N], A[N], B[N]; int que[N], data[N]; /* dp[i]= min{ dp[j]+ ( s[i]- s[j]+ i- j- 1- L )^2 } 令 A[i]= s[i]- i; B[j]= s[j]+ j+ 1+ L 原方程化为 dp[…
2010-08-06 13:55 · [动态规划]dp优化 · 评论(0)
[HDU][3045][Picnic Cows][斜率优化]
#include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; #define min(a,b) ( (a)< (b)? (a): (b) ) int n, m; int const N= 400100; typedef long long LL; /* dp[i]= min{ dp[j]+ sum[i]- sum[j]+ ( i- j )* data[j+ 1] } 要求分段的序列长度不小于 m,即 i- j+ 1>= m 假设 j> k, 要使决策 j 比决策 k 优, 则有 dp[j]+ su…
2010-08-05 10:42 · [动态规划]dp优化 · 评论(0)
Kingsoft西山居笔试试题
一.填空题: 1. Char szTest[]=”12345\t\n\0abcd\0”; 则 strlen(szTest)值为____, sizeof(szTest)值为___ 2. Int anTest[5][10]; int n1= &anTest[4]- &anTest[10], n2= &anTest[3][1]- &anTest[1][3]; 则 n1 的值为_____. 3. Char szNum[]=”123456789”; int n= *(short*)(szNum+ 4)- *(short*)(szNum); 则 n 的值为_____. 4. STL中二分查找算法函数名称…
2010-06-21 11:53 · 程序笔试 · 评论(1)
[HDU][3415][Max Sum of Max-K-sub-sequence][线段树]
原题意思是求一个不超过 k 的连续序列的和的最大值。 枚举连续序列的起点 i, 然后在 [i, i+k] 区间找一个最大值,更新答案。 #include <stdio.h> #include <stdlib.h> #include <string.h> #define max(a,b) ( (a)> (b)? (a): (b) ) #define min(a,b) ( (a)< (b)? (a): (b) ) int const N= 200010; int dat[N], sum[N]; int n, nn, k; struct Node{ int Max, pos; Node(){} N…
2010-06-05 17:03 · [数据结构]线段树 · 评论(0)
[HDU][3416][Marriage Match IV][网络流]
先求出最短路径,然后用最短路径上的边构建一个新图,在新图上求最小割。 #include <iostream> #include <queue> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> using namespace std; int const N= 1010, M= 200010; int n, m; int const inf= 0x7fffffff; int res; struct Node{ Node(){} Node(int a,int b ):adj(a), wt(b) {…
2010-06-05 17:00 · [图论]网络流 · 评论(0)
[ZOJ/ZJU][3190][Resource Archiver][AC自动机]
给你 n 个串,和 m 个病毒串。要把这 n 个串连起来来,可以重叠,但不能包含 m 个病毒串中的任意一个。求把 n 个串连起来的最小长度。 #include <iostream> #include <bitset> #include <cstdio> #include <cstdlib> #include <queue> using namespace std; int const N= 1010, M= 60010; int n, m, cnt, bit[15]; char str[N]; struct Trie{ int next[2]; int fail, end; void ini…
2010-05-28 23:07 · [字符串]AC自动机 · 评论(0)
[ZJOI2010]network 网络扩容
给定一张有向图,每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求: 1、 在不扩容的情况下,1到N的最大流; 2、 将1到N的最大流增加K所需的最小扩容费用。 求出最大流后,残余网络的流量不变,费用改为 0. 对原图的每一条边,对应增加一条流量为 k,费用为 w 的边,再增加一个源,源到 1 的流量为 k,费用为 0。求最小费用最大流,即为第二问答案。 #include <stdio.h> #include <stdlib.h> #include <string.h> #define min(a,b) ( (a)< (b)? (a): (b) ) #defin…
2010-05-27 17:36 · [图论]网络流 · 评论(0)
[AHOI2009][Mincut 最小割]
判断边是否在某个最小割集中 以及 判断边是否为最小割的必需边。 在残余网络中求出强连通分量,对于不在同一强连通分量且满流的边,必然在某一最小割中。 题目链接 #include <stdio.h> #include <stdlib.h> #include <string.h> #define min(a,b) ( (a)< (b)? (a): (b) ) int const N= 4010, M= 60010; struct Edge{ int adj, flow, idx; Edge* next; }tb[M<<1]; int n, m, S, T, cnt; Edge* mat[N]; i…
2010-05-27 14:25 · [图论]网络流 · 评论(0)
[XTU][1485][Beautiful Tree][树形DP + 背包 + 二分]
题目意思为有一棵树,对每个结点有两个值 v[i] 和 w[i],让你在这树上找一棵子树,使得 sum{ v[i] }/ sum { w[i] } 最大。二分这个答案 r ,对每个结点,重新计算一个值 t[i]= v[i]- r* w[i]。问题变成判定是否存大一棵子树,使得 t[i] 权值和大于0。 #include <iostream> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; int const N= 110; int v[N], w[N],…
2010-05-24 22:49 · [图论]树 · 评论(0)