ZROI提高失恋测 (Day8)
A.许强强
平面图的欧拉公式 (: V-E+X=2) .
其中, (V) 是点数, (E) 是边数, (X) 是连通数.
所以我们只需维护点集和边集最后统计 (size) 即可.
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define int long long
#define pb push_back
#define db double
#define ull unsigned long long
#define lowbit(x) ( x & ( - x ) )
using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;
template < class T >
inline T read () {
T x = 0 , f = 1 ; char ch = getchar () ;
while ( ch < '0' || ch > '9' ) {
if ( ch == '-' ) f = - 1 ;
ch = getchar () ;
}
while ( ch >= '0' && ch <= '9' ) {
x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
ch = getchar () ;
}
return f * x ;
}
const int N = 5e5 + 100 ;
set < pii > p ;
set < pair < pii , pii > > e ;
char s[N] ;
int n , tx , ty ;
signed main (int argc , char * argv[]) {
p.insert ( { 0 , 0 } ) ;
scanf ("%s" , s + 1 ) ; n = strlen ( s + 1 ) ;
rep ( i , 1 , n ) {
int dx = tx , dy = ty ;
if ( s[i] == 'U' ) ++ dy ;
if ( s[i] == 'D' ) -- dy ;
if ( s[i] == 'L' ) -- dx ;
if ( s[i] == 'R' ) ++ dx ;
p.insert ( { dx , dy } ) ;
e.insert ( { { tx , ty } , { dx , dy } } ) ;
e.insert ( { { dx , dy } , { tx , ty } } ) ;
tx = dx ; ty = dy ;
}
int V = p.size () , E = e.size () / 2 ;
printf ("%lld
" , 2ll - V + E ) ;
#ifndef ONLINE_JUDGE
system ("pause") ;
#endif
return 0 ;
}
B.春神
咕咕咕...(我还不会)
C.周队
你显然可以把所有的有恐怖袭击的点存起来,然后每次枚举判断.
这样的复杂度是 (O(n^2 imes X)) 的,其中 (X) 是有恐怖袭击的点数.
但我们发现枚举恐怖袭击的点数判断是可能做到 (Theta(1)) 的,如果你运气够好,枚举到第二个就出现了相同的曼哈顿距离,就不需要继续枚举了,而如果每次都这样,你的实际总复杂度就是 (Theta(n^2)).这显然可以通过.
但我们发现这是不可能的,不过我们可以使用 (random\_shuffle) 来打乱存储的数组,这样期望复杂度是优秀的.
因为它要卡你,必须让你每次都枚举到最后,你随机打乱一下,就卡不到你了.
(当然这不是正解)
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define pb push_back
#define db double
#define ull unsigned long long
#define lowbit(x) ( x & ( - x ) )
using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;
template < class T >
inline T read () {
T x = 0 , f = 1 ; char ch = getchar () ;
while ( ch < '0' || ch > '9' ) {
if ( ch == '-' ) f = - 1 ;
ch = getchar () ;
}
while ( ch >= '0' && ch <= '9' ) {
x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
ch = getchar () ;
}
return f * x ;
}
const int N = 1e3 + 7 ;
int n , cnt , tot ; pii pos[N*N] ;
bool e[N][N] , vis[N*2+100] ;
inline int dist (int x , int y , int a , int b) { return abs ( x - a ) + abs ( y - b ) ; }
signed main (int argc , char * argv[]) {
n = rint () ; cnt = 0 ;
rep ( i , 1 , n ) rep ( j , 1 , n ) {
e[i][j] = rint () ;
if ( e[i][j] ) pos[++cnt] = { i , j } ;
}
std::random_shuffle ( pos + 1 , pos + cnt + 1 ) ;
for (int i = 1 ; i <= n ; ++ i) {
for (int j = 1 ; j <= n ; ++ j) {
bool f = false ; MEM ( vis , 0 ) ;
rep ( k , 1 , cnt ) {
int dis = dist ( i , j , pos[k].one , pos[k].two ) ;
if ( vis[dis] ) { f = true ; break ; }
vis[dis] = true ;
}
if ( f ) putchar ('Y') ; else putchar ('N') ;
putchar (' ') ;
}
putchar ('
') ;
}
return 0 ;
}