标题：TIC初赛：3AC 2放弃
出处：Felix021
时间：Sun, 10 May 2009 01:12:24 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1583

内容：
对于一个felix能做出4题的比赛，我想这次的题目实在是够简单了。毕竟是初赛。
A题，服务器173上的A题（据测试，至少有4台独立的服务器170~173跑着POJ的程序）
就是那个求和的程序，那显然应该速战速决1AC——这是我机器上14:01:02写完的程序：
#include<iostream>
using namespace std;

int main(){
    int n, i, t, sum = 0;
    scanf("%d", &n);
    for (i = 0; i < n; ++i){
        scanf("%d", &t);
        sum += t;
    }
    printf("%d\n", sum);
    return 0;
}


173上的B题，也就是企鹅豆豆的那题，让我想起了打豆豆的笑话。
一眼看过去，觉得是一个超简单的题目，sort一遍，然后O(n^2)遍历求出一个i，比penguin[i]高且力气大的企鹅是最多的。
通过了test case，然后提交，WA。
暂时忽略之，然后看了CDE题的题意，发现还是应该先搞B。
于是回过头来，仔细想了一下，发现自己SB了：
以H(Height)和S(Strength)建立一个直角坐标系，把所有的企鹅放进去
然后对任意两个企鹅a, b: 如果La < Lb 且 Sa < Sb，那么画一条从a到b的有向线段，于是就构成了一张图，或者是一个有交叉的森林，或者又可以叫做拓扑图？反正就是那么一个东西，然后有那么几个点只有出度没有入度（暂且称之为源点），有那么几个点只有入度没有出度（暂且称之为终点），我们要找一条从某一个源点到某一个终点的最长的路线。顺着这个思路，于是就想到了BFS：对每一个点都BFS过去，最后遍历所有的点，找出最大的深度，就是所求结果了。很快code完，提交，TLE。囧。看了一下，发现自己非常SB地在每次BFS以后都把所有的点的depth初始化了。注释掉这一句，提交，AC，14:32:58。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct penguin{
    int h, s;
    int dep;
    vector<int>q;
};
int n;
penguin p[1024];
bool cmp(const penguin &a , const penguin &b){
    return a.h < b.h;
}

void bfs(int i){
    vector<int>q;
    int a, b, c, t;
    int dep = 0;
    q.push_back(i);
    a = 1, b = 0;
    while(b < a){
        c = q[b]; //当前的企鹅
        dep = p[c].dep;
        for (unsigned int j = 0; j < p[c].q.size(); ++j){
            t = p[c].q[j];
            if(dep+1 > p[t].dep){
                p[t].dep = dep + 1;
                q.push_back(t);
                a++;
            }
        }
        b++;
    }
    q.clear();
}

int main(){
    int i, j, ans = 0;
    scanf("%d", &n);
    for (i = 0; i < n; ++i){
        scanf("%d%d", &p[i].h, &p[i].s);
        p[i].dep = 1;
    }
    for (i = 0; i < n; ++i){
        for (j = 0; j < n; ++j){
            if(i == j) continue;
            if(p[j].h > p[i].h && p[j].s > p[i].s){
                p[i].q.push_back(j);
            }
        }
    }
    ans = 0;
    for(i = 0; i < n; ++i){
        //printf("i = %d\n", i);
        bfs(i);
        for(j = 0; j < n; ++j){
            //printf("%d ", p[j].dep);
            ans = max(ans, p[j].dep);
            //p[j].dep = 1;
        }
        //printf("\n");
    }
    printf("%d\n", ans);
    return 0;
}

——坦白说这是第一次在比赛中用BFS AC题目，虽然我是BFS队里的。
后来Sandy和Boluor都来问我情况，发现我AC了这题，但是他们卡住了。他们的思路是把所有的企鹅按高度排序，然后使用DP求最长严格递增子序列的长度。不过他们忽略了两个高度相等的情况，于是WA了很久。后来sandy发现这个trick后ac了，boluor则继续wa，直到改用我说的BFS方法才AC。比赛后仔细想了想，如果使用DP，那么求这个问题的最优方法是O(NlogN)（详见某年国家队的论文，我不会=.=），一般的DP是O(n^2)，而我的BFS方法也是O(n^2)。之前会TLE是因为了SB的做法导致了极端情况；实际上为了避免可能存在的极端情况，可以通过STL的shuffle函数这样的方式来初始化BFS的顺序，这样就可以保证算法不会退化，但是恐怕是难以优化到O(NlogN)了。还好数据量不大。

C题Ball，是计算几何，本能的抵触，大概想了一下，发现有n种情况要考虑，暂时忽略之。
D题String，是字符串处理的，看起来估计要自动机去整它，无视之。

