头像

夜语声烦

中国反卷协会




在线 


最近来访(12)
用户头像
独揽清风
用户头像
蟹黄酱gaga
用户头像
qhm
用户头像
7tai
用户头像
yxc
用户头像
18890394937

活动打卡代码 AcWing 9. 分组背包问题

夜语声烦
2小时前
#include <iostream>
using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

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

    for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for (int j = 0; j < s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 0; j -- )
            for (int k = 0; k < s[i]; k ++ )
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;

    return 0;
}



活动打卡代码 AcWing 5. 多重背包问题 II

夜语声烦
4小时前

采用二进制优化,转换成01背包

#include<iostream>
using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M]; // 体积<M

int main()
{
    cin >> n >> m;
    int cnt = 0; //分组的组别
    for(int i = 1;i <= n;i ++)
    {
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1; // 组别里面的个数
        while(k<=s)
        {
            cnt ++ ; //组别先增加
            v[cnt] = a * k ; //整体体积
            w[cnt] = b * k; // 整体价值
            s -= k; // s要减小
            k *= 2; // 组别里的个数增加
        }
        //剩余的一组
        if(s>0)
        {
            cnt ++ ;
            v[cnt] = a*s; 
            w[cnt] = b*s;
        }
    }

    n = cnt ; //枚举次数正式由个数变成组别数

    //01背包一维优化
    for(int i = 1;i <= n ;i ++)
        for(int j = m ;j >= v[i];j --)
            f[j] = max(f[j],f[j-v[i]] + w[i]);

    cout << f[m] << endl;
    return 0;
}


活动打卡代码 AcWing 4. 多重背包问题

夜语声烦
4小时前

注:所有物品的体积v[N]和价值w[N]都可以不开数组

这样做还有一个好处:解决了空间复杂度过大的问题,例如,如果某件物品数量很多,改造成01背包后新的v[N]和w[N]会很占内存,v[N]、w[N]不开数组后,只需要f数组就够了.

#include <bits/stdc++.h>
using namespace std;

int f[105];
int n,m;
int v,w,s;

int main()
{
    cin >> n >> t;
    while(n--)
    {
        cin >> w >> v >> s;
        for(int i = 1;i <= s;i++)
            for(int j = t;j >= w;j--)
                f[j]=max(f[j],f[j-w]+v);
    }
    cout << f[m];
    return 0;
}


活动打卡代码 AcWing 143. 最大异或对

143. 最大异或对

#include<iostream>
using namespace std;

const int N = 1e5 + 10,M = 31 * N;
int a[N],son[M][2];//有N个整数,每个整数31位,所以M = 31 * N
int idx,n;

void insert(int x)
{
    int p = 0;
    for(int i = 30;~i;i--)//~i = i >= 0
    {                     //最大是2^31 - 1所以要右移30位(默认已经在最后以为
        int &s = son[p][x >> i & 1];//这里写的是引用,s怎么变化,son[p][x>>i&1]也会跟着变化,他俩是完全等价的
        if(!s) s = ++idx;
        p = s;
    }
}

int query(int x)
{
    int p  = 0,res = 0;
    for(int i = 30; ~i;i--)//因为要找最大异或值,所以要从最大位开始
    {
        int s = x >> i & 1;
        if(son[p][!s])
        {
            res += 1 << i;
            p = son[p][!s];
        }
        else p = son[p][s];
    }
    return res;
}

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

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

    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 1346. 回文平方

1346. 回文平方

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

char to_char(int n)
{
    if(n <= 9) return n + '0';
    return n - 10 + 'A';
}

string change(int n,int b)
{
    string res;
    while (n)
    {
        res += to_char(n % b);
        n /= b;
    }
    reverse(res.begin(),res.end());
    return res;
}

bool check(string s)
{
    string res = s;
    reverse(res.begin(),res.end());
    return res == s;
}

int main()
{
    int b;
    cin >> b;
    for(int i = 1;i <= 300;i++)
    {
        string res = change(i * i,b);
        if(check(res))
            cout << change(i,b) << ' ' << res << endl;
    }
}


活动打卡代码 AcWing 756. 蛇形矩阵

756. 蛇形矩阵

#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int q[N][N];

int main()
{
    cin >> n >> m;
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    int x = 0, y = 0, d = 1;
    for (int i = 1; i <= n * m; i ++ )
    {
        q[x][y] = i;
        int a = x + dx[d], b = y + dy[d];
        if (a < 0 || a >= n || b < 0 || b >= m || q[a][b])
        {
            d = (d + 1) % 4;
            a = x + dx[d], b = y + dy[d];
        }
        x = a, y = b;
    }

    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
            cout << q[i][j] << ' ';
        cout << endl;
    }

    return 0;
}




活动打卡代码 AcWing 898. 数字三角形

898. 数字三角形

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n,m;
int a[510][510];

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= i;j++)
            scanf("%d", &a[i][j]);

    for (int i = n-1; i >= 1; i-- )
        for(int j = 1;j <= i;j++)
            a[i][j] += max(a[i+1][j],a[i+1][j+1]);

    cout << a[1][1];
}


活动打卡代码 AcWing 104. 货仓选址

104. 货仓选址

#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int a[N],n,i,ans,sum;
int main()
{
    cin>>n;
    for (i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);//排序
    int sm=a[n/2+1];//中位数
    for (i=1;i<=n;i++)
        ans=ans+abs(a[i]-sm);//统计和中位数之间的差
    cout<<ans;
    return 0;
}




活动打卡代码 AcWing 1113. 红与黑

#include <bits/stdc++.h>
using namespace std;

int n,m;
char a[50][50];
int fx[5]={0,0,1,0,-1};
int fy[5]={0,1,0,-1,0};
int cnt,s,t;
int dfs(int x,int y){
    a[x][y]='@';
    cnt++;
    int tx,ty;
    for(int i=1;i<5;i++){
        tx=x+fx[i];
        ty=y+fy[i];
        if(a[tx][ty]=='.'){
            dfs(tx,ty);
        }
    }
    return cnt;
}

int main(){
    while(~scanf("%d%d",&n,&m))
    {
        if(n == m && n == 0) exit(0);
        int i,j,c=0;
        for(i=1;i<=m;i++){
            for(j=1;j<=n;j++){
                cin >> a[i][j];
                if(a[i][j]=='@'){
                    s = i,t = j;
                }
            }
        }
        dfs(s,t);
        cout << cnt << endl;
        cnt = 0;
    }
}


活动打卡代码 AcWing 2058. 笨拙的手指

2058. 笨拙的手指

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

using namespace std;

int get(string s,int b)
{
    int res = 0;
    for(auto c: s)
        res = res * b + c - '0';
    return res;
}

int main()
{
    string a,b;
    cin >> a >> b;
    unordered_set<int> S;
    for(auto& c: a)
    {
        c ^= 1;
        S.insert(get(a,2));
        c ^= 1;
    }

    for(auto& c: b)
    {
        char t = c;
        for(int i = 0;i < 3;i ++)
            if(i + '0' != t)
            {
                c = i + '0';
                int x = get(b,3);
                if(S.count(x))
                {
                    cout << x << endl;
                    return 0;
                }
            }
        c = t;
    }

    return 0;
}