实验目的

实现并实验掌握PSO算法，用c++、java、c编程语言来实现。

实验内容

通过c++编程实现对一下两个函数的全局最小值的具体数值以及N维空间中的位置。
其中本次实验N = 2；
他们分别是：
func1；
func2；

实验过程

在描述实验过程之前需要说明一个问题即：
在最优化问题中输入变量X是一个N维向量，最终优化的结果也是一个位置即N维变量。
实验步骤：
1、整理并声明变量
首先整理我们需要的变量：
粒子速度、位置的最大最小值；一个粒子群的群规模大小p_size；一个存储粒子群位置的变量；一个存储粒子群速度的变量；
一个保存粒子群个体历史最优位置的变量；一个保存粒子群全局最优位置的变量；
接着整理我们需要使用到的参数：
速度衰减常数；速度改变使用到的两个参数div1，div2；加速度的个体和社会权重self_weight，social_weight;

2、初始化变量
使用C++随机数生成引擎std::random_engine，生成满足范围要求的随机数字;

3、进行适应度评估并更新速度和位置
此次实验仅评估函数的数值，故函数适应度即为自己当前位置值与最优位置（使得函数值最小）的距离。
简单点来说即现在自己的函数值和SOCIAL_BEST以及SELF_BEST的大小关系。此处还应该更新每个粒子的
个体最优位置和粒子群的社区最优位置。

4、迭代循环
如果当前epoch(it_times)是否达到规定次数(it_max)，如果达到退出循环并且输出社区最优位置和该位置对应的函数值。

5、实现代码：

#include <iostream>
#include <vector>
#include <random>

using std::cin;
using std::cout;
using std::vector;

constexpr double vmin = -5;
constexpr double vmax = 5;
constexpr double Area_l = -50;
constexpr double Area_r = 50;
constexpr int it_max = 100;
constexpr double self_scale = 1.3;
constexpr double social_scale = 1.3;
//收敛常数
constexpr double alpha = 0.729;
constexpr double dv1 = 0.5;
constexpr double dv2 = 0.5;

int demension = 2;
int p_size = 30;
int it_times = 0;
vector<double>social_best_position(demension);
vector<vector<double>>per_best_position(p_size);

//输入一个X向量，返回一个实数值
double func(vector<double>&X)
{
    //X向量是一个输入向量表示一个点的在各维度的位置
    double sum = 1;
    for(auto xi:X)sum += xi * xi / 4000;
    double tem = 1;
    //此处注意公式里的i从1开始，我们是0基的
    for(int i = 0;i < X.size(); i ++)tem *= cos(X[i] / sqrt(i + 1));
    sum -= tem;

    return sum;
}

double func2(vector<double>&X)
{
    double sum = 20;
    for(int i = 0;i < X.size(); i ++)
    {
        sum += X[i]*X[i] - 10*cos(M_PI*2*X[i]);
    }
    return sum;
}


void iterate(vector<vector<double>>&p_x, vector<vector<double>>&p_v)
{
    //特殊初始化social_best

    for(int i = 0; i < p_size; i ++)
    {
        if (func(p_x[i]) < func(social_best_position))social_best_position = p_x[i];
        if (func(p_x[i]) < func(per_best_position[i]))per_best_position[i] = p_x[i];
    }

    std::random_device rd;
    std::default_random_engine engine(rd());
    std::uniform_real_distribution<>weight1_rand(0,self_scale);
    std::uniform_real_distribution<>weight2_rand(0,social_scale);

    for(int i = 0;i < p_size - 1; i ++)
    {
        for(int j = 0; j < demension; j ++)
        {
            //更新pi的速度
            if (it_times > 0)
            {
                p_v[i][j] = p_v[i][j]*alpha + dv1*weight1_rand(engine)*(per_best_position[i][j] - p_x[i][j]) 
                + dv2*weight2_rand(engine)*(social_best_position[j] - p_x[i][j]);
            }
            else
            {
                p_v[i][j] = p_v[i][j]*alpha + dv1*weight1_rand(engine)*p_x[i][j] 
                + dv2*weight2_rand(engine)*(social_best_position[j] - p_x[i][j]);
            }
            if (p_v[i][j] < vmin)p_v[i][j] = vmin;
            if (p_v[i][j] > vmax)p_v[i][j] = vmax;
            //更新X的位置
            if (p_x[i][j] + p_v[i][j] < Area_l)
            {
                p_x[i][j] = Area_l;
                p_v[i][j] *= -1;
            }
            else if (p_x[i][j] + p_v[i][j] > Area_r)
            {
                p_x[i][j] = Area_r;
                p_v[i][j] *= -1;
            }
            else p_x[i][j] = p_x[i][j] + p_v[i][j];
        }
    }
}


