天天看點
傳回

鄭輕第六屆校賽 -- 部分題解

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算法及其應用
下一篇: 從根節點找到某一節點的路徑

繼續閱讀