E题PaperCut，DP，或者说分治。由于Jieyu说他AC了，而且基本上差不多是硬搞了，于是就去做。公式是很容易推的，但是code完以后样例过不了。发现把min写成max了，囧，改之，还是不对。后来发现是切割后的处理不对，因为这是分格子，所以对于切割的点 i ，一边是 i-1 ，另一边是 i 。我把 -1 漏掉了。改过来以后通过了两个样例的数据。但是TLE了。这个时候是已经加了cache[10][10][10][10][50]来保存中间计算结果的。jieyu说需要预处理，先求出所有的cache[x1][y1][x2][y2][0]。想了一会儿，推出一个结论：
引用
记f(x1, y1, x2, y2) = cache[x1][y1][x2][y2][0]， xm = (x1+x2)/2，那么
f(x1,y1, x2,y2) = f(x1,y1, xm, y2) + f(xm, y1, x2, y2) + sum(x1,y1, xm,y2) * sum(xm,y1, x2,y2)
而sum(x1,y1, x2,y2) = sum(x1,y1, xm,y2) + sum(xm,y1, x2,y2)


第一个等式的前两项很好理解，最后一项其实也很容易推知（这是去年个人选拔赛的某一题的结论了，印象中一共遇到两次）
第二个等式那基本上就是废话。
至此思路是完全正确了，但是就这么着耗了我将近2个小时，直到17:52左右才终于通过了test case，提交AC。
发现错误出现在两个方面：
1。二分的过程出了问题，又是上面的那个问题，不过这次是+1。
2。被jieyu误导了，或者说是我自己的代码不对，通过4层for循环初始化并没有求出所有的cache[x1][y1][x2][y2][0]。于是在执行过程中也调用calcache函数，但是还是出错，到最后才悟道，原来同样的4层for循环初始化也没有求出所有的sum[x1][y2][x2][y2]。于是放弃初始化，全部改成在过程中求解（反正每个就求一次，时间是一样的），然后才终于AC。
这里贴一个整洁一点的代码吧：
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

int d[10][10];
int sum[10][10][10][10];
int cache[10][10][10][10][50];
int n, m, k;

int calsum(int xs, int ys, int xe, int ye){
    int ans = sum[xs][ys][xe][ye];
    if(ans < 0){
        if(xs == xe){
            ans = 0;
            int x1, y1;
            for(x1 = xs; x1 <= xe; x1++){
                for(y1 = ys; y1 <= ye; y1++){
                    ans += d[x1][y1];
                }
            }
        }else{
            int xm = (xs + xe) / 2;
            int sum1 = calsum(xs, ys, xm, ye);
            int sum2 = calsum(xm+1, ys, xe, ye);
            ans = sum1 + sum2;
        }
        sum[xs][ys][xe][ye] = ans;
    }
    return ans;
}

int calcache(int xs, int ys, int xe, int ye){
    int ans = cache[xs][ys][xe][ye][0];
    if(ans < 0){
        if(xs == xe){
            if(ys == ye){
                ans = 0;
            }else{
                int ym = (ys + ye) / 2;
                int cache1 = calcache(xs, ys, xe, ym);
                int cache2 = calcache(xs, ym+1, xe, ye);
                ans = cache1 + cache2 + calsum(xs,ys,xe,ym) * calsum(xs,ym+1,xe,ye);
            }
        }else{
            int xm = (xs + xe) / 2;
            int cache1 = calcache(xs, ys, xm, ye);
            int cache2 = calcache(xm+1, ys, xe, ye);
            ans = cache1 + cache2 + calsum(xs,ys,xm,ye) * calsum(xm+1,ys,xe,ye);
        }
        cache[xs][ys][xe][ye][0] = ans;
    }
    return ans;
}

int f(int xs,int ys,int xe,int ye,int k){
    if(xs < 0 || xe < 0 || ys < 0 || ye < 0 || xs > xe || ys > ye) return 0;
    int ans = cache[xs][ys][xe][ye][k];
    if(ans == -1){
        if(k == 0){
            ans = calcache(xs, ys, xe, ye);
        }else{
            int i, j;
            int v1, v2;
            ans = -1;
            for(i = xs; i <= xe; ++i){
                for(j = 0; j <= k - 1; ++j){
                    v1 = f(xs, ys, i-1, ye, j);
                    v2 = f(i, ys, xe, ye, k-1-j);
                    if(ans < 0){
                        ans = v1 + v2;
                    } else{
                        ans = min(ans, v1+v2);
                    }
                }
            }
            for(i = ys; i <= ye; ++i){
                for(j = 0; j <= k - 1; ++j){
                    v1 = f(xs, ys, xe, i-1, j);
                    v2 = f(xs, i, xe, ye, k-1-j);
                    if(ans < 0){
                        ans = v1 + v2;
                    } else{
                        ans = min(ans, v1+v2);
                    }
                }
            }
        }
        cache[xs][ys][xe][ye][k] = ans;
    }
    return ans;
}

