学步园

A - Watching a movie

快进看电影，要看到所有的精彩部分，给定快进的时间间隔，和每个精彩时间段的开始时间和结束时间。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define OT printf
#define MAXN 50
#define INF 0x7f7f7f7f
#define RUN(x) freopen(#x, "r", stdin);
#define REP(i, n) for(i = 0; i < n; i++)
#define FOR(i, s, e) for(i = s; i < e; i++)

inline int RD(int &x)
{
        x = 0;
        char ch = getchar();
        while(ch < '0' || ch > '9') { ch = getchar(); if(ch == EOF) return 0; }
        while(ch >= '0' && ch <= '9') { x *= 10; x += ch - '0'; ch = getchar(); }
        return 1;
}
inline int RD(int &x0, int &x1) { return RD(x0) + RD(x1); }

/*..........................................dizzy............................................*/

int n, x, i;
int l[MAXN], r[MAXN];
int t[100010];

int main()
{
#ifndef ONLINE_JUDGE
    RUN(A.in);
#endif // ONLINE_JUDGE

    RD(n, x);
    REP(i, n) RD(l[i], r[i]);
    int s = 1, ans = 0, k = 0;
    while(true)
    {
        if(s + x <= l[k])
        {
            s += x;
            continue;
        }
        ans += r[k] - s + 1;
        if(k == n - 1) break;
        s = r[k++] + 1;
        if(s + x > l[k])
        {
            ans += r[k] - s + 1;
            if(k == n - 1) break;
            s = r[k++] + 1;
        }
    }
    OT("%d\n", ans);

    return 0;
}

B - Lecture
map

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <string>
#include <math.h>
#include <map>
using namespace std;
#define OT printf
#define MAXN 3010
#define INF 0x7f7f7f7f
#define RUN(x) freopen(#x, "r", stdin);
#define REP(i, n) for(i = 0; i < n; i++)
#define FOR(i, s, e) for(i = s; i < e; i++)

inline int RD(int &x)
{
        x = 0;
        int flag = 1;
        char ch = getchar();
        while(!isdigit(ch) && ch != -1) { ch = getchar(); if(ch == EOF) return 0; }
        if(ch == '-') flag = -1;
        while(ch >= '0' && ch <= '9') { x *= 10; x += ch - '0'; ch = getchar(); }
        x *= flag;
        return 1;
}
inline int RD(int &x0, int &x1) { return RD(x0) + RD(x1); }

/*..........................................dizzy............................................*/

int n, m, i;
string fst[MAXN], snd[MAXN];
map<string, string> s, ss;
map<string, string>::iterator it;

int main()
{
//    ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    RUN(B.in);
#endif // ONLINE_JUDGE
    RD(n, m);
    REP(i, m)
    {
        cin >> fst[i] >> snd[i];
        s[fst[i]] = snd[i];
        ss[snd[i]] = fst[i];
    }

    REP(i, n)
    {
        if(i) cout << ' ';
        string tmp;
        cin >> tmp;
        it = s.find(tmp);
        if(it != s.end())
        {
            if(tmp.size() <= s[tmp].size()) cout << tmp;
            else cout << s[tmp];
        }
        else
        {
            if(tmp.size() < ss[tmp].size()) cout << tmp;
            else cout << ss[tmp];
        }
    }

    return 0;
}

C - Crazy Town 

注意long long的问题，，绝杀失败。。

对于某一条直线，A，B分居两边，那么一定要跨过这条直线。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define OT printf
#define MAXN 100010
#define LL long long
#define INF 0x7f7f7f7f
#define RUN(x) freopen(#x, "r", stdin);
#define REP(i, n) for(i = 0; i < n; i++)
#define FOR(i, s, e) for(i = s; i < e; i++)

inline LL RD(LL &x)
{
        x = 0;
        LL flag = 1;
        char ch = getchar();
        while(!isdigit(ch) && ch != '-') { ch = getchar(); if(ch == EOF) return 0; }
        if(ch == '-') { flag = -1; ch = getchar(); }
        while(ch >= '0' && ch <= '9') { x *= 10; x += ch - '0'; ch = getchar(); }
        x *= flag;
        return 1;
}
inline LL RD(LL &x0, LL &x1) { return RD(x0) + RD(x1); }
inline LL RD(LL &x0, LL &x1, LL &x2) { return RD(x0) + RD(x1) + RD(x2); }

/*..........................................dizzy............................................*/

typedef struct Point
{
        LL x, y;
        Point() {}
        Point(LL _x, LL _y):
                x(_x), y(_y) {}
        bool operator <(const Point &argu) const
        {
                if(x == argu.x) return y < argu.y;
                return x < argu.x;
        }
        LL operator ^(const Point &argu) const
        {
            return x * argu.y - y * argu.x;
        }
        LL operator *(const Point &argu) const
        {
            return x * argu.x + y * argu.y;
        }
        Point operator -(const Point &argu) const
        {
            return Point(x - argu.x, y - argu.y);
        }
        void in()
        {
            scanf("%d%d", &x, &y);
        }
        void out()
        {
            printf("%d %d\n", x, y);
        }
}Vector;

LL x, y, a, b, c, n, i;
Point A, B;

int main()
{
#ifndef ONLINE_JUDGE
    RUN(C.in);
#endif // ONLINE_JUDGE

    LL ans = 0;
    RD(x, y); A = Point(x, y);
    RD(x, y); B = Point(x, y);

    RD(n);
    REP(i, n)
    {
        RD(a, b, c);
        LL suma = A.x * a + A.y * b + c;
        LL sumb = B.x * a + B.y * b + c;
        if(suma > 0 && sumb < 0 || suma < 0 && sumb > 0)
            ans++;
    }
    OT("%d\n", ans);

    return 0;
}

还好昨晚没做，不然肯定又要灰了。。