• C. Binary String Reconstruction


    C. Binary String Reconstruction

    time limit per test

    2 seconds

    memory limit per test

    256 megabytes

    input

    standard input

    output

    standard output

    Consider the following process. You have a binary string (a string where each character is either 0 or 1) ww of length nn and an integer xx. You build a new binary string ss consisting of nn characters. The ii-th character of ss is chosen as follows:

    • if the character wi−xwi−x exists and is equal to 1, then sisi is 1 (formally, if i>xi>x and wi−x=wi−x= 1, then si=si= 1);
    • if the character wi+xwi+x exists and is equal to 1, then sisi is 1 (formally, if i+x≤ni+x≤n and wi+x=wi+x= 1, then si=si= 1);
    • if both of the aforementioned conditions are false, then sisi is 0.

    You are given the integer xx and the resulting string ss. Reconstruct the original string ww.

    Input

    The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

    Each test case consists of two lines. The first line contains the resulting string ss (2≤|s|≤1052≤|s|≤105, each character of ss is either 0 or 1). The second line contains one integer xx (1≤x≤|s|−11≤x≤|s|−1).

    The total length of all strings ss in the input does not exceed 105105.

    Output

    For each test case, print the answer on a separate line as follows:

    • if no string ww can produce the string ss at the end of the process, print −1−1;
    • otherwise, print the binary string ww consisting of |s||s| characters. If there are multiple answers, print any of them.

    Example

    input

    Copy

    3
    101110
    2
    01
    1
    110
    1
    

    output

    Copy

    111011
    10
    -1
    

    =========================================================================

    我们先满足必须是0的位置,然后为了尽可能满足其余1的情况,我们让剩余位置全是1即可,然后在进行无解的判断,条件就按照题目给的写就够了

    1. # include
    2. # include
    3. using namespace std;
    4. char s[100000+10],t[100000+10];
    5. int main ()
    6. {
    7. int n;
    8. cin>>n;
    9. while(n--)
    10. {
    11. scanf("%s",s+1);
    12. int x;
    13. cin>>x;
    14. for(int i=1;i<=strlen(s+1);i++)
    15. {
    16. t[i]='1';
    17. }
    18. for(int i=1;i<=strlen(s+1);i++)
    19. {
    20. if(s[i]=='0')
    21. {
    22. if(i-x>=1)
    23. t[i-x]='0';
    24. if(i+x<=strlen(s+1))
    25. t[i+x]='0';
    26. }
    27. }
    28. int flag=0;
    29. for(int i=1;i<=strlen(s+1);i++)
    30. {
    31. if(s[i]=='1')
    32. {
    33. if(!((i-x>=1&&t[i-x]=='1')||(i+x<=strlen(s+1)&&t[i+x]=='1')))
    34. {
    35. flag=1;
    36. break;
    37. }
    38. }
    39. else
    40. {
    41. if((i-x>=1&&t[i-x]=='1')||(i+x<=strlen(s+1)&&t[i+x]=='1'))
    42. flag=1;
    43. }
    44. }
    45. if(flag)
    46. {
    47. cout<<"-1"<
    48. }
    49. else
    50. {
    51. for(int i=1;i<=strlen(s+1);i++)
    52. {
    53. cout<
    54. }
    55. cout<
    56. }
    57. }
    58. return 0;
    59. }

  • 相关阅读:
    【剑指offer|图解|双指针】训练计划 I + 删除有序数组中的重复项
    《深入浅出Vue.js》打卡Day1
    美团一面复活赛4/18
    yarn安装私有依赖包,报错unexpected end of file问题
    Android 11.0 Launcher3 workspaces桌面去掉下拉状态栏功能
    Python+AI给老照片上色
    ZnDPA-Cy7 荧光细胞凋亡检测凋亡靶向探针
    【软考】4.2 关系代数
    牛客网sql练习
    表达式语言的新趋势!了解SPEL如何改变开发方式
  • 原文地址:https://blog.csdn.net/jisuanji2606414/article/details/126243570