9难度我跪了

2 条评论

  • @ 2016-05-02 14:20:29

    不知A+B难倒了多少英雄好汉

  • A+B问题,一道历史悠久的问题,下面就给出该题的多种解法。

    解法一:首先用cin/scanf读入两个int类型数a和b,再用cout/printf输出a+b的结果。核心代码:cin>>a>>b; cout<<a+b<<endl;

    解法二:为了防止计算a+b时占用过多内存(其实也没多少),可使用C++的提供的内联汇编来完成本题。核心代码:

    __asm
    (
    "mov %1,%%eax \n\t"
    "mov %2,%%ebx \n\t"
    "add %%eax,%%ebx \n\t"
    "mov %%ebx,%0"
    :"=m"(b)
    :"m"(a),"m"(b)
    );
    最后输出b即可。(事实上,这就是不让编译器替我们把高级语言翻译为汇编语言,直接就替它做了)

    解法三:为防止出题人故意出大数据恶心我们,可采用高精度加法完成此题。核心代码:

    char s1[101] , s2[101] , l1 , l2 , l3;
    int a[101]={0} , b[101]={0} , c[102]={0};
    cin >> s1 >> s2;
    l1 = strlen(s1);
    l2 = strlen(s2);
    for (int i = 0 ; i < l1 ; i++) a[l1 - i] = s1[i] - '0';
    for (int i = 0 ; i < l2 ; i++) b[l2 - i] = s2[i] - '0';
    l3 = max(l1 , l2);
    for (int i = 1 ; i <= l3 ; i++)
    {
    c[i] += a[i] + b[i];
    c[i + 1] = c[i] / 10;
    c[i] %= 10;
    }
    if (c[l3 + 1] == 1) l3++;
    for (int i = l3 ; i >= 1 ; i--) cout << c[i]; cout<<endl;

    解法四:(从此以后均为扯淡)

    设f[i][j]表示i+j的值。可得状态转移方程为f[i][j] = max(f[i-1][j]+1 , f[i][j-1]+1)。由于任何数加0数值不变(公理),所以边界条件为f[0][i]=f[i][0]=i。最后输出f[a][b]即可。核心代码:

    for (int i = 1 ; i <= a ; i++) f[i][0] = i;
    for (int i = 1 ; i <= b ; i++) f[0][i] = i;
    for (int i = 1 ; i <= a ; i++)
    for (int j = 1 ; j <= b ; j++)
    f[i][j] = max(f[i - 1][j] + 1 , f[i][j - 1] + 1);

    解法五:分析解法四时间复杂度知若时间为O(a*b)。若a*b过大则程序必定超时。观察代码容易发现,根据分配律(公理)得:

    f[i][j-1]+1=(i)+(j-1)+1=(i)+(j)-1+1=(i-1)+(j)+1=f[i-1][j]+1

    根据上式我们可以立即将时间和空间复杂度都降低一维。核心代码:

    f[0] = 0;
    for (int i = 1 ; i <= max(a , b) ; i++)
    f[i] = f[i - 1] + 1;

    最后输出f[a]+f[b]。可以看到,时间复杂度为O(max(a,b)),为线性,可以通过此题。

    解法六:

    首先orz给出本解法的神犇

    设图G=(V, E)为一流网络,包含2个源点S1、S2和1个汇点T。构造该图使得:

    从S1、S2分别发出a、b条边,每条边的容量为1,这些边应当连接到max(a, b)个顶点上,且没有两条边拥有相同的两个端点。从这max(a, b)个顶点分别连一条容量为+∞的边到汇点T。然后在这个流网络上面跑Dinic算法、Ford-Fulkerson算法之类的东西,可以练练写网络流的手感。

  • 1

信息

ID
1000
难度
9
分类
(无)
标签
(无)
递交数
73372
已通过
28159
通过率
38%
被复制
196