状态压缩+DP

1972的增强版

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

题意是给出小于10个的骰子，要求竖着叠成一条，而且每两个相接的骰子相接的面的数字相同

求侧面数字的最大和。如果叠不出来输出0

为什么我用线段数这么不灵活呢？

大概思路是线段数记录某牛之前的坐标小于这个牛的牛的坐标和和牛的个数

然后其他部分线性数组记录

OK，贴代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define MAXN 20005
class cow
{
public:
    int v;
    int pos;
    cow(){};
    ~cow(){};
};

bool cmp(cow a,cow b)
{
    return a.v < b.v;
}
cow cw[MAXN];
long long belowXNT[MAXN];//树状数组，保存小于等于某坐标的牛的个数,计算时使用
long long belowXN[MAXN];//一般数组，保存小于等于某坐标和索引的牛的个数
long long velowXRT[MAXN];//树状数组，保存索引小于等于某的牛且坐标也小于它的牛的坐标之和,计算时使用
long long velowXR[MAXN];//一般数组，保存索引小于等于某的牛且坐标也小于它的牛的坐标之和
long long velowXRA[MAXN];//一般数组，保存小于等于某牛的坐标之和

int lowbit(int t)
{
    return t&(t^(t-1));
}
void setVal(int pos, int num, long long treeG[], int maxn)
{
    while (pos <= maxn)
    {
        treeG[pos] += num;
        pos += lowbit(pos);
    }
}
long long getSum(int pos, long long treeG[])
{
    long long sum = 0;
    while (pos > 0)
    {
        sum += treeG[pos];
        pos -= lowbit(pos);
    }
    return sum;
}



int main()
{
    int i,n;
    long long output = 0;
    memset(belowXN, 0, sizeof(belowXN));
    memset(belowXNT, 0, sizeof(belowXN));
    memset(velowXR, 0, sizeof(velowXR));
    memset(velowXRA, 0, sizeof(velowXRA));
    memset(velowXRT, 0, sizeof(velowXRT));
    scanf("%d",&n);
    for(i = 0 ; i < n ; i ++)
        scanf("%d %d", &cw[i].v, &cw[i].pos);

    sort(cw, cw + n, cmp);
    for(i = 0 ; i < n ; i ++)
    {
        velowXRA[i] = velowXRA[i - 1] + cw[i].pos;
        setVal(cw[i].pos, 1, belowXNT, MAXN);
        setVal(cw[i].pos, cw[i].pos, velowXRT, MAXN);
        velowXR[i] = getSum(cw[i].pos, velowXRT);
        belowXN[i] = getSum(cw[i].pos, belowXNT);
    }

    for(i = 1 ; i < n ; i ++)
        //output += cw[i].v * ((belowXN[i] - 1) * cw[i].pos - velowXR[i] + cw[i].pos + velowXRA[i] - velowXR[i] - (i - belowXN[i] + 1) * cw[i].pos);
        output += cw[i].v * ((belowXN[i] - i + belowXN[i] - 1 ) * cw[i].pos - 2 * velowXR[i] + velowXRA[i]);//这里是上面式子的简化版

    printf("%lld\n",output);
    return 0;
}

又来发解题报告了

这回是树状DP

/*
 * 树状DP
 * 首先把数据想象成树状的
 * 由于输入数据为树状，不需要构建树
 * 可令degree[i]为包括i且以i为根节点的所有子节点数量
 * dp[i]为删除i后的最大子节点数量或父亲节点数量 （这里我理解了很久）
 */
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int>chirld[10002];
int dp[10002] = {0}
    ,degree[10002] = {0}
    ,isJudged[10002] = {0};

int search(int pos,int &n);
int main()
{
    int n,i,a,b;
    bool isnone = true;
    scanf("%d",&n);
    for(i = 1 ; i < n ; i ++)
    {
        scanf("%d %d",&a,&b);
        chirld[a].push_back(b);
        chirld[b].push_back(a);
    }

    search(1 , n);

    for(i = 1 ; i <= n ; i ++)
        if(dp[i] * 2 <= n)
            printf("%d\n",i) , isnone = false;

    if(isnone)
        printf("NONE\n");
    return 0;
}

