题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=3277

线段树+离散化

ACM预选赛过去了,可是我们队什么都没拿到,这给我们的打击是相当大的,这也很大程度上体现了我们的不足

一直没能静下心,来,今天决定不能再这么悲伤下去,我要奋斗,继续学习,就从之前的断点线段树开始

题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=2549

这道题伤了我很久脑筋

因为是a+b+c=d,数据量是1000,很自然地想到a+b=d-c

这样转化为n^2的算法.

但是我开始枚举d-c的集合二分查找a+b的几何不知道为什么WA掉了

后面就想其他的办法,参考了一下别人的做法,我觉得差不多和我一样,然后重写.我也和他一样无耻的用STL库函数了

//最长单调子序列 复杂度nlog(n)
//参数(原序列,序列长度,生成的序列),传入序列长度必须大于0
//返回值中lengthRecord中前k项表示长度为k的最小字序列
//LIScmp为关系函数,原函数表明lengthRecord为递增(不含等于)
typedef double LISTYPE;
#define LISMAXN 10000
int LIScmp(LISTYPE a,LISTYPE b)
{
    return a < b;
}
long LISLength(LISTYPE list[],long n,LISTYPE lengthRecord[])
{
    long length = 1,lth;
    LISTYPE lR[LISMAXN];
    lR[0] = list[0];

    for(int i = 1 ; i < n ; i ++)
    {
        //二分查找,复杂度 log(n)
        int…

//Prime连通路模块
#define N 1000         //最大数据规模
#define MAXNUM 3000000   //最大路径长度
typedef double PrimeType;//路径类型

PrimeType PrimeRecord[N];
PrimeType dis[N][N];
int isLined[N] = {1,0};

PrimeType GetPrimeLength(const long n)
{
    PrimeType tmpLen = MAXNUM;
    long tmpPos = 0,left = n - 1;
    PrimeType sumLen = 0;

    for(long i = 1 ; i < n ; i ++)
        PrimeRecord[i] = dis[0][i];
    while(left --)
    {
        tmpLen = MAXNUM;…

//MULDATATYPE为矩阵元素类型,MAXMAT为最大矩阵大小

typedef long MULDATATYPE;
#define MAXMAT 100
#define inf 1000000000

#define fabs(x) ((x)>0?(x):-(x))
#define zero(x) (fabs(x)<1e-10)

struct mat
{
    long n,m;
    MULDATATYPE data[MAXMAT][MAXMAT];
    void operator =(const mat& a);
    mat operator +(const mat& a);
    mat operator -(const mat& a);
    //0-1邻接矩阵
    mat operator &(const mat& a);
    mat operator |(const mat& a);
};…

工作学习经历

• 2026.07-至今: ***
• 2025.09-2026.06: 游幻科技（上海）有限公司（追觅科技旗下） - 服务端技术负责人
• 2017.09-2025.08: 腾讯科技\(上海\)有限公司 - 北极光工作室后台组
• 2016.10-2017.07: 上海格奕网络科技有限公司 - 后端技术负责人
• 2014.10-2016.10: 上海莫游网络科技有限公司 - 联合创始人、CTO
• 2012.06-2014.10: 腾讯科技\(上海\)有限公司 - 北极光工作室后台组
• 2011.06-2012.06: 腾讯科技\(上海\)有限公司 - 北极光工作室后台组 - 实习…

今天在湖南的OJ上做题,发现不到两小时,他服务器就挂了,但是发现他和POJ上的一些题一样而且是连号的,就到POJ上继续了，我们队出了6题。

A题是POJ的3507 Judging Olympia这题是队友干掉的,我没看

B题是POJ的3508 Hide That Number同样是队友AC掉,我没看

懒惰了，暂时休息一下

这次我只AC了一题（在结束的那一刻，另一题在题目来源地网站上AC了，我们的OJ上仍然WA，我们OJ的Special Judge真是—_—!）

H题是用木棒拼数字，给出木棒数量，要求算出拼出的最大和最小数字

校赛个人训练赛第五场报告

今天战绩还行，AC了5题，今天总体没有太复杂的算法题，不过测试数据强度比之前有所增加 我的钱四题很早就过了，但是第五题很晚才出主要是代码写得太混乱，思路也错了两次 我过的题有五道，分别是ABCDG

A Coming Near

A题是计算两个多边形的最近距离

点到直线距离

// (x0,y0)到(x1,y1)和(x2,y2)确定的直线的距离

double disBetweenPointAndLine(double x0,double y0,double x1,double y1,double x2,double y2)
{
    //化为ax+by+c=0的形式
    double a = y1-y2;
    double b = x2-x1;
    double c = x1*y2-x2*y1;
    double d = (a*x0+b*y0+c)/sqrt(a*a+b*b);
    /*
    如果是线段判断垂足

    double xp = (b*b*x0-a*b*y0-a*c)/(a*a+b*b);
    double yp = (-a*b*x0+a*a*y0-b*c)/(a*a+b*b);
    double xb = (x1>x2)?x1:x2;…

//n每个用例的点个数
//MAXN为最大点个数
//PTYPE为坐标值类型
#include<iostream>
#include<cmath>
using namespace std;

#define MAXN 1005
#define EPS 1e-10
typedef double PTYPE;

struct point
{
    PTYPE x,y;
};
struct node
{
    PTYPE k;
};
int cmp(const void * a, const void * b)
{
    return((*(PTYPE*)a-*(PTYPE*)b>0)?1:-1);
}
node numK[MAXN * MAXN / 2];
point pt[MAXN];
int main()
{

    int n , maxNum = 1 , tmpNum = 0;…

Problem A

我没看题,队友很快AC我就没花时间看

Problem B

DP题,但是我们确实都没想到方法,实在是我们的经验不足

B题补充: B题的DP方法比较诡异(起码我理解了很久) 令fn[i][j]为有i个数j次交换位置的排列数量 很明显,当i+1时,如果把新增的数放在最后一位,那么交换次数不变(新增的数为i+1,最大). 如果把新增的数放在第1到i位之间的话有i种放法, 对于每一种fn[i][j]的排列中我们总能找到一种序列使得{(.)(.)()(.)(.)…(i+1)},["()表示一个元素"] 中(i+1)和()交换位置后前i个元素的排列和其相同 又因为(*)的位置可以有i种放法,以此我们发现,fn[i+1][j]=fn[i][j]+fn[i][j-1]×i 继续贴代码:

根的关系:

牛顿迭代解方程(x0附近的根)

double Newton_Iterative(double a,double b,double c,double d,double x0)
{
    double f0,f0d,x;
    x = x0;
    do
    {
        x0 = x;
        f0 = ((a * x + b) * x + c) * x + d;
        f0d = ( 3 * a * x + 2 * b ) * x + c;
        x = x0 - f0 / f0d;
    }…

校赛个人赛第三场部分解题报告（A,D,F,I）

这次我完成了四道题分别是A,D,F,I

一大半时间我都花在了A上，我犯了很究级的错误

首先是VC6.0的algorithm里没有min函数，而我用min做变量名导致CE4次，找了半天才找出来

校赛个人赛第六，七场总结

这两场比赛体现了英文水平的重要性

第六场的题目超长，用词还诡异，话了很长时间才看懂

这两场题目都比较有难度，第六场我只出了2题

A Grey Area

A题是很诡异的统计，是一道纯模拟就能过的题，其他的不多说了

先提一个简单的问题，如果有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？

有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但…也只能如此了。

POJ打破传统,以前是做一题送一题,现在是做一题送两题,那么我们就不用客气了

言归正传 题号:2606 Rabbit hunt 2780 Linearity 1118 Lining Up

大致题意是输入N个点.计算能穿过最多的点的直线,并输出最大点的个数

最初的想法很简单

枚举没两个点连成的直线,然后枚举每个点,计算通过这条直线的点的个数,但是这个方法的复杂度为O(n^3)

资料由互联网收集整理，供新手参考学习 这里又生动点的演示：http://www.cnblogs.com/wangfupeng1988/archive/2011/12/26/2302216.html

/*
=============================================================================
相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）：
1、稳定排序和非稳定排序
简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就
说这种排序方法是稳定的。反之，就是非稳定的。
比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，
则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,
a2,a3,a5就不是稳定的了。
2、内排序和外排序
在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；…

POJ 3267 The Cow Lexicon

这题是一道DP问题,我的想法如下:

1.可以令 deleteNum[pos]为输入字符串在pos处需要删除的最少字符数量;

2.如果输入字符串长度为len,则初始化deleteNum[len] = 0;(字符串由0开始计数)

//并查集
//注意类型匹配
const int maxn = 100002;
int DSet[maxn];
void init(int n) {
    for(int i = 0 ; i <= n ; i ++)
        DSet[i] = i;
}
int findP(int id) {
if(DSet[id] != id)
    DSet[id] = findP(DSet[id]);
    return DSet[id];
}
//返回根节点ID
int UnionEle(int a,int b) {
    a = findP(a);
    b = findP(b);
    if(a > b)
        a ^= b ^= a ^= b;
    DSet[b] = a;
    return a;
}