USACO刷题集锦(Part.2)

发表于 | 更新于 | 分类于 | 阅读次数：

完了，第三章就难死了，后面估计每张都是一个新的PART。。

$Section 3.1$

  • 难题：P2723，2724还有等等，估计每道题都要稍微摸一下了。。。

$eg_1:P2723$ 丑数 Humble Numbers

题意：
对于一给定的素数集合 S = {p1, p2, …, pK},考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，$p1,p1*p2,p1*p1,p1*p2*p3…$(还有其它)。该集合被称为S集合的“丑数集合”。注意：我们认为1不是一个丑数。

你的工作是对于输入的集合S去寻找“丑数集合”中的第N个“丑数”。所有答案可以用longint(32位整数)存储。

思路：一个黄题把我搞得天昏地暗。。但真的不会啊！

以为是DP啥的，以为问你乘积就是背包加法的板子改改，发现根本没有任何关系。。而且抄题解写出来个3重DP很明显超时了。

然后题解再往后翻翻，发现了一个叫作STL的东西。。。

问你第N小其实弄一个优先队列搞就行了，但是可能会有重复的而且开$MAP$的话你最大存不，于是又想到了还有set这种东西。。

于是用STL就搞过去了…真不知道这么裸的板子为啥想不到怎么做。

难点：没有难点

代码（关键部分）：

1
2
3
4
5
6
while(i<=n)
{
	i++; ll h=q.top(); q.pop();
	for (ll j=1;j<=k;j++) 
	if (!s.count(h*a[j])) s.insert(h*a[j]),q.push(h*a[j]);  
}

没错，真的这么短

$eg_2:P2724$联系 Contact

题意：

帮助奶牛们用一个能够分析他们在文件中记下的记录的工具来找到真相。他们在寻找长度在A到B之间（包含A和B本身）在每天的数据文件中重复得最多的比特序列 (1 <= A <= B <= 12)。他们在找那些重复得最多的比特序列。一个输入限制告诉你应输出多少频率最多的序列。

思路：
首先边读边处理前A->B长度还是非常好写的，搞一个map判一下即可。

难点：

看了几篇都说输出难，我觉得有点偏但是不难啊。

这题输出用了很多技巧：

//输出N个频率最高的序列（按照频率由高到低的次序）。
//由短到长排列频率相同的这些序列，如果长短相同，按二进制大小排列。
//如果出现的序列个数小于N，输出存在的序列。 
//对于每个存在的频率，先输出单独包含该频率的一行，
//再输出以空格分隔的这些序列。每行六个（除非剩下的少于六个

根据上面可以看出要先排序，而且频率排完内部也要排，还是按二进制。。

于是写出了神仙一样的$cmp$比较函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool cmp(star a,star b){
    if (a.t>b.t) return 1;  //比频率
    if (a.t==b.t)
    {
        int l1=a.s.size(),l2=b.s.size();
        if (l1<l2) return 1;  //比长度
        else if (l1==l2) {
            for (int i=0;i<=l1;i++) if (a.s[i]<b.s[i]) return 1;   //二进制暴力比大小
            else if (a.s[i]>b.s[i]) return 0; 
				//这里不能直接return 0，还有再判。。
        }
    }
    return 0;
}

写完之后就照着输出就行了，还有无数个小细节没注意，感觉真的没必要这么详细，就是在抠字眼了。

代码：过于毒瘤没代码。

$eg_3:P2725$邮票 Stamps

题面：给一组 N 枚邮票的面值集合（如，{1 分，3 分}）和一个上限 K —— 表示信封上能够贴 K 张邮票。计算从 1 到 M 的最大连续可贴出的邮资。

思路：
依稀记得入门DP不会被新人OIer嘲讽的尴尬。

其实你看数据范围小，也不是想$NOIP2017D1T1$毒瘤其实就可以考虑直接DP然后暴力判断了。。

设f[i]是第i枚邮票最少要几分钱，然后列出式子：

$$f[i]=min(f[i],f[i-a[j]]+1)$$

暴力DP就好了，上限能多大多大

难点：还是要面向数据范围编程的啊。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstring>
using namespace std;

int k,m,a[1000];
int f[5000000];

