学步园

F - Kings on a Chessboard

国王周围的八个格子不可以再放国王（但是国王可以挨着边界），问在给定大小的棋盘有多少种方法可以放k个国王。

和
POJ 2411 是一模一样的做法。

有两个注意点：

1.国王最多可以放(x + 1) * (y + 1) / 4个，所以国王最多只可能放64个；

2.国王是可以挨着墙壁的，所以设计状态的时候到了最后还剩一个位置时可以再放个国王。

#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define OT printf
#define MOD 1000000007
#define LL long long
#define MAXN (1 << 16) + 10
#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, int &x2) { return RD(x0) + RD(x1) + RD(x2); }

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

bool vis[MAXN];
int cnt[MAXN];
int sta[16 * MAXN][2];
int x, y, k, tot;
int dp[2][MAXN][65];

void dfs(int l, int now, int pre, int nk, int pk)
{
    if((nk + pk > k)) return ;
    if(l > y) return ;

    if(l == y)
    {
        cnt[now] = nk, cnt[pre] = pk;
        sta[tot][0] = pre;
        sta[tot++][1] = now;
    }
    if(l == y - 1)
    {
        dfs(l + 1, (now | 1) << 1, pre << 1, nk + 1, pk);
        dfs(l + 1, now << 1, (pre | 1) << 1, nk, pk + 1);
    }

    dfs(l + 2, (now | 1) << 2, pre << 2, nk + 1, pk);
    dfs(l + 2, now << 2, (pre | 1) << 2, nk, pk + 1);
    dfs(l + 1, now << 1, pre << 1, nk, pk);
}

//int getk(int x)
//{
//    int ans = 0;
//    while(x)
//    {
//        if(x & 1) ans++;
//        x = x >> 1;
//    }
//    return ans;
//}

int work()
{
    if((x + 1) / 2 * (y + 1) / 2 < k) return 0;
    int i, j, c;
    LL ret = 0; tot = 0;
    dfs(0, 0, 0, 0, 0);
//    REP(i, tot) cout << sta[i][0] << ' ' << sta[i][1] << endl;
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;

    FOR(i, 1, x + 1)
    {
        memset(dp[i % 2], 0, sizeof(dp[i % 2]));
        REP(j, tot) REP(c, k + 1)
        {
            if(cnt[sta[j][1]] + c <= k)
            {
                dp[i % 2][sta[j][1]][cnt[sta[j][1]] + c] += dp[(i - 1) % 2][sta[j][0]][c];
                dp[i % 2][sta[j][1]][cnt[sta[j][1]] + c] %= MOD;
            }
        }
    }

    memset(vis, true, sizeof(vis));
    REP(i, tot)
    {
        if(vis[sta[i][1]])
        {
            ret += dp[x % 2][sta[i][1]][k];
            ret %= MOD;
            vis[sta[i][1]] = false;
        }
    }

    return ret;
}

int main()
{
//    RUN(Kings_on_a_Chessboard.in);

    int t; RD(t);
    while(t--)
    {
        RD(x, y, k);
        if(x < y) swap(y, x);
        OT("%d\n", work());
    }
    return 0;
}

I - Space Travel

floyd + 三维上的线段最短距离。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MAXN 110
#define eps 1e-8

int sig(double x)
{
    return (x > eps) - (x < -eps);
}

typedef struct Point
{
        double x, y, z;
        Point(double _x = 0.0, double _y = 0.0, double _z = 0.0):
                x(_x), y(_y), z(_z) {}

        double dis(const Point &argu) const
        {
            return sqrt((x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y) + (z - argu.z) * (z - argu.z));
        }
        Point operator ^(const Point &argu) const
        {
            return Point(y * argu.z - z * argu.y, z * argu.x - x * argu.z, x * argu.y - y * argu.x);
        }
        double operator *(const Point &argu) const
        {
            return x * argu.x + y * argu.y + z * argu.z;
        }
        Point operator +(const Point &argu) const
        {
            return Point(x + argu.x, y + argu.y, z + argu.z);
        }
        Point operator -(const Point &argu) const
        {
            return Point(x - argu.x, y - argu.y, z - argu.z);
        }
        double len() const
        {
            return sqrt(x * x + y * y + z * z);
        }
        double dis_line(Point &a, Point &b)
        {
            return ((*this - a) ^ (b - a)).len() / (b - a).len();
        }
        double dis_seg(Point &a, Point &b)
        {
            if(sig((*this - a) * (b - a)) >= 0 && sig((*this - b) * (a - b)) >= 0) return dis_line(a, b);
            return min(dis(a), dis(b));
        }
        double V6(Point a, Point b, Point c)
        {
            return (((a - *this) ^ (b - *this)) * (c - *this));
        }
        int side(Point &a, Point &b, Point &c) { return sig(V6(a, b, c)); }
        void in()
        {
            scanf("%lf%lf%lf", &x, &y, &z);
        }
        void out()
        {
            printf("%.10lf %.10lf %.10lf\n", x, y, z);
        }
}Vector;