int main(){
    int i, j;
    scanf("%d%d%d", &n, &m, &k);
    for (i = 0; i < n; ++i){
        for (j = 0; j < m; ++j){
            scanf("%d", &d[i][j]);
        }
    }
    memset(sum, -1, sizeof(sum));
    memset(cache, -1, sizeof(cache));
    printf("%d\n", f(0, 0, n-1, m-1, k));
    return 0;
}


晚上去吃饭的时候听Sandy说了一下C题Ball的思路，其实只要标准化一下，把A球置为静止，B球相对A运动，那么之后的处理就相当简单了。代码比较快就写完了，但是tic的提交系统已经关闭了，怨念阿：
#include<iostream>
#include<cmath>
using namespace std;

struct coord_t{
    double x, y;
    coord_t(){};
    coord_t(double _x, double _y):x(_x),y(_y){}
};

struct ball{
    coord_t p, v;
    double r;
};

inline int cmp(const double &a, const double &b){
    if(fabs(a-b) < 1e-9) return 0;
    if(a - b > 0) return 1;
    else return 0;
}

inline double pow2(double a){
    return a * a;
}

inline double len2(const coord_t &a){
    return (pow2(a.x) + pow2(a.y));
}

inline double len(const coord_t &a){
    return sqrt(len2(a));
}

inline double dist2(const coord_t &a, const coord_t &b){
    return (pow2(b.x-a.x) + pow2(b.y - a.y));
}


int main(){
    int T;
    double xa, ya, vax, vay, ra, xb, yb, vbx, vby, rb;
    ball a, b;
    scanf("%d", &T);
    while (T--){
        scanf("%lf%lf%lf%lf%lf", &xa, &ya, &vax, &vay, &ra);
        scanf("%lf%lf%lf%lf%lf", &xb, &yb, &vbx, &vby, &rb);
        
        // 标准化，把a放在原点，速度置为0
        a.p.x = 0, a.p.y = 0, 
        a.v.x = 0, a.v.y = 0, 
        a.r = ra;
        
        // b就要做相应的调整了
        b.p.x = xb - xa,   b.p.y = yb - ya, 
        b.v.x = vbx - vax, b.v.y = vby - vay, 
        b.r = rb;

        if(cmp(dist2(a.p, b.p), pow2(a.r + b.r)) == 0){
            // 两个球本来就是靠在一起的
            printf("%.3lf %.3lf %.3lf %.3lf %.3lf\n",
                      0.0,   xa,   ya,   xb,   yb);
        }else{
            // 本来没靠在一起
            double A, B, C, Dab;
            //求出b的运动轨迹的直线方程Ax + By + C = 0
            A = b.v.y, B = -b.v.x, C = b.v.x * b.p.y - b.v.y * b.p.x;
            //求出a点到b运动轨迹的距离
            Dab = fabs(A * a.p.x + B * a.p.y + C) / sqrt(pow2(A) + pow2(B));
            
            if(cmp(b.v.x, 0) == 0 && cmp(b.v.y == 0) || cmp(Dab, a.r + b.r) < 0){
                //如果根本不可能相碰(b不动，或者距离大于ab的半径和)
                printf("Impossible\n");
                continue;
            }
            //b到a的向量
            coord_t ba(a.p.x-b.p.x, a.p.y-b.p.y);
            //b的运动方向向量
            coord_t bc(b.v.x, b.v.y);
            //两个向量的夹角
            double cosABC = ba.x * bc.y + ba.y * bc.x;
            cosABC = cosABC / (len(ba) * len(bc));
            //夹角小于0，说明B远离A移动
            if(cmp(cosABC, 0) <= 0){
                printf("Impossible\n");
                continue;
            }
            // 下面是会相遇的情况
            // b运行到a点的时候两球相碰，则ae = ra + rb
            // <--d----e----<-----b
            //    |   /
            //    |  /
            //    | /
            //    |/
            //    a
            double db, de, eb, ae, da = Dab;
            ae = a.r + b.r;
            db = sqrt(len2(ba)-pow2(da));
            de = sqrt(pow2(ae)-pow2(da));
            eb = db - de;
            //求出时间
            double time = eb / len(b.v);
            //求出a坐标
            xa = xa + vax * time;
            ya = ya + vay * time;
            //求出b坐标
            xb = xb + vbx * time;
            yb = yb + vby * time;
            printf("%.3lf %.3lf %.3lf %.3lf %.3lf\n",
                     time,   xa,   ya,   xb,   yb);
        }
    }
    return 0;
}



Generated by Bo-blog 2.1.0