Yijan's Blog HomeArchives
AGC051C

AGC051C Flipper

可以注意到，我们对 $x$ 和 $x+1$ 两个位置作用 flipper 后，可以对 $(x,y),(x,y+1),(x+3,y),(x+3,y+1)$ 进行翻转，可以称此为一次基本操作。同时，我们只需要不断进行基本操作，可以对任何 $x$ 轴长度为 $3$ 的倍数的矩形的四个端点进行操作。

这提示我们把 $x$ 坐标按模 $3$ 分类，得到三个坐标系。在这三个坐标系中，基本操作可以对任何一个矩形的四个端点进行操作。事实上，如果需要操作的点在每个 $x,y$ 坐标上均有偶数个，那么一定可以把所有点操作完成。证明可以考虑任取两行和其中一行中有点的一列，进行一次操作后点的个数一定减少了，并且不会破坏每行每列偶数个点的性质。

同时，如果只进行上述基本操作，对每个坐标系我们只需要取 $\max(a,b)$ 个点保留即可做到剩余的点最少，其中 $a,b$ 分别是有奇数个点的行数和列数。因为如果奇数行比较多，可以在所有奇数列和一个奇数行相交的地方翻转操作或不操作的状态，可以用 $\max(a,b)$ 步构造出一个合法解，同时这显然杀死操作数的下界。

这样就结束了吗？可以发现仅仅使用上述的基本操作是不能涵盖所有操作的，例如一共只进行一次操作。具体来讲，如果想要考虑到所有操作翻转情况，还需要一种操作：给三个坐标系中的相邻两行都增加一个点。同理，不断进行调整可以得到给三个坐标系中任意偶数行增加一个点，或者说翻转奇偶状态。如果有这个操作，它可以和之前的基本操作拼起来得到任何一个翻转操作序列。

可以发现，这个特殊操作只会对奇数行的数量有影响，不会对奇数列的数量有影响。因此假设三个图中奇数行的数量分别是 $a_1,a_2,a_3$ ，奇数列的数量分别是 $b_1,b_2,b_3$ ，在进行操作时其实就是对一些 $a$ 增加一，另一些减少 $1$ ，然后计算 $\sum_{1 \le i \le 3} \max(a_i,b_i)$ 。同时，我们可以对每行分别考虑，每行都相当于有一个 $(\pm 1,\pm 1,\pm 1)$ 的算子可以用，你需要用任意一些算子来最小化刚刚那个式子。

