华南农业大学算法分析与设计第一章题解

9715 相邻最大矩形面积

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<vector<int>> getNear(vector<int>& nums){
    vector<vector<int>> ans(nums.size());
    stack<vector<int>> s;
    for(int i =0;i<nums.size();i++){
        while (!s.empty() && nums[s.top()[0]]>nums[i]){//如果栈顶元素比当前的检索元素要大,那么就结束它
            //检查左边元素和右边元素,设置答案
            vector<int> top =  s.top();
            s.pop();
            for(int j = 0;j<top.size();j++){//结算该列表中的元素
                int idx = top[j];
                //然后ans[i][0]就是左边离他最近的那个元素,是栈的下边
                //ans[i][1]就是右边离他最近的那个元素
                int left = s.empty()?-1:s.top().back();
                ans[idx].push_back(left);
                ans[idx].push_back(i);
            }
        }
        if(!s.empty() && nums[s.top()[0]] == nums[i]){
            s.top().push_back(i);
        }else{
            vector<int> v;
            v.push_back(i);
            s.push(v);
        }
    }
    while (!s.empty()){
        vector<int> v= s.top();
        s.pop();
        int left = s.empty()?-1:s.top().back();
        for(int i = 0;i<v.size();i++){
            ans[v[i]].push_back(left);
            ans[v[i]].push_back(nums.size());
        }
    }
    return ans;
}


int main(){
    int n;cin>>n;
    vector<int> v;
    for(int i = 0;i<n;i++){
        int x;cin>>x;
        v.push_back(x);
    }
    vector<vector<int>> near= getNear(v);
    int ans = 0;
    for(int i =0;i<near.size();i++){
        //cout<<i<<":"<<v[i]<<" "<<near[i][0]<<" "<<near[i][1]<<",ans:"<<v[i]*(near[i][1]-near[i][0]-1)<<endl;
        ans = std::max(ans,v[i]*(near[i][1]-near[i][0]-1));
    }
    cout<<ans<<endl;
    return 0;
}

