天天看点
返回

郑轻第六届校赛 -- 部分题解

1427: 数字转换

Time Limit: 1 Sec   Memory Limit: 128 MB

Submit: 379   Solved: 93

Submit Status Web Board

Description

老师交给小明一个任务，有两个数字x和y（x<y），通过以下两种操作：一、将x乘以2；二、将x的值加上1。小明希望能通过尽可能少的操作来完成这个任务，但是不知道怎么做，现在请大家来帮帮他的忙吧。

Input

两个整数x，y（0<=x<y<=10^6)。

Output

一个整数n，表示最少经过多少次操作，x可以变成y。

Sample Input

2 5 10 80

Sample Output

2 3

HINT

Source

郑轻第六届校赛

闲来无事刷刷别人家的校赛题，感觉还挺水的，我都水了6个题，可能今天状态还好吧，，不过今天还有个字典树是卡住了，，下次再看吧，，唉。。。（一刷就上瘾了，都没去看大物了，，明天好好看书复习

郑轻第六届校赛 -- 部分题解

）

AC代码：

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

int main()
{
	int x, y;
	while(scanf("%d %d", &x, &y) != EOF)
	{
		int cnt = 0;
		if(x == 0) { x = 1; cnt++; }
		while(x != y)
		{
			if(y/2 >= x)
			{
				cnt++;
				if(y&1) cnt++;
				y = y / 2;
			}
			else
			{
				y--;
				cnt++;
			}
		} 
		printf("%d\n", cnt);
	}
	return 0;
}

1428: 神秘密码

Time Limit: 1 Sec   Memory Limit: 128 MB

Submit: 256   Solved: 147

Submit Status Web Board

Description

小Q是一名标准的IT宅男，同时也是一名软贱攻城狮，主攻加解密算法。由于他实在是太喜欢加密解密神马的、以至于这个晚上、他在做梦的时候还在想着加解密的事情囧~。

    梦中，他不慎进入了一个密码的世界，这个小世界中杂乱无序的漂浮着一些整数。他稀里糊涂的知道、闯出这个小世界的关键是找到所谓的“密码钥匙”，钥匙是一个字符串，由天上这些整数构成。同时，他也很不科学的知道这些整数的正确的顺序。也知道每个字符串中的每个字符就是对应整数的ASCII码字符。而问题的关键是，他不记得整数与字符之间的ASCII映射。

    “这怎么办，难道我就困在这个这里出不去了么T_T？我是很喜欢解密，但是。。

    人家还木有女盆友、

    人家还没有挣到Money、

    人家还没有买车、

    人家还没有买房、

    人家还没有。。。

    人家。。哇啊儿。。。。”好吧，这厮。。哭了。。。

    原谅这位整天只知道钻研技术、而不经世事的童鞋吧。那你来帮他一下肿么样？

Input

输入有T（1<=T<=100）组。

每组一个整数n(1<=n<=1000)，而后有n个正整数。

保证输入合法。

Output

对于每组，请输出密码钥匙，每组占一行。

Sample Input

1 27 65 67 77 32 105 115 32 104 101 97 108 116 104 121 44 32 106 117 115 116 32 100 111 32 105 116 33

Sample Output

ACM is healthy, just do it!

HINT

Source

郑轻第六届校赛

AC代码：

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

int a[1005];

int main()
{
	int T, n;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);	
		for(int i=0; i<n; i++)
		{
			scanf("%d", &a[i]);
		}
		for(int i=0; i<n; i++)
			printf("%c", a[i]);
		printf("\n");
	}
	return 0;
}

1430: 多少个0

Time Limit: 1 Sec   Memory Limit: 128 MB

Submit: 213   Solved: 56

Submit Status Web Board

Description

一个n*n的方格，每个格子中间有一个数字是2或者5，现在从方格的左上角走到右下角，每次只能选择向下或者向右移动一格两种移动方式，让所有经过的格子中的数字相乘，求使最后的结果中末尾处0的数字最少。

Input

第一行是一个正整数n(0<n<100)。

接下来n行是一个n*n的矩阵。

Output

一个正整数m，表示最后的结果末尾处最少有m个0。

Sample Input

4 2 5 2 5 5 2 5 2 2 5 5 5 2 2 2 2

Sample Output

1

HINT

Source

