AcWing 605. 简单乘积恶搞    原题链接    简单

作者： 作者的头像   cht ,  2020-04-14 19:02:59 ,  所有人可见 ,  阅读 5148

41


18

题目描述

读取两个整数值。

在此之后，计算它们的乘积并将结果存储在名为PROD的变量中。

输出结果如下例所示。

样例

输入样例：
3
9
输出样例：
PROD = 27

算法1

(正常做法)

直接a*b。

时间复杂度

$O(1)$

C++ 代码

#include<iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    cout << "PROD = " << a * b << endl;
    return 0;
}

（此算法十分简单）

算法2

(二分)

用二分处理，先把负数转换，然后二分。

时间复杂度 #### 作者没算

C++ 代码

#include<iostream>

using namespace std;

int f = 0;//数的状态（0，-..,...）

int main()
{
    int a, b;
    cin >> a >> b;

    if(a == 0 || b == 0) f = 2;//处理状态
    else if(a < 0 && b >= 0 || b < 0 && a >= 0)
    {
        f = 1;
        if(a < 0) a = a * -1;
        else b = b * -1;
    }

    int l = -100000000, r = 100000000;
    while(r - l >= 1)
    {
        int mid = (l + r) / 2;//二分
        if(mid >= a * b) r = mid;
        else l = mid + 1;
    }

    if(f == 2) 
    {
        cout <<"PROD = "  << l;
    }
    else if(f == 0)
    {
        cout <<"PROD = "  << l;
    }
    else cout << "PROD = -" << l;
}

此算法较为简单

算法3

(高精度)
（让我崩溃。。。）

时间复杂度 没算

C++ 代码(照着y总写的)

#include <iostream>
#include <vector>

using namespace std;

vector<int> f(vector<int> &a, int b)//处理函数
{
    vector<int> c;//定义结果
    int x = 0;
    for (int i = 0; i < a.size() || x; i ++ )//一位一位运算
    {
        if (i < a.size()) x += a[i] * b;//每次把a【i】乘b
        c.push_back(x % 10);
        x = x / 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();

    return c;
}


int main()
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> a2;
    for (int i = a.size() - 1; i >= 0; i -- ) a2.push_back(a[i] - '0');
    auto c = f(a2, b);
    for (int i = c.size() - 1; i >= 0; i -- ) printf("%d", c[i]);

    return 0;
}

（此算法有一点点难）

算法4

(位运算)

C++ 代码(由 抽风_1 提供)

#include <stdio.h>

int add(int a, int b)
{
    while (b)
    {
        int x = a ^ b;
        int y = (a & b) << 1;
        a = x;
        b = y;
    }
    return a;
}

int main()
{
    int a, b;
    int res = 0;
    scanf("%d%d", &a, &b);
    if (b < 0)
    {
        a = add(~a, 1);
        b = add(~b, 1);
    }
    while (b)
    {
        if (b & 1) res = add(res, a);
        a <<= 1;
        b >>= 1;
    }
    printf("PROD = %d", res);
    return 0;
}

作者：抽风_1
链接：https://www.acwing.com/file_system/file/content/whole/index/content/481481/#comment_21875
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

本次恶搞到此结束，定期更新！！！

32 评论

用户头像
抽风_1   2020-04-15 09:24      3    踩      回复

位运算解法：

#include <stdio.h>

int add(int a, int b)
{
    while (b)
    {
        int x = a ^ b;
        int y = (a & b) << 1;
        a = x;
        b = y;
    }
    return a;
}

int main()
{
    int a, b;
    int res = 0;
    scanf("%d%d", &a, &b);
    if (b < 0)
    {
        a = add(~a, 1);
        b = add(~b, 1);
    }
    while (b)
    {
        if (b & 1) res = add(res, a);
        a <<= 1;
        b >>= 1;
    }
    printf("PROD = %d", res);
    return 0;
}
用户头像
cht   2020-04-15 18:45      1    踩      回复

不愧acsaber排名那么nb，大佬

用户头像
抽风_1   2020-04-15 23:32         踩      回复

SPFA解法

#include <stdio.h>
#include <string.h>

const int N = 10010;

int e[N], ne[N], w[N], h[N], idx;
int dist[N];
bool state[N];
int q[N];
int hh, tt;

void add(int a, int b, int c)
{
    e[ ++ idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
}

int spfa(int end)
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    state[1] = true;
    q[0] = 1;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        state[t] = false;
        for (int i = h[t]; i; i = ne[i])
            if (dist[e[i]] > dist[t] + w[i])
            {
                dist[e[i]] = dist[t] + w[i];
                if (!state[e[i]])
                {
                    state[e[i]] = true;
                    q[ ++ tt] = e[i];
                }
            }
    }
    return dist[end];
}

