USACO Training

[USACO X.X.X系列]

4.1.1 麦香牛块【初等数论/动态规划】

以为一路做下去会挺顺，没想到这一题就卡住了= =

[Description]

给定不超过10个小于等于256的整数，一个数能被表示，当且仅当在存在一种方案使得在这一些数里取一些数（每个数可以取无限个）加起来等于这个数。若所有数能被表示，输出0；若有无限个数不能被表示，输出0；若有有限个数不能被表示，输出最大值。

[Solution]

若给定的整数里有1，则所有数能被表示。
若给定的所有数的gcd不为1，则有无限个数不能被表示。
以上输出0就可以了，那最后一种情况怎么办呢？

引理 若a,b>0且gcd(a,b)=1，对于任意的非负数a,b，a×x+b×y不能表示的最大值是a×b-a-b.

有了这个，我们就知道这些数不能表示的最大整数最多为256*255-256-255=64769，再用一个类似于满背包的DP转移一下就可以了。

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>

inline int gcd(int x,int y){ return !y?x:gcd(y,x%y); }

const int maxn=10;
const int maxx=64770;
int a[maxn],f[maxx];

int main(){
  int n,GCD=0; scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
    GCD=gcd(GCD,a[i]);
    if(a[i]==1){ printf("0"); return 0; }
  }
  if(GCD-1){ printf("0"); return 0; }
  f[0]=1;
  for(int i=0;i<n;i++)
    for(int j=a[i];j<maxx;j++)
      f[j]=f[j] | f[j-a[i]];
  for(int i=maxx-1;i;i--)
    if(!f[i]){ printf("%d",i); return 0; }
}

2.1.3 三值的排序

[Description]

排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌序的时候。 在这个任务中可能的值只有三种1,2和3。我们用交换的方法把他排成升序的。 写一个程序计算出，给定的一个1,2,3组成的数字序列，排成升序所需的最少交换次数。

[Hint]

n≤1000

[Solution]

查题解什么置换群，吓得我滚到地上。但毕竟这是第2章的题目，是有很容易的解法的。
我们将原序列a排个序记为b，对比a/b.
若某一位上a/b相等，可以不动它，直接跳过。
若某两位i,j上a[i]=b[j],a[j]=b[i]，那么通过一次交换a[i],a[j]就能达到目的。
剩下的一定是三个“循环”交换，这时交换两次就可以做到。

[Code]

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

const int maxn=1000;
int a[maxn],b[maxn],x[3][3],cnt;

int main(){
  int n; scanf("%d",&n);
  for(int i=0;i<n;i++) scanf("%d",&a[i]);
  memcpy(b,a,sizeof(b)); sort(b,b+n);
  for(int i=0;i<n;i++)
    if(a[i]!=b[i]) x[a[i]-1][b[i]-1]++,cnt++;
  int ans=min(x[0][1],x[1][0])+min(x[1][2],x[2][1])+min(x[0][2],x[2][0]);
  printf("%d",ans+(cnt-=2*ans)/3*2);
  return 0;
}

3.1.3 丑数

[Description]

给定一个质数集合，元素个数不大于100。一个数为丑数当且仅当这个数的所有质因子都在这个集合内，1不是丑数，求第k大的丑数，k<=100000.

[Solution]

已知前i-1个丑数，第i个丑数一定是某个质数乘上之前丑数的所有之中大于第i-1个丑数的最小值。因为满足单调性，开一个状态记录每个质数当前乘到了那个质数即可。

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>

const int inf=~0u>>1;
const int maxp=100;
const int maxn=1e5+1;
int p[maxp],now[maxp];
int f[maxn]={1};

int main(){
  int k,n; scanf("%d%d",&k,&n);
  for(int i=0;i<k;i++) scanf("%d",&p[i]);
  for(int i=1;i<=n;i++){
    int nxt=inf,pos;
    for(int j=0;j<k;j++){
      while(p[j]*f[now[j]]<=f[i-1]) now[j]++;
      if(nxt>p[j]*f[now[j]]) nxt=p[j]*f[now[j]],pos=j;
    }
    f[i]=nxt,now[pos]++;
  }
  printf("%d",f[n]);
  return 0;
}

3.1.5 连接

[Description]

给定一个长度不超过20000的01串，求所有长度在A~B(A≤B≤12)的子串中，出现频率为前k的子串，若出现频率相同，则先输出长度短的，若长度相同，先输出二进制下大的串。

[Solution]

转化为十进制数进行哈希。原以为这样就可以了。没想到满是陷阱。
一是所有的0开头的串都会被忽略，即0，00，000…的哈希值都是相同的；
二是并不是直接按从小大大输出，而是先按补零后的长度，再按大小输出。
解决的方法很简单，在每个串之前加上一个字符1再进行哈希就可以了，完美解决。
用字典树也可以…

3.2.2 01串

[Description]

求长度为n(n≤32)的01串中，1不超过I个的第L大的字符串。

[Solution]

普遍的题解都是DP.
然而最近做组合数学比较多…竟然也搞出来了…

3.2.4 饲料分配

[Description]

给定(x1,y1,z1),(x2,y1,z2),(x3,y3,z3),(x4,y4,z4)求正整数a,b,c,k使得a(x1,y1,z1)+b(x2,y1,z2)+c(x3,y3,z3)=k(x4,y4,z4)

[Solution]

说了答案在100以内，你直接枚举不就好了？！233

2.3.2 奶牛家谱

[Description]

给定一个长度≤20000的字符串S，给出最多200个长度不超过的单词，求可以用单词表示的最长前缀长度。

[Solution]

现在S中找到所有单词可能出现的位置，再实力进行DP。

Comment