int main()
{
    cin>>k>>m; int ma=0; 
    memset(f,0x3f,sizeof(f)); f[0]=0;
    for (int i=1;i<=m;i++) cin>>a[i],ma=max(ma,a[i]);  ma=ma*k;  //上限
    
    for (int i=1;i<=m;i++) 
      for (int j=1;j<=ma;j++) if (j-a[i]>=0) f[j]=min(f[j],f[j-a[i]]+1);
      
    for (int i=1;i<=ma+1;i++) 
	if (f[i]>k) {
        cout<<i-1<<endl; return 0;
    }
}

$Section 3.2$

  • 写了一节不到就已经这么多行了。。还整理了1H了，太慢了！！！
  • 跳了一些沙雕至极的沙雕题，以后黄题一下都不写，浪费时间啊..
  • 除此之外的题都要讲。

$eg_1:P2727$01串 Stringsobits

题面：
他们是排列好的，而且包含所有长度为N且这个二进制数中1的位数的个数小于等于L(L<=N)的数。

你的任务是输出第i（1<=i<=长度为N的二进制数的个数）小的。

（注：题目这里表述不清，实际是，从最小的往大的数，数到第i个符合条件的，这个意思），长度为N，且1的位数的个数小于等于L的那个二进制数。

难点：
题面您第一遍读懂了吗？

看了讨论发现从0算起，1小于L的都算进去，求第I个。。
比如样例

5 3 19

那应该是
样例无误：
如下：

1 00000
2 00001
3 00010
4 00011
5 00100
6 00101
7 00110
8 00111
9 01000
10 01001
11 01010
12 01011
13 01100
14 01101
15 01110
~~15 01111 （有四个1，不符条件，pass掉）~~
16 10000
17 10001
18 10010
19 10011

然后你发现读完题你还是不会做。

思路：

暴力搜肯定是不行的，那又得考虑DP了。求出第i个符合条件的不知道，但设$f[i][j]$为长度为i，含有j个”1”的个数，求这个还是很好想的：

$$f[i][j]=f[i-1][j]+f[i-1][j-1]$$

第一项考虑i位是0，第二项考虑i为是1。先定义一个前缀和$s[i][j]$表示“含有<=j个1”的个数，之后会用的（但是想肯定要先理解后面的）。

这东西有啥用呢？到这就不会用了看上面那个例子就知道，第一次，超过L个”1”的地方，的下一位，一定会进位。（唐突逗号）

也就是说问长度为N的第K位，如果K比$s[N-1][L]$大，说明首项肯定进位了，就先输出首项的1，然后递归下去求还有N-1的长度，第$K-s[N-1][L]$项，如果不进位了就输出0继续递归。

算了还是看看代码理解吧，虽然我觉得应该是先想到进位这一套东西然后再去想DP，但是看了tag把DP搞出来结果后面反而不会了，无奈。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;

int n,l,k;
int f[33][33],s[33][33];
//f[i][j] --> L=i,have "1"=j 
//s[i][j] --> L=i,have "1"<=j
void dfs(int n,int m,int k)
{
// 	cout<<endl<<n<<" "<<m<<" "<<k<<" "<<s[n-1][m]<<endl;
    if (n<1) return;
    if (s[n-1][m]<k) cout<<1,dfs(n-1,m-1,k-s[n-1][m]);
    else cout<<0,dfs(n-1,m,k);
}

int main()
{
    cin>>n>>l>>k;
    for (int i=0;i<=n;i++) s[i][0]=f[i][0]=1;
    for (int i=1;i<=n;i++) s[0][i]=f[0][i]+s[0][i-1]; s[0][1]=0; 
    for (int i=1;i<=n;i++){
        for (int j=1;j<=i;j++) //可处理m>n情况 
        f[i][j]=f[i-1][j]+f[i-1][j-1];
      for (int j=1;j<=n;j++)
        s[i][j]=f[i][j]+s[i][j-1];
    }
    dfs(n,l,k);cout<<endl;
}

$eg_2:P2729 $饲料调配 Feed Ratios

题面：
农夫约翰从来只用调配得最好的饲料来喂他的奶牛。饲料用三种原料调配成：大麦，燕麦和小麦。他知道自己的饲料精确的配比，在市场上是买不到这样的饲料的。他只好购买其他三种混合饲料（同样都由三种麦子组成），然后将它们混合，来调配他的完美饲料。

思路：
虽然N=3但是不要放弃任何一个练习新算法的机会，打一手高斯消元。

