嘘~ 正在从服务器偷取页面 . . .

[A_


[AGC011D] Half Reflector 题解

题目链接:[AGC011D] Half Reflector

题意

NN 个装置排成一排,组成一个系统。每个装置有两种状态 AABB 。具体地,假想有一个小球从最左侧进入这个系统,则两种状态的行为如下:

  1. AA :将球反弹回原方向
  2. BB :让球通过,不改变方向

当然,每当一个小球经过一个装置后,无论是以 AA 状态还是 BB 状态经过,装置都将改变原来的状态 (即 AABBBBAA )。现在给定初始情况下所有装置的状态,求 KK 个小球经过后装置的状态。

输入格式

第一行包含两个正整数 N,K(N2×105, K109)N,K(N2×105, K109),分别表示装置的个数和经过的小球数。

第二行包含一个由 AABB 构成的字符串 S(|S|=N)S(|S|=N),其中第 ii 个字符表示左起第 ii 个装置的状态。

输出格式

输出一行,包含一个字符串 SKSK,表示 KK 次小球经过后状态的状态,具体格式同输入。

可以发现,对于很多情况,小球会来回弹来弹去,以至于对原串进行了类似于翻转的操作

不妨对 S1S1 的情况进行讨论,方便起见,称 AA 为「墙」,BB 为「地」。

  1. S1S1 为「墙」,此时小球弹回,S1S1 变为地。

  2. S1S1 为「地」,通过对较小情况的尝试,不难发现一个结论:记 ˉx¯x 为与 xx 相反的状态,

    S1S1 为「地」时,SS 的新状态 TTTi=¯Si+1(i<n)Ti=¯¯¯¯¯¯¯¯¯¯Si+1(i<n)TnTn 为「墙」,且小球一定从右边离开系统

尝试证明这个结论:

|S||S| 归纳证明。显然当 |S|3|S|3 时成立。于是设 |S||S|n1n1 处成立,尝试验证 |S|=n|S|=n 的情形

不妨考虑 S2S2 的情况。

  1. S2S2 为「墙」

    (图例:>>> 表示向右运动的球,<<< 表示向左运动的球,| 表示「墙」,_ 表示「地」)

    none
    (a) >>> _     |     ……
    (b)     | >>> |     ……
    (c)     | <<< _     ……
    (d)     _ >>> _     ……

    (d) 表明了之后 T1=¯S2=T1=¯¯¯¯¯¯S2= 「地」,考虑到右边 n1n1 个位置

    而他们恰好构成原问题的大小为 n1n1 的子问题,由归纳法可知 T2,T3,TnT2,T3,Tn 亦均满足结论。

  2. S2S2 为「地」

    none
    (a) >>> _     _     ……
    (b)     | >>> _     ……

    同样的,(b) 显然已经满足命题条件了,从而可以用归纳假设,且 T1=¯S2=T1=¯¯¯¯¯¯S2= 「墙」,从而该情况成立。

综上,由归纳原理知,原命题成立。

于是我们要快速模拟这个过程。考虑到每次小球移动,要么是将 S1 翻转,或者整体平移一位

显然这个翻转是不用进行实际操作的,当且仅当进行了奇数次平移最终答案才会翻转。

而在平移的过程中,后面补充的字符依次为「墙」「地」「墙」…(交替出现)

因此我们考虑如何计算平移的次数。

对于 S1 是「墙」,则不会发生平移,而 S1 是「地」时会发生平移

那么只需要统计每个位置是否是「墙」即可。

注意,由于我们取消了取反操作,所以应该判断奇数位是否为「墙」,偶数位是否为「地」

特别地,对于 kn 的部分,不难发现,当 n 为奇数时两步一平移,否则一步一平移,可以 O(1) 计算

时间复杂度 O(n)

代码:

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

int n,k; char s[N],t[N];
int get(int x) { return (x < n ? (int)s[x] : (x ^ n)) & 1; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int i, j, c; cin >> n >> k >> s;
    for(i = 0; i < n && k; ++i)
    {
        c = 1 + ((i ^ (int)s[i]) & 1);
        if(k >= c) k -= c; else break;
    }
    if(i == n && k) { c = 1 + (n & 1); i += k / c; k %= c; }
    for(j = 0; j < n; j++) t[j] = get(i + j);
    for(t[0] ^= k, j = 0; j < n; j++) t[j] = (i & 1 ? 'A' + t[j] : 'A' + 1 - t[j]);
    cout << t << '\n';
    return 0;
}

参考文献

[1] https://yhx-12243.github.io/OI-transit/records/ac2340%3Bagc011D.html


文章作者: q779
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 q779 !
评论
你认为这篇文章怎么样?
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.1.3
  目录