Point pp[MAXN];
double dis[MAXN][MAXN];

double min(double a, double b)
{
    if(sig(a - b) <= 0) return a;
    else return b;
}

double dis_line2(Point a1, Point b1, Point a2, Point b2)
{
    Point v = (b1 - a1) ^ (b2 - a2);
    if(!sig(v.len())) return 0;
    return fabs((a2 - a1) * v) / v.len();
}

double dis_seg2(Point a, Point b, Point c, Point d)
{
    Point v = (b - a) ^ (d - c), o1 = a + v, o2 = c + v;
    if((c.side(o1, a, b) * d.side(o1, a, b) < 0) && (a.side(o2, c, d) * b.side(o2, c, d) < 0))
        return dis_line2(a, b, c, d);
    else return min(min(a.dis_seg(c, d), b.dis_seg(c, d)), min(c.dis_seg(a, b), d.dis_seg(a, b)));
}

double work()
{
    int n; scanf("%d", &n);
    n *= 2; n += 2;
    pp[0].in(); pp[n - 1].in();
    for(int i = 1; i < n - 1; i ++) pp[i].in();

    for(int i = 0; i < n; i++) dis[i][i] = 0.0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < i; j++)
            dis[i][j] = dis[j][i] = pp[i].dis(pp[j]);

    for(int i = 1; i < n - 1; i += 2)
    {
        dis[i][i + 1] = dis[i + 1][i] = 0.0;
        for(int j = 0; j < n; j++)
        {
            if(i == j || i + 1 == j) continue;
            double tmp = pp[j].dis_seg(pp[i], pp[i + 1]);
            dis[i][j] = dis[j][i] = min(dis[i][j], tmp);
            dis[i + 1][j] = dis[j][i + 1] = min(dis[i + 1][j], tmp);
        }
    }

    for(int i = 1; i < n - 1; i += 2)
        for(int j = 1; j < n - 1; j += 2)
        {
            if(i == j) continue;
            double tmp = dis_seg2(pp[i], pp[i + 1], pp[j], pp[j + 1]);
            dis[i][j] = dis[j][i] = min(dis[i][j], tmp);
            dis[i + 1][j] = dis[j][i + 1] = min(dis[i + 1][j], tmp);
            dis[i][j + 1] = dis[j + 1][i] = min(dis[i][j + 1], tmp);
            dis[i + 1][j + 1] = dis[j + 1][i + 1] = min(dis[i + 1][j + 1], tmp);
        }

//    for(int i = 0; i < n; i++)
//    {
//        for(int j = 0; j < n; j++)
//            printf("%11.8lf %d %d   ", dis[i][j], i, j);
//        printf("\n");
//    }

    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

    return dis[0][n - 1];
}

int main()
{
//    freopen("I.in", "r", stdin);
//    freopen("I.out", "w", stdout);

    int cas; scanf("%d", &cas);
    while(cas--)
    {
        printf("%.18lf\n", work());
    }
    return 0;
}

I - Dimensions

差点忘了这个恶模拟。。我实在是太弱了，写这道题以至于昏厥。。

以后一定要从全局考虑。。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <map>
using namespace std;
#define MAXN 300
#define OT printf
#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;
}

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

struct Unit
{
    double num;
    int p[6];
    Unit() {}
    void clr(void) { num = 1.0; memset(p, 0, sizeof(p)); }
    void out() { int i; OT("%.8lf ", num); REP(i, 6) OT("%d ", p[i]); puts(""); }

    bool operator ==(Unit &x)
    {
        int i;
        REP(i, 6) if(p[i] != x.p[i]) return false;
        return true;
    }
    Unit& operator +(const Unit &x) const
    {
        Unit sum = x;
        sum.num = num + x.num;
        return sum;
    }
    Unit& operator -(const Unit &x) const
    {
        Unit sum = x;
        sum.num = num - x.num;
        return sum;
    }
    Unit& operator *(const Unit &x) const
    {
        Unit sum;
        sum.num = num * x.num;
        int i;
        REP(i, 6) sum.p[i] = p[i] + x.p[i];
        return sum;
    }
};

Unit uu[MAXN];
const char Symbol[6][4] = {"m", "kg", "s", "A", "K", "cd"};
char un[MAXN][MAXN];
int tot;

int srch(char *str)
{
    int i;
    REP(i, tot) if(strcmp(un[i], str) == 0) return i;
    return -1;
}

