USACO铜组测试2

admin管理员组

文章数量:815114

USACO铜组测试2

USACO铜组测试2

T1-奶牛唱歌

试题链接

D2ege. 奶牛唱歌
时间限制：1.0s 内存限制：256.0MB
输入文件名：herd.in 输出文件名：herd.out
问题描述
一个鲜为人知的事实是，奶牛拥有自己的文字：「牛文」。牛文由 26 个字母 ‘a’ 到 ‘z’ 组成，但是当奶牛说牛文时，可能与我们所熟悉的 ‘abcdefghijklmnopqrstuvwxyz’ 不同，她会按某种特定的顺序排列字母。
为了打发时间，奶牛 Bessie 在反复哼唱牛文字母歌，而 Farmer John 好奇她唱了多少遍。
给定一个小写字母组成的字符串，为 Farmer John 听到 Bessie 唱的字母，计算 Bessie 至少唱了几遍完整的牛文字母歌，使得 Farmer John 能够听到给定的字符串。Farmer John 并不始终注意 Bessie 所唱的内容，所以他可能会漏听 Bessie 唱过的一些字母。给定的字符串仅包含他记得他所听到的字母。
输入格式
输入的第一行包含 26 个小写字母 ‘a’ 到 ‘z’ 的牛文字母表顺序。下一行包含一个小写字母组成的字符串，为 Farmer John 听到 Bessie 唱的字母。字符串的长度不小于 1 且不大于 1000。
输出格式
输出 Bessie 所唱的完整的牛文字母歌的最小次数。
输入样例
abcdefghijklmnopqrstuvwxyz
mood
None
输出样例
3
None
样例说明
在这个样例中，牛文字母表与日常的字母表的排列一致。
Bessie 至少唱了三遍牛文字母歌。有可能 Bessie 只唱了三遍牛文字母歌，而 Farmer John 听到了以下被标记为大写的字母。
abcdefghijklMnOpqrstuvwxyz
abcdefghijklmnOpqrstuvwxyz
abcDefghijklmnopqrstuvwxyz
测试点性质
测试点 2-5 中，牛文字母表与日常的字母表相同。
测试点 6-10 没有额外限制。

这一题就是一个绕人的字符串操作题。大概意思是这样：
（1）如果听到的字母在前一个字母的后边，那么应将其归类为同1遍。
（2）否则应该是另外一遍听到的，ans++；

#include <bits/stdc++.h>
using namespace std;string s;
char c;
int ans,last=-1;int main(){freopen("herd.in","r",stdin);freopen("herd.out","w",stdout);cin>>s;while(cin>>c){if(s.find(c,last+1)==-1){++ans;last=s.find(c);}else last=s.find(c,last+1);}printf("%d\n",ans+1);fclose(stdin);fclose(stdout);return 0;
}

T2-照片分组

试题链接

D5b69. 照片分组
时间限制：1.0s 内存限制：256.0MB
输入文件名：group.in 输出文件名：group.out
问题描述
Farmer John 正再一次尝试给他的 N 头奶牛拍照（2≤N≤1000）。
每头奶牛有一个范围在 1…100 之内的整数的「品种编号」。Farmer John 对他的照片有一个十分古怪的构思：他希望将所有的奶牛分为不相交的若干组（换句话说，将每头奶牛分到恰好一组中）并将这些组排成一行，使得第一组的奶牛的品种编号之和为偶数，第二组的编号之和为奇数，以此类推，奇偶交替。
Farmer John 可以分成的最大组数是多少？
输入格式
输入的第一行包含 N。下一行包含 N 个空格分隔的整数，为 N 头奶牛的品种编号。
输出格式
输出 Farmer John 的照片中的最大组数。可以证明，至少存在一种符合要求的分组方案。
输入样例
7
1 3 5 7 9 11 13
None
输出样例
3
None
样例说明
在这个样例中，以下是一种分成最大组数三组的方案。将 1 和 3 分在第一组，5、7 和 9 分在第二组，11 和 13 分在第三组。
输入样例
7
11 2 17 13 1 15 3
None
输出样例
5
None
样例说明
在这个样例中，以下是一种分成最大组数五组的方案。将 2 分在第一组，11 分在第二组，13 和 1 分在第三组，15 分在第四组，17 和 3 分在第五组。

这一题，就是一个关键词----奇偶性！
小学学的还行的人都知道：
奇+奇=偶
奇+偶=奇
偶+偶=偶
当然这里不是你吃的“鸡”与“藕”
由此不需要关心具体数值，统计就属个数即可。
最好的（即最大的）情况是什么？是奶牛们自成一组。此时（下面称偶数个数为a，奇数个数为b）a=b（偶数开头奇数结尾）或a=b+1（偶数开头偶数结尾），为了均衡，有一下操作：
（1）将两个奇数变为一个偶数。
（2）将两个偶数变为一个偶数。（相当于减少一个偶数）

