题解 P2104 【二进制】

· · 题解

1.一般实现

既然不能误认子弟。。。正常的，AC的代码是必要的。。。

题目是让程序依次按照输入的运算符顺序计算：

‘*2’：在二进制中，乘以2就相当于十进制中的乘以十，只需要将数字右移一位即可。由于我们是用字符串形式存储的，所以直接在字符串格式存储的二进制数字末尾加零即可。

‘/2’：除以二就是乘以二的逆运算，乘以二把数字有移一位，除以二就要将数字左移一位即可。字符串处理的话，我们只需要将数字末尾赋值成'\0'即可

‘+2’：就有些麻烦了，因为需要处理进位。这里拿10011举例。10011 + 1，列竖式计算，逢二进一，结果为10100。稍微观察一下，末位加一，变为2后，需要向前进位，原数变为零，而倒数第二位原本是1，加上1以后也需要进位。直到第三位，是0了，再加1，该位值为1，无需进位，得到10100。于是，我们就得到了加一的规律：从后往前遍历，将每一位赋值成0，直到遇到原本的零，将其赋值成1，结束计算。然鹅，如果原数一个零也没有，例如11111，加一就涉及到进一的问题了。但是，题目中有提到：“数据保证+，-操作不会导致最高位的进位与退位”，所以，我们并不需要考虑这个问题而将整个数组移位。

‘-2’：类似地，-2也是+2的逆运算，原来是将一变零，遇到原本就是零为止，现在只需要将零变一，遇到原本就是一为止。

AC code:

#include<bits/stdc++.h>
using namespace std;
char s[100000000] = {0}, oper[6000000] = {0};
int main()
{
    int n, m;
    scanf("%d%d%s%s", &n, &m, s, oper);
    for(int i = 0; i < m; i++)
        switch(oper[i])
        {
            case '*': s[n++] = '0';  break;
            case '/': s[--n] = '\0'; break;
            case '+': for(int k = n; s[--k] != '0' && (s[k] = '0') || !(s[k] = '1'); ); break;
            case '-': for(int k = n; s[--k] != '1' && (s[k] = '1') || !(s[k] = '0'); ); break;
        }
    puts(s);
}

2.稍改：main()递归

此方案类似于前者，但不需要用任何的循环、三元表达式、逗号表达式。由于此题卡常，不开O2会有五个点TLE,也别开02，因为可能会有更多的点TLE（O2优化会使得main的调用时间变长）。

首先要了解一下main() main()是可以有参数的，但必须为一个int型和一个char** 型。main()同样也可以递归。

其次，正常的+ - * / 是没有运算顺序的。但是，||和&&为了节约时间，是有从左到右的运算顺序的。

a || b()：先计算a的值，如果为true，那么全式的值一定为true，就不需要求b()的值。所以可以将a||b()用作与之等效的用法if(a == false) b();

a && b()：先计算a的值，如果为false，那么全式的值一定为false，就不需要求b()的值。所以可以将a&&b()用作与之等效的用法if(a == true) b();

于是，就有了这个代码：

#include<bits/stdc++.h>
using namespace std;
char s[100000000] = {0}, oper[6000000] = {0};
int n = -1;
int main(int argc, char **argv)
{
    return (n + 1 || scanf("%d%d%s%s", &n, &argc, s, oper) && 0 || (*argv = NULL) || main(argc, argv) && 0) 
        && (argc || puts(s) && 0)
        && (oper[strlen(oper) - argc] - '*' || (s[n++] = '0') && main(argc - 1, argv) && 0)
        && (oper[strlen(oper) - argc] - '/' || !(s[--n] = '\0') && main(argc - 1, argv) && 0)
        && (oper[strlen(oper) - argc] - '+' || (
            (!*argv || (*(--*argv) != '0' && (**argv = '0') && (main(argc, argv) || 1) || !(**argv = '1')
                || (*argv = NULL) || main(argc - 1, argv)) && 0)
            && (*argv || !(*argv = s + n) || main(argc, argv) && 0)))
        && (oper[strlen(oper) - argc] - '-' || (
            (!*argv || (*(--*argv) != '1' && (**argv = '1') && (main(argc, argv) || 1) || !(**argv = '0')
                || (*argv = NULL) || main(argc - 1, argv)) && 0)
            && (*argv || !(*argv = s + n) || main(argc, argv) && 0)))
        && 0;
}