char wrd[MAXN][MAXN];
char str[MAXN], stra[MAXN], strb[MAXN];

void init()
{
    int i;
    REP(i, 6)
    {
        uu[i].clr();
        uu[i].p[i] = 1;
        uu[i].num = 1.0;
    }

    REP(i, 6) strcpy(un[i], Symbol[i]);
    tot = 6;
}

inline int getWrd(char *str)
{
    int cnt = 0, k = 0, i;
    int len = strlen(str);

    memset(wrd, 0, sizeof(wrd));
    REP(i, len)
    {
        if(str[i] == ' ') wrd[cnt][k] = '\0', cnt++, k = 0, i++;
        wrd[cnt][k++] = str[i];
    }
//    REP(i, cnt + 1) cout << wrd[i] << endl;
    return cnt;
}

inline void getUnit(int cnt, int id)
{
    int s = 0;
    double w = 1.0;
    uu[id].clr();

    int len0 = strlen(wrd[0]);
    if(isdigit(wrd[0][len0 - 1])) sscanf(wrd[0], "%lf", &w), s++;
    uu[id].num = w;

    int flag = 1, i, j, t;
    FOR(i, s, cnt + 1)
    {
        if(wrd[i][0] == '/') { flag = -1; continue; }
        double v = 1.0;
        int lenw = strlen(wrd[i]);
        if(isdigit(wrd[i][lenw - 1]))
        {
            wrd[i][lenw - 2] = '\0';
            v = (double)(wrd[i][lenw - 1] - '0');
        }

        int c = srch(wrd[i]);

        if(~c)
        {
            if(flag > 0) REP(t, v) uu[id].num *= uu[c].num;
            else REP(t, v) uu[id].num /= uu[c].num;
            REP(j, 6) { uu[id].p[j] += flag * v * uu[c].p[j]; }
        }
    }
}

inline bool ck1(char ch)
{
    if(ch == '=') return true;
    return false;
}

inline bool ck2(int i)
{
    if((str[i] == '+' || str[i] == '-' || str[i] == '*') && str[i + 1] == ' ') return true;
    return false;
}

void colUnit(int u)
{
    int i, j;
    REP(i, u)
    {
        gets(str);
        int len = strlen(str);
        REP(j, len) if(ck1(str[j])) break;
        str[j - 1] = '\0';
        int cnt = getWrd(str + j + 2);
        getUnit(cnt, tot);
        memset(str + j, 0, sizeof(str + j));
        strcpy(un[tot], str);
        tot++;
    }
}

inline void put(int id)
{
    int i;
    OT("%.6lf", uu[id].num);
    bool sub = false;
    REP(i, 6)
    {
        if(uu[id].p[i] < 0) sub = true;
        if(uu[id].p[i] > 0)
        {
            OT(" %s", Symbol[i]);
            if(uu[id].p[i] > 1) OT("^%d", uu[id].p[i]);
        }
    }

    if(sub)
    {
        OT(" /");
        REP(i, 6) if(uu[id].p[i] < 0)
        {
            OT(" %s", Symbol[i]);
            if(uu[id].p[i] < -1) OT("^%d", -uu[id].p[i]);
        }
    }
    puts("");
}

void work(int u, int n)
{
    int i, j;
    char ch;
    bool flag = false;
    Unit &a = uu[MAXN - 1], &b = uu[MAXN - 2], &ans = uu[MAXN - 3];
    a.clr(), b.clr(), ans.clr();

    gets(str);
    int len = strlen(str);
    FOR(i, 1, len) if(ck2(i)) { flag = true; break; }

    if(flag)
    {
        strcpy(strb, str + i + 2);
        ch = str[i]; str[i - 1] = '\0';

        int cnt = getWrd(strb);
        getUnit(cnt, MAXN - 2);
        memset(str + i, 0, sizeof(str + i));
    }

    strcpy(stra, str);
    int cnt = getWrd(stra);
    getUnit(cnt, MAXN - 1);

    if(flag)
    {
        if(ch == '+')
        {
            if(a == b) { ans = (a + b); put(MAXN - 3); }
            else puts("Incompatible");
        }
        if(ch == '-')
        {
            if(a == b) { ans = (a - b); put(MAXN - 3); }
            else puts("Incompatible");
        }
        if(ch == '*') { ans = (a * b); put(MAXN - 3); }
    }
    else put(MAXN - 1);
}

int main()
{
//    RUN(Dimensions.txt);
//    freopen("out_2.txt", "w", stdout);

    int u;
    while(RD(u))
    {
        init();
        colUnit(u);

        int i, n; RD(n);
        REP(i, n) work(u, n);
    }

    return 0;
}