int main()
{
    //def the particle set
    vector<vector<double>>p_set(p_size);
    //def the speed vector of each particle the speed should be the same demension with X
    vector<vector<double>>pv_set(p_size);
    //target is to minimize the func value

    //初始化粒子初始位置和初始速度
    std::random_device rd;
    std::default_random_engine eng(rd());
    std::uniform_real_distribution<>x_dis(-10,10);
    std::uniform_real_distribution<>v_dis(vmin,vmax);

    for(int i = 0; i < p_size; i ++)
    {
        for(int j = 0; j < demension; j ++)
        {
            p_set[i].push_back(x_dis(eng));
        }
    }


    for(int i = 0; i < p_size; i ++)
    {
        for(int j = 0; j < demension; j ++)
        {
            pv_set[i].push_back(v_dis(eng));
        }
    }

    //初始化social_best
    social_best_position = p_set[0];
    //初始化per_best
    for(int i = 0; i < p_size; i ++)
    {
        per_best_position[i] = p_set[i];
    }

    // cout << "\n";
    for(it_times = 0; it_times < it_max; it_times ++)
    {
        iterate(p_set, pv_set);
        if (it_times%5 == 0)cout << "now best is x:" << social_best_position[0] << " y: " << social_best_position[1] << "\n";
        if (it_times%5 == 0)cout << "the func value is " << func(social_best_position) << "\nthe " << it_times << " epoch\n";
    }

    cout << "the best position is:\n";
    for(auto i:social_best_position)cout << i << " ";
    cout << "\nthe least function value is " << func(social_best_position) << '\n';

    return 0;
}

实验结果

由代码运行结果：
func1的最优位置在：，此处的函数值（全局最小值）为：
func2的最优位置在：，此处的函数值（全局最小值）为：

计划：

本次复习计划打算把基础课的诸多算法板子进行复习和巩固。
目标是分次对基础课的常用内容进行复习。大致节奏是一天一章。
标准是能够自己完整敲出各个板子为准，同时复习其算法思想。

第一天：

今日内容：第一章

快排

思路：

从右往左使得序列满足左侧小于某个数X，右侧大于某个数X。
注意递归！注意递归！注意递归！【递归结束的条件】

#include <iostream>
#include <algorithm>
#include <queue>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e5 + 10, mod = 1e9 + 7;

int a[N];

void qs(int s[],int l, int r)
{
    if (l >= r)return;

    int i = l - 1, j = r + 1;
    int x = s[l + r >> 1];
    while(i < j)
    {
        while(s[++i] < x);
        while(s[--j] > x);
        if (i < j)swap(s[i],s[j]);
    }
    qs(s, l, j);
    qs(s, j + 1, r);
}


int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    //code here
    int n;
    scanf("%d", &n);
    infor(i, 1, n)scanf("%d", &a[i]);
    qs(a, 1, n);
    infor(i, 1, n)printf("%d ", a[i]);

    return 0;
}

快速选择排序

思路：

每次快排后都可以得出标杆左侧有多少个数，
如果k小于标杆的序列那么只需递归左侧，
否则递归右侧。

代码：

#include <iostream>
#include <algorithm>
#include <queue>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e5 + 10, mod = 1e9 + 7;

int a[N];