int main()
{
    int a, n;
    scanf("%d %d", &a, &n);
    if(n < 0) a = -a, n = -n;
    n ++ ;
    for (int i = 1; i < n; i ++ )
        add(i, i + 1, a);
    printf("PROD = %d", spfa(n));
    return 0;
}
用户头像
抽风_1   2020-04-15 23:33      1    踩      回复

堆优化dijkstra解法（手写堆）

#include <stdio.h>
#include <string.h>

const int N = 10010;

int e[N], h[N], ne[N], w[N], idx;
int dist[N];
bool state[N];
int heap_first[N], heap_second[N];
int size;

void add(int a, int b, int c)
{
    e[ ++ idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
}

void heap_swap(int i, int j)
{
    if (i ^ j)
    {
        heap_first[i] ^= heap_first[j];
        heap_first[j] ^= heap_first[i];
        heap_first[i] ^= heap_first[j];
        heap_second[i] ^= heap_second[j];
        heap_second[j] ^= heap_second[i];
        heap_second[i] ^= heap_second[j];
    }
}

void down(int p)
{
    int t = p;
    if (p << 1 <= size && heap_first[p << 1] < heap_first[t])
        t = p << 1;
    if ((p << 1 | 1) <= size && heap_first[p << 1 | 1] < heap_first[t])
        t = p << 1 | 1;
    if (t ^ p)
    {
        heap_swap(t, p);
        down(t);
    }
}

void up(int p)
{
    while (p >> 1 && heap_first[p >> 1] > heap_first[p])
    {
        heap_swap(p >> 1, p);
        p >>= 1;
    }
}

void insert(int first, int second)
{
    size ++ ;
    heap_first[size] = first;
    heap_second[size] = second;
    up(size);
}

void erase(int p)
{
    heap_swap(p, size -- );
    up(p);
    down(p);
}

int dijkstra(int end)
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    insert(0, 1);
    while (size)
    {
        int t = heap_second[1];
        erase(1);
        if (state[t])continue;
        state[t] = true;
        for (int i = h[t]; i; i = ne[i])
            if (dist[e[i]] > dist[t] + w[i])
            {
                dist[e[i]] = dist[t] + w[i];
                insert(dist[e[i]], e[i]);
            }
    }
    return dist[end];
}

int main()
{
    int a, n, f = 1;
    scanf("%d %d", &a, &n);
    if (n < 0) n = -n, a = -a;
    if (a < 0) f = -f, a = -a;
    n ++ ;
    for (int i = 1; i < n; i ++ )
        add(i, i + 1, a);
    printf("PROD = %d\n", f * dijkstra(n));
    return 0;
}
用户头像
cht   2020-04-16 08:21    回复了 抽风_1 的评论         踩      回复

卧槽

用户头像
cht   2020-04-16 08:22    回复了 抽风_1 的评论         踩      回复

堆是除了高精度最让我头疼的哥们

用户头像
cht   2020-04-16 08:22    回复了 抽风_1 的评论         踩      回复

然后是BFS

用户头像
抽风_1   2020-04-16 09:31    回复了 cht 的评论         踩      回复

hh

用户头像
抽风_1   2020-04-16 09:44    回复了 cht 的评论      1    踩      回复

bfs版

#include <stdio.h>

const int N = 10010;

int e[N], ne[N], h[N], w[N], idx;
int q[N], hh, tt;
int dist[N];
bool state[N];

void add(int a, int b, int c)
{
    e[ ++ idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
}

int bfs(int end)
{
    q[0] = 1;
    state[1] = true;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        if (t == end) return dist[t];
        for (int i = h[t]; i; i = ne[i])
            if (!state[e[i]])
            {
                state[e[i]] = true;
                q[ ++ tt] = e[i];
                dist[e[i]] = dist[t] + w[i];
            }
    }
    return -1;
}

int main()
{
    int a, n;
    scanf("%d %d", &a, &n);
    printf("PROD = ");
    if (n < 0) n = -n, a = -a;
    if (a < 0) putchar('-'), a = -a;
    n ++ ;
    for (int i = 1; i < n; i ++ )
        add(i, i + 1, a);
    printf("%d", bfs(n));
    return 0;
}
用户头像
抽风_1   2020-04-16 09:53         踩      回复

dfs解法

#include <stdio.h>

const int N = 10010;

int e[N], h[N], ne[N], w[N], idx;
int dist[N];
bool state[N];