int search(int pos,int &n)
{
    int i,j;
    degree[pos] = 1;
    isJudged[pos] = 1;
    dp[pos] = 0;

    for(i = 0 ; i < chirld[pos].size() ; i ++)
    {
        if(!isJudged[chirld[pos].at(i)])//如果已经判断过就是父亲节点了
        {
            degree[pos] += search(chirld[pos].at(i) , n);
            if(dp[pos] < degree[chirld[pos].at(i)])
                dp[pos] = degree[chirld[pos].at(i)];
        }
    }

    if(dp[pos] < n - degree[pos])//判断父亲节点数量
        dp[pos] = n - degree[pos];
    return degree[pos];
}

题目链接: http://acm.pku.edu.cn/JudgeOnline/bbs?problem_id=2528

这题又是线段树+离散化

慢慢的对离散化有点感觉了,但是这题我还是错了3次

题目大意是一层一层地叠板子,问最后能看到几块

输入是板子的开始和结束位置

题目链接: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掉了

//最长单调子序列 复杂度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 b,e,m;
        b = 0;
        e = length - 1;
        while(b <= e && e >= 0)
        {
            m = (b + e) / 2;
            if(LIScmp(lR[m],list[i]))
                b = m + 1;
            else
                e = m - 1;
        }
        lR[b] = list[i];
        if(b >= length)
            length ++;
    }
    /*
    *计算序列部分
    *复杂度nlog(n)
    */
    lth = 1;
    for(int i = 1 ; i < n ; i ++)
    {
        //二分查找,复杂度 log(n)
        int b,e,m;
        b = 0;
        e = lth - 1;
        while(b <= e && e >= 0)
        {
            m = (b + e) / 2;
            if(LIScmp(lR[m],list[i]))
                b = m + 1;
            else
                e = m - 1;
        }
        lR[b] = list[i];
        if(b >= lth)
            lth ++;
        if(lth == length)
        {
            for(b = 0 ; b < length ; b ++)
                lengthRecord[b] = lR[b];
            break;
        }
    }
    //计算序列部分代码与之前的类似,可以直接Copy然后修改
    return length;
}

//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;
        for(long i = 1 ; i < n ; i ++)
            if(!isLined[i] && PrimeRecord[i] < tmpLen)
                tmpPos = i,tmpLen = PrimeRecord[i];

        sumLen += tmpLen;
        isLined[tmpPos] ++;
        for(long i = 1 ; i < n ; i ++)
            if(dis[tmpPos][i] < PrimeRecord[i])
                PrimeRecord[i] = dis[tmpPos][i];
    }

    return sumLen;
}

//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);
};

//c=a*b
//注意引用
int Mat_MulMode(mat& c,const mat& a,const mat& b,MULDATATYPE mod)
{
    long i,j,k;
    if (a.m != b.n)
        return 0;
    c.n = a.n , c.m = b.m;
    for (i = 0 ; i < c.n ; i ++)
        for (j = 0 ; j < c.m ; j ++)
            for (c.data[i][j] = k = 0 ; k  < a.m ; k ++)
                c.data[i][j] = (c.data[i][j] + a.data[i][k] * b.data[k][j]) % mod;
    return 1;
}
//c=a^b(其中必须满足b>0)
int Mat_PowMode(mat& c,mat a,long b,MULDATATYPE mod)
{
    c = a;
    b --;
    while(b)
    {
        mat tmp;
        if(b & 1)
        {
            tmp = c;
            Mat_MulMode(c,tmp,a,mod);
        }
        tmp = a;
        Mat_MulMode(a,tmp,tmp,mod);
        b = b>>1;
    }
    return 1;
}
//c=a+b
int Mat_AddMode(mat& c,const mat& a,const mat& b,MULDATATYPE mod)
{
    long i,j;
    if (a.n != b.n || a.m != b.m)
        return 0;
    c.n = a.n , c.m = b.m;
    for (i = 0 ; i < c.n ; i ++)
        for (j = 0 ; j < c.m ; j ++)
            c.data[i][j] = (a.data[i][j] + b.data[i][j]) % mod;
    return 1;
}
//c=a-b
int Mat_SubMode(mat& c,const mat& a,const mat& b,MULDATATYPE mod)
{
    long i,j;
    if (a.n != b.n || a.m != b.m)
        return 0;
    c.n = a.n , c.m = b.m;
    for (i = 0 ; i < c.n ; i ++)
        for (j = 0 ; j < c.m ; j ++)
            c.data[i][j] = (a.data[i][j] - b.data[i][j]) % mod;
    return 1;
}


