HNUCM2020年春季ACM集训队选拔赛(3)题解
按照手机键盘输入字母的方式，计算所花费的时间 如：a,b,c都在“1”键上，输入a只需要按一次，输入c需要连续按三次。
如果连续两个字符不在同一个按键上，则可直接按，如：ad需要按两下，kz需要按6下。
如果连续两字符在同一个按键上，则两个按键之间需要等一段时间，如ac，在按了a之后，需要等一会儿才能按c。
现在假设每按一次需要花费一个时间段，等待时间需要花费两个时间段。
现在给出一串字符，需要计算出它所需要花费的时间。
一个长度不大于100的字符串，其中只有手机按键上有的小写字母。
输出输入可能包括多组数据，对于每组数据，输出按出Input所给字符串所需要的时间。
样例输入bob
www
7
7
这是一个拼音九键的图我们知道了每一个字符需要按的次数（每按一次需要1秒钟）
如果一个字符和它前一个字符所在的按键相等它就需要等待2秒
用一个数组a保存需要按的次数a[i]表示数字i需要按的次数
用一个数组b保存所在的按键的编号b[i]表示数组i所在按键的编号…
遍历一遍得到答案
#include
using namespace std;
char s[105];
int main()
{
int a[27]={0,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,1,2,3,1,2,3,4};
int b[27]={0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,8,8,8,8};
while(~scanf("%s",s+1)){
int ls=strlen(s+1),ans=a[s[1]-'a'+1];
for(int i=2;i<=ls;++i){
if(b[s[i]-'a'+1]==b[s[i-1]-'a'+1]){
ans+=2;
}
ans+=a[s[i]-'a'+1];
}
printf("%d\n",ans);
}
}
问题 B: 买房
题目描述
某程序员开始工作，年薪N万，他希望在中关村公馆买一套60平米的房子，现在价格是200万。
假设房子价格以每年百分之K增长，并且该程序员未来年薪不变，且不吃不喝，不用交税。
每年所得N万全都积攒起来，问第几年能够买下这套房子（第一年房价200万，收入N万）。
有多行，每行两个整数N（10<=N<=50）, K（1<=K<=20）。
输出针对每组数据，如果在第21年或者之前就能买下这套房子，则输出一个整数M，表示最早需要在第M年能买下，否则输出Impossible，输出需要换行。
样例输入50 10
40 10
40 8
8
Impossible
10
每一年计算出房子的价格和这个人所挣的钱进行比较
如果在21年前工资大于等于房子价格说明能购买，反之不能
#include
using namespace std;
char s[105];
int main()
{
int n,k;
while(~scanf("%d %d",&n,&k)){
int ans=0;
double ad=0.01*k,a=200,b=n;
for(int i=1;i<=21;++i,b+=n,a+=a*ad){
if(a<=b){
ans=i;
break;
}
}
if(ans){
printf("%d\n",ans);
}else{
printf("Impossible\n");
}
}
}
问题 C: 与7相关的数
题目描述
一个正整数,如果它能被7整除,或者它的十进制表示法中某个位数上的数字为7, 则称其为与7相关的数。
现求所有小于等于n(n<100)的与7无关的正整数的平方和。
案例可能有多组。对于每个测试案例输入为一行,正整数n,(n<100)。
输出对于每个测试案例输出一行，输出小于等于n的与7无关的正整数的平方和。
样例输入21
样例输出2336
思路按题目要求计算就行
#include
using namespace std;
bool ju(int x){
if(x%7==0){
return false;
}
while(x){
if(x%10==7){
return false;
}
x/=10;
}
return true;
}
int main()
{
int n;
while(~scanf("%d",&n)){
int ans=0;
for(int i=1;i<=n;++i){
if(ju(i)){
ans+=i*i;
}
}
printf("%d\n",ans);
}
}
问题 D: 采药
题目描述
辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。
为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。
医师把他带到个到处都是草药的山洞里对他说： “孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。
我会给你一段时间，在这段时间里，你可以采到一些草药。
如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。
可能有多组测试数据，对于每组数据，输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入70 3
71 100
69 1
1 2
3
思路裸的01背包问题
此处是肖鹏学长的01背包博客
#include
using namespace std;
int a,b,dp[1005];
int main()
{
int t,m;
while(~scanf("%d %d",&t,&m)){
memset(dp,0,sizeof(dp));
for(int i=1;i=a;--j){
dp[j]=max(dp[j],dp[j-a]+b);
}
}
printf("%d\n",dp[t]);
}
}
问题 E: 鸡兔共笼
题目描述
一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。
已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。
每组测试数据占1行，每行一个正整数a (a < 32768)。
输出输出包含n行，每行对应一个输入,包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开。
如果没有满足要求的答案，则输出两个0。
2
3
20
0 0
5 10
如果脚的个数是奇数说明没有答案
否则存在答案
最少的脚的个数大于等于4当然是优先算兔子，如果最后还剩下有就用鸡补上
最多的脚数的情况就是都是鸡
也就是说有三种情况
1.脚是奇数–没有答案
2.脚数是偶数但不能被四整除–答案就是(n/4+1，n/2)
3.脚数能被四整除–答案就是（n/4，n/2）
#include
using namespace std;
int main()
{
int n,m;
while(~scanf("%d",&n)){
for(int i=1;i<=n;++i){
scanf("%d",&m);
if(m&1){
printf("0 0\n");
}else if(m%4){
printf("%d %d\n",m/4+1,m/2);
}else{
printf("%d %d\n",m/4,m/2);
}
}
}
}
问题 F: 为了虫群
题目描述
小 Y 率领的人类的部队已经踏上了异虫的基地——查尔星。 作为异虫的首脑，你决定派出爆虫来迎击人类的部队。
爆虫身上长有充满酸液的囊。当它接近敌人时，会触发体内的不稳定化学物质进行反应，将自身引爆，向外泼洒强酸。自爆会摧毁爆虫，但同时也会对半径 R 之内(包括 距离为 R 的点 )的敌人造成大量伤害。
你观察到，人类有 n 名陆战队员，站成一条直线。 每个陆战队员的坐标是 xi。你有 k 个爆虫。爆虫的酸液会对陆战队员造成巨大伤害，将其瞬间消灭。 你可以把每只爆虫安排在直线上的任意位置，然后引爆，从而消灭距离该爆虫不超过 R 的所有陆战队员。
为了消灭所有 n 个陆战队员，你需要计算，爆虫的爆炸半径 R 至少要多少。
输入输入共两行。第一行是用空格隔开的两个整数 n 和 k。
第二行是用空格隔开的 n 个实数，表示每个陆战队员的坐标 xi。所有坐标按升序给出。（可能存在某个位置有多名队员）
1≤k<n≤100,000
-107≤xi≤107
输出输出共一行。爆虫的最小爆炸半径 R。保留 6 位小数。
样例输入5 2
-10.0 -6.0 10 11 15
2.500000
思路因为爆虫的半径对满足单调性
也就是说
对于爆虫的半径a<b 如果b可以那么a也可以，如果a不可以，那么b也不可以
可以二分答案不断缩小可能区间，缩小到一定精度就可以跳出了
#include
using namespace std;
const int maxn=1e5+5;
double a[maxn];
int n,k;
bool ju(double mid){//判断半径为mid可不可以满足
double len=0;
int num=1;
for(int i=2;i<=n;++i){//循环判断mid半径下最少需要的虫子数
if(len+a[i]-a[i-1]k){//需要的虫子大于k说明不满足
return false;
}
return true;
}
int main()
{
while(~scanf("%d %d",&n,&k)){
for(int i=1;i0.00000001){
double mid=(l+r)/2;
if(ju(mid*2)){
ans=mid;
r=mid;
}else{
l=mid;
}
}
printf("%lf\n",ans);
}
}
问题 G: 找宝箱
题目描述
作为一个强迫症患者，小明在走游戏里的迷宫时一定要把所有的宝箱收集齐才肯罢休。
现在给你一个 N×M 的迷宫，里面有障碍、空地和宝箱，小明在某个起始点，每一步小明可以往上、下、左、右走，当然前提是没有走出迷宫并且走到的点不是障碍。如果小明走到了某个为宝箱的点，那么这个宝箱就被他收集到了，然后此处变为空地。
现在你需要计算小明最少需要走多少步才能收集齐所有的宝箱。
输入输入共有两行。
第一行一个两个正整数 N 和 M，表示迷宫大小。
接下来 N 行，每行 M 个整数，第 i+1 行的第 j 个整数表示迷宫第 i 行第 j 列的情况， 0 表示空地，-1 表示障碍，1 表示宝箱，2 表示小明的起始点。保证 2 只有一个。
1≤N,M≤100，宝箱个数不超过5个。
输出一行一个整数，表示小明最少的步数。如果无法收集齐所有宝箱，输出-1。
样例输入3 5
1 -1 1 -1 2
0 -1 0 -1 0
0 0 0 0 0
12
思路因为宝箱的个数不多，可以用bfs处理出宝箱和起点两两之间的最短距离
再用全排列函数（next_permutation）或者dfs列出所有宝箱的访问顺序，计算步数取最小值
#include
using namespace std;
const int inf=0x3f3f3f3f;
int w[105][105],vis[105][105],n,m,cnt;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
struct node{
int i,j,step;
};
node chest[6];
int len[6][6],p[6];
void bfs(int st,int step){
memset(vis,0,sizeof(vis));
queue pq;
node now=chest[st],ne;
now.step=0,vis[now.i][now.j]=1;
pq.push(now);
while(!pq.empty()){
now=pq.front(),pq.pop();
if(w[now.i][now.j]==1||w[now.i][now.j]==2){//走到宝箱或者起点
for(int i=0;i<=cnt;++i){
if(chest[i].i==now.i&&chest[i].j==now.j){
len[st][i]=now.step;
break;
}
}
}
for(int i=0;i=1&&ne.i=1&&ne.j<=m&&vis[ne.i][ne.j]==0&&w[ne.i][ne.j]!=-1){//没有出界，没有被走过，可以走
vis[ne.i][ne.j]=1;
ne.step=now.step+1;
pq.push(ne);
}
}
}
}
int main(){
while(~scanf("%d %d",&n,&m)){
cnt=0;
memset(len,inf,sizeof(len));
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%d",&w[i][j]);
if(w[i][j]==1){
chest[++cnt].i=i;
chest[cnt].j=j;
}
if(w[i][j]==2)
chest[0].i=i,chest[0].j=j;
}
}
for(int i=0;i<=cnt;++i){//处理宝箱和起点两两间的距离
bfs(i,0);
}
for(int i=0;i<=cnt;++i)
p[i]=i;
int ans=inf;
do{
int num=0;
for(int i=1;i=inf)
ans=-1;
printf("%d\n",ans);
}
}
问题 H: gcd 区间
题目描述
给定一行 n 个正整数 a[1]…a[n]。
m 次询问，每次询问给定一个区间[L,R]，输出 a[L]…a[R]的最大公因数。
输入第一行两个整数 n，m。
第二行 n 个整数表示 a[1]…a[n]。
以下 m 行，每行 2 个整数表示询问区间的左右端点。
保证输入数据合法。
1 <= n <= 1000，1 <= m <= 1,000,000 0 < 数字大小 <= 1,000,000,000
输出共 m 行，每行表示一个询问的答案。
样例输入5 3
4 12 3 6 7
1 3
2 3
5 5
1
3
7
n的范围不大，可以先预处理出所有情况，最后直接输出就行，当然线段树和树状数组也可
#include
#define ll long long
using namespace std;
ll a[1005],ans[1005][1005];
ll gcd(ll a,ll b){
if(b==0)
return a;
return gcd(b,a%b);
}
int main(){
int n,m;
while(~scanf("%d %d",&n,&m)){
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;++i){
ans[i][i]=a[i];
for(int j=i+1;j<=n;++j){
ans[i][j]=gcd(a[j],ans[i][j-1]);
}
}
int l,r;
for(int i=1;i<=m;++i){
scanf("%d %d",&l,&r);
printf("%lld\n",ans[l][r]);
}
}
}
作者：名字在哪啊