int sqs(int q[], int l, int r, int k)
{
    if (l >= r)return q[l];

    int i = l - 1, j = r + 1;
    int x = q[l + r >> 1];
    while(i < j)
    {
        while(q[++i] < x);
        while(q[--j] > x);
        if (i < j)swap(q[i],q[j]);
    }

    if (k <= j)return sqs(q, l, j, k);
    else return sqs(q, j + 1, r, k);
}


int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    //code here
    int n,k;
    scanf("%d%d", &n, &k);
    infor(i, 1, n)scanf("%d", &a[i]);

    int ans = sqs(a, 1, n, k);

    printf("%d\n",ans);

    return 0;
}

归并排序

思路：

一分为二，认为两份已经排好序（因此此处的递归在while之前完成）
之后使用双指针选择，每次选择比较两个指针中较小的值填入临时数组。
注意两个while循环使末尾部分正确填充！
最后把临时数组赋给原数组。

代码：

#include <iostream>
#include <algorithm>
#include <queue>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e5 + 10, mod = 1e9 + 7;

int n;
int a[N];
int temp[N];

void ms(int q[], int l, int r)
{
    if (l >= r)return ;

    int mid = l + r >> 1;
    ms(q, l, mid);
    ms(q, mid + 1, r);

    int i = l, j = mid + 1, k = 1;

    while(i <= mid && j <= r)
    {
        if (q[i] < q[j])temp[k++] = q[i++];
        else temp[k++] = q[j++];
    }

    while(i <= mid)temp[k++] = q[i++];
    while(j <= r)temp[k++] = q[j++];

    for(int i = l, j = 1; i <= r; i ++, j ++)
    {
        q[i] = temp[j];
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    //code here
    scanf("%d", &n);
    infor(i, 1, n)scanf("%d", &a[i]);
    ms(a, 1, n);
    infor(i, 1, n)printf("%d ", a[i]);

    return 0;
}

几类功能

1、图像分类：告诉你图片里是什么
2、目标检测：告诉你图片里有什么并且用矩形框标出
3、语义分割：对每一个像素进行分类并打上标签
4、实例（图像）分割：对同一语义的不同实例会进行区分

数据相关：

分为训练集，验证集，测试集

制作流程：

1、分析需求
2、采集数据
获得你的数据图像，如果下载的别人的已经标注好的数据集则直接跳到第4部分。
3、数据标注
如果数据没有标注标签，那么需要人工标注标签。
4、训练模型
由easydl封装的训练，完全不用管
5、评估模型
对模型进行校验
6、部署模型
部署在h5应用上

思路：

二分但是不知道怎么写check函数。
最终看了大佬的题解，用单调队列进行求连续的k个数的和的最大值
每次求和都求一次前缀和并减去假设的均值，使得问题变成能否找到连续的长度为K（s <= k <= t）的序列
使得他们的序列和0，如果可以大于0那么说明有更大的均值可以取，反之说明没有更大的均值了。

代码：

#include <iostream>
#include <algorithm>
#include <queue>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e5 + 10, mod = 1e9 + 7;

int a[N];
int n, s, t;
double precise = 0.0001;

//如果不能做到那么返回false,否则返回true
bool check(double x)
{
    double sum[N];
    infor(i, 1, n)sum[i] = sum[i - 1] + a[i] - x;

    int head = 1, tail = 0;
    int q[N];
    infor(i, s, n)
    {
        while(head <= tail && sum[q[tail]] > sum[i - s])tail --;
        q[++tail] = i - s;
        while(head < tail && q[head] < i - t)head ++;
        if (head <= tail && sum[i] - sum[q[head]] >= 0)return true;
    }
    return false;
}

bool mcheck(double mid)
{
    double sum[N];
    infor(i, 1, n)sum[i] = sum[i - 1] + double(a[i]) - mid;

    deque<int>q;
    infor(i, s, n)
    {
        while(!q.empty() && sum[q.back()] > sum[i - s])q.pop_back();
        q.push_back(i - s);
        while(!q.empty() && sum[i] - sum[q.front()])q.pop_front();
        if (!q.empty() && q.front() - q.back() <= t - s)return true;
    }

    return false;
}


int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    scanf("%d",&n);
    scanf("%d%d",&s,&t);
    infor(i, 1, n)scanf("%d",&a[i]);

    //n^2
    double l = -1e4 - 1, r = 1e4 + 1;
    while(r - l > precise)
    {
        double mid = (l + r) / 2;
        if (!check(mid))r = mid;
        else l = mid;
    }

    printf("%.3f",l);

    return 0;
}

