Wuyanru's blog
0%

[GYM105755B] Bitstring Accruing Policy Convergence

发表于 分类于 ，

比较神秘的题，神秘到我说不出来他是什么类型的题。

题目链接。

官方题解。

题意

对于一个 串 ，定义 表示将 中所有 替换成 ，所有 替换成 得到的字符串。

定义 与 ，其中 。

给定一个长度为 的序列 ，要求构造两个 串 ，满足：

  1. 的长度不超过 。
  2. 中 和 数量分别相同。
  3. 令 和 ，则 当且仅当存在 满足 。

保证有解。

，。

题解

考虑将一个 串看作平面上的折线，其中 表示向右走一步， 表示向右走一步。

然后将 都在平面上画出来。

称网格 为左下角坐标为 的网格。

观察可得，网格 在 的中间当且仅当网格 在 的中间。

这个过程同样是可逆的（网格 在 的中间当且仅当网格 在 的中间）。

那么一个网格 经过 次迭代后，应该会变到网格 ，其中 均为可计算的常数。

那么首先有一个结论：

相邻的两个网格不可能同时在 的中间。

证明：以横坐标相差 举例，假设现在有两个网格 和 都在 中间。

考虑倒退 次迭代之前两个网格的位置，假设其坐标分别为 。

写个程序算一下可以发现此时一定会有 和 ，也就是说这两个格子不可能同时在 中间。

那么我们可以知道， 中不同的位置一定是相邻成对出现的。

考虑若 这个格子在 中间，则这两个串 这两个位置恰好不同。

假设现在有两个位置 不同，那么其对应的 中间的网格 应满足 。

而我们知道 取值应该都在 中间，所以这个式子可以解出一个唯一确定的 。

那么现在我们就知道了初始时 中间有哪些网格，直接构造就可以了。

代码

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
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
using _=__int128;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int L=22;
struct wtf
{
    ll A,B,C;
    wtf(ll A=0,ll B=0,ll C=0):A(A),B(B),C(C){}
    wtf operator + (wtf x){ return wtf(A+x.A,B+x.B,C+x.C);}
};
wtf x,y;
pi b[300005];
ll a[300005];
int n,c;
void exgcd(_ a,_ b,_ &x,_ &y)
{
    if(!b){ x=1,y=0;return ;}
    _ xp,yp;exgcd(b,a%b,xp,yp);
    x=yp,y=xp-a/b*yp;
}
int main()
{
    x=wtf(1,0,0),y=wtf(0,1,0);
    for(int i=1;i<=L;i++)
    {
        wtf mx=x,my=y;
        x=mx+mx+my;x.C++;y=mx+my;
    }

    _ vA=x.A+y.A,vB=x.B+y.B,X,Y;
    exgcd(vA,vB,X,Y);

    n=read();assert(n%2==0);
    for(int i=1;i<=n;i++) a[i]=lread();
    sort(a+1,a+n+1);

    for(int i=1;i<=n;i+=2)
    {
        assert(a[i+1]==a[i]+1);
        ll w=a[i]-1-x.C-y.C;

        _ x=X*w,y=Y*w,v=0;
        if(x<0) v=-((-x+vB-1)/vB);
        if(y<0) v=(-y+vA-1)/vA;
        x-=vB*v,y+=vA*v;
        b[++c]=pi(x,y);
    }

    sort(b+1,b+c+1);
    string s,t;int sx=0,sy=0,tx=0,ty=0;
    for(int l=1,r;l<=c;l=r)
    {
        r=l+1;
        while(r<=c&&b[r].first==b[l].first) r++;
        
        while(sy<b[l].second) sy++,s+='1';
        while(sx<b[l].first) sx++,s+='0';

        sx++,s+='0';

        while(ty<b[l].second) ty++,t+='1';
        while(tx<b[l].first) tx++,t+='0';

        while(ty<=b[r-1].second) ty++,t+='1';
        tx++,t+='0';
    }
    while(sy<ty) sy++,s+='1';
    cout<<s<<endl<<t<<endl;
    return 0;
}