郑轻第六届校赛

思路：DP，去找2和5在一条路径（左上到右下）上数目的最大值

AC代码：

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

int n;
int a[105][105];
int dp2[105][105];
int dp5[105][105];

int main()
{
	while(scanf("%d", &n) != EOF)
	{
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				scanf("%d", &a[i][j]);
		memset(dp2, 0, sizeof(dp2));
		memset(dp5, 0, sizeof(dp5));
		if(a[1][1] == 2) dp2[1][1] = 1;
		else dp5[1][1] = 1;
		for(int i=2; i<=n; i++)
		{
			for(int j=1; j<=i; j++)
			{
				dp5[i][j] = max(dp5[i-1][j], dp5[i][j-1]);
				dp2[i][j] = max(dp2[i-1][j], dp2[i][j-1]);
				if(a[i][j] == 2) dp2[i][j]++;
				else dp5[i][j]++;
				dp5[j][i] = max(dp5[j][i-1], dp5[j-1][i]);
				dp2[j][i] = max(dp2[j][i-1], dp2[j-1][i]);
				if(a[j][i] == 2) dp2[j][i]++;
				else dp5[j][i]++;
			}
		} 
		int ma = max(dp2[n][n], dp5[n][n]);
		//printf("%d %d\n", dp2[n][n], dp5[n][n]);
		printf("%d\n", 2 * n - 1 - ma);
	}
	return 0;
}

1432: 背包again

Time Limit: 1 Sec   Memory Limit: 128 MB

Submit: 193   Solved: 53

Submit Status Web Board

Description

Gy最近学习了01背包问题，无聊的他又想到了一个新的问题，给定n个物品的价值，和01背包一样，每个物品只能选1次或0次，求最小不能被得到的价值。

Input

第一行一个正整数T(T <= 100)，表示有T组数据。

每组数据输入格式如下：

第一行为一个正整数N(N<=100)，表示物品个数。

第二行N个正整数，表示每个物品的价值vi(1<=vi<=1000000)

Output

共输出T行，即每组数据相应答案。

Sample Input

2 3 2 4 8 4 1 2 4 8

Sample Output

1 16

HINT

Source

郑轻第六届校赛

AC代码：

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

const int N = 110;
int a[N];

int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int n, m;
		scanf("%d", &n);
		for(int i=0; i<n; i++) scanf("%d", &a[i]);
		sort(a, a+n);
		m = 0;		 //m代表从0到m都能被得到 （DP思想） 
		for(int i=0; i<n; i++)
		{
			if(a[i] - m > 1)	//如果当前的数比m还大超过1的话，m+1就是最小不能被得到的，可以用反证证明 
			break;
			m = m + a[i];
		}
		printf("%d\n", m + 1);	//因为0到m都能被得到，所以m+1不能被得到 
	}
	return 0;
}

1433: What are you doing?

Time Limit: 1 Sec   Memory Limit: 128 MB

Submit: 221   Solved: 103

Submit Status Web Board

Description

“Hey my friends！What are you doing？”

    小伙伴们都在期待了N多年的大学中度过一段时间了，不知道大家都在忙什么呢？有咩有找到自己奋斗的目标？

    据说有个叫LOL的帮派横空出世了，影响了无数大学的宅同胞。这里面有两个好斗的角色，一个叫PanSen（简称PS），一个叫JanSheng（简称JS）。这两个家伙以好斗闻名、外人称为“双雄”。不过他俩谁都不服对方，只要一见面、就必然会很“亲热”地招呼对方。（当然、用他们自己的话说是在传递爱与友谊。不过路人怎么总会觉得有点残忍类。。）

    就在刚刚，这俩家伙又见面了。

    “秃，那厮，洒家终于练就了无上神功。每个第 x 次攻击可释放一次大招，让这一次的攻击造成 c 倍伤害给你。你就认命吧！”PS道。

    “呦~，我当时谁呢，在下不才、也刚练成了一点点小本事。每攻击 y 次后可以触发一个神状态，从下一次攻击开始、连续 z 次的攻击都可以造成双倍伤害，z次攻击过去之后、再重新开始为下一次神状态充电。让我好好‘招待你吧’！”JS回道。

    “公猪母猪加油、大猪小猪加油~”路人甲喊着。

    “闭嘴！”，“住口！”双雄扭头、同时发话。

    “有奸情，果然、感情是打出来的，古人诚不欺我。。”，路人乙小声嘀咕。

    双雄满脑黑线、殴斗继续。。。。    

    好了，这个战斗发生在刚刚，那么告诉你一些信息，你可以判断出最后谁胜出了么？

    已知：

    1、PS每次攻击可以让JS掉 a 点血，JS每次攻击可以让PS掉 b 点血；

    2、PS有血量HP_p，JS有血量HP_j，血量不大于0即代表失败，战斗结束；

    3、按照不成文规定，俩家伙是轮流攻击对方，JS先发动攻击。

