UVA 12633 Super Rooks on Chessboard

正文索引 [隐藏]

题目翻译
题解
代码

题目翻译

超级车可以攻击行、列、主对角线 3 个方向。R∗C的棋盘上有N个超级车，问不能被攻击的格子总数。（R,C,N≤50000)

题解

首先行和列的格子情况我们很容易处理。
然后我们观察主对角线，在一条主对角线上的格子的特征很明显 i – j 为一个定值。
用R[x]表示某一行不被行攻击，C[x]表示某一列是否不被列攻击。那么一条主对角线上没有被行列攻击的格子数量为D[k] = ∑ ∑ ( R[i] * C[j] * [i – j == k])
如此可以使用FFT处理。

代码

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
const int Maxn = 50000;
const double Pi = acos(-1.0);
struct complex {
    double r, i;
    complex(double r = 0, double i = 0):r(r), i(i) {}
    complex operator + (const complex &ot) const {
        return complex(r + ot.r, i + ot.i);
    }
    complex operator - (const complex &ot) const {
        return complex(r - ot.r, i - ot.i);
    }
    complex operator * (const complex &ot) const {
        return complex(r * ot.r - i * ot.i, r * ot.i + i * ot.r);
    }
}x1[Maxn * 4 * 2], x2[Maxn * 4 * 2];
void change(complex *y, int len) {
    for(int i = 1, j = len / 2; i < len - 1; ++i) {
        if(i < j) swap(y[i], y[j]);
        int k = len / 2;
        while(j >= k) {
            j -= k;
            k >>= 1;
        }
        j += k;
    }
}
void FFT(complex *y, int len, int on) {
    change(y, len);
    for(int h = 2; h <= len; h <<= 1) {
        complex wn = complex(cos(on * 2 * Pi / h), sin(on * 2 * Pi / h));
        for(int j = 0; j < len; j += h) {
            complex w = complex(1, 0);
            for(int k = j; k < j + h / 2; ++k) {
                complex u = y[k];
                complex t = y[k+h/2] * w;
                y[k] = u + t;
                y[k+h/2] = u - t;
                w = w * wn;
            }
        }
    }
    if(on == -1) {
        for(int i = 0; i < len; ++i)
            y[i].r /= len;
    }
}
int cntX[Maxn + 5], cntY[Maxn + 5], cntR[Maxn * 2 + 5];
int cntRow, cntColumn;
int R, C, N;
int delta;
inline void solve(int T)
{
    scanf("%d%d%d", &R, &C, &N);
    cntRow = R;
    cntColumn = C;
    memset(cntX, 0, sizeof(cntX));
    memset(cntY, 0, sizeof(cntY));
    memset(cntR, 0, sizeof(cntR));
    for (int i = 1; i <= N; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if ((++cntX[x]) == 1) cntRow--;
        if ((++cntY[y]) == 1) cntColumn--;
        cntR[C + x - y]++;
    }
    int n = ceil(log(R + C + 5) / log(2)) + 1;
    n = 1 << n;
    for (int i = 0 ; i < n; i++) x1[i] = complex(0, 0);
    for (int i = 1; i <= R; i++) x1[i] = complex((cntX[i] == 0), 0);
    for (int i = 0 ; i < n; i++) x2[i] = complex(0, 0);
    for (int i = 1; i <= C; i++) x2[C - i] = complex((cntY[i] == 0), 0);
    FFT(x1, n, 1);
    FFT(x2, n, 1);
    for (int i = 0; i <= n; i++) x1[i] = x1[i] * x2[i];
    FFT(x1, n, -1);
    LL Ans = (LL)cntRow * (LL)cntColumn;
    for (int i = 1; i <= R + C ; i++) Ans -= (LL)(cntR[i] > 0 ? 1 : 0) * (LL)(x1[i].r + 0.5);
    printf("Case %d: %lld\n", T, Ans);
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T = 0;
    while(scanf("%d", &T) != EOF)
        for (int i = 1; i <= T; i++)
            solve(i);
    return 0;
}

#include<cstdio>

#include<cmath>

#include<iostream>

#include<cstring>

#define LL long long

using namespace std;

const int Maxn = 50000;

const double Pi = acos(-1.0);

struct complex {

double r, i;

complex(double r = 0, double i = 0):r(r), i(i) {}

complex operator + (const complex &ot) const {

return complex(r + ot.r, i + ot.i);

}

complex operator - (const complex &ot) const {

return complex(r - ot.r, i - ot.i);

}

complex operator * (const complex &ot) const {

return complex(r * ot.r - i * ot.i, r * ot.i + i * ot.r);

}

}x1[Maxn * 4 * 2], x2[Maxn * 4 * 2];

void change(complex *y, int len) {

for(int i = 1, j = len / 2; i < len - 1; ++i) {

if(i < j) swap(y[i], y[j]);

int k = len / 2;

while(j >= k) {

j -= k;

k >>= 1;

}

j += k;

}

void FFT(complex *y, int len, int on) {

change(y, len);

for(int h = 2; h <= len; h <<= 1) {

complex wn = complex(cos(on * 2 * Pi / h), sin(on * 2 * Pi / h));

for(int j = 0; j < len; j += h) {

complex w = complex(1, 0);

for(int k = j; k < j + h / 2; ++k) {

complex u = y[k];

complex t = y[k+h/2] * w;

y[k] = u + t;

y[k+h/2] = u - t;

w = w * wn;

}

if(on == -1) {

for(int i = 0; i < len; ++i)

y[i].r /= len;

}

int cntX[Maxn + 5], cntY[Maxn + 5], cntR[Maxn * 2 + 5];

int cntRow, cntColumn;

int R, C, N;

int delta;

inline void solve(int T)

{

scanf("%d%d%d", &R, &C, &N);

cntRow = R;

cntColumn = C;

memset(cntX, 0, sizeof(cntX));

memset(cntY, 0, sizeof(cntY));

memset(cntR, 0, sizeof(cntR));

for (int i = 1; i <= N; i++)

{

int x, y;

scanf("%d%d", &x, &y);

if ((++cntX[x]) == 1) cntRow--;

if ((++cntY[y]) == 1) cntColumn--;

cntR[C + x - y]++;

}

int n = ceil(log(R + C + 5) / log(2)) + 1;

n = 1 << n;

for (int i = 0 ; i < n; i++) x1[i] = complex(0, 0);

for (int i = 1; i <= R; i++) x1[i] = complex((cntX[i] == 0), 0);

for (int i = 0 ; i < n; i++) x2[i] = complex(0, 0);

for (int i = 1; i <= C; i++) x2[C - i] = complex((cntY[i] == 0), 0);

FFT(x1, n, 1);

FFT(x2, n, 1);

for (int i = 0; i <= n; i++) x1[i] = x1[i] * x2[i];

FFT(x1, n, -1);

LL Ans = (LL)cntRow * (LL)cntColumn;

for (int i = 1; i <= R + C ; i++) Ans -= (LL)(cntR[i] > 0 ? 1 : 0) * (LL)(x1[i].r + 0.5);

printf("Case %d: %lld\n", T, Ans);

}

int main()

{

//freopen("in.txt","r",stdin);

//freopen("out.txt","w",stdout);

int T = 0;

while(scanf("%d", &T) != EOF)

for (int i = 1; i <= T; i++)

solve(i);

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