三道题感觉是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))
转移 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 ;
}
全部评论
(28) 回帖