头像

zwm


访客:3904

离线:1小时前



zwm
2天前
#include <iostream>
using namespace std;

const int N = 100010;

int n, m;
int father[N];
int set_sum[N];//当前集合中的元素个数

int find(int x) // 找祖宗
{
    if (father[x] != x) father[x] = find(father[x]);
    return father[x];
}

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

    for (int i = 1; i <= n; i ++ )//初始化
    {
        father[i] = i;
        set_sum[i] = 1;
    }

    while (m -- )
    {
        string op;
        int a, b;
        cin >> op;

        if (op == "C")
        {
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a != b)
            {
                father[a] = b;
                set_sum[b] += set_sum[a];
            }
        }
        else if (op == "Q1")
        {
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            cin >> a;
            cout << set_sum[find(a)] << endl;
        }
    }

    return 0;
}



活动打卡代码 AcWing 836. 合并集合

zwm
4天前
#include <iostream>
using namespace std;

int father[100005];// 存储节点的父节点
int n,quetion;

int find(int x)//返回x的祖宗节点的编号(即集合的编号)
{
    if(father[x] != x) father[x] = find(father[x]);
    return father[x];
}

void unionn(int r1,int r2)//合并r1和r2两个集合
{
    father[find(r1)] = find(r2);
}

void init()//初始化
{
    for(int i=1;i<=n;i++)
    {
        father[i] = i;//根为自己
    }

    return ;
}

int main()
{
    scanf("%d%d",&n,&quetion);

    init();//初始化

    while(quetion--)
    {
        char choose;//操作
        int x,y;

        cin>>choose;
        scanf("%d%d",&x,&y);

        if(choose == 'M')//合并集合
        {
            unionn(x,y);//要确保两个集合不在同一集合的情况下就合并
        }
        else
        {
            if(find(x) == find(y)) printf("Yes\n");
            else printf("No\n");
        }
    }

    return 0;
}



zwm
14天前
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

const int mod=1e9+7;

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

    unordered_map<int,int> hash;//哈希表存储所有质因子的指数和
    while(n--)
    {
        int x;
        cin>>x;

        for(int i=2;i<=x/i;i++)
        {
            while(x % i == 0) 
            {
                x/=i;
                hash[i]++;//记录指数和
            }
        }
    }

    long long sum=1;
    for(auto t : hash) sum = sum * (t.second + 1) % mod;

    cout<<sum;

    return 0;
}

wa

2020-09-05_17h45_11.png

强烈拒绝0回复惨案 QAQ




zwm
14天前
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

const int mod=1e9+7;

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

    unordered_map<int,int> hash;//哈希表存储所有质因子的指数和
    while(n--)
    {
        int x;
        cin>>x;

        for(int i=2;i<=x/i;i++)
        {
            while(x % i == 0) 
            {
                x/=i;
                hash[i]++;//记录指数和
            }
        }
    }

    long long sum=1;
    for(auto t : hash) sum = sum * (t.second + 1) % mod;

    cout<<sum;

    return 0;
}

wa

2020-09-05_17h45_11.png

强烈拒绝0回复惨案 QAQ




zwm
20天前
#include <bits/stdc++.h>
using namespace std;

const int N=1010;
int n,m;
char a[N],b[N];
int f[N][N];

int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s%s",a+1,b+1);

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1] + 1);
        }
    }

    printf("%d",f[n][m]);
    return 0;
}


活动打卡代码 AcWing 282. 石子合并

zwm
20天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;


const int N=310;

int f[N][N];//f[i][j]为第i到j这个区间中的最小合并代价
int a[N];//代价
int sum[N];//前缀和

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++) sum[i]=sum[i-1] + a[i];//处理前缀和

    for(int len=2;len <= n;len++)//枚举区间长度
        for(int i=1;i + len -1 <=n;i++)//枚举区间起点,如果区间结尾不超过长度,就合法
        {
            int j=i + len -1;//区间终点
            f[i][j]=0x3f3f3f3f;//初始化为最大值
            for(int k=i;k<j;k++)
            {
                f[i][j]=min(f[i][j] , f[i][k] + f[k+1][j] + sum[j] - sum[i-1]);
                //f[起点][终点]=min(f[起点][终点],f[起点][中断点] + f[中断点][终点] + 当前合并的代价)
            }
        }

    cout<<f[1][n];

    return 0;
}



zwm
22天前
#include <bits/stdc++.h>
using namespace std;

int a[1005];
int f[1005];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++) f[i]=1;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
        }
    }

    int maxx=-0x3f3f3f3f;
    for(int i=1;i<=n;i++) maxx=max(maxx,f[i]); 
    cout<<maxx;

    return 0;
}


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

zwm
22天前
#include <iostream>
#include <algorithm> 
using namespace std;

const int N=505,INF=10e9;
int f[N][N];
int a[N][N];//原图

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

    for(int i=0;i<=n;i++)
        for(int j=0;j<=i+1;j++)
            f[i][j]=-INF;//初始化为负无穷     

    f[1][1]=a[1][1];//初始化第一行为第一个数
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            f[i][j]=max(f[i-1][j-1],f[i-1][j]) + a[i][j];
        }
    }

    int maxx=-INF;
    for(int i=1;i<=n;i++) maxx=max(maxx,f[n][i]);//整理答案

    cout<<maxx;

    return 0;
}


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

zwm
23天前
//枚举第i个物品选哪个(或不选)
#include <iostream>
#include <algorithm>
using namespace std;

const int N=110;
int v[N][N];//v[i][j]=第i组第j个物品的体积
int w[N][N];//w[i][j]=第i组第j个物品的价值
int s[N];//s[i]=第i组在物品个数
int f[N];
int n,m;//组数,背包容量

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];

    return 0;
}


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

zwm
23天前
#include <iostream>
#include <algorithm>
using namespace std;

const int N=20050,M=2005;
int v[N],w[N],f[N];

int main()
{
    int n,m,cnt=0;
    cin>>n>>m;
    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;
            k*=2;
        }
        if(s>0)
        {
            cnt++;
            w[cnt]=s*b;
            v[cnt]=s*a;
        }
    }

    n=cnt;

    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];

    return 0;
}