思路：

二维前缀和加枚举

代码：

#include <iostream>
#include <algorithm>

using namespace std;

constexpr int N = 5e3 + 10;

int s[N][N];
int n,m;
int ans;
int a,b,c;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    m = min(5001,m);

    for(int i = 0;i < n;i ++)
    {
        cin >> a >> b >> c;
        s[++a][++b] += c; 
    }

    for(int i = 1;i <= 5001;i ++)
        for(int j = 1;j <= 5001;j ++)
        {
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + s[i][j];
        }

    for(int i = m;i <= 5001;i ++)//枚举的正方形的右下角的坐标
        for(int j = m;j <= 5001;j ++)
        {
            ans = max(ans,s[i][j] - s[i-m][j] - s[i][j-m] + s[i-m][j-m]);
        }
    cout << ans << endl;
    return 0;
}

思路：

通过数学优化，使用O（n）的方法进行计算得出答案。

代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e5 + 10, mod = 1e9 + 7;

LL prefix[N];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    //code here
    int n;
    cin >> n;
    infor(i, 1, n)
    {
        cin >> prefix[i];
    }
    infor(i, 1, n)
    {
        prefix[i] += prefix[i - 1];
    }

    //enum i 1th end j 2th end if is end then is included
    if (prefix[n]%3 != 0)
    {
        cout << 0 << endl;
        return 0;
    }

    LL cnt = 0ll, ans = 0ll;
    infor(i, 1, n - 2)
    {
        if (prefix[i] == prefix[n] / 3)cnt ++;
        if (prefix[n] - prefix[i + 1] == prefix[n]/3)ans += cnt;
    }

    cout << ans << endl;

    return 0;
}

思路：

完全背包

代码：

公式优化版

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e3 + 10, mod = 1e9 + 7;

int book[5] = {0, 10, 20, 50, 100};
int dp[N];//从前i个物品选，体积不超过j的方案数量

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    //code here
    int m;
    cin >> m;
    dp[0] = 1;

    infor(i, 1, 4)
    {
        infor(j, book[i], m)
        {
            dp[j] += dp[j - book[i]];
        }
    }

    cout << dp[m] << "\n";

    return 0;
}

朴素版：

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e3 + 10, mod = 1e9 + 7;

int book[5] = {0, 10, 20, 50, 100};
int dp[N][N];//从前i个物品选，体积不超过j的方案数量

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    //code here
    int m;
    cin >> m;
    dp[0][0] = 1;

    infor(i, 1, 4)
    {
        infor(j, 0, m)
        {
            for(int k = 0; k * book[i] <= j; k ++)
            {
                dp[i][j] += dp[i - 1][j - k * book[i] ];
            }
        }
    }

    cout << dp[4][m] << "\n";

    return 0;
}

思路：

01背包问题，

dp[i][j] = dp[i - 1][j](不选物品i体积就为j的方案数量) + dp[i - 1][j - v[i](选物品i的方案数量);

代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e3 + 10, mod = 1e9 + 7;

LL dp[N];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    //code here
    int n, m;
    cin >> n >> m;
    infor(i, 1, n)
    {
        LL v;
        cin >> v;
        defor(j, m, v)
        {
            dp[j] = dp[j] + dp[j - v];
        }
    }
    cout << dp[m] << '\n';
    return 0;
}

A题：

思路：
模拟题
代码：

