CF1031E Triple Flips

Arahc 11.0
  2022-11-09 08:00 2022-11-09 08:00 创建   2023-03-21 13:14:42 2023-03-21 13:14:42 更新      1.6k 字  8 分钟  

题面

简化题意

给定一个 01 串，每次操作可以选择三个下标 i,j,ki,j,k 满足 i<j<k,j−i=k−ji<j<k,j-i=k-j，然后将 i,j,ki,j,k 三个位置 01 翻转。

构造一组操作数不超过 ⌊n3⌋+12\left\lfloor\frac{n}{3}\right\rfloor+12 的方案，使得原序列全部变成 0，或判定无解。

n≤105n\leq 10^5。

题解

考虑操作数 ⌊n3⌋\left\lfloor\frac{n}{3}\right\rfloor 的意义，即平均每次操作都要做到把三个数变成 0。最后留有 1212 个调整用的操作数。而观察打表不难发现，对于 n≤10n\leq 10 的情况，可以用不超过 1212 步操作还原。也就是说，对于 n>10n>10 的情况，我们可以只管怎么用 ⌊n3⌋\left\lfloor\frac{n}{3}\right\rfloor 的操作数把前面的部分还原了，不需要管最后剩下的这 1010 个数。

最简单的肯定是三个一组地考虑（不妨设每组的开头一定是个 1，否则如果是 0，说明这个位置已经还原了，不需要管）：对于 111 的情况，将三个 1 一起反转即可。但是不是这种情况的组合，就无法用一次操作完成了。

三个一组无法完成的情况，考虑六个一组，能否用两次操作完成。答案是肯定的。

读到这里的话你应该就能去试试然后手玩六个一组的所有情况了 qwq。值得注意的是，由于六个或三个一组的所有情况我们都有办法应对，而最后 1010 个数字我们可以爆搜解决，因此在处理当前六个一组的时候，是可以操作修改后面的格子的，无需考虑影响，只要每个六个一组使用的操作次数不超过两次即可。

下面是六个一组的所有情况的一种可行方案（蓝色方框表示一次操作，红色斜正方形表示一次操作，紫色的表示两此操作都用到了这个位置）：

一种方案

当然你可以整合其中类似的操作方案，不然分讨 24 种情况还是有点让人自闭的。

顺带提一句最后那些数字怎么办，你把状态全部记下来，把能通过一次操作转化的状态连边，跑一遍最短路即可。

代码

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Begin;
const int max_n=100005,max_m=1000006,max_s=1052,inf=1000000000000015LL;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
struct graph{
    int ct,hd[max_s],to[max_m<<1],nx[max_m<<1],ln[max_m<<1];
    graph(){ct=1;}
    inline void add(int u,int v,int w=0){
        nx[++ct]=hd[u],hd[u]=ct,to[ct]=v,ln[ct]=w;
    }
}e;

int n,a[max_n];

vector< tuple<int,int,int> > ans;

inline void Flip(int x,int y,int z){
    ans.emplace_back(x,y,z);
    a[x]^=1,a[y]^=1,a[z]^=1;
}

bool vis[max_s];
int dis[max_s],fr[max_s];
priority_queue< pair<int,int> > q;

inline void dijs(int st){
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;
    q.emplace(0,st);
    while(!q.empty()){
        int u=q.top().second;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=e.hd[u];i;i=e.nx[i]){
            int v=e.to[i];
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1,fr[v]=u;
                q.emplace(-dis[v],v);
            }
        }
    }
}

inline void dfs(int S){
    if(S==0) return;
    int T=fr[S],x[3]={0,0,0};
    for(int i=0,j=0;i<10 && j<3;++i) if(((S>>i)&1)!=((T>>i)&1))
        x[j++]=i;
    ans.emplace_back(x[0]+n-9,x[1]+n-9,x[2]+n-9);
    dfs(T);
}

