【USACO3.1】解题报告

前言

又有两个多月没有更新USACO了。
好吧现在确实很少在上面刷题了。
以后的题目链接不再放USACO了，因为点进去只能到首页。以后就放洛谷上了。
USACO:http://train.usaco.org

3.1.2.Agri-Net

思路：

最小生成树裸题。不解释。

代码：

#include <cstdio>
using namespace std;
int a[101][101],n,b[101],k,sum,minn;

int main()
{
    scanf("%d",&n);
    b[1]=1;
    for (int i=1;i<=n;i++)
     for (int j=1;j<=n;j++)
      scanf("%d",&a[i][j]);
    for (int q=1;q<=n-1;q++)
    {
        minn=2147483647;
        for (int i=1;i<=n;i++)
         if (b[i]==1)
          for (int j=1;j<=n;j++)
           if (b[j]==0&&a[i][j]<minn&&i!=j)
           {
           	  k=j;
           	  minn=a[i][j];
           }
        if (minn!=2147483647)
        {
            sum+=minn;
            b[k]=1;
        }   
    } 
    printf("%d
",sum);
    return 0;
}

3.1.3.Score Inflation

思路：

显然完全背包。
又是一道裸体2333

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

const int N=10010;
int n,m,w[N],v[N],f[N],ans;

int main()
{
    scanf("%d%d",&m,&n);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);
    for (int i=1;i<=n;i++)
        for (int j=w[i];j<=m;j++)
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    for (int i=1;i<=m;i++)
        ans=max(ans,f[i]);
    printf("%d
",ans);
    return 0;
}

3.1.4.Humble Numbers

思路：

这道题就有点意思了。
显然，第 $i$ 个丑数肯定是由第 $1sim i-1$ 个丑数中的某一个乘上某一个质数得来的。
所以我们先循环 $n$ 次来找 $n$ 个丑数，然后枚举质数，对于每个质数二分丑数，使得该丑数 $imes$ 质数 $>$ 第 $i-1$ 个丑数，并且选择尽量小的。
这样的时间复杂度是 $O(NK log N)$ 。跑的比较慢，懒得改了。加优化上去过了。

代码：

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

#include <cstdio>
#include <algorithm>
using namespace std;

const int N=100010;
const int M=110;
int n,m,l,r,prime[M],a[N];

int main()
{
    fill(a,a+N,2147483647);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&prime[i]);
    a[0]=1;
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            a[i]=min(a[i],a[upper_bound(a,a+i,a[i-1]/prime[j])-a]*prime[j]);
    printf("%d",a[m]);
    return 0;
}

3.1.5.Contact

$color{blue} exttt{题解链接}$

3.1.6.Stamps

思路：

显然背包。
首先，如果邮票集合中没有1元的肯定是不行的。因为1元都没法凑出来。直接输出0。
如果有1元，那么任何价值都可以凑出来。
设 $f[i]$ 表示至少使用几张邮票可以凑出 $i$ 元来。如果 $f[i]>n$ 就说明不行了。

代码：

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

const int N=10000* 200+10;
int n,m,a[51],f[N];
bool ok;

int main()
{
    //freopen("testdata.in","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
        if (a[i]==1) ok=1;
    }
    if (!ok) return !printf("0");
    memset(f,0x3f3f3f3f,sizeof(f));
    f[0]=0;
    f[1]=1;
    for (int i=2;i<=N;i++)
    {
        for (int j=1;j<=m;j++)
            if (i>=a[j]) f[i]=min(f[i],f[i-a[j]]+1);
        if (f[i]>n) return !printf("%d
",i-1);
    }
}