#include <iostream>
#include <algorithm>
#include <vector>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e5 + 10, M = 1e3;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    int x;
    cin >> x;
    if (x <= 7)
    {
        cout << "very easy\n";
    }
    else if (x <= 233)
    {
        cout << "easy\n";
    }
    else if (x <= 10032)
    {
        cout << "medium\n";
    }
    else if (x <= 114514)
    {
        cout << "hard\n";
    }
    else if (x <= 1919810)
    {
        cout << "very hard\n";
    }
    else cout << "can not imagine\n";

    return 0;
}

B题：

思路：
代码：

C题：

思路：
贪心，越大的背包应该放在越中间的位置。
代码：

#include <iostream>
#include <algorithm>
#include <vector>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e5 + 10, mod = 1e9 + 7;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    //code here
    int n;
    cin >> n;

    vector<LL>a(n);
    vector<LL>b(n);
    infor(i, 0, n - 1)a[i] = i + 1;
    sort(a.begin(), a.end());

    int l = 0, r = n - 1, cnt = 0;
    bool flag = true;

    while(l < r)
    {
        if (flag)
        {
            b[l++] = a[cnt++];
            flag = !flag;
        }
        else
        {
            b[r--] = a[cnt++];
            flag = !flag;
        }
    }

    b[l] = a[cnt];
    a = b;

    infor(i, 1, n - 1)
    {
        for(int j = 0; j < b.size(); j ++)
        {
            b[j] = (b[j] + b[j + 1]) % mod;
        }
        b.pop_back();
    }

    cout << b[0] << '\n';
    for(auto i : a)cout << i << " ";

    return 0;
}

D题：

思路：
最初思想：暴力枚举每一个位置，然后求贡献总和，找到修改后贡献总和最小的那个位置。
关键在于如何O(1)的求出每个位置的贡献。f[i]表示i的前面，b[i]表示i的后面
每个位置的贡献 = f[i]空集 * b[i]”udu + f[i]”u” * b[i]”du” + f[i]”ud” * b[i]”u” + f[i]”udu”*b[i]空集。
使用dp讲我们需要的数组dp出来即可。要理解状态转移方程和需要注意空集的选法总是1.
还有出题人非常恶心的卡了LL。
代码：

#include <iostream>
#include <algorithm>
#include <vector>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 2e5 + 10, mod = 1e9 + 7;

string s;

LL dpf[N][4], dpb[N][4];
string e = "udu";

