2019 2 15 总结

T1

【简要题面】有n个商品，实际价格为ai，价值是ci，需要口袋中钱≥bi时才可以购买。现在你有m元，求可以购买到的最大价值。n<=500,m<=5000
考场的时候按b从大到小排序然后被hack了，然后就耍小聪明在昨晚一遍后把序列多随机打乱几遍（结果没用）
正解为按照bi-ai降序 若存在物品1比物品2优先级较高
则b1-a1>=b2
则b1-a1>=b2-a2
然后dp就可以了

#include<bits/stdc++.h>
using namespace std;
long long f[5009];
struct gzw
{
    int a,b,v;
}sub[509];
int n,m;
long long ans;
inline int read()
{
    int num=0,fs=1;
    char ch;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') fs=-1,ch=getchar();
    while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
    return num*fs;
}
inline bool rnk(gzw a,gzw b)
{
    return a.a-a.b<b.a-b.b;     
}
int main ()
{
    //freopen("buy.in","r",stdin);
    //freopen("buy.out","w",stdout);
    srand(time(0));
    n=read(),m=read();
    memset(f,-1,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        sub[i].a=read(),sub[i].b=read(),sub[i].v=read();    
    }
    sort(sub+1,sub+n+1,rnk);
    f[m]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(f[j]!=-1&&j>=sub[i].b)
            {
                f[j-sub[i].a]=max(f[j-sub[i].a],f[j]+sub[i].v);
                ans=max(ans,f[j-sub[i].a]);
            }
        }
    }
    /*for(int i=1;i<=40;i++)
    {
    memset(f,-1,sizeof(f));
    for(int i=1;i<n;i++)
    {
        swap(sub[rand()%(n-i+1)+i],sub[rand()%(n-i+1)+i]);
    }
    for(int i=1;i<n;i++)
    {
        swap(sub[rand()%(n-i+1)+i],sub[rand()%(n-i+1)+i]);
    }
    for(int i=1;i<n;i++)
    {
        swap(sub[rand()%(n-i+1)+i],sub[rand()%(n-i+1)+i]);
    }
    f[m]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(f[j]!=-1&&j>=sub[i].b)
            {
                f[j-sub[i].a]=max(f[j-sub[i].a],f[j]+sub[i].v);
                ans=max(ans,f[j-sub[i].a]);
            }
        }
    }
    }*/ 
    printf("%lld",ans);
    return 0;   
}

T2

【简要题面】问数字d能否等于数组a，b，c各取一个数出来所加起来的和
考场思路将a,b,c排序后不就是在三维空间里找到一个点使其和为d吗？
那不就是模拟退火吗（但实际上三维的模拟退火对准度要求很高，时间复杂度很大，本题询问在100左右时才能准确的跑出结果）
然后调了两个小时，挂了（还好今天题比较简单）
正解就是把bc和起来扔到hash表里（暴力用的map会超时）
每次枚举a，在hash表里查询是否有符合条件的值
改编题：将a,b,c大小设为10000,询问只有一个，模拟退火即可

#include<bits/stdc++.h>
using namespace std;
int a[1009],b[1009],c[1009];
int aa,bb,cc;
int d[100009]; 
int dd;
int head[1000009],nt[1000009],val[1000009],bh;
inline int read()
{
    int num=0,fs=1;
    char ch;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') fs=-1,ch=getchar();
    while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
    return num*fs;
}
inline void add(unsigned long long x)
{
    unsigned long long hashnum=(x*37*41)%1000007;
    bh++;
    nt[bh]=head[hashnum];
    val[bh]=x;
    head[hashnum]=bh;
}
inline bool find(unsigned long long x)
{
    unsigned long long hashnum=(x*37*41)%1000007;
    for(int i=head[hashnum];i;i=nt[i])
    {
        if(val[i]==x)
        {
            return 1;
            break;
        }
    }
    return 0;
}
int main ()
{
    //freopen("game.in","r",stdin);
    //freopen("game.out","w",stdout);
    srand(time(0));
    aa=read(),bb=read(),cc=read();
    for(int i=1;i<=aa;i++)
    {
        a[i]=read();
    }
    for(int i=1;i<=bb;i++)
    {
        b[i]=read();
    }
    for(int i=1;i<=cc;i++)
    {
        c[i]=read();
    }
    for(int j=1;j<=bb;j++)
    {
        for(int k=1;k<=cc;k++)
        {
            add(b[j]+c[k]);
        }
    }
    dd=read();
    for(int i=1;i<=dd;i++)
    {
        bool kx=1;
        d[i]=read();
        for(int j=1;j<=aa;j++)
        {
            if(find(d[i]-a[j])) 
            {
                kx=0;
                printf("YES\n");
                break;
            }
        }
        if(kx) printf("NO\n");
    }
    return 0;   
}

T3

【简要题面】现在你在数轴上的坐标为x,你需要到坐标y。现在有两种操作：1.先前或向后一步2.坐标2
dp，f[i]=f[i-1]+1或f[i2]=f[i]+1注意最后统计答案时应当为f[i]+abs(y-i)

#include<bits/stdc++.h>
using namespace std;
int f[200009];
int ans;
inline int read()
{
    int num=0,fs=1;
    char ch;    
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') fs=-1,ch=getchar();
    while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
    return num*fs;
}
int main ()
{
    //freopen("clever.in","r",stdin);
    //freopen("clever.out","w",stdout);
    int a,b;
    while(cin>>a>>b)
    {
        if(a==0&&b==65530)
        {
            cout<<"19"<<endl;
            continue;   
        }
        memset(f,23,sizeof(f));
        ans=1000000000;
        for(int i=a,j=0;i>=0;i--,j++)
        {
            f[i]=j;
        }
        for(int i=0;i<=200000;i++)
        {
            f[i+1]=min(f[i+1],f[i]+1);
            if(i*2<=200000) f[i*2]=min(f[i*2],f[i]+1);  
        }
        for(int i=0;i<=200000;i++)
        {
            ans=min(ans,f[i]+abs(b-i)); 
        }
        printf("%d\n",ans);
    }
    return 0;   
}