namespace SmallN{
    inline void dfs(int S){
        if(S==0) return;
        int T=fr[S],x[3]={0,0,0};
        for(int i=0,j=0;i<n && j<3;++i) if(((S>>i)&1)!=((T>>i)&1))
            x[j++]=i+1;
        ans.emplace_back(x[0],x[1],x[2]);
        dfs(T);
    }
    inline void main(){
        int N=(1<<n);
        for(int s=0;s<N;++s)
            for(int i=0;i<n;++i)
                for(int j=i+1;2*j-i<n;++j){
                    int x=i,y=j,z=2*j-i;
                    e.add(s,s^(1<<x)^(1<<y)^(1<<z));
                }
        dijs(0);
        int s=0;
        for(int i=1,j=0;i<=n;++i,++j)
            s|=(a[i]<<j);
        if(dis[s]>inf) return void(puts("NO"));
        dfs(s);
        puts("YES");
        write(ans.size()),putchar('\n');
        for(auto p:ans){
            write(get<0>(p)),putchar(' ');
            write(get<1>(p)),putchar(' ');
            write(get<2>(p)),putchar('\n');
        }
    }
}

bool End;
#define File ""
signed main(){
    // #ifndef ONLINE_JUDGE
    // freopen(File ".in","r",stdin);
    // freopen(File ".out","w",stdout);
    // #endif
    // cerr<<"Memory : "<<(&Begin-&End)/1024.0/1024<<"\n";
    n=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    if(n<=10) return SmallN::main(),0;
    for(int s=0;s<1024;++s)
        for(int i=0;i<10;++i)
            for(int j=i+1;2*j-i<10;++j){
                int x=i,y=j,z=2*j-i;
                e.add(s,s^(1<<x)^(1<<y)^(1<<z));
            }
    dijs(0);
    for(int i=1;i<=n-10;++i) if(a[i]){
        if(a[i+1] && a[i+2]){
            Flip(i,i+1,i+2);
            continue;
        }
        if(!a[i+1] && !a[i+2]){
            if(!a[i+3] && !a[i+4] && !a[i+5]){
                Flip(i,i+2,i+4),
                Flip(i+2,i+4,i+6);
                continue;
            }
            for(int j=3;j<=5;++j) if(a[i+j]){
                Flip(i,i+j,i+j+j);
                break;
            }
            continue;
        }
        if(!a[i+1]){
            Flip(i,i+2,i+4);
            continue;
        }
        else{
            if(!a[i+3] && !a[i+4] && !a[i+5]){
                Flip(i+1,i+4,i+7),
                Flip(i,i+4,i+8);
                continue;
            }
            if(a[i+3] && a[i+4] && a[i+5]){
                Flip(i+1,i+3,i+5),
                Flip(i,i+4,i+8);
                continue;
            }
            if(a[i+3] && a[i+4]){
                Flip(i+1,i+2,i+3),
                Flip(i,i+2,i+4);
                continue;
            }
            if(a[i+3] && a[i+5]){
                Flip(i,i+3,i+6),
                Flip(i+1,i+5,i+9);
                continue;
            }
            if(a[i+4] && a[i+5]){
                Flip(i,i+4,i+8),
                Flip(i+1,i+5,i+9);
                continue;
            }
            Flip(i,i+1,i+2);
            for(int j=3;j<=5;++j) if(a[i+j]){
                Flip(i+2,i+j,i+2*j-2);
                break;
            }
            continue;
        }
    }
    int s=0;
    for(int i=n-9,j=0;i<=n;++i,++j)
        s|=(a[i]<<j);
    if(dis[s]>inf) return puts("NO"),0;
    dfs(s);
    puts("YES");
    write(ans.size()),putchar('\n');
    for(auto p:ans){
        write(get<0>(p)),putchar(' ');
        write(get<1>(p)),putchar(' ');
        write(get<2>(p)),putchar('\n');
    }
    return 0;
}
  • 标题: CF1031E Triple Flips
  • 作者: Arahc
  • 创建于 : 2022-11-09 08:00:00
  • 更新于 : 2023-03-21 13:14:42
  • 链接: https://arahc.github.io/2022/11/09/【题解】CF1031E-Triple-Flips/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
CF1031E Triple Flips
  1. 题面
  2. 题解
  3. 代码