void work(LL dp[][4], int n)//dp[a][b] 表示从前i个中，b字串有多少个
{
    dp[0][0] = 1;
    infor(i, 1, n)
    {
        //空集总是有一种选法的
        dp[i][0] = 1;
        infor(j, 1, 3)
        {
            dp[i][j] = dp[i - 1][j];
            if (s[i - 1] == e[j - 1])dp[i][j] += dp[i - 1][j - 1];
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    //code here
    cin >> s;
    int n = s.size();

    work(dpf, n);
    reverse(s.begin(), s.end());
    work(dpb, n);
    reverse(s.begin(), s.end());

    LL ans = 1e18;
    int res = -1;
    infor(i, 1, n)
    {
        LL temp = 0;
        infor(j, 0, 3)
        {
            temp += dpf[i - 1][j]*dpb[n - i][3 - j];
        }
        if (temp < ans)
        {
            ans = temp;
            res = i;
        }
    }
    s[res - 1] = 'z';
    cout << s << '\n';
    return 0;
}

E题：

思路：
代码：

F题：

思路：
按照题中说的照做，每次去除最大的值操作m次，注意一个数最大不超过3次就会收敛了。
使用小根堆，
维护询问的答案的数组ans[i],的值为询问为k时，答案是多少。
代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e5 + 10, mod = 1e9 + 7;

int a[2*N];
int book[6*N];

int func(int x)
{
    int res = 0;
    defor(i, 31, 0)
    {
        res += ((x >> i) & 1);
    }
    return res;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    //code here
    int n, q;
    cin >> n >> q;
    infor(i, 0, n - 1)cin >> a[i];
    priority_queue<int, vector<int>, less<int>>heap;

    infor(i, 0, n-1)heap.push(a[i]);

    // --- 不知道为啥这样写会段错
    // int onenum = 0;
    // infor(i, 1, 3*n)
    // {
    //     auto tem = heap.top();
    //     heap.pop();
    //     tem = func(tem);
    //     heap.push(tem);
    //     book[i] = heap.top();
    // }
    // --- 

    int cnt = 0;
    while(!heap.empty())
    {
        int top = heap.top();
        heap.pop();
        if (top == 1)continue;
        heap.push(func(top));
        book[cnt++] = top;
    }

    while(q--)
    {
        int k;
        cin >> k;
        if (k >= cnt)
        {
            cout << 1 << '\n';
            continue;
        }
        cout << book[k] << '\n';
    }
    return 0;
}

G题：

思路：
取出k对数，取每一对的时候取法只有两种：
1、取出最小的两个数相乘（因为可能有负数）
2、取出最大的两个数相乘（正整数情况）
代码：

#include <iostream>
#include <algorithm>
#include <vector>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e5 + 10, mod = 1e9 + 7;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    //code here
    int n, k;
    cin >> n >> k;
    vector<LL>a(n);
    infor(i, 0, n - 1)
    {
        cin >> a[i];
    }

    sort(a.begin(),a.end());

    int l = 0, r = a.size() - 1;

    LL res = 0ll;
    infor(i, 0, k - 1)
    {
        LL ans1 = a[l] * a[l + 1];
        LL ans2 = a[r] * a[r - 1];
        if (ans1 >= ans2)
        {
            l += 2;
            res += ans1;
        }
        else
        {
            r -= 2;
            res += ans2;
        }
    }

    cout << res << '\n';

    return 0;
}

H题：

思路：
根据题目模拟，算区间占比即可
代码：

#include <iostream>
#include <algorithm>
#include <vector>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e5 + 10, M = 1e3;

int main()
{
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);

    int x, l, r;
    scanf("%d", &x);
    scanf("%d%d", &l, &r);
    if (x <= l)printf("%d", 0);
    else if (l < x && x <= r)
    {
        printf("%.9f", ( (x - l)*1.0)/((r - l + 1)*1.0) );
    }
    else printf("%d",1);

    return 0;
}

A题：

思路：
由于Q的范围是1E5，所以想到每次询问得再log(n)下的复杂度，通过二分迅速找到最后一个不大于x价值的
物品的索引，同过往前加求出最大可以选k个的情况下的最大价值是多少。
由于如果线性的往前加可能会需要o(n)这样就变成了o(n^2)会tle。因此需要用前缀和预处理降低这一步的
时间复杂度，处理后变为0(1)。
因此总的变为o(Qlog(n))。
代码：

#include <iostream>
#include <algorithm>
#define infor(i, a, b) for(int i = a; i <= b; i ++)
#define defor(i, a, b) for(int i = b; i >= a; i --)

using namespace std;

using LL = long long;

constexpr int N = 1e5 + 10;

LL price[N], value[N];
LL s[N];
LL n, t, a, q;

int sol(int k)//返回最后一个小于等于k的坐标
{
    int l = 0, r = n;
    while(l < r)
    {
        int mid = l + r  + 1>> 1;
        if (price[mid] > k)r = mid - 1;
        else l = mid;
    }
    // cout << l << "\n";
    return l;
}


int main()
{
    cin >> n >> q;
    infor(i, 1, n)cin >> price[i];
    sort(price + 1, price + n + 1);
    infor(i, 1, n)s[i] = s[i - 1] + price[i];
    infor(i, 1, q)
    {
        LL k, x;
        cin >> k >> x;
        LL ans = 0ll;
        LL tar = (LL)sol(x);
        //注意tar - k 可能小于0的，而实际只有tar个，所以要保证数组索引 >= 0
        ans += (s[tar] - s[max(0ll,tar - k)]);
        cout << ans << '\n';
    }
    return 0;
}

B题：

思路：
博弈，每个人都采取最优解。
代码：

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    if (n&1)cout << "Yaya-win!\n";
    else cout << "win-win!\n";
    return 0;
}

C题：

