100，100，100，0，75分能不能面试凭运气吧。
1. Append least characters to a given string so that the string becomes a palindrome. Print the final palindrome.
#include <iostream>
using namespace std;
string solve(string s)
{
int i = 0, j = s.size() - 1;
for(; i < j; i++) {
if(s[i] == s[j]) {
j--;
} else {
j = s.size() - 1;
}
}
int m = min(i, j);
int n = max(i, j);
for(; m >= 0; m--, n++) {
if(n > s.size() - 1) {
s.push_back(s[m]);
}
}
return s;
}
int main() {
string s; cin >> s;
std::cout << solve(s);
return 0;
}
2. 把一些物品分给a或者b，也可以弃置，要求最后a和b拿到的物品的权重和相同，且弃置物品的权重和最小，输出最小弃置物品的权重和。 数据规模比较小，最多15个物品，直接brute-force。
#include <iostream>
#include <vector>
using namespace std;
const int inf = 999999;
// kth item
void solve(vector<int> items, int a, int b, int k, int discard, int* minimum)
{
if(k == -1) {
if(a == b) {
if(discard < *minimum) *minimum = discard;
}
return;
}
if(discard > *minimum) return;
solve(items, a + items[k], b, k - 1, discard, minimum);
solve(items, a, b + items[k], k - 1, discard, minimum);
solve(items, a, b, k - 1, discard + items[k], minimum);
}
int solve(vector<int> items)
{
int minimum = inf;
solve(items, 0, 0, items.size() - 1, 0, &minimum);
return minimum;
}
int main() {
int T; cin >> T;
while(T--) {
int n; cin >> n;
vector<int> items(n);
for(int i = 0; i < n; ++i) {
cin >> items[i];
}
cout << solve(items) << endl;
}
return 0;
}
3. 一群人排队买票，可以一个人单独买，也可以前后两个人一起买，单独买的时间总和和一起买的时间不一样，售票处8点开门，求最早关门时间，如08:00:40 am关门。
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
int a[2010], b[2010], cost[2010];
string sec2str(int sec)
{
stringstream ss;
bool is_am = true;
int hour = sec / 3600;
sec = sec - hour * 3600;
int minute = sec / 60;
sec = sec - minute * 60;
if(hour + 8 > 12) {
hour = hour + 8 - 12;
is_am = false;
} else {
// if(hour + 8 == 12) is_am = false;
hour += 8;
}
if(hour < 10) {
ss << "0";
}
ss << hour << ":";
if(minute < 10) {
ss << "0";
}
ss << minute << ":";
if(sec < 10) {
ss << "0";
}
ss << sec << " ";
if(is_am) {
ss << "am";
} else {
ss << "pm";
}
return ss.str();
}
string solve(int* a, int* b, int n)
{
if(n == 0) return sec2str(0);
if(n == 1) return sec2str(a[0]);
if(n == 2) return sec2str(min(a[0] + a[1], b[0]));
cost[0] = 0;
cost[1] = a[0];
for(int i = 2; i < n + 1; ++i) {
cost[i] = min(cost[i-1] + a[i-1], cost[i-2] + b[i-2]);
}
return sec2str(cost[n]);
}
int main() {
int T; cin >> T;
while(T--) {
int n; cin >> n;
for(int i = 0; i < n; ++i) {
cin >> a[i];
}
for(int i = 0; i < n - 1; ++i) {
cin >> b[i];
}
cout << solve(a, b, n) << endl;
}
return 0;
}
4. Directed Graph，大概就是要在里面找到cycle，不熟悉这个类型的，时间也不够了，放弃了。
全部评论
(2) 回帖