ZROI提高失恋测 $Day8$

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\n" , 2ll - V + E ) ;
    #ifndef ONLINE_JUDGE
    system ("pause") ;
    #endif
    return 0 ;
}

B.春神

咕咕咕…(我还不会)

C.周队

你显然可以把所有的有恐怖袭击的点存起来,然后每次枚举判断.

这样的复杂度是 $O(n^2\times 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 ('\n') ;
    }
    return 0 ;
}