CodeForces Round 128 DIV2

写于 2012 年 07 月 04 日 11 时 38 分
更新于 2022 年 12 月 31 日 15 时 33 分

大纲

1. Description
2. Analysis
3. Code

　　这次玩脱了。好不容易四题都做出来，却因为小细节挂了两题。

Description

Two Problems

　　题意就是说，CF有两题，每题初始分A和B，然后每题在每分钟会扣DA和DB分。给你比赛总时间T，问你某个人可不可能拿到X分。（注意可能做出一题、两题或者一题也没做出）

　　(0 ≤ x ≤ 600; 1 ≤ t, a, b, da, db ≤ 300且保证及时比赛时间到了各题的分数也不会小于0)

Game on Paper

　　有一个 NN 方格纸。在上面的方格里一格格涂黑。每一步涂一格一共涂 m 次，给定 xi 和 yi。问最少涂几步方格纸里会出现一个 33 的正方形。

　　(1 ≤ n ≤ 1000, 1 ≤ m ≤ min(n· n, 105))

Photographer

　　照相内存卡里有d容量。其中高质量照片占a容量、低质量占b容量。然后有n个顾客，每个顾客需要xi张高质量照片和yi张低质量照片。摄影师如果给一个人拍照了，就应该满足他所有要求（即给xi张高质量照片和yi张低质量照片）。问摄影师最多能给几个人拍照。

　　(1 ≤ n ≤ 105, 1 ≤ d ≤ 109, 1 ≤ a ≤ b ≤ 104, 0 ≤ xi, yi ≤ 105)

Hit Ball

　　封闭房间里，从房间的一头最底下的中间以某个方向踢球（一定是网对面踢），问踢到另一头的墙上的时候，x、z各是多少。

　　(各座标以及向量都是小于等于100的正整数)

Hit Ball

Transportation

　　还没看。

Analysis

Two Problems

　　这题只要注意几个trick就行了：可以做出0题、1题或者2题。直接两个for枚举各题在几分钟内做出来，然后做一下0题、1题的特殊判断就好了。

Game on Paper

　　在每次涂的时候，以当前涂的点位中心，设它为九宫格的其中一个位置（一共九种位置），对于每种位置，都判断其对应的九宫格是不是 3*3 的黑色就好了。(我做的时候在设位置的时候 x - 1, y - 1 手贱敲成了 x - 1, y - 2，lock 之后才发现。悲剧)

Photographer

　　贪心。对于每个人将其所需的总容量算出来再进行递增排序。最后求的时候推荐累减的方式判断，因为我累加然后用 int 最后爆范围了。

Hit Ball

　　首先拿出空间几何的线面相交模板。然后来一个 while，每次循环的时候判断当前所在的点与方向适量形成的直线与 (X, 0, Z) 面的交点在不在终点墙壁大小的范围内。若不是则说明中途撞墙了判断方向向量：x < 0则线面相交判断是不是撞左墙，若是则 x 正负值变一下；x > 0 则线面相交判断是不是撞右墙，若是则 x 正负值变一下。z < 0则判断是不是以求抢地，若是则 z 正负变一下。最后 z > 0 则判断是不是撞天花板，若是则z正负值变一下。然后以球撞击的点为新的起点，与新的方向向量形成新的直线，继续下一次循环。因为房间大小最大是 100 * 100 * 100，而方向向量各方向是 1 到 100 的整数，不是小数，则撞击次数不会很多，直接 while 撞击也不会超。

Code

Two Problems

#include <iostream>
using namespace std;

int main()
{
    int x, t, a, b, da, db;
    while(~scanf("%d%d%d%d%d%d", &x, &t, &a, &b, &da, &db))
    {
        bool flag = false;
        for(int i = 0; i < t; i++)
        {
            if(x == a - i * da)
            {
                flag = true;
                break;
            }

            for(int j = 0; j < t; j++)
            {
                if(x == b - j * db)
                {
                    flag = true;
                    break;
                }

                if(x == a - i * da + b - j * db)
                {
                    flag = true;
                    break;
                }
            }
            if(flag) break;
        }
        if(0 == x) flag = true;

        printf("%s\n", flag ? "YES" : "NO");
    }

    return 0;
}

Game on Paper

#include <iostream>
using namespace std;

bool mat[1015][1015];

bool check2(int sx, int sy)
{
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            //if(i == 1 && j == 1) continue;

            if(!mat[sx + i][sy + j]) return false;
        }
    }

    return true;
}

bool check(int x, int y)
{
    if(check2(x, y)) return true;
    if(check2(x, y - 1)) return true;
    if(check2(x, y - 2)) return true;
    if(check2(x - 1, y)) return true;
    if(check2(x - 1, y - 1)) return true;
    if(check2(x - 1, y - 2)) return true;
    if(check2(x - 2, y)) return true;
    if(check2(x - 2, y - 1)) return true;
    if(check2(x - 2, y - 2)) return true;

    return false;
}

int main()
{
    int n, m;
    int x, y;
    while(~scanf("%d%d", &n, &m))
    {
        int ans = -1;
        memset(mat, 0, sizeof(mat));
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d", &x, &y);
            mat[x + 1][y + 1] = true;

            if(ans == -1)
            {
                if(check(x + 1, y + 1))
                {
                    ans = i + 1;
                }
            }
        }

        printf("%d\n", ans);
    }

    return 0;
}

Photographer

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

struct client
{
    int id;
    int memo;
};

bool cmp(client a, client b)
{
    return a.memo < b.memo;
}

