跪很惨,有人吐槽吗!
- 添加评论
跪很惨,有人吐槽吗!
第一题AC的代码
#include <iostream>
#include <vector>
using namespace std;
#define MAX_COUNT 100001
int nums[MAX_COUNT];
int sums[MAX_COUNT];
int cal_sum(int i, int j){
// included i, j
return sums[j] - sums[i] + nums[i];
}
int binary_search(vector<int> &nums, int target){
// sorted assced
// find last idx where > target
if(nums.size() == 0) return -1;
int l = 0, r = nums.size() - 1;
while(l + 1 < r){
int mid = (l + r) / 2;
if(nums[mid] > target){
l = mid;
}else{
r = mid - 1;
}
}
if(l+1 >= 0 and l + 1 < nums.size() and nums[l+1] > target){
return l + 1;
}
if(l >=0 and l < nums.size() and nums[l] > target){
return l;
}
return -1;
}
int main(){
int t;
cin >> t;
int pre_sum = 0;
for(int i = 0; i < t; i++){
cin >> nums[i];
pre_sum += nums[i];
}
if(pre_sum < 0){
for(int i = 0; i < t; i++){
nums[i] = -1 * nums[i];
}
}
sums[0] = nums[0];
for(int i = 1; i < t; i++){
sums[i] = nums[i] + sums[i-1];
}
int res = 0;
int all_sum = cal_sum(0, t-1);
int avg_sum = all_sum / 3;
int left_num = all_sum % 3;
vector<int> left_avg_idxs;
vector<int> left_one_idxs;
vector<int> right_avg_idxs;
vector<int> right_one_idxs;
for(int i=1; i < t; i++){
int s1 = cal_sum(0, i-1);
if(s1 == avg_sum){
left_avg_idxs.push_back(i);
}else if(s1 == avg_sum + 1){
left_one_idxs.push_back(i);
}
}
for(int i=t-1; i > 0; i--){
int s1 = cal_sum(i, t-1);
if(s1 == avg_sum){
right_avg_idxs.push_back(i);
}else if(s1 == avg_sum + 1){
right_one_idxs.push_back(i);
}
}
int same_avg_count = 0;
for(int i = 0; i < left_avg_idxs.size(); i++){
int idx = binary_search(right_avg_idxs, left_avg_idxs[i]);
if(idx >= 0){
same_avg_count += (idx + 1);
}
}
int diff_avg_count = 0;
for(int i = 0; i < left_one_idxs.size(); i++){
// binary search find last position left_one_idxs[i] < right...
int idx = binary_search(right_avg_idxs, left_one_idxs[i]);
if(idx >= 0){
diff_avg_count += (idx + 1);
}
}
for(int i = 0; i < left_avg_idxs.size(); i++){
int idx = binary_search(right_one_idxs, left_avg_idxs[i]);
if(idx >= 0){
diff_avg_count += (idx + 1);
}
}
int one_one_count = 0;
for(int i = 0; i < left_one_idxs.size(); i++){
int idx = binary_search(right_one_idxs, left_one_idxs[i]);
if(idx >= 0){
one_one_count += (idx + 1);
}
}
if(left_num == 0){
res += same_avg_count;
}else if(left_num == 1){
res += same_avg_count;
res += diff_avg_count;
}else{
res += diff_avg_count;
res += one_one_count;
}
cout << res << endl;
}
第一题有ac 代码吗?
string s, t;
int n;
int res;
void work(int p, int c) {
if(p >= n) {
res = min(res, c);
return;
}
if(s[p] == t[p]) work(p + 1, c);
else {
for (int j = p + 1; j < n; j++) {
if(s[j] == t[p]) {
swap(s[p], s[j]);
work(p + 1, c + 1);
swap(s[p], s[j]);
}
}
}
}
void solve() {
cin >> s >> t;
n = s.size();
res = s.size();
work(0, 0);
cout << res << endl;
}
有人贴一下第二题通过的代码么
逻辑好好。。厉害