头像

Frank2008_1


访客:1643

离线:9小时前


活动打卡代码 AcWing 2. 01背包问题

#include<iostream>
using namespace std;

const int N=1010;
int v[N],w[N];
int f[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    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 1699.涂色游戏

1699涂色游戏中有个疑问,没有想明白,求助各位大佬。
样例2中,第4行数据:

668232501 586472717 2

上述两个数字互质。
根据格子编号大小,依次手工填色结果如下:
0号格子:红(题目规定0号必定为红);
586472717号格子:蓝(p2为蓝色);
668232501号格子:红(p1为红色);
1172945434号格:蓝(对应586472717*2p2蓝)
1336465002号格:红(对应668232501*2p1红)
以此类推,都是红蓝交错涂色,直到公倍数出现,即
391900130449175217号格子:红(公倍数和0号格子地位相同,跟着大数668232501填写,可以做到红蓝交错)
小数蓝,大数红,公倍数选红,可以做到连续涂色数为1,满足k=2的要求
为什么样例中的输出答案是No
(在题目输入中规定p1在前,p2在后,那么当p1>p2时,0号涂红,p2涂蓝,p1涂红,会出现比p2<p1更为有利的方案,可是样例2似乎并没有遵从这一有利方案,认为p1,p2中的小数填红?)




1699涂色游戏中有个疑问,没有想明白,求助各位大佬。
样例2中,第4行数据:

668232501 586472717 2

上述两个数字互质。
根据格子编号大小,依次手工填色结果如下:
0号格子:红(题目规定0号必定为红);
586472717号格子:蓝(p2为蓝色);
668232501号格子:红(p1为红色);
1172945434号格:蓝(对应586472717*2p2蓝)
1336465002号格:红(对应668232501*2p1红)
以此类推,都是红蓝交错涂色,直到公倍数出现,即
391900130449175217号格子:红(公倍数和0号格子地位相同,跟着大数668232501填写,可以做到红蓝交错)
小数蓝,大数红,公倍数选红,可以做到连续涂色数为1,满足k=2的要求
为什么样例中的输出答案是No
(在题目输入中规定p1在前,p2在后,那么当p1>p2时,0号涂红,p2涂蓝,p1涂红,会出现比p2<p1更为有利的方案,可是样例2似乎并没有遵从这一有利方案,认为p1,p2中的小数填红?)



活动打卡代码 AcWing 830. 单调栈

Frank2008_1
1个月前
#include<iostream>
using namespace std;

const int N=100001;
int stack[N];
int top=0;

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>t;
        while(top>0&&stack[top-1]>=t)
            top--;
        if(top==0)
            cout<<"-1 ";
        else
            cout<<stack[top-1]<<" ";
        stack[top++]=t;
    }
    return 0;
}



活动打卡代码 AcWing 829. 模拟队列

Frank2008_1
1个月前
#include<iostream>
using namespace std;

const int N=100001;
int a[N];
int h=0,t=0;

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        if(s=="push")
        {
            int x;
            cin>>x;
            a[t++]=x;
        }
        else if(s=="pop")
            h++;
        else if(s=="query")
            cout<<a[h]<<endl;
        else
            if(h<t)
                cout<<"NO"<<endl;
            else
                cout<<"YES"<<endl;
    }
    return 0;
}



活动打卡代码 AcWing 828. 模拟栈

Frank2008_1
1个月前
#include<iostream>
using namespace std;

const int N=100001;
int stack[N],top=0;

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string t;
        cin>>t;
        if(t=="push")
        {
            int x;
            cin>>x;
            stack[top++]=x;
        }
        else if(t=="pop")
            top--;
        else if(t=="empty")
            if(top==0)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        else
            cout<<stack[top-1]<<endl;
    }
    return 0;
}



活动打卡代码 AcWing 827. 双链表

Frank2008_1
1个月前
#include<iostream>
using namespace std;

const int N=100001;
int e[N],L[N],R[N];
int idx=2;

void init()
{
    L[0]=-1,R[0]=1;
    L[1]=0,R[1]=-1;
}
void insert_R(int k,int x)
{
    e[idx]=x;
    L[idx]=k;
    R[idx]=R[k];
    L[R[k]]=idx;
    R[k]=idx;
    idx++;
}
void insert_L(int k,int x)
{
    insert_R(L[k],x);
}
void my_delete(int k)
{
    R[L[k]]=R[k];
    L[R[k]]=L[k];
}
int main()
{
    init();
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        if(s=="L")
        {
            int x;
            cin>>x;
            insert_R(0,x);
        }
        else if(s=="R")
        {
            int x;
            cin>>x;
            insert_L(1,x);
        }
        else if(s=="IL")
        {
            int k,x;
            cin>>k>>x;
            k++;
            insert_L(k,x);
        }
        else if(s=="IR")
        {
            int k,x;
            cin>>k>>x;
            k++;
            insert_R(k,x);
        }
        else
        {
            int k;
            cin>>k;
            k++;
            my_delete(k);
        }
    }
    int p=R[0];
    while(R[p]!=-1)
    {
        cout<<e[p]<<" ";
        p=R[p];
    }
    return 0;
}



活动打卡代码 AcWing 826. 单链表

Frank2008_1
1个月前
#include<iostream>
using namespace std;

const int N=100001;
int e[N],ne[N];
int head=-1;
int idx=0;

void insert_head(int x)
{
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}
void insert(int k,int x)
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}
void my_delete(int k)
{
    ne[k]=ne[ne[k]];
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char t;
        cin>>t;
        if(t=='H')
        {
            int x;
            cin>>x;
            insert_head(x);
        }
        else if(t=='D')
        {
            int k;
            cin>>k;
            if(k==0)
                head=ne[head];
            else
                my_delete(k-1);
        }
        else
        {
            int k,x;
            cin>>k>>x;
            insert(k-1,x);
        }
    }
    int p=head;
    while(p!=-1)
    {
        cout<<e[p]<<" ";
        p=ne[p];
    }
    return 0;
}



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

Frank2008_1
1个月前
#include<iostream>
using namespace std;

const int N=1010;
int f[N],v[N][N],w[N][N],s[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(int j=1;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=1;k<=s[i];k++)
                if(j>=v[i][k])
                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
    }
    cout<<f[m]<<endl;
    return 0;
}



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

Frank2008_1
1个月前
#include<iostream>
using namespace std;

const int N=1e6+10;
int f[N];
int v[N],w[N],s[N];

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