client c[100005];

int main()
{
    int n;
    __int64 d;
    int a, b;
    int x, y;

    while(~scanf("%d%I64d", &n, &d))
    {
        scanf("%d%d", &a, &b);
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d", &x, &y);
            c[i].id = i + 1;
            c[i].memo = a * x + b * y;
        }

        sort(c, c + n, cmp);
        __int64 sum = 0L;
        int maxi = -1;
        for(int i = 0; i < n; i++)
        {
            if(sum + c[i].memo <= d) sum += c[i].memo, maxi = i;
            else break;
        }

        printf("%d\n", maxi + 1);
        for(int i = 0; i <= maxi; i++)
        {
            printf("%d%c", c[i].id, i == maxi ? '\n' : ' ');
        }
    }

    return 0;
}

Hit Ball

#include <iostream>
#include <math.h>
using namespace std;
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
struct point3{double x,y,z;};
struct line3{point3 a,b;};
struct plane3{point3 a,b,c;};

point3 xmult(point3 u,point3 v){
    point3 ret;
    ret.x=u.y*v.z-v.y*u.z;
    ret.y=u.z*v.x-u.x*v.z;
    ret.z=u.x*v.y-u.y*v.x;
    return ret;
}

point3 subt(point3 u,point3 v){
    point3 ret;
    ret.x=u.x-v.x;
    ret.y=u.y-v.y;
    ret.z=u.z-v.z;
    return ret;
}

point3 pvec(plane3 s){
    return xmult(subt(s.a,s.b),subt(s.b,s.c));
}

point3 intersection(line3 l,plane3 s){
    point3 ret=pvec(s);
    double t=(ret.x*(s.a.x-l.a.x)+ret.y*(s.a.y-l.a.y)+ret.z*(s.a.z-l.a.z))/
        (ret.x*(l.b.x-l.a.x)+ret.y*(l.b.y-l.a.y)+ret.z*(l.b.z-l.a.z));
    ret.x=l.a.x+(l.b.x-l.a.x)*t;
    ret.y=l.a.y+(l.b.y-l.a.y)*t;
    ret.z=l.a.z+(l.b.z-l.a.z)*t;
    return ret;
}

int main()
{
    double a, b, m;
    double vx, vy, vz;

    while(~scanf("%lf%lf%lf%lf%lf%lf", &a, &b, &m, &vx, &vy, &vz))
    {
        /** 5 walls */
        plane3 door, lw, rw, top, ground;
        door.a.x = 0, door.a.y = 0, door.a.z = 0;
        door.b.x = 1, door.b.y = 0, door.b.z = 0;
        door.c.x = 0, door.c.y = 0, door.c.z = 1;
        lw.a.x = 0, lw.a.y = 0, lw.a.z = 0;
        lw.b.x = 0, lw.b.y = 1, lw.b.z = 0;
        lw.c.x = 0, lw.c.y = 0, lw.c.z = 1;
        rw.a.x = a, rw.a.y = 0, rw.a.z = 0;
        rw.b.x = a, rw.b.y = 1, rw.b.z = 0;
        rw.c.x = a, rw.c.y = 0, rw.c.z = 1;
        ground.a.x = 0, ground.a.y = 0, ground.a.z = 0;
        ground.b.x = a, ground.b.y = 0, ground.b.z = 0;
        ground.c.x = a / 2, ground.c.y = m, ground.c.z = 0;
        top.a.x = 0, top.a.y = 0, top.a.z = b;
        top.b.x = a, top.b.y = 0, top.b.z = b;
        top.c.x = a / 2, top.c.y = m, top.c.z = b;

        line3 l;

        l.a.x = a / 2;
        l.a.y = m;
        l.a.z = 0;

        l.b.x = (a / 2) + vx;
        l.b.y = m + vy;
        l.b.z = vz;

        point3 v;
        v.x = vx, v.y = vy, v.z = vz;

        point3 myans;
        while(true)
        {
            point3 ans, ans1, ans2, ans3, ans4;
            memset(&ans1, 0, sizeof(point3));
            memset(&ans2, 0, sizeof(point3));
            memset(&ans3, 0, sizeof(point3));
            memset(&ans4, 0, sizeof(point3));

            ans = intersection(l, door);
            if(ans.x >= 0 && ans.z >= 0 && ans.x <= a && ans.z <= b)
            {
                myans = ans;
                break;
            }

            point3 totans;

            if(v.x < 0)
            {
                ans1 = intersection(l, lw);
                if(ans1.z >= 0 && ans1.z <= b)
                {
                    v.x = -v.x;
                    totans = ans1;
                }
            }
            else
            if(v.x > 0)
            {
                ans2 = intersection(l, rw);
                if(ans2.z >= 0 && ans2.z <= b)
                {
                    v.x = -v.x;
                    totans = ans2;
                }
            }

            if(v.z > 0)
            {
                ans3 = intersection(l, top);
                if(ans3.x >= 0 && ans3.x <= a)
                {
                    v.z = -v.z;
                    totans = ans3;
                }
            }
            else
            if(v.z < 0)
            {
                ans4 = intersection(l, ground);
                if(ans4.x >= 0 && ans4.x <= a)
                {
                    v.z = -v.z;
                    totans = ans4;
                }
            }

            l.a = totans;
            l.b = totans;
            l.b.x += v.x;
            l.b.y += v.y;
            l.b.z += v.z;
        }

        printf("%.10lf %.10lf\n", myans.x, myans.z);
    }

    return 0;
}