9716.矩形的并

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        double[][] rectangles = new double[n][4];
        for (int i = 0; i < n; i++) {
            double x1 = scanner.nextDouble(),y1 = scanner.nextDouble(),x2 = scanner.nextDouble(),y2= scanner.nextDouble();
            rectangles[i][0] = x1;
            rectangles[i][1] = y1;
            rectangles[i][2] = x2;
            rectangles[i][3] = y2;
        }
        double ans = rectangleArea(rectangles);
        System.out.println(String.format("%.2f",ans));
    }

    public static int MOD = (int)1e9+7;
    public static double rectangleArea(double[][] rectangles) {
        //1.首先搞清楚rectangle是[x1,y1,x2,y2]
        //然后咱们把矩形按照x进行排序,从小到大,先把x拿出来
        double ans = 0;
        List<Double> xes = new ArrayList<>();
        for (double[] rectangle : rectangles) {
            xes.add(rectangle[0]);
            xes.add(rectangle[2]);
        }
        Collections.sort(xes);
        for(int i = 1;i<xes.size();i++){
            //2.计算出宽度,取出端点
            double front = xes.get(i-1);//线段的起始端点
            double backend = xes.get(i);//线段的结束端点
            double len = backend-front;
            if(len == 0){
                continue;//宽度为0,没有计算价值
            }
            //然后计算所有在这个x范围的内矩形,我们先把y给它给拿进来
            List<double[]> lines = new ArrayList<>();//这个代表着在区间里面,所有的y线段
            for (double[] rectangle : rectangles) {
                //首先搞清楚rectangle是[x1,y1,x2,y2]
                //x1是左下角
                //x2是右上角
                //然后找出来所有和x有交集的
                if(rectangle[0]<= front && rectangle[2]>= backend){
                    //我们将这一段y给加入到候选区间中
                    lines.add(new double[]{rectangle[1],rectangle[3]});
                }
            }
            //然后就开始转化为了`区间合并问题了`
            if(lines.size() == 0){
                continue;
            }
            double[][] intervals = lines.toArray(new double[0][]);
            //首先按照起点进行排序
            Arrays.sort(intervals, new Comparator<double[]>() {
                @Override
                public int compare(double[] o1, double[] o2) {
                    return (int)(o1[0]-o2[0]);
                }
            });
            long total = 0;
            double[] cur = intervals[0];
            for(int j = 0;j<intervals.length;j++){
                double[] next = intervals[j];
                if(cur[1] >= next[0]){
                    cur[1] = Math.max(cur[1],next[1]);
                }else{
                    total += cur[1] - cur[0];
                    cur = next;
                }
            }
            total += cur[1] - cur[0];
            ans += total*len;
        }
        return ans;
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(double* o1,double* o2){
    if(o2[0] - o1[0] >0){
        return true;
    }
    return false;
}

double rectangleArea(vector<vector<double>>&rectangles){
    double ans=0;
    //首先对x进行排序
    vector<double> xes;
    //x1 y1 x2 y2
    for (int i = 0;i<rectangles.size();i++){
        xes.push_back(rectangles[i][0]);
        xes.push_back(rectangles[i][2]);
    }
    sort(xes.begin(),xes.end());//对x进行排序
    //然后计算出宽度
    for(int i = 1;i<xes.size();i++){
        double front = xes[i-1];
        double backend = xes[i];
        double len = backend - front;
        //然后计算这个区间上,存在的矩形的y轴的最大覆盖区间
        if(len == 0){
            continue;
        }
        vector<double*> lines;//存储y轴的线段
        //x1 y1 x2 y2
        for(int j = 0;j<rectangles.size();j++){
            if(front >= rectangles[j][0] && backend <= rectangles[j][2]){
                double* line = new double[2];
                line[0] = rectangles[j][1];
                line[1] = rectangles[j][3];
                //cout<<line[0]<<" "<<line[1]<<endl;
                lines.push_back(line);
            }
        }
        //然后对这些y线段进行排序
        if(lines.empty()){
            continue;
        }
        //转化为区间排序的问题,按照起点进行排序
        sort(lines.begin(),lines.end(), cmp);
        double total = 0;
        double* cur = lines[0];
        for(int j =0;j<lines.size();j++){
            //cout<<cur[0]<<" "<<cur[1]<<" ";
            double* next = lines[j];
            if(cur[1]>=next[0]){
                cur[1] = std::max(cur[1],next[1]);
            }else{
                total += (cur[1] - cur[0]);
                cur = next;
            }
        }
        //cout<<cur[0]<<" "<<cur[1]<<" ";
        total += (cur[1] - cur[0]);
        //cout<<len<<" "<<total<<endl;
        ans += (total*len);
        //dcout<<endl;
    }
    return ans;
}

int main() {
    int n;cin>>n;
    vector<vector<double>> rectangles;
    for (int i = 0; i < n; ++i){
        double x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        vector<double> v;
        v.push_back(x1);v.push_back(y1);v.push_back(x2);v.push_back(y2);
        rectangles.push_back(v);
    }
    double ans = rectangleArea(rectangles);
    printf("%.2lf",ans);
    return 0;
}

10345.前缀平均值

#include <iostream>
#include <vector>
#include <iomanip>
using namespace  std;

void solve_10375(vector<double>&nums){
    if(nums.size() == 0){
        return ;
    }
    int n = nums.size();
    //先求前缀和
    double* sum = new double[nums.size()+1];
    //base-case
    sum[0] = 0;
    for(int i = 1;i<n+1;i++){
        sum[i] = sum[i-1]+nums[i-1];
        cout<<fixed<<setprecision(2)<<(sum[i]/i)<<" ";
    }
}

int main() {
    ios::sync_with_stdio(false);
    int n ;cin>>n;
    vector<double> v;
    for (int i = 0; i < n; ++i){
        double num;cin>>num;
        v.push_back(num);
    }
    solve(v);
    return 0;
}

17086 字典序的全排列

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int id = 1;
int* book;
void backtrack(vector<int>&nums,vector<int>&track){
    if(nums.size() == track.size()){
        cout<<id<<" ";id++;
        for (const auto &item : track){
            cout<<item;
        }
        cout<<endl;
        return;
    }
    for(int i = 0;i<nums.size();i++){
        if(book[i] == 1){
            continue;
        }
        //做出选择
        track.push_back(nums[i]);
        book[i] = 1;
        //回溯递归
        backtrack(nums,track);
        //撤销选择
        book[i] = 0;
        track.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(false);
    int n;cin>>n;
    string s;cin>>s;
    book = new int [n];
    vector<int> nums;
    for (int i = 0; i < n; ++i){
        nums.push_back(s[i]-'0');
        book[i] = 0;
    }
    sort(nums.begin(),nums.end());
    vector<int> track;
    backtrack(nums,track);
    return 0;
}

8593 最大覆盖问题

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

void solve(vector<int>& nums){
    if(nums.size() == 1){
        cout<<1<<endl;
        return;
    }
    int ans = INT32_MIN;
    int slow = nums.size()-1,fast = nums.size()-2;
    while (fast!=-1){
        while (fast!=-1 && nums[fast]<= abs(nums[slow]) ){
            fast--;
        }
        ans = std::max(ans,slow-fast);
        slow = fast;
    }
    cout<<ans<<endl;
}

int main(){
    int n;cin>>n;
    vector<int> nums;
    for (int i = 0; i < n; ++i){
        int x;cin>>x;
        nums.push_back(x);
    }
    solve(nums);
    return 0;
}
//备注:这道题之所以不用fast回滚的原因如下
//当fast == slow-1的时候,这时候就是一个base-case,如果nums[fast]>nums[slow],这时候成立,slow下一个位置是slow-1
//当fast > slow-1的时候,如果nums[fast]>nums[slow],那么我们可以知道nums[slow-1]<abs(nums[slow])
//那么也就是在[fast,slow]上,对于任意i元素,均有nums[i]<=abs(nums[slow])
//由于了加了绝对值,我们无法保证在[fast,slow-1]上的所有元素都满足nums[i]<=abs(nums[slow-1])
//因此还需要检索abs(nums[slow-1])与前边这些元素的情况,假如abs(nums[slow-1])比刚才的abs(nums[slow])都还要大,就证明abs(nums[slow-1])比[fast,slow-2]上的所有元素都要大,就可以复用刚才检测出来的元素

11075 强盗分赃

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

void solve(int n){
    long ans = 0;
    int flag = 0;
    for(long i = 255,j=0;;i+=255,j++){
        ans = 12*(i+j)+8+53*((i+1+j)/256);
        if(ans>n){
            break;
        }
        flag = 1;
        cout<<ans<<" ";
    }
    if(flag == 0){
        cout<<"impossible";
    }
    return;
}

int main(){
    int n;cin>>n;
    solve(n);
    return 0;
}

11076 浮点数的分数表达（优先做）

我的解法比较啰嗦，但是把三种情况都给讨论好了，按照这个思路是没有错的

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <numeric>

using namespace std;
//可用快速幂技巧优化
long long myPow(long long x,int y){
    for(int i = 0;i<y;i++){
        x*=10;
    }
    return x;
}

long long GCD(long long  a,long long  b){
    return b>0?GCD(b,a%b):a;
}

int main(){
    string s;cin>>s;
    int slow = 2,fast = 2;
    //1.找到循环节
    while (fast!=s.size() && s[fast]!='('){
        fast++;
    }
    //如果数字里面没有循环节
    if(fast == s.size()){
        //这时候的话就是直接来
        fast--;
        slow = 2;
        int m = fast - slow;
        int powNor = myPow(10,m);
        long long tmp1 = 0;
        for(int left = slow ;left<=fast;left++){
            tmp1 = tmp1*10+(s[left]-'0');
        }
        long long gcd = GCD(tmp1, powNor);
        long long xUp = tmp1/gcd;
        long long xDown = powNor/gcd;
        cout<<xUp<<" "<<xDown<<endl;
        return 0;
    }
    fast--;
    if(s[fast] == '.'){
        //表示全部是循环节
        slow = fast+2;
        fast = s.size()-2;
        long tmp2 = 0;
        for(int left = slow;left<=fast;left++){
            tmp2 = tmp2*10+(s[left]-'0');
        }
        int m = fast - slow;
        long long powSec = myPow(10,m)-1;
        long long yUp = tmp2;
        long long yDown = powSec;
        long gcd = GCD(yUp,yDown);
        yUp /= gcd;
        yDown /= gcd;
        cout<< yUp<<" "<<yDown<<endl;
    }else{
        //这时候还要先把循环节前的数字给搞定
        int n = fast - slow;
        long long powNor = myPow(10,n);
        long tmp1 =0;
        for(int left = slow;left<=fast;left++){
            tmp1 = tmp1*10+(s[left]-'0');
        }
        //然后开始处理循环节部分
        slow = fast+2;
        fast = s.size()-2;
        int m = fast - slow;
        long tmp2=0;
        for(int left = slow;left <= fast;left++){
            tmp2 = tmp2*10+(s[left]-'0');
        }
        long long powSec = myPow(10,m)-1;
        long long gcd = GCD(tmp2,powSec);
        long long yUp = tmp2/gcd;
        long long yDown = powSec/gcd;
        long long ansUp = tmp1*yDown+yUp;
        long long ansDown = powNor*yDown;
        gcd = GCD(ansUp,ansDown);
        ansUp /= gcd;
        ansDown /= gcd;
        cout<<ansUp<<" "<<ansDown<<endl;
    }
    return 0;
}

17963 完美数

#include <iostream>

using namespace std;
//如果一个数的真约数之和等于这个自然数本身，则这个自然数就称为完美数。
//比如6就是一个完美数，而8却不是。
//如果2^n - 1是一个质数，那么，由公式N(n)=2^(n-1)*(2^n-1)算出的数一定是一个完美数。例如，
//当n=2时，2^2 - 1 = 3是一个质数，于是N(2)=2^(2-1)*(2^2-1)=2*3=6是一个完美数；当n=3时，2^3 - 1 = 7也是一个质数，
//N(3)=4*7=28是一个完美数；当n=5时，N(5)=496也是一个完美数。

long long myPow(long long x,long long y){
    long long ans =1;
    for(int i =0;i<y;i++){
        ans*= x;
    }
    return ans;
}

int main(){
    long long * a = new long long[8];
    a[0] = 2;a[1]=3;a[2]=5;a[3]=7;a[4]=13;a[5]=17;a[6]=19;a[7]=31;
    for(int i = 0;i<8;i++){
        long long tmp1 = myPow(2,a[i]-1);
        long long tmp2 = tmp1*2-1;
        long long ans = tmp1*tmp2;
        cout<<i+1<<" "<<ans<<endl;
    }
}