void add(int a, int b, int c)
{
    e[ ++ idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
}

void dfs(int t)
{
    for (int i = h[t]; i; i = ne[i])
        if (!state[e[i]])
        {
            state[t] = true;
            dfs(e[i]);
            dist[t] = dist[e[i]] + w[i];
            state[t] = false;
        }
}

int main()
{
    int a, n;
    scanf("%d %d", &a, &n);
    printf("PROD = ");
    if (n < 0) n = -n, a = -a;
    if (a < 0) putchar('-'), a = -a;
    n ++ ;
    for (int i = 1; i < n; i ++ )
        add(i, i + 1, a);
    dfs(1);
    printf("%d", dist[1]);
    return 0;
}
用户头像
抽风_1   2020-04-16 10:14         踩      回复

kruskal解法

#include <stdio.h>
#include <string.h>

const int N = 10010;

struct Edge
{
    int a, b, w;
}edges[N];

int a, n;
int res;
int fa[N];

int find(int x)
{
    if (x ^ fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}

int kruskal()
{
    for (int i = 1; i <= n; i ++ )
    {
        int a = find(edges[i].a);
        int b = find(edges[i].b);
        int w = edges[i].w;
        if (a ^ b)
        {
            fa[a] = b;
            res += w;
        }
    }
    return res;
}

int main()
{
    scanf("%d %d", &a, &n);
    printf("PROD = ");
    if (n < 0) n = -n, a = -a;
    if (a < 0) putchar('-'), a = -a;
    n ++ ;
    for (int i = 1; i < n; i ++ )
    {
        edges[i].a = i;
        edges[i].b = i + 1;
        edges[i].w = a;
        fa[i] = i;
    }
    printf("%d", kruskal());
    return 0;
}
用户头像
抽风_1   2020-04-16 10:20      1    踩      回复

树状数组解法

#include <stdio.h>
#include <string.h>

const int N = 10010;

int a, n;
int tr[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

int main()
{
    scanf("%d %d", &a, &n);
    printf("PROD = ");
    if (n < 0) n = -n, a = -a;
    for (int i = 1; i <= n; i ++ )
        add(i, a);
    printf("%d", sum(n));
    return 0;
}
用户头像
抽风_1   2020-04-16 10:28      1    踩      回复

并查集解法

#include <stdio.h>
#include <string.h>

const int N = 10010;

int a, n;
int fa[N], size[N];

int find(int x)
{
    if (fa[x] ^ x) fa[x] = find(fa[x]);
    return fa[x];
}

void merge(int a, int b)
{
    a = find(a), b = find(b);
    size[b] += size[a];
    fa[a] = b;
}

int main()
{
    scanf("%d %d", &a, &n);
    printf("PROD = ");
    if (n < 0) n = -n, a = -a;
    for (int i = 1; i <= n; i ++ )
        fa[i] = i, size[i] = a;
    for (int i = 1; i < n; i ++ )
        merge(i, n);
    printf("%d", size[n]);
    return 0;
}
用户头像
cht   2020-04-16 11:10    回复了 抽风_1 的评论         踩      回复

加个私信吧，要不然一会我这乱了

用户头像
抽风_1   2020-04-16 11:15    回复了 cht 的评论         踩      回复

嗯嗯

用户头像
acwing界麻瓜   2020-09-17 16:49    回复了 抽风_1 的评论         踩      回复

太强了吧，我就会a*b，/xk

用户头像
lixiaoqian_qwq   2021-09-27 21:30    回复了 抽风_1 的评论         踩      回复

这是什么神奇的堆呀qwq

用户头像
Bingxiu   9个月前      1    踩      回复

C++ 一行解法：https://www.acwing.com/solution/content/224527/

用户头像
抽风_1   2020-04-14 23:07      1    踩      回复

建议加一个高精乘高精

用户头像
double666   10个月前         踩      回复

PROD不应该是一个变量吗

用户头像
H.A.H.   2021-12-12 19:36         踩      回复

怕不是……

用户头像
闻天语   2022-08-19 11:58         踩      回复

闲得慌

用户头像
H.A.H.   2022-08-19 12:00    回复了 闻天语 的评论         踩      回复

本蒟蒻弱弱的说一句：FFT！

用户头像
闻天语   2022-08-19 12:01    回复了 H.A.H. 的评论         踩      回复

......................

用户头像
cht   2022-08-19 16:13    回复了 H.A.H. 的评论         踩      回复

k

用户头像
Athos   2021-09-19 16:12         踩      回复

向两大佬学习！！

用户头像
the.midnight   2021-09-12 19:09         踩      回复

tql

用户头像
窗边的树   2021-05-28 14:14         踩      回复

简单的a*b被两位大佬玩成了花儿，膜拜！

用户头像
cht   2020-04-15 18:42         踩      回复

我研究一下然后放上

用户头像
cht   2020-04-15 18:42         踩      回复

thanks

用户头像
cht   2020-04-15 08:35         踩      回复

谢谢大佬，以后会加

用户头像
抽风_1   2020-04-14 23:07         踩      回复

%%%%%%%%%%%