首先，$(-1,-1,-1)$ 一定会被使用，所以可以最开始就用完。可以发现如果使用过 $(+1,-1,-1)$ 就一定不会使用 $(-1,+1,+1)$ ，否则这两个去掉某一个肯定更优。同时，不可能同时使用 $(+1,+1,-1)$ 和 $(+1,-1,+1)$ ，因为这俩在一起对答案的贡献是负的。又可以发现，一起选择两个有两个减一的操作是赚的，所以一定可以尽量用完个数最少的 $(-,-,+)$ ，然后尽量用完次少的。可以先枚举一个尽量减少的值，对它使用 $(-1,-1,+1),(-1,+1,-1)$ ，最后再分别尝试用 $(+1,-1,-1)$ 和 $(-1,+1,+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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include "bits/stdc++.h"
#include "atcoder/all"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
// #pragma GCC optimize(2)
typedef long long ll;
const int MAXN = 1e6 + 10;
const int P = 1e9 + 7;
int n;

vector<pii> pois;
map<int,int> idxx , idxy;
int ret[MAXN];
int cx , cy;
int cnx[MAXN] , cny[MAXN] , idx[MAXN];
int sol() {
    vector<pii> poi[3];
    rep( i , 0 , 2 ) poi[i].clear();
    for( auto& t : pois ) {
        poi[t.se % 3].pb( t );
    }
    int ans = 1e9;
    int cur[3] , bd[3];
    map<int,int> S;
    rep( rem , 0 , 2 ) {
        idxx.clear() , idxy.clear();
        cx = cy = 0;
        auto &po = poi[rem];
        for( auto& t : po ) {
            if( !idxx.count( t.fi ) ) idxx[t.fi] = ++ cx;
            if( !idxy.count( t.se ) ) idxy[t.se] = ++ cy;
            cnx[idxx[t.fi]] ++ , cny[idxy[t.se]] ++;
        }
        int res = 0 , rx = 0 , ry = 0;
        rep( i , 1 , cx ) if( cnx[i] & 1 ) ++ rx;
        rep( i , 1 , cy ) if( cny[i] & 1 ) ++ ry;
        bd[rem] = ry , cur[rem] = rx;
        for( auto& t : idxx ) if( cnx[t.se] & 1 ) {
            S[t.fi] |= ( 1 << rem );
        }
        rep( i , 1 , cx ) cnx[i] = 0;
        rep( i , 1 , cy ) cny[i] = 0;
    }
    int ops[12];
    mem( ops );

    for( auto t : S ) ++ ops[t.se];
    int fcur[3];

    auto chkans = [&]( ) {
        int ret = 0;
        rep( i , 0 , 2 )
            ret = ret + max( fcur[i] - bd[i] , 0 );
        ans = min( ans , ret );
    };

    int tim = 0;
    auto reset = [&] () {
        tim = 0;
        memcpy( fcur , cur , sizeof fcur );
    };
    auto doop = [&]( int x ) {
        if( x & 1 ) -- fcur[0]; else ++ fcur[0];
        if( x & 2 ) -- fcur[1]; else ++ fcur[1];
        if( x & 4 ) -- fcur[2]; else ++ fcur[2];
        ++ tim;
        if( ~tim & 1 ) chkans();
    };
    auto rollback = [&] ( int x ) {
        if( x & 1 ) ++ fcur[0]; else -- fcur[0];
        if( x & 2 ) ++ fcur[1]; else -- fcur[1];
        if( x & 4 ) ++ fcur[2]; else -- fcur[2];
        -- tim;
    };

    reset();
    chkans();

    rep( i , 0 , 2 ) rep( j , 0 , 2 ) if( j != i ) {
        int t = i ^ j ^ 3;
        int si = ( 1 << i ) , sj = ( 1 << j ) , st = ( 1 << t );
        reset();
        rep( k , 1 , ops[7] ) doop( 7 );
        rep( k , 1 , ops[sj | st] ) doop( sj | st );
        rep( k , 1 , ops[si | st] ) doop( si | st );
        rep( k , 1 , ops[si | sj] ) doop( si | sj );
    }
    rep( i , 0 , 2 ) rep( j , 0 , 2 ) if( j != i ) {
        int t = i ^ j ^ 3;
        int si = ( 1 << i ) , sj = ( 1 << j ) , st = ( 1 << t );
        reset();
        rep( k , 1 , ops[7] ) doop( 7 );
        rep( k , 1 , ops[sj | st] ) doop( sj | st );
        rep( k , 1 , ops[si | st] ) doop( si | st );
        rep( k , 1 , ops[st] ) doop( st );
    }
    // cout << bd[0] << ' ' << bd[1] << ' ' << bd[2] << endl;
    // cout << cur[0] << ' ' << cur[1] << ' ' << cur[2] << endl;
    // rep( i , 0 , 7 ) cout << "# " << i << ' ' << ops[i] << endl;
    return ans + bd[0] + bd[1] + bd[2];
}

void solve() {
    cin >> n;
    rep( i , 1 , n ) {
        int x , y;
        scanf("%d%d",&x,&y);
        pois.eb( x , y );
    }
    int res = sol();
    cout << res << endl;
}

signed main() {
//	 freopen("in","r",stdin);
	// freopen("fout","w",stdout);
	// int T;cin >> T;while( T-- ) solve();
	solve();
}

文章作者: yijan
文章链接: https://yijan.co/AGC051C/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！
AGC