void mat::operator =(const mat& a)
{
    n = a.n;
    m = a.m;
    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < m ; j ++)
            data[i][j] = a.data[i][j];
}
mat mat::operator +(const mat &a)
{
    long i,j;
    mat tmpMat;
    tmpMat.m = m;
    tmpMat.n = n;
    for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
            tmpMat.data[i][j] = data[i][j] + a.data[i][j];
    return tmpMat;
}
mat mat::operator -(const mat &a)
{
    long i,j;
    mat tmpMat;
    tmpMat.m = m;
    tmpMat.n = n;
    for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
            tmpMat.data[i][j] = data[i][j] - a.data[i][j];
    return tmpMat;
}
mat mat::operator &(const mat &a)
{
    long i,j;
    mat tmpMat;
    tmpMat.m = m;
    tmpMat.n = n;
    for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
            tmpMat.data[i][j] = data[i][j] & a.data[i][j];
    return tmpMat;
}
mat mat::operator |(const mat &a)
{
    long i,j;
    mat tmpMat;
    tmpMat.m = m;
    tmpMat.n = n;
    for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
            tmpMat.data[i][j] = data[i][j] | a.data[i][j];
    return tmpMat;
}

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

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

懒惰了，暂时休息一下

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

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

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

点到直线距离

// (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;
    double yb = (y1>y2)?y1:y2;
    double xs = x1+x2-xb;
    double ys = y1+y2-yb;
    if(xp > xb || xp < xs || yp > yb || yp < ys)
    {
        d = sqrt((x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1));
        if(d > sqrt((x0 - x2) * (x0 - x2) + (y0 - y2) * (y0 - y2)))
            d = sqrt((x0 - x2) * (x0 - x2) + (y0 - y2) * (y0 - y2));
    }
    */
    return fabs(d);
}

线段间最短距离

//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;
    while(scanf("%d",&n),n)
    {
        for(int i = 0 ; i < n ; i ++)
            scanf("%lf %lf",&pt[i].x,&pt[i].y);
        for(int i = 0 ; i <  n ; i ++)
        {
            int pos = 0;
            for(int j = i + 1 ; j < n ; j ++)
                if((pt[i].x - pt[j].x) > EPS)
                    numK[pos ++].k = (pt[j].y - pt[i].y) / (pt[j].x - pt[i].x);
                else
                    numK[pos ++].k = 100000;

            qsort(numK,pos,sizeof(numK[0]),cmp);
            int tmpNum = 2;
            for(int j = 1 ; j < pos ; j ++)
            {
                if(numK[j].k == numK[j - 1].k)
                    tmpNum ++;
                else
                {
                    if(tmpNum > maxNum)
                        maxNum = tmpNum;
                    tmpNum = 2;
                }
            }
            if(tmpNum > maxNum)
                maxNum = tmpNum;
        }


        printf("%d\n",maxNum);
        maxNum = 1;
    }
    return 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 继续贴代码:

$$ ax^3+bX^2+cx+d=0 $$

根的关系:

$$ x1 + x2 + x3 = (-\frac{b}{a}) $$

$$ x1 \times x2 + x1 \times x3 + x2 \times x3 = \frac{c}{a} $$

$$ x1 \times x2 \times x3 = (-\frac{d}{a}) $$

牛顿迭代解方程(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;
    }
    while(fabs(f0) >= 1e-12);
    return x;
}

牛顿迭代法

校赛个人赛第三场部分解题报告（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个点.计算能穿过最多的点的直线,并输出最大点的个数

POJ 3267 The Cow Lexicon

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

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

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