招行信用卡中心提前批笔试

三道题感觉是Easy Medium Hard 的难度，赛后放代码

第一题按照题意模拟，0的话猜了个输出为0。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cstdlib>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std ;

int n ;

unordered_map<int,string> dict ;

void solve(int x) {
	string res = "" ;

	vector<int> ten(3 , 0) ;
	int p = 0 ;
	while (x) {
		ten[p++] = x % 10 ;
		x /= 10 ;
	}
	for (int i = 2 ; i >= 0 ; --i) {
		res += dict[ten[i]] ;
	}
	// cout << endl ;
	// cout << res << endl ;
	reverse(res.begin() , res.end()) ;
	
	string ans = "" ;
	p = 0 ;
	for (int i = 0 ; i < res.size() ; ++i) {
		if (i + 1 != res.size() && res[i] == '0')	continue ;
		p = i ;
		break ;
	}
	ans = res.substr(p) ;
	cout << ans << endl ;
}

int main() {

	dict[0] = "0000" ;
	dict[1] = "0001" ;
	dict[2] = "0010" ;
	dict[3] = "0011" ;
	dict[4] = "0100" ;
	dict[5] = "0101" ;
	dict[6] = "0110" ;
	dict[7] = "0111" ;
	dict[8] = "1000" ;
	dict[9] = "1001" ;

	cin >>  n  ;

	for (int i = 0 ; i < n ; ++i) {
		int a ;
		cin >> a ;
		solve(a) ;
	}
	return 0 ;
}

第二题先去掉-1的情况，然后贪心构造，ababa然后+剩余K-2个小写字母的顺序。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cstdlib>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std ;

int n , k ;


int main() {

	cin >> n >> k ;
	if (k > n || (k == 1 && n != 1)) {
		cout << -1 << endl ;
		return 0 ;
	}

	if (k == 1) {
		cout << "a" << endl ;
		return 0 ;
	}

	if (k == 2) {
		string res = "" ;
		for (int i = 0 ; i < n ; ++i) {
			if (i % 2 == 0) {
				res += "a" ;
			} else res += "b" ;
		}
		cout << res << endl ;
		return 0 ;
	}

	string res = "" ;
	for (int i = 0 ; i < n ; ++i) {
		if (i < (n - k + 2)) {
			if (i % 2 == 0) {
				res += "a" ;
			} else res += "b" ;
		} else {
			res += ('a' + (2 + (i - (n - k + 2)))) ; 
		}
	}

	cout << res << endl;

	return 0 ;
}

第三题首先判断1+2+...+(n-1)是否小于S，如果小于，则输出-1。

之后考虑动态规划。dp[i][j] 表示从质量为j的史莱姆分裂i次可以得到的最大得分。答案是满足dp[i][n]>=S的最小的i。
转移 dp[i][j]=max(dp[i][j] , dp[i-1][k] + k * (j-k))

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cstdlib>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std ;
typedef long long ll ;

int n , S ;

int main() {

	cin >> n >> S ;

	if ((n - 1) * n / 2 < S) {
		cout << -1 << endl ;
		return 0 ;
	} 

	vector<vector<int> > dp(n + 1 , vector<int> (n + 1 , 0)) ;

	for (int i = 1 ; i <= n ; ++i) {
		for (int j = 2 ; j <= n ; ++j) {
			if (i == 1) {
				for (int k = 1 ; k < j ; ++k) {
					dp[i][j] = max(dp[i][j] , k * (j - k)) ;
				}
			} else {
				//for (int l = 0 ; l < i ; ++l) {
					for (int k = 1 ; k < j ; ++k) {
						dp[i][j] = max(dp[i][j] , dp[i - 1][k] + k * (j - k)) ;
					}
				//}
			}
		}
		if (dp[i][n] >= S) {
			cout << i << endl ;
			return 0 ;
		}
	}


	return 0 ;
}

#招商银行信用卡中心#