Round #358 (div 2) 总结

codeforces

A.Alyona and Numbers

来源

http://codeforces.com/contest/682/problem/A

解答

分别统计mod 5的余数的个数，枚举余数直接做。

B.Alyona and Mex

来源

http://codeforces.com/contest/682/problem/B

解答

初始mex为0，如果两个数a,b变小后都可以使得当前的mex+1，显然取小的那个变小。所以从小到大排序后模拟就可以了。

C.

来源

http://codeforces.com/contest/682/problem/C

题目

给出一棵有根树，如果结点v的子树里有一个结点u，dist(u,v)>a[u]那么就称v是sad。现在你可以从叶子开始删点(删完后可能会产生的叶子，根不是叶子)，问删到剩下没有一个点是sad的时候，最少删了几个点？

解答

根据删除叶子的规则，对于dist(u,v)>a[u]，肯定要删除u。v其实是u到根路径上的点，要不要删除u取决于a[u]本身及u到根的最大连续和。

从根开始dp(注意负数)，求每个结点到根的路径中包含该结点连续的最大和。如果这个最大和大于给出的限制a[u]，就标记一下。最后从根开始再遍历一遍树，跳过标记点，就能求出剩下的结点个数。（这题在dp的时候我后来检查发现会爆int，于是重新交了一遍。后来发现爆了不会影响最终答案，因为数据范围是10^9，爆了的点肯定有个祖先是没有爆int但超过10^9的，就会有标记，整棵子树会删去）

总结

写代码的时候注意数据范围。

D.

来源

http://codeforces.com/contest/682/problem/D

题目

给出两个字符串和k(k<=10)，分别从两个字符串里取出k个不相交子串$a_1,a_2,...,a_k$和$b_1,b_2,...,b_k$。要求$a_1=b_1,a_2=b_2,...,a_k=b_k$并且k个串的长度和最大。求出最大的长度和，数据保证有解。

解答

最长公共子序列的变形。
选k个子串序列可以弱化成选<=k个(数据保证有解，把长的拆开就可以凑出k个了)。
dp的状态可以是F[i][j][k]。表示第一个字符串以i为结尾，第二个字符串以j为结尾，已经选出k个子串序列。显然，如果s1[i]!=s2[j]，有F[i][j][k]=max(F[i-1][j][k],F[i][j-1][k])。如果s1[i]=s2[j]，那么既有上面的转移，也有F[i][j][k]=max(F[i-r][j-r][k-1]+r,F[i][j][k])的转移。其中r表示s1[i-r+1..i]=s2[j-r+1..j]。这个r如果枚举会超时。
前面我们说到k弱化为<=k，所以我们这里的r越长越好(一段连续的分开取，会增加k的个数，一定不是最优解，可直接去掉)，即r是s1以i结尾，s2以j结尾的最长的公共子串，这个预处理就可以完成，用len[i][j]表示。如果s1[i]=s2[j]，则len[i][j]=len[i-1][j-1]+1；否则len[i][j]=0。

总结

根据题意弱化条件，变'='为'<='。
一步一步剖分问题，将原问题转化为经典问题。

E.

来源

http://codeforces.com/contest/682/problem/E

题目

给出n(3<=n<=5000)个点，一个S。要你在平面内画一个三角形，包含这n个点以及三角形的面积不超过4S。数据保证有解。

解答

几何结论下的简单几何题。
有个结论是，如果在面积为1的平面里放入n个点，那么包含这n个点的三角形面积一定不会超过4。找出这个三角形也很简单，只要找到n个点中最大的三角形ABC，分别过顶点作对边的平行线得到三角形A'B'C'，这个三角形A'B'C'一定包含平面内的所有点，并且面积是三角形ABC的4倍。证明。
那么知道结论后，问题就转化为求平面中最大的三角形。我的做法是求出一个凸包，在凸包上枚举两个顶点i,j，求出第三个顶点k。根据峰值单调性，如果i固定，当j往后移动之后，k也一定往后移动，这样可以O(N^2)求出最大面积的三角形。

    int x,y,z;
    long long s=0;
    for (int i=1; i<=n; i++)   // 枚举凸包上的点
    {
        int j=next(i);   // 逆时针的下一个点
        int k=next(j);
        while(next(j)!=i)
        {
            while(j==k || area(i,j,k)<area(i,j,next(k))
                k=next(k);
            long long t=area(i,j,k);
            if (t>s) s=t,x=i,y=j,z=k;
            j=next(j);
        }
    }

然而当我过了这题后，发现一些好像是暴力乱搞的更快(其实并不暴力并不乱搞)，貌似应用了几何中常见的增量法。

    int x=0,y=1,z=2;
    while(1)
    {
        bool flag=1;
        for(int i=0;i<n;i++)
        {
            if(calc(p[i],p[x],p[y])>calc(p[z],p[x],p[y])) z=i, flag=0;
            if(calc(p[i],p[y],p[z])>calc(p[x],p[y],p[z])) x=i, flag=0;
            if(calc(p[i],p[z],p[x])>calc(p[y],p[z],p[x])) y=i, flag=0;
            }
            if(flag) break;
        }

原代码链接
糖老师给了一个论文网站，收集了一些关于求出凸包后线性求出最大面积三角形的算法。(不知道为什么之前可以打开看，现在不行了，貌似要购买)
在cf上看到了anta大神的代码，求出凸包后，只枚举一个顶点，其它两个顶点似乎都是具有单调性的，也就是说可以O(n)求出最大面积三角形。

    int A = 0, B = 1, C = 2;
    vector<P> res = { ch[A], ch[B], ch[C] };
    P::T2 best = triangleArea(ch[A], ch[B], ch[C]), cur = best, tmp;
    do {
        while(1) {
            while(cur <= (tmp = triangleArea(ch[A], ch[B], ch[(C + 1) % n])))
                (++ C) %= n, cur = tmp;
            if(cur <= (tmp = triangleArea(ch[A], ch[(B + 1) % n], ch[C]))) {
                (++ B) %= n, cur = tmp;
                continue;
            }
            break;
        }
        if(cur > best) {
            res[0] = ch[A], res[1] = ch[B], res[2] = ch[C];
            best = cur;
        }
        (++ A) %= n;
        if(A == B) (++ B) %= n;
        if(B == C) (++ C) %= n;
        cur = triangleArea(ch[A], ch[B], ch[C]);
    } while(A != 0);

原代码链接
至于为什么？有待证明。

总结

1 几何中不知道怎么做的时候，增量调整往往会有不错的收益，代码好些效率也很高。

2 多看大神代码，好好品味品味😂

魏子卿
2016年7月7日