思路：
长度相等可以非常快的确定，主要在长度不等的时候：
长串的前导0问题，会导致长度长的串不一定比长度短的串要大。
代码：
学习自jls，%%%！

#include <iostream>
#include <algorithm>
#include <cstring>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;
using PII = pair<int, int>;

constexpr int N = 1e5 + 10, M = 1e3;

string a, b;
int flag = 1;

int main()
{
    cin >> a >> b;
    if (a.size() == b.size())
    {
        if (a == b)
            cout << "=\n";
        else
            cout << "!\n";
        return 0;
    }

    if (a.size() < b.size())
    {
        swap(a, b);
        flag *= -1;
    }

    char front = a[0];

    int n = a.size(), m = b.size();

    infor(i, 0, n - m - 1)
    {
        if (a[i] != front)
        {
            cout << (flag == 1 ? '>' : '<') << "\n";
            return 0;
        }
    }

    a.erase(a.begin(), a.begin() + n - m);

    if (a == b)
    {
        cout << "!\n";
        return 0;
    }

    infor(i, 0, m - 1)
    {
        if (a[i] != b[i])
        {
            //如果不是前导0就无法确定大小关系
            if (b[i] != front)
            {
                cout << "!\n";
                return 0;
            }
            //如果时前导0，那么就可以确定此时的b是小于此时的a的，输出答案即可
            break;
        }
    }
    cout << (flag == 1 ? '>' : '<') << "\n";
    return 0;
}

H题：

思路：
模拟即可，注意边界的判定，以及-1的情况的判断。
代码：

#include <iostream>
#include <algorithm>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = b; i >= a; i--)

using namespace std;

using LL = long long;

constexpr int N = 1e5 + 10, M = 1e3;
LL x, y, k, n, t;
LL sold = 0ll;
LL nth = 0ll;

int main()
{
    cin >> x >> y >> k >> n >> t;
    while(t > 0)
    {
        t -= (n - nth)*(x + sold / k * y);
        if (nth == n - 1 && t > 0)
        {
            cout << -1 << '\n';
            return 0;
        }
        sold += n - nth;
        nth++;
    }
    cout << nth << '\n';
    return 0;
}

K题：

思路：
思维题，发现每次去除人数的最大值是x % (x / 2 + 1)，其中x是当前有多少人。
代码：

#include <iostream>
#include <algorithm>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = b; i >= a; i--)

using namespace std;

using LL = long long;

constexpr int N = 1e5 + 10, M = 1e3;
LL x, y, k, n, t;
LL sold = 0ll;
LL nth = 0ll;

int main()
{
    LL x;
    cin >> x;
    int cnt = 0;
    while(x > 2)
    {
        x -= (x%(x/2ll + 1ll)) ;
        cnt ++;
        // cout << "left x : " << x << '\n';
    }
    cout << cnt << '\n';
    return 0;
}

L题：

思路：
dp，关键在于如何化解：在倒着dp时不知道上一步的临时总人数是多少。
化解方法为倒着dp即可。看代码就可以理解。
代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#define infor(i, a, b) for (int i = a; i <= b; i++)
#define defor(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

using LL = long long;

constexpr int N = 1e5 + 10;

int cost[N], cont[N];
int dp[N];//dp[i]表示剩余人数为i的所有方案中花费的最小值
int n, m;

//关键在于：dp如果从i小推大，即不能把dp[i]放在左侧，不然不知道上一步去除人数前的总人数

int main()
{
    cin >> n >> m;

    infor(i, 1, m)
    {
        cin >> cost[i] >> cont[i];
    }

    memset(dp, 0x3f, sizeof(dp));
    //剩余n个人无需任何代价
    dp[n] = 0;

    defor(i, n, 1)//倒着dp人数
    {
        infor(j, 1, m)//枚举指令
        {
            if (cont[j] < i)dp[i - i%cont[j]] = min(dp[i - i%cont[j]], dp[i] + cost[j]);
        }
    }
    infor(i, 1, n)
    {
        if (dp[i] != dp[0])
        {
            cout << dp[i] << '\n';
            return 0;
        }
    }
    return 0;
}