此贴仅仅纪念自己笔试情况留念！见谅，因为做的不好！希望亲爱的同学们不要喷，更希望你们可以留言回复你们的解法情况！非常感谢！
第一题：给一个字符串，可以在右边无限添加字符，问能构成的最短的回文字符串是什么？输出即可！
思路：找出最右边的能构成回文的最长长度，然后再在右边添加左边一部分（反向）的长度个数量的回文字符即可，
代码：
#include<bits/stdc++.h>
using namespace std;
bool ispalindrom(string& s, int l, int r) {
while(l < r) {
if(s[l++] != s[r--]) return false;
}
return true;
}
int main(void)
{
#ifndef ONLINE_JUDGE
ifstream cin("in.txt");
#endif
//faster_cin_cout;
int n;
string s;
while(cin >> s) {
if(s.size() == 0) cout << "" <<endl;
else {
int rightLen = 0;
for(int i = 0; i < s.size(); i++) {
if(ispalindrom(s, i, s.size()-1)) {
rightLen = s.size() - i;
break;
}
}
n = s.size();
int k = n - rightLen - 1;
while(k >= 0) s.push_back(s[k--]);
cout << s << endl;
}
}
return 0;
}
第二题：给n个数，如果按照平分的话，问最后最少删除的数的总量是多少？
思路：因为数据不大（n <= 15），直接最多秒枚举2^15个状态，本质就是01背包问题，
然后看 i 和 2*i是否分别都存在，其中2*i <= sum, sum 为n个元素的和！
代码：
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
#ifndef ONLINE_JUDGE
ifstream cin("in.txt");
#endif
int t;
int n;
cin >> t;
while(t--) {
cin >> n;
vector<int> a(n+1, 0);
int sum = 0;
for(int i = 1; i <= n; ++i) cin >> a[i], sum += a[i];
vector<bool> f(sum+1, 0);
int size = (1<<n);
for(int stat = 0; stat < size; ++stat) {
int s = 0;
int t = 1;
for(int i = 1; i <= n; ++i, t<<=1) {
if(stat&t) s += a[i];
}
f[s] = true;
}
int ans = 0;
for(int i = sum/2; i >= 1; --i) {
if(f[i] && f[i<<1]) {
ans = i;
break;
}
}
cout << sum - 2*ans << endl;
}
return 0;
}
第三题：给出个顾客买东西需要花费的时间 a[i]，并且每一个顾客可以和前面一个顾客一起买东西的时间b[i]，
问最少需要多少时间，这n个顾客可以全部买完，
思路：每一个顾客的购买方式有两种方法（单独买，或者跟前面一个人一起买），除了第一个顾客，
可以进行两种状态转移！
代码：
#include<bits/stdc++.h>
using namespace std;
void PRINTF(int times) {
int hour = times / 3600;
times %= 3600;
int minute = times / 60;
times %= 60;
int second = times;
if(hour < 4) {
printf("%02d:%02d:%02d am\n", 8+hour, minute, second);
} else {
printf("%02d:%02d:%02d pm\n", 8+hour, minute, second);
}
}
int main(void)
{
#ifndef ONLINE_JUDGE
ifstream cin("in.txt");
#endif
//faster_cin_cout;
int t;
int n;
cin >> t;
while(t--) {
cin >> n;
vector<int> a(n+1, 0), b(n+1, 0);
for(int i = 1; i <= n; ++i) cin >> a[i];
if(n == 1) {
PRINTF(a[1]);
continue;
}
for(int i = 2; i <= n; ++i) cin >> b[i];
vector<int> f(n+1, 0x3f3fffff), pre(n+1, 0);
f[0] = 0;
for(int i = 1; i <= n; ++i) f[i] += f[i-1] + a[i];
for(int i = 2; i <= n; ++i) {
f[i] = min(f[i], min(f[i-1] + a[i], f[i-2] + b[i]));
}
PRINTF(f[n]);
}
return 0;
}
第四题：给出n个人，以及他们之间的m对关系，x y 表示x 认可y，请问他们相互认可的总数有多少对？
思路：暂时只能暴力搜索！希望大佬可以留下你们的优美解法
代码：
#include<bits/stdc++.h>
using namespace std;
int n, m;
void dfs(vector<vector<int>>& tree, vector<vector<char>>& cnt, int u, int fa) {
for(int v : tree[u]) {
cnt[fa][v]++;
cnt[u][v]++;
dfs(tree, cnt, v, fa);
}
}
int main(void)
{
#ifndef ONLINE_JUDGE
ifstream cin("in.txt");
#endif
//faster_cin_cout;
int u, v;
while(cin >> n >> m) {
vector<vector<int>> tree(n+1, vector<int>());
vector<vector<char>> cnt(n+1, vector<char>(n+1, 0));
for(int i = 1; i <= m; ++i) {
cin >> u >> v;
tree[u].push_back(v);
}
for(int i = 1; i <= n; ++i) {
dfs(tree, cnt, i, i);
}
int ans = 0;
for(int i = 1; i <= n; ++i) {
for(int j = i+1; j <= n; ++j) {
if(cnt[i][j] && cnt[j][i]) ++ans;
}
}
cout << ans << endl;
}
return 0;
}
全部评论
(3) 回帖