头像

种花家的虎式坦克

$\href{https://www.acwing.com/blog/content/28491/}{题解主页}$




离线:10小时前


最近来访(1602)
用户头像
liaoyanxu
用户头像
mYcc
用户头像
yxc的小迷妹
用户头像
梦若浮生
用户头像
Finn2009
用户头像
小迪迪Yc_Zhu
用户头像
宇宙有边
用户头像
yangxiufeng
用户头像
Redamancy_501
用户头像
吴梦涵2022
用户头像
这个仇我记下了
用户头像
violet_garden
用户头像
落月成孤倚灬
用户头像
acwing_96177
用户头像
垫底抽風
用户头像
糊涂装天才
用户头像
ZARD_影
用户头像
抿了抿嘴
用户头像
ybsqsjzbdbb
用户头像
明日原由纪

新鲜事 原文

暂时不放个人主页了,换成题解主页,个人主页在我的分享里面



精选题解3篇(按点赞数排序)

1. 高精度乘法

2. 逆序对的数量

3. 高精度除法

(按阅读量排序)

1. 逆序对的数量

2. 数的范围

3. 快速排序

(按详细度排序)

1. 高精度加法

2. a ^ b

3. 逆序对的数量

欢迎讨论自己的题解




<-求赞

思路

直接x -= lowbit(x),减多少次就说明有多少个1

#include<iostream>

using namespace std;

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

int main()
{
    int n;
    cin>>n;

    while(n--)
    {
        int x;
        cin>>x;

        int res=0;
        while(x) x-=lowbit(x),res++;

        cout<<res<<endl;
    }

    return 0;
}



<-求赞

思路(双指针)

因为序列是有序的,所以我们从头往后扫描b数组,只要有一个a数组中的元素匹配不上,就不匹配。

否则是匹配的。

c++代码:

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d",&b[i]);

    int i = 0, j = 0;
    while (i < n && j < m)
    {
        if(a[i] == b[j]) i ++ ;
        j ++ ;
    }

    if(i == n) puts("Yes");
    else puts("No");

    return 0;
}



<- 求赞

思路1(暴力)

暴力枚举b,不停的乘a,最后%p。

时间复杂度:$O(b)$

肯定会超时,还会超内存。

思路2(暴力优化)

不在最后%p,是边乘边模p。

还是会超时,但内存不会超了。

思路3(快速幂)

这也是我们的最终写法。

举个例子:

比如说我们要求3的1000000次方是多少。

可以先算3^1,3^2………………3^(2^19)是多少。

再算1000000的二进制是多少,如果这一位是1,那么就把这一位对应的3的多少次方乘起来。

时间复杂度:$O(log _ 2n)$

c++代码(此处只展示快速幂解法):

#include <iostream>

using namespace std;

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

    int res = 1 % p;
    while (b)
    {
        if (b & 1) res = (long long)res * a % p;
        a = (long long)a * a % p;
        b >>= 1;
    }

    cout << res << endl;

    return 0;
}



算法竞赛进阶指南打卡活动

<-强烈建议收藏!!!

持续更新ing!!!

0x00 基本算法(1/40)

0x01 位运算(1/4)

a^b

0x10 基本数据结构(0/37)

0x20 搜索(0/32)

0x30 数学知识(0/41)

0x40 数据结构进阶(0/34)

0x50 动态规划(0/72)

0x60 贪心(0/73)




<-求赞

思路

二分查找

这道题可以用我们之前的二分思路来解答。

利用二分模版,我们可以很轻松的解决答案。

具体思路见 数的范围

c++代码:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int a[N],b[N];

int main()
{
    int n,m,x;
    cin>>n>>m>>x;
    for(int i=0;i<n;i++)    cin>>a[i];
    for(int j=0;j<m;j++)    cin>>b[j];

    int j=0;
    for(int i=0;i<n;i++)
    {
        int k=x-a[i];
        int l=0,r=m-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(b[mid]>=k)   r=mid;
            else l=mid+1;
        }
        // cout<<l<<"-----"<<endl;
        if(b[l]==k) {
            cout<<i<<" "<<l<<endl;
            break;
        }
    }
    return 0;
}



#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

#define v first
#define w second

using namespace std;

typedef pair<int, int> PII;

const int N = 60, M = 32010;

int n, m;
PII master[N];
vector<PII> servent[N];
int f[M];

int main()
{
    cin >> m >> n;

    for (int i = 1; i <= n; i ++ )
    {
        int v, p, q;
        cin >> v >> p >> q;
        p *= v;
        if (!q) master[i] = {v, p};
        else servent[q].push_back({v, p});
    }

    for (int i = 1; i <= n; i ++ )
        for (int u = m; u >= 0; u -- )
        {
            for (int j = 0; j < 1 << servent[i].size(); j ++ )
            {
                int v = master[i].v, w = master[i].w;
                for (int k = 0; k < servent[i].size(); k ++ )
                    if (j >> k & 1)
                    {
                        v += servent[i][k].v;
                        w += servent[i][k].w;
                    }
                if (u >= v) f[u] = max(f[u], f[u - v] + w);
            }
    }

    cout << f[m] << endl;

    return 0;
}


活动打卡代码 AcWing 734. 能量石

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;

int n;
struct Stone
{
    int s, e, l;
}stones[N];

bool cmp(Stone a, Stone b)
{
    return a.s * b.l < b.s * a.l;
}

int f[N][M];

int main()
{
    int T;
    cin >> T;
    for (int C = 1; C <= T; C ++ )
    {
        cin >> n;
        int m = 0;
        for (int i = 1; i <= n; i ++ )
        {
            int s, e, l;
            cin >> s >> e >> l;
            stones[i] = {s, e, l};
            m += s;
        }

        sort(stones + 1, stones + 1 + n, cmp);

        for (int i = 1; i <= n; i ++ )
            for (int j = 0; j <= m; j ++ )
            {
                f[i][j] = f[i - 1][j];
                if (j >= stones[i].s)
                {
                    int s = stones[i].s, e = stones[i].e, l = stones[i].l;
                    f[i][j] = max(f[i][j], f[i - 1][j - s] + max(0, e - l * (j - s)));
                }
            }

        int res = 0;
        for (int i = 0; i <= m; i ++ ) res = max(res, f[n][i]);

        printf("Case #%d: %d\n", C, res);
    }

    return 0;
}



#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;

int n;
struct Stone
{
    int s, e, l;
}stones[N];

bool cmp(Stone a, Stone b)
{
    return a.s * b.l < b.s * a.l;
}

int f[N][M];

int main()
{
    int T;
    cin >> T;
    for (int C = 1; C <= T; C ++ )
    {
        cin >> n;
        int m = 0;
        for (int i = 1; i <= n; i ++ )
        {
            int s, e, l;
            cin >> s >> e >> l;
            stones[i] = {s, e, l};
            m += s;
        }

        sort(stones + 1, stones + 1 + n, cmp);

        for (int i = 1; i <= n; i ++ )
            for (int j = 0; j <= m; j ++ )
            {
                f[i][j] = f[i - 1][j];
                if (j >= stones[i].s)
                {
                    int s = stones[i].s, e = stones[i].e, l = stones[i].l;
                    f[i][j] = max(f[i][j], f[i - 1][j - s] + max(0, e - l * (j - s)));
                }
            }

        int res = 0;
        for (int i = 0; i <= m; i ++ ) res = max(res, f[n][i]);

        printf("Case #%d: %d\n", C, res);
    }

    return 0;
}