首页 > 代码库 > UVA - 12633 Super Rooks on Chessboard FFT
UVA - 12633 Super Rooks on Chessboard FFT
题目链接：点这里
题意:
给你一个矩阵R*C，n个点，与给的的n个点同一列同一行，同一条主对角线上的点都被染黑
问你最后有多少个点没有被染黑
题解：
把每一列每一行没有被染黑的x,y找出来，其任意组合起来是没这种情况下的答案（同一条主对角线上的点都被染黑）
对于 x - y，我们可以拿来判断两个点是不是相同的一条主对角线上
那么对x、-y进行任意组合，FFT加速
总的答案就是，没有被染过行数*没有被染过的列数 - （找不到相同的x- y）
具体看代码吧
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 1e5+10, M = 1e3+20,inf = 2e9,mod = 1e9+7;struct Complex { double r , i ; Complex () {} Complex ( double r , double i ) : r ( r ) , i ( i ) {} Complex operator + ( const Complex& t ) const { return Complex ( r + t.r , i + t.i ) ; } Complex operator - ( const Complex& t ) const { return Complex ( r - t.r , i - t.i ) ; } Complex operator * ( const Complex& t ) const { return Complex ( r * t.r - i * t.i , r * t.i + i * t.r ) ; }} ;void FFT ( Complex y[] , int n , int rev ) { for ( int i = 1 , j , t , k ; i < n ; ++ i ) { for ( j = 0 , t = i , k = n >> 1 ; k ; k >>= 1 , t >>= 1 ) j = j << 1 | t & 1 ; if ( i < j ) swap ( y[i] , y[j] ) ; } for ( int s = 2 , ds = 1 ; s <= n ; ds = s , s <<= 1 ) { Complex wn = Complex ( cos ( rev * 2 * pi / s ) , sin ( rev * 2 * pi / s ) ) , w ( 1 , 0 ) , t ; for ( int k = 0 ; k < ds ; ++ k , w = w * wn ) { for ( int i = k ; i < n ; i += s ) { y[i + ds] = y[i] - ( t = w * y[i + ds] ) ; y[i] = y[i] + t ; } } } if ( rev == -1 ) for ( int i = 0 ; i < n ; ++ i ) y[i].r /= n ;}Complex s[N*4],t[N*4];int R,C,n,T,col[N],row[N],d[N*2];int main() { int cas = 1; scanf("%d",&T); while(T--) { scanf("%d%d%d",&R,&C,&n); for(int i = 1; i <= R; ++i) col[i] = 1; for(int i = 1; i <= C; ++i) row[50000 - i] = 1; memset(d,0,sizeof(d)); for(int i = 1; i <= n; ++i) { int x,y; scanf("%d%d",&x,&y); d[x - y + 50000] = 1; col[x] = 0; row[50000 - y] = 0; } int n1 = 1; while(n1 < 50000*2) n1<<=1; for(int i = 0; i <= R; ++i)s[i] = Complex(col[i],0); for(int i = R+1; i < n1; ++i)s[i] = Complex(0,0); for(int i = 0; i < 50000 - C; ++i)t[i] = Complex(0,0); for(int i = 1; i <= C; ++i) t[50000 - i] = Complex(row[50000 - i],0); for(int i = 50000; i < n1; ++i) t[i] = Complex(0,0); FFT(s,n1,1);FFT(t,n1,1); for(int i = 0; i < n1; ++i) s[i] = s[i] * t[i]; FFT(s,n1,-1); LL A = 0, B = 0; for(int i = 1; i <= R; ++i) if(col[i]) A++; for(int i = 1; i <= C; ++i) if(row[50000 - i]) B++; LL ans = A*B; for(int i = 1+50000 - C; i <= 50000*2 - 1; ++i) { int x = (int ) (s[i].r + 0.5); if(d[i]) ans -= x; } printf("Case %d: %lld\n",cas++,ans); } return 0;}
UVA - 12633 Super Rooks on Chessboard FFT
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。