Input

输入有T组。

每组按顺序读入多个整数：

HP_p、HP_j（0<HP_p、HP_j<=1000），表示PanSen和JanSheng的生命值；

a、b、c、x、y、z（0<a、b、c、x、y、z<=1000），意义如上。

输入保证合法。

Output

对于每组，输出获胜人的名字的简称、单独占一行。

Sample Input

2 10 10 1 1 2 9 9 2 10 10 1 1 2 9 7 2

Sample Output

PS JS

HINT

适度LOL可练就反应迅速等无上神功，但过度LOL则有损身心健康，适度就好。

望各位小伙伴找到自己奋斗的目标、并早日成功。

Source

郑轻第六届校赛

AC代码：

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

int main()
{
	int T;
	int PS, JS, a, b, c, x, y, z;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d %d %d %d %d %d %d %d", &PS, &JS, &a, &b, &c, &x, &y, &z);
		int cur = 1;
		while(1)
		{
			if(PS <= 0 || JS <= 0) break;
			if(cur % x == 0) JS -= c;
			else JS -= a;
			if((cur-1) % ( y + z ) <= y) PS -= b;
			else PS -= 2*b;
			cur++;
		}
		if(PS <= 0) printf("JS\n");
		else printf("PS\n");
	}
	return 0;
}

1435: A+B

Time Limit: 1 Sec   Memory Limit: 128 MB

Submit: 159   Solved: 114

Submit Status Web Board

Description

喜闻乐见A+B。

读入两个用英文表示的A和B，计算它们的和并输出。

Input

第一行输入一个字符串，表示数字A；第二行输入一个字符串表示数字B。A和B均为正整数。

Output

输出一个正整数n，表示A+B的和(A+B<100)。

Sample Input

one five four three four two six

Sample Output

1960

HINT

从0到9的对应的英文单词依次为：zero, one , two , three , four , five , six , seven , eight , nine 。

Source

郑轻第六届校赛

AC代码：

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

int fun(char a[])
{
	int len = strlen(a), ans = 0;
	for(int i=0; i<len; i++)
	{
		if(a[i] == 'z'  && a[i+1] == 'e') { ans = ans * 10 + 0; i += 4; }
		else if(a[i] == 'o'  && a[i+1] == 'n') { ans = ans * 10 + 1; i += 3; }
		else if(a[i] == 't'  && a[i+1] == 'w') { ans = ans * 10 + 2; i += 3; }
		else if(a[i] == 't'  && a[i+1] == 'h') { ans = ans * 10 + 3; i += 5; }
		else if(a[i] == 'f'  && a[i+1] == 'o') { ans = ans * 10 + 4; i += 4; }
		else if(a[i] == 'f'  && a[i+1] == 'i') { ans = ans * 10 + 5; i += 4; }
		else if(a[i] == 's'  && a[i+1] == 'i') { ans = ans * 10 + 6; i += 3; }
		else if(a[i] == 's'  && a[i+1] == 'e') { ans = ans * 10 + 7; i += 5; }
		else if(a[i] == 'e'  && a[i+1] == 'i') { ans = ans * 10 + 8; i += 5; }
		else if(a[i] == 'n'  && a[i+1] == 'i') { ans = ans * 10 + 9; i += 4; }
	}
	return ans;
}

int main()
{
	char str1[205], str2[205];
	while(gets(str1) != NULL)
	{
		gets(str2);
		printf("%d\n", fun(str1) + fun(str2));
	}
	return 0;
}
各种训练、校省赛 ACM 校赛 zzuli algorithm dp
上一篇: Floyd-Warshall算法及其应用
下一篇: 从根节点找到某一节点的路径

继续阅读