Fork me on GitHub

ZROI普及五连测Day4

Posted on | | Views:

ZROI普及五连测 $Day4$

ZROI普及五连测 $Day4$

A.刷题王者

水题,略

B.回到原点

先把能抵消的全部抵消,剩下的就是需要调整的.
剩下的一定是不能抵消的,而且 $U,D$ 和 $L,R$ 两组一定是每组至多剩一种没有匹配完.

调整的时候,考虑自身内部调整和相互匹配,取 $min$ 即可.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#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 ) )
#define mabs(x) ( x < 0 ? - 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 + 10 ;

char s[N] ;
int v[N] , w[N] ;
int n , x , y ;
int cnt[4] ;

signed main (int argc , char * argv[]) {
    scanf ("%s" , s + 1 ) ; n = strlen ( s + 1 ) ;
    if ( n & 1 ) return puts ("-1") , 0 ;
    rep ( i , 1 , n ) if ( s[i] == 'U' ) v[i] = 1 ; else if ( s[i] == 'D' ) v[i] = - 1 ;
    rep ( i , 1 , n ) if ( s[i] == 'L' ) w[i] = 1 ; else if ( s[i] == 'R' ) w[i] = - 1 ;
    rep ( i , 1 , n ) { v[i] += v[i-1] ; w[i] += w[i-1] ; }
    x = abs ( v[n] ) ; y = abs ( w[n] ) ;
    if ( ( x + y ) & 1 ) return puts ("-1") , 0 ;
    if ( x == y ) printf ("%d\n" , x ) ;
    else {
        int del = abs ( x - y ) ;
        if ( x > y ) x -= del , y += del ;
        else x += del , y -= del ;
        if ( ( x & 1 ) && ( y & 1 ) ) {
            int tmp = x / 2 + y / 2 + 1 ;
            printf ("%d\n" , min ( del + x , tmp ) ) ;
        } else {
            int tmp = x / 2 + y / 2 ;
            printf ("%d\n" , min ( del + x , tmp ) ) ;
        }
    }
    return 0 ;
}

C.快乐矩阵

把矩阵黑白间隔染色 $:$

你发现,每次一定是选择一个黑格子,一个白格子.

然后由于是矩阵,所以我们一定可以构造出一条从 $(1,1)$ 到 $(n,m)$ 的不重不漏的路径.

每次沿着这样的路径一路修改下去,每次操作把上一个格子清零,这样一定能推到最后.

到最后能置为全 $0$ 的充要条件一定是黑格子之和等于白格子之和.

愉快 $AC$ .

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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 = 5e2 + 11 ;

int idx , res1 , res2 ;
int e[N][N] , n , m ;
bool stats[N] ;

signed main (int argc , char * argv[]) {
    n = rint () ; m = rint () ;
    rep ( i , 1 , n ) rep ( j , 1 , m ) e[i][j] = rint () ;
    rep ( i , 1 , m ) stats[i] = stats[i-1] ^ 1 ;
    rep ( i , 1 , n ) rep ( j , 1 , m ) {
        if ( i & 1 ) {
            if ( stats[j] ) res1 += e[i][j] ;
            else res2 += e[i][j] ;
        } else {
            if ( stats[j] ) res2 += e[i][j] ;
            else res1 += e[i][j] ;
        }
    }
    puts ( res1 == res2 ? "Yes" : "No" ) ;
    return 0 ;
}

D.梦中的位运算

明白这样一个事实 $:$

$$x^2+y^2\le (x\&y)^2 + (x|y)^2$$

引理 $:$
$1$守恒定律 $:$ 在该题目叙述的系统中,$1$既不会凭空产生也不会凭空消失,只会从一个元素转移到另一个元素,系统中 $1$ 的代数和时时刻刻保持不变.(滑稽.jpg)

所以…你贪心地把所有 $1$ 堆一起就好了…

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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 = 1e5 + 100 ;

int n , v[N] , cnt[65] , g[65] , ans ;

vector < bool > tmp ;
inline void divide (int x) {
    tmp.clear () ;
    while ( x ) { tmp.pb ( x & 1ll ) ; x >>= 1ll ; }
    // for (int k : tmp) printf ("%lld " , k ) ; puts ("") ;
    for (int i = 0 ; i < tmp.size () ; ++ i)
        if ( tmp[i] ) ++ cnt[i] ;
    return ;
}
 
inline int quick (int a , int p) {
    int res = 1ll ;
    while ( p ) {
        if ( p & 1ll ) res *= a ;
        a *= a ; p >>= 1ll ;
    }
    return res ;
}

signed main (int argc , char * argv[]) {
    n = rint () ; rep ( i , 1 , n ) v[i] = rint () ;
    rep ( i , 0 , 62 ) g[i] = quick ( 2ll , i ) ; 
    rep ( i , 1 , n ) divide ( v[i] ) ;
    // rep ( i , 0 , 4 ) printf ("%lldth : %lld\n" , i , cnt[i] ) ;
    rep ( i , 1 , n ) {
        int res = 0 ;
        per ( j , 62 , 0 ) if ( cnt[j] ) -- cnt[j] , res += g[j] ;
        v[i] = res ;
    }
    rep ( i , 1 , n ) ans += v[i] * v[i] ;
    printf ("%lld\n" , ans ) ;
    return 0 ;
}
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多