11 条题解

  • 16
    @ 2022-3-26 16:30:55

    来点汇编 (

    C++

    #include <iostream>
    
    int main() {
        int a, b, c1, c2, c3;
        std::cin >> a >> b;
        __asm__(
            "movl %1, %%eax\n\t"
            "movl %2, %%ebx\n\t"
            "addl %%ebx, %%eax\n\t"
            "movl %%eax, %0\n\t"
            : "=r"(c1)
            : "r"(a), "r"(b)
            : "%eax");
        __asm__(
            "movl %1, %%eax\n\t"
            "movl %2, %%ebx\n\t"
            "subl %%ebx, %%eax\n\t"
            "movl %%eax, %0\n\t"
            : "=r"(c2)
            : "r"(a), "r"(b)
            : "%eax");
        __asm__(
            "movl %1, %%eax\n\t"
            "movl %2, %%ebx\n\t"
            "imull %%ebx, %%eax\n\t"
            "movl %%eax, %0\n\t"
            : "=r"(c3)
            : "r"(a), "r"(b)
            : "%eax");
        std::cout << c1 << " " << c2 << " " << c3;
        return 0;
    }
    
    • 12
      @ 2022-3-25 20:27:34

      草其实这个才是预期解

      https://www.jianshu.com/p/7bba031b11e7

      • @ 2023-6-4 20:41:52

        ~你真写位运算就输了~

    • 10
      @ 2022-3-26 15:56:38

      C++

      #include <iostream>
      #include <vector>
      #include <numeric>
      using namespace std;
      int main()
      {
          int a,b;
          cin>>a>>b;
          vector<int> va = {a};
          vector<int> vb = {b};
          vector<int> vab = {b, a};
          vector<int> w(2);
          int sum = accumulate(vab.begin(), vab.end(), 0);
          adjacent_difference(vab.begin(), vab.end(), w.begin());
          int sub = w[1];
          int mul = inner_product(va.begin(), va.end(), vb.begin(), 0);
          cout<<sum<<' '<<sub<<' '<<mul<<endl;
          return 0;
      }
      

      Python

      eval

      a, b = map(int, input().split())
      u = eval(f"{a}{chr(43)}{b}")
      v = eval(f"{a}{chr(45)}{b}")
      w = eval(f"{a}{chr(42)}{b}")
      print(u, v, w)
      

      利用复数搞负数

      a, b = map(int, input().split())
      cp = complex(0, b)
      cp = cp.conjugate()
      ls1 = [a, b]
      ls2 = [a, int(cp.imag)]
      ls3 = [a for i in range(b)]
      print(sum(ls1), sum(ls2), sum(ls3))
      

      find 搞负数 Fraction 搞除法

      from fractions import Fraction
      
      
      a, b = map(int, input().split())
      f = "".find("233")
      ls1 = [a, b]
      ls2 = [a, Fraction(b, f)]
      mul = Fraction(a, Fraction(1, b))
      print(sum(ls1), sum(ls2), mul)
      
      • 8
        @ 2022-10-3 9:03:00

        整活归整活,符合题意的代码还是要写的。

        我们都知道 ^ 运算符是 不进位的加法 ,那么对于加法来说只需要 想个办法模拟进位 即可。

        对于两个二进制数 10101100 来说,他们的相加即为0001 0110

        都知道 & 运算是全 1 为真,那么对于二进制数来说,两个 1 不就是进位吗?

        所以对于第四位上的进位,就可以视为 (1010&1100)<<1

        加法解决了,减法其实就是加上一个数的相反数,计算机里使用的是 补码 ,负数表示为其绝对值 取反再加一 ,如 -1 即为 (~1)+1 ,恰好可以使用加法解决。

        乘法本质上是一个数自己加自己数次,使用循环搞定。

        ……

        草,好像不能用 i++

        那回头来看二进制乘法

        1010
        *   1001
        --------
            1010
           0000
          0000
         1010
        --------
         1011010
        

        发现什么了?

        由于二进制只有 10 所以 a*b 其实相当于把 a 分别左移上 b 中每个一所在的位数,最后相加。

        那你用过快速幂没有?

        怎么判断一个二进制数每位有没有一,只需要想个办法把每位的一扔到最后一位(可以通过右移实现),然后再与一即可。

        加法的代码:

        ll add(ll a,ll b){
        	return b==0?a:add(a^b,(a&b)<<1);
        }
        

        减法:

        ll reduce(ll a,ll b){
        	return add(a,add(~b,1));
        }
        

        乘法:

        ll times(ll a,ll b){
        	ll re=0;
        	bool A=a<0,B=b<0;
        	a=abs(a),b=abs(b);
        	while(b){
        		if(b&1) re=add(re,a);
        		a<<=1,b>>=1;
        	}
        	return A^B?add(~re,1):re;
        }
        

        全代码:

        #include<cstdio>
        #include<cmath>
        using namespace std;
        #define ll long long 
        ll add(ll a,ll b){
        	return b==0?a:add(a^b,(a&b)<<1);
        }
        ll reduce(ll a,ll b){
        	return add(a,add(~b,1));
        }
        ll times(ll a,ll b){
        	ll re=0;
        	bool A=a<0,B=b<0;
        	a=abs(a),b=abs(b);
        	while(b){
        		if(b&1) re=add(re,a);
        		a<<=1,b>>=1;
        	}
        	return A^B?add(~re,1):re;
        }
        ll a,b;
        int main()
        {
        	scanf("%lld%lld",&a,&b);
        	printf("%lld %lld %lld",add(a,b),reduce(a,b),times(a,b));
        	return 0;
        }
        

        该用位运算还是要用的。

        此处参拜白咕咕神教教主
        • 7
          @ 2022-3-26 16:08:56

          首先是一个不那么正经的解法

          我们考虑到这题的数据只有 1024,那么,我们考虑小学时老师教你的:

          你有 2 个苹果,然后你又拿到了 3 个苹果,最后你有 5 个苹果,所以 2+3=52 + 3 = 5 那加法就完成了(代码中的 ushortunsigned short

          short $(ushort x, ushort y) {
          	return std::string().append(x, '.').append(y, '.').length();
          }
          

          那么减法呢?我们知道,xy=x+(y)x - y = x + \left( -y \right),在计算机中,y=y+1-y = \sim y + 1,so,xy=x+y+1x - y = x + \sim y + 1,调用之前写的加法就好:

          short _(short x, short y) {
          	y = ~y;
          	return $($(x, reinterpret_cast<ushort&>(y)), 1);
          }
          

          最后乘法,还是考虑小学的时候老师教你的:

          x×yx \times y 就是 yyxx 相加。

          还是用 string。我们往一个空的 string 里面塞 yy 次长度为 xx 的字符串,然后就好了。
          但是我们发现一个问题:我们既不能 for (int i = 0;i < y;i++),也不能 while (y--)。这可怎么办呢?还是用 string。我们每循环一次就往一个初始为空的字符串里塞一个字符,这个串有多长我们就循环了多少次。然后,乘法也被淦掉了:

          int X(short x, short y) {
          	std::string str = "";
          	std::string tt = std::string().append(x, ' ');
          	std::string res = "";
          	while (str.append(1, ' ').length() <= y) {
          		res.append(tt);
          	}
          	return res.length();
          }
          

          最后是这种做法的完整代码:

          #include <iostream>
          #include <string>
          #define ushort unsigned short
          short $(ushort x, ushort y) {
          	return std::string().append(x, '.').append(y, '.').length();
          }
          short _(short x, short y) {
          	y = ~y;
          	return $($(x, reinterpret_cast<ushort&>(y)), 1);
          }
          int X(short x, short y) {
          	std::string str = "";
          	std::string tt = std::string().append(x, ' ');
          	std::string res = "";
          	while (str.append(1, ' ').length() <= y) {
          		res.append(tt);
          	}
          	return res.length();
          }
          int main() {
          	int x, y;
          	std::cin >> x >> y;
          	std::cout << $(x, y) << ' ' << _(x, y) << ' ' << X(x, y) << std::endl;
          }
          

          玩够了不着调的瞎搞做法,咱回过头来瞅瞅如何用位运算解题。(三年后的补档)

          正经的解法

          加法

          咱先研究俩一位数相加的情况,有:

          • 0 + 0 = 00
          • 1 + 0 = 01
          • 0 + 1 = 01
          • 1 + 1 = 10

          注意到:xxyy 相加,高位为 xandyx \operatorname{and} y,低位为 xxoryx \operatorname{xor} y

          然后咱考虑进位,有:

          • 0 + 0 + 1 = 00 + 1 = 01
          • 1 + 0 + 1 = 01 + 1 = 10
          • 0 + 1 + 1 = 01 + 1 = 10
          • 1 + 1 + 1 = 10 + 1 = 11

          发现实际上进位实际上可以作为一单独过程处理,而不影响先前的结论。(事实上全加器就是可以由多个半加器拼合而成的)

          现在拓展到任意二进制数,以 7 + 14 为例:

              0  1  1  1 (7)
           +  1  1  1  0 (14)
           --------------
          [1][1][1][0]   (carry bits)
           --------------
           1  0  1  0  1 (21)
          

          显然要是像咱平时列竖式那样一位一位整有点麻烦。(其实也不麻烦)

          但基于我们之前的结论:进位可以作为一个单独过程处理。有啥用呢?我们将进位与异或分离处理,则:

               0  1  1  1 (7)
            +  1  1  1  0 (14)
            --------------
               1  0  0  1 (9)
          c:0  1  1  0    (12)
            --------------
            0  0  1  0  1 (5)
          c:1  0  0       (16)
            --------------
            1  0  1  0  1 (21)
          c:0  0          (0)
          

          其中每一次变换的第一行都是上一组的两个值按位异或的结果;第二行(carry)为上一组两个值按位与并左移一位的结果。注意到:

          • 每一组数的和不变;这保证结果正确
          • 进位(carry)数的有效位数变短;这保证进位最终变为 0(程序能够结束)

          部分代码:

          short add(ushort x, ushort y) {
              while (y != 0) {
                  int r = x & y;
                  x ^= y;
                  y = r << 1;
              }
              return x;
          }
          

          (实际上这种方式最差需要 O(log(n))\mathcal{O}(\log(n)),与按位单独计算相同,但比咱之前瞎搞做法的 O(n)\mathcal{O}(n) 好)

          减法

          利用补码,原理相同,不再赘述

          部分代码:

          short sub(short x, short y) {
              y = ~y;
              return add(add(x, reinterpret_cast<ushort&>(y)), 1);
          }
          

          乘法

          显而易见的有一种想法就是,x×yx \times y 就是 yyxx 相加。这种方式 yy 次相加效率较低。既然正经做法,咱想想是否有更快的方式呢?

          可以从快速幂中借鉴思路。快速幂解决的是 r=nkr = n^k,即 kknn 相乘的问题。其核心是将指数 kk 分解:

          k=n=02nbn\displaystyle k = \sum_{n=0}^\infty 2^n b_n

          得到结果 rr

          r=n=0a2nbn\displaystyle r = \prod_{n=0}^{\infty} a^{2^n b_n}

          其中 a2nbna^{2^n b_n} 可以写作 (a2n)bn\left(a^{2^n}\right)^{b_n},其中 a2n=(a2n1)2a^{2^n} = \left(a^{2^{n-1}}\right)^2 可在 O(1)\mathcal{O}(1) 时间内得到,而 bnb_n 仅有 0(使结果便为 1)与 1(保持结果不变)两种情况,从而实现快速

          而咱所要解决的乘法是 r=nkr = n^k,即 kknn 相乘的问题。同样将 kk 分解后,所要得到的结果 rr

          $\displaystyle r = \sum_{n=0}^{\infty} a \times {2^n b_n}$

          相似的,a×2nbna \times {2^n b_n} 可以写作 (2na)bn\left(2^n a\right)b_n,其中 2na=(2n1a)×22^n a = \left(2^{n-1}a\right) \times 2 可在 O(1)\mathcal{O}(1) 时间内得到,而 bnb_n 仅有 0(使结果便为 0)与 1(保持结果不变)两种情况。你问乘 2 咋整?左移。

          部分代码:

          int mul(short x, short y) {
              int res = 0;
              while (y != 0) {
                  if ((y & 1) == 1) {
                      res = add(x, res);
                  }
                  x <<= 1;
                  y >>= 1;
              }
              return res;
          }
          

          最终代码实现:

          #include <iostream>
          #include <string>
          typedef unsigned short ushort;
          short add(ushort x, ushort y) {
              while (y != 0) {
                  int r = x & y;
                  x ^= y;
                  y = r << 1;
              }
              return x;
          }
          short sub(short x, short y) {
              y = ~y;
              return add(add(x, reinterpret_cast<ushort&>(y)), 1);
          }
          int mul(short x, short y) {
              int res = 0;
              while (y != 0) {
                  if ((y & 1) == 1) {
                      res = add(x, res);
                  }
                  x <<= 1;
                  y >>= 1;
              }
              return res;
          }
          int main() {
              int x, y;
              std::cin >> x >> y;
              std::cout << add(x, y) << ' ' << sub(x, y) << ' ' << mul(x, y) << std::endl;
          }
          
          • 7
            @ 2022-3-26 16:00:01

            实际上就两种大体做法:

            1. 使用各大语言的 method 来代替运算符出现
            2. 使用列表的求和或者长度方法来乱搞

            具体实现各显神通

            你真写位运算就输了

            Python

            import operator
            
            a, b = map(int, input().split())
            print("{} {} {}".format(operator.add(a, b),
                  operator.sub(a, b), operator.mul(a, b)))
            

            C++

            #include <functional>
            #include <iostream>
            
            using namespace std;
            
            int main() {
                std::ios::sync_with_stdio(false);
            
                int a, b;
                std::cin >> a >> b;
                std::cout << plus<>{}(a, b) << ' ' << minus<>{}(a, b) << ' ' << multiplies<>{}(a, b) << '\n';
            
                return 0;
            }
            
            #include <functional>
            #include <iostream>
            #include <valarray>
            
            using namespace std;
            
            int main() {
                std::ios::sync_with_stdio(false);
            
                int a, b;
                std::cin >> a >> b;
                std::cout << std::valarray<int>{a,b}.sum() << ' ' 
                          << std::valarray<int>{a,std::negate<>{}(b)}.sum() << ' '
                          << std::valarray<int>(a,b).sum() << '\n'; 
            
                return 0;
            }
            
            • 2
              @ 2023-11-4 19:26:53

              网上找得到

              #include <iostream>
              #include <functional>
              using namespace std;
              int main()
              {
                  int a,b;
                  cin>>a>>b;
                  cout<<plus<>{}(a,b)<<" "<<minus<>{}(a,b)<<" "<<multiplies<>{}(a,b)<<endl;
                  return 0;
              }
              
              • 1
                @ 2025-11-18 15:52:58

                只会乘法awa

                众所周知,一个数字除以另一个数字等于乘上这个数字的倒数

                那么我们反过来:

                一个数字乘上另一个数字等于除以另一个数字的倒数

                那么就用个double就可以解决乘法了

                加法减法不会了

                • 1
                  @ 2024-3-16 9:30:27

                  Python 可以直接调用特殊方法的,不一定非要引包。

                  a, b = map(int, input().split())
                  print(a.__add__(b),a.__sub__(b),a.__mul__(b))
                  
                  • 0
                    @ 2024-11-2 15:31:27

                    C++

                    根据作者的意思,我们可以导入functional库,使用plus,minus和multiplies函数。 使用方法如下:

                    #include<functional>
                    #include<iostream>
                    using namespace std;
                    int main(){
                        int a,b;cin>>a>>b;
                        plus<int> fplus;
                        int x=fplus(a,b);
                        minus<int> fminus;
                        int y=fminus(a,b);
                        multiplies<int> fmultiplies;
                        int z=fmultiplies(a,b);
                        cout<<x<<' '<<y<<' '<<z;
                        return 0;
                    }
                    
                    

                    至于代码中的fplus,fminus和fmultiplies则是我随便取的名字,可以换成其他的名字,只要合法就行。

                    • -8
                      @ 2023-10-15 13:55:13

                      8 7 6 5 6 5 4 3 4 3 2 1 2 3 2 1 2 3 4 3 4 5 6 5 6 7 8 7 8 9 10

                      • 1

                      信息

                      ID
                      246
                      时间
                      1000ms
                      内存
                      256MiB
                      难度
                      2
                      标签
                      (无)
                      递交数
                      339
                      已通过
                      77
                      上传者