#include<bits/stdc++.h>
using namespace std;int n,a,b,bin;int main(){freopen("group.in","r",stdin);freopen("group.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&bin);if(bin%2)++b;else ++a;}while(a!=b&&a!=b+1){if(a>b+1){--a;}else{b-=2;++a;}}printf("%d\n",a+b);fclose(stdin);fclose(stdout); return 0;
}

T3-牛舍安排

试题链接

Dg9s3. 牛舍安排
时间限制：1.0s 内存限制：256.0MB
输入文件名：stalling.in 输出文件名：stalling.out
问题描述
Farmer John 有 N 头奶牛（1≤N≤20），高度为 a1…aN。他的牛栏有 N 个牛棚，高度限制分别为 b1…bN（例如，如果 b5=17，那么一头高度不超过 17 的奶牛可以住在牛棚 5 里）。Farmer John 有多少种不同的方式安排他的奶牛，使得每头奶牛均住在不同的牛棚里，并且使得每个牛棚的高度限制均得到满足？
输入格式
输入的第一行包含 N。
第二行包含 N 个空格分隔的整数 a1,a2,…,aN。
第三行包含 N 个空格分隔的整数 b1,b2,…,bN。所有的高度和高度限制均在范围 内。
输出格式
输出 Farmer John 可以将每头奶牛安排到不同的牛棚里，使得每个牛棚的高度限制均得到满足的方法数。注意输出的数量可能需要使用 64 位整数型，例如 C++ 中的 long long。
输入样例
4
1 2 3 4
2 4 3 4
None
输出样例
8
None
样例说明
在这个例子中，我们不能将第三头奶牛安排到第一个牛棚里，因为 3=a3>b1=2。类似地，我们不能将第四头奶牛安排到第一或第三个牛棚里。一种符合高度限制的安排方式为将奶牛 1 安排到牛棚 1，奶牛 2 安排到牛棚 2，奶牛 3 安排到牛棚 3，奶牛 4 安排到牛棚 4。
测试点性质
测试点 1-5 满足 N≤8。
测试点 6-12 没有额外限制。

这一题一开始的想法是----数据量小，搜起来！
实际上最大复杂度：20! ----这是我的电脑一个月也运行不了的……
复杂度：O(nⁿ)
得分：12个点过5个

#include <bits/stdc++.h>
using namespace std;int n,b[30],a[30],vh[30],ans;void readp(){scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&a[i]);for(int i=1;i<=n;++i)scanf("%d",&b[i]);
}void dfs(int step){if(step>n){++ans;return;}for(int i=1;i<=n;++i){if(vh[i])continue;//之前被选过if(a[step]>b[i])continue;//容纳不下vh[i]=1;dfs(step+1);vh[i]=0;}
}int main(){freopen("stalling.in","r",stdin);freopen("stalling.out","w",stdout);readp();dfs(1);printf("%d\n",ans);fclose(stdin);fclose(stdout);return 0;
}

但是，这题是一个很经典的数学题----排列组合（乘法原理）
先sort一下（a或b都可以，不过这决定了你看问题的方向，我是sort b数组）b[1]可以容纳一些牛，b[2]也是，当务之急是搞清楚他们的重复段。由于sort过了，结果很容易给出，b[1]包含的b[2]必定也包含！b[3]就包含了b[1]b[2]
所以重复段是b[i-1]（以下称b[i]所能容纳牛的个数为c[i]）
那么，每个c[1]里的1所衍生出的可能就是c[2]-1，以此类推（因为第1个有n种选择，第2个有（n-1）种选择，第3个有（n-2）种选择（因为有几个已经被前面的选走了））

#include <bits/stdc++.h>
using namespace std;long long n,b[30],a[30],c[30];void readp(){scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&a[i]);for(int i=1;i<=n;++i)scanf("%d",&b[i]);sort(b+1,b+1+n);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(a[j]<=b[i])++c[i];
}long long f(){long long ans=c[1];for(int i=2;i<=n;++i)ans*=c[i]-i+1;//等于ans*=c[i]-(i-1);当然这里也可以乘完再减return ans;
}int main(){freopen("stalling.in","r",stdin);freopen("stalling.out","w",stdout);readp();	printf("%lld\n",f());fclose(stdin);fclose(stdout);return 0;
}

本文标签： USACO铜组测试2