高斯消元核心还是三步走：找系数最大的，消去当前项，回带。

哦这题好像有四个变量，但有一个是范围是好小好小的，枚举一下就行。

还是有很多精度的小细节，以后做到再重温吧。

代码：板子，没有代码。
我错了有代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

for (int k=1;k<=2;k++) //NO.系数
   {
       //first: choose max
       int maxnum=0;
       for (int i=1;i<=3;i++)
         if (fabs(xs[maxnum][k])<fabs(xs[i][k])) maxnum=i;
       if (fabs(xs[maxnum][k])<0.0000001) {  //系数=0，无解 
           cout<<"NONE"<<endl; return 0;
       }
       swap(xs[maxnum],xs[k]); //消着就只剩后面的式子有系数了。
       
       //second: dive the K
       double div=xs[k][k]; //xs[k,k]会改变，，提前记录 
       for (int i=k;i<=4;i++) xs[k][i]=xs[k][i]/div*1.0; //使k的系数为1
       for (int i=k+1;i<=3;i++){
           double div=xs[i][k];
           for (int j=k;j<=4;j++) xs[i][j]-=xs[k][j]*div; 
       }
         //第i个式子的第j元素消去相应大小
   }

   //third: sweep the K
   bool f=1;
   for (int i=3;i>=1;i--) {		
       ans[i]=(xs[i][4]+0.00000001)/xs[i][i];
       if (pd(ans[i])||ans[i]<0) f=0;
       for (int j=1;j<=3;j++) xs[j][4]-=ans[i]*xs[j][i];  //得到答案就代入 
   }
   if (!f) continue;
   for (int i=1;i<=3;i++) cout<<fixed<<setprecision(0)<<ans[i]<<" "; 
   cout<<f4<<endl; 
   return 0;

不然咋重温啊。

$eg_3:P2730$ 魔板

题面：

太长了。
就是给你个数列，支持好几个操作ABC，问你用最少的基本操作完成基本状态到目标状态的转换，输出基本操作序列。

思路：

题面本来是二维，但输入是一维，USACO良心帮了一把。

点开TAG有个康托展开，吓得我赶紧看了下，最后发现是用来做HASH的。。映射表MAP天下第一！

康托也从没用过，，又学了一个没用的东西，有空随便看看吧。

然后暴力即可，沙雕题，居然还是蓝的。

代码：无。

$Section 3.3$

  • 章节名字叫欧拉回路，但我没做一道欧拉回路题
  • 最短路好评,DP好评。

$eg_1:P1930$ 亚瑟王的宫殿

题面：
太长了。

大概是给个棋盘，上面有走日字形的骑士有走九宫格的国王，选一个集合点时所有棋子过去的步数最少，但是一个骑士若经过国王，可带一个国王走，步数仅算骑士的。

思路：
拿到题时毫无思路

后来想想问最少步数肯定要确定集合点吧，

确定集合点肯定要算出骑士到点距离吧（–>那就用类似洪水填充从集合点BFS整张图就行），

算出距离肯定要接国王吧（贪心想想，好像也可以不接），

接国王肯定不会直接跳他头上，没准是旁边一个点，还要枚举接国王的点吧。

难点：但是枚举接国王点题解有争议啊，，具体的话还是转LG自行看吧。

代码：不贴了。。

$eg_2:P2732$商店购物 Shopping Offers

题面：

就是给你不超过5件商品，商品可以一个或多个商品组合起来降价销售，例如：

一朵花的价格是 2 zorkmids （z），而一个花瓶的价格是 5z 。为了吸引更多的顾客，商店举行了促销活动。

三朵花的价格是 5z 而不是 6z， 两个花瓶和一朵花的价格是 10z 而不是 12z。 编写一个程序，计算顾客购买一定商品的花费，尽量利用优惠使花费最少。尽管有时候添加其他商品可以获得更少的花费，但是你不能这么做。

对于上面的商品信息，购买三朵花和两个花瓶的最少花费的方案是：以优惠价购买两个花瓶和一朵花（10z），以原价购买两朵花（4z）。

思路：

一看肯定是完全背包，然后就不会想了。为啥不会？因为这东西他还有捆绑销售的啊！

然后转念一想，像那种分组背包的，不都是把捆绑单独作为一个元素处理的吗。

