前4题AC，最后一题用dfs超时，过了55%
1. 链表断开分组。
2. 魔法球
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
static bool cmp(int& a, int& b){
return a > b;
}
int max_num = 1000000007;
int main(){
int T = 0;
cin >> T;
while(T--){
int n = 0;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i)cin >> a[i];
sort(a.begin(), a.end(), cmp);
int ans = 0;
int temp = 0;
for(int i = 0; i < n; ++i){
ans += a[i] + temp;
ans %= max_num;
temp = ans;
}
cout << ans << endl;
}
return 0;
} 3. 小船载人，小船限制载重w，最多载两人，当载两个人时，两个人的体重之和必须为偶数，载一个人则没有限制。给定n个人的体重，求所需小船最少个数。 #include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
static bool cmp(int& a, int& b){
return a > b;
}
int findFirstIndex(vector<int>& a, int left, int target){
int right = a.size() - 1, ans = a.size();
while(left <= right){
int mid = (left + right) / 2;
if(a[mid] == target){
ans = mid;
break;
}
else if(a[mid] < target){
ans = mid;
right = mid - 1;
}
else{
left = mid + 1;
}
}
return ans;
}
int main(){
int T = 0;
cin >> T;
while(T--){
int n = 0, w = 0;
cin >> n >> w;
unordered_map<int, int> maps;
for(int i = 0; i < n; ++i){
int temp;
cin >> temp;
maps[temp]++;
}
vector<int> a;
for(auto it = maps.begin(); it != maps.end(); it++){
a.emplace_back((*it).first);
}
sort(a.begin(), a.end(), cmp);
int ans = 0;
for(int i = 0; i < a.size(); ++i){
int x = a[i];
if(maps[x] == 0)continue;
int max_y = w - x;
int begin = findFirstIndex(a, i, max_y);
maps[x]--;
for(int j = begin; j < a.size(); ++j){
int y = a[j];
if((x + y) % 2 == 1 || maps[y] == 0)continue;
maps[y]--;
break;
}
ans++;
if(maps[x] != 0)i--;
}
cout << ans << endl;
}
return 0;
} 4. 字符串长度为n，找到长为k的字典序最大子序列（可以不连续）#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int dp[1001][1001] = {-1};
int main(){
int n, k;
cin >> n >> k;
string str;
cin >> str;
if(n == k){
cout << str << endl;
}
else{
string ans = "";
for(int i = 0; i < n; ++i){
dp[i][i] = i;
}
for(int step = 1; step < n; ++step){
for(int i = 0; i < n - step; ++i){
int j = i + step;
int idx = dp[i][j - 1];
if(str[j] > str[idx]){
dp[i][j] = j;
}
else{
dp[i][j] = dp[i][j - 1];
}
}
}
int left = -1;
for(int i = 0; i < k; ++i){
int right = n - k + i;
ans.push_back(str[dp[left + 1][right]]);
left = dp[left + 1][right];
}
cout << ans << endl;
}
return 0;
} 5. n个色块，开始任意选择一个神奇色块，值为x，包含神奇色块的及周围同一数值的色块（都为x）可以一起变为另一个值y，消耗能量abs(x - y)，求将n个色块变为同一数所消耗的最小能量。 超时代码，过了55%
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int ans = 2147483647;
vector<int> a;
void dfs(int cur, int left, int right, int val){
if(cur > ans){
return;
}
if(left == 0 && right == a.size() - 1){
ans = cur;
return;
}
if(left > 0 && right < a.size() - 1 && a[left - 1] == a[right + 1]){
int new_left = left - 1;
int new_right = right + 1;
int temp = abs(val - a[new_left]);
for(int i = left - 2; i >= 0; --i){
if(a[i] == a[new_left])new_left = i;
else break;
}
for(int i = right + 2; i < a.size(); ++i){
if(a[i] == a[new_right])new_right = i;
else break;
}
dfs(cur + temp, new_left, new_right, a[new_left]);
}
else{
if(left > 0){
int new_left = left - 1;
int temp = abs(val - a[new_left]);
for(int i = left - 2; i >= 0; --i){
if(a[i] == a[new_left])new_left = i;
else break;
}
dfs(cur + temp, new_left, right, a[new_left]);
}
if(right < a.size() - 1){
int new_right = right + 1;
int temp = abs(val - a[new_right]);
for(int i = right + 2; i < a.size(); ++i){
if(a[i] == a[new_right])new_right = i;
else break;
}
dfs(cur + temp, left, new_right, a[new_right]);
}
}
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; ++i){
int k;
cin >> k;
a.emplace_back(k);
}
for(int i = 0; i < n; ++i){
int j = i;
while(j < n){
if(a[i] != a[j]){
j--;
break;
}
j++;
}
dfs(0, i, j, a[i]);
i = j;
}
cout << ans << endl;
return 0;
} 
全部评论
(1) 回帖