于是就打了，但是这背包容量很恶心，不同物体有不同容量。但是物体不超过5个，于是5维数组打起。。

难点：5维数组太恶心了没想到，其他海星。

然后编号居然不是1~5，开个map搞搞。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstring>
#include <map>
using namespace std;

struct object{
    int n,p;
    int c[6];
}a[300];

int f[6][6][6][6][6],s,b,cc,kk,st,w[10];
map<int,int> m;

int main()
{
    cin>>s;
    for (int i=1;i<=s;i++) {
        cin>>a[i].n;
        for (int j=1;j<=a[i].n;j++) {
            cin>>cc>>kk;
            if (!m[cc]) m[cc]=++st;
            a[i].c[m[cc]]=kk;
        }  cin>>a[i].p;
    }
    cin>>b; 
    for (int i=s+1;i<=s+b;i++){
        cin>>cc>>kk>>a[i].p; a[i].n=1;
        if (!m[cc]) m[cc]=++st;
        w[m[cc]]=kk; a[i].c[m[cc]]=1;
        ;
    }  s+=b;
    //readin
    memset(f,0x6f,sizeof(f)); f[0][0][0][0][0]=0;
    
    for (int q=1;q<=s;q++) 
    for (int i=0;i<=w[1];i++)
     for (int j=0;j<=w[2];j++)
      for (int k=0;k<=w[3];k++)
       for (int l=0;l<=w[4];l++)
        for (int u=0;u<=w[5];u++)
    {
        if (i>=a[q].c[1]&&j>=a[q].c[2]&&k>=a[q].c[3]&&l>=a[q].c[4]&&u>=a[q].c[5]) 
          f[i][j][k][l][u]=min(f[i][j][k][l][u],
          f[i-a[q].c[1]][j-a[q].c[2]][k-a[q].c[3]][l-a[q].c[4]][u-a[q].c[5]]+a[q].p);
    }
    cout<<f[w[1]][w[2]][w[3]][w[4]][w[5]]<<endl;
}

$Section 3.4$ “破锣摇滚”乐队 Raucous Rockers

题面：

你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲，发行M(1 <= M <= 20)张CD。每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐，一首歌不能分装在两张CD中。CD数量可以用完，也可以不用完。
你决定根据以下标准进行选择：

1.歌曲必须按照创作的时间顺序在所有的CD盘上出现。(注：第i张盘的最后一首的创作时间要早于第i+1张盘的第一首)

2.选中的歌曲数目尽可能地多

思路：完全，没有，思路

觉得像背包但永远写不出式子，甚至定义不出来。

现在还是半懂不懂。。先放代码再慢慢理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;

int n,m,t,f[1000][1000];  //f[i][j]-->to no.i CD,have used j
int a[100];

int main()
{
	cin>>n>>t>>m;
	for (int i=1;i<=n;i++) cin>>a[i];
	
	for (int k=1;k<=n;k++)  //the first?
	for (int i=m;i>=1;i--)  //dao xu?
	  for (int j=t;j>=a[k];j--) 
		f[i][j]=max(f[i][j],  //f[i][j-1]?
				max(f[i][j-a[k]],f[i-1][t])+1);
	cout<<f[m][t]<<endl;
}

难点：
（半小时后）哦我看懂了。。

####一. DP设置及DP循环次序先后

首先我设$f[i][j]$为到第i个CD，且已经用了j分钟的最多音乐数。

然后就很不好理解

翻到一篇神仙题解，直接设了用$f[i]$表示用了所有CD共j分钟的最多音乐数。

然后这不就是01背包了吗？所以倒序啥的，音乐种类先搜啥的就很好理解了。但是这样写还是要注意每隔一个K就要判断一下是否超过，到头来三重循环还是要的。

还是说回这篇代码：第一重是枚举音乐种类，第二三重都是枚举背包容量，只不过这样写要分开表示。。

####二. 状态转移？

有三种情况。

  1. 不选这碟片，直接跳，类01背包.
  2. 选这碟片而且貌似容量还够，类01背包
  3. 选这碟片但是我重新开一张CD了，这不用关当前容量如何因为是新开的，只要小于最大容量均可，$f[i-1][t]$也只是存储仅$i-1$张光盘的最优答案罢了。

说的好像依然很模糊，那就模糊吧，以后有空再翻出来看看呗。。