B

标准题解代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Order {
    int to, profit;
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector<vector<Order>> orders(n + 1);  // 存储每个城市的订单
    vector<int> dp(n + 1, 0);             // dp[i]表示到达城市i时的最大收益

    // 读取订单数据
    for (int i = 0; i < m; i++) {
        int a, b, p;
        cin >> a >> b >> p;
        orders[a].push_back({b, p});
    }

    // 动态规划核心逻辑
    for (int i = 1; i <= n; i++) {
        // 从城市i-1直接移动到i（不接订单）
        dp[i] = max(dp[i], dp[i - 1]);
        
        // 处理所有从i出发的订单
        for (auto &order : orders[i]) {
            int to = order.to;
            int profit = order.profit;
            // 更新目标城市的收益
            if (to > i) {  // 确保订单终点是后续城市
                dp[to] = max(dp[to], dp[i] + profit);
            }
        }
    }

    cout << dp[n];
    return 0;
}

关键逻辑解析

状态定义

dp[i] 表示到达城市 i 时能获得的最大收益。初始化时，所有城市收益为0，因为未接订单时无法获得收益。

状态转移

直接移动：从城市 i-1 移动到 i 时不接订单，此时 dp[i] = max(dp[i], dp[i-1])。
接订单转移：遍历所有从 i 出发的订单，更新目标城市 to 的收益为 dp[i] + profit，并通过 max 保留最大值。

边界条件

订单终点必须大于当前城市 (to > i)，否则订单无效。

最终答案存储在 dp[n] 中，表示到达终点城市的最大收益。

优化点分析

剪枝操作：在遍历订单时，若订单终点 to 不大于当前城市 i，可直接跳过，避免无效计算。

时间复杂度

代码的时间复杂度为 O(n + m)，其中 n 是城市数量，m 是订单数量。每个订单仅被处理一次，符合题目要求。

空间优化

使用一维 dp 数组代替二维数组，通过滚动更新减少空间复杂度。

常见错误

未处理直接移动的情况：漏掉 dp[i] = max(dp[i], dp[i-1]) 会导致无法从城市 i-1 直接移动到 i，从而丢失可能的路径。
订单终点未校验：若未校验 to > i，可能错误处理无效订单（如终点是当前城市或更早城市），导致结果错误。

测试用例示例

输入：

输出：

解释：路径为 1 → 3 → 4 → 5，收益为 10 + 5 + 15 = 30，但直接选择订单 1→5 收益为 20，而通过 3→4→5 的额外订单总收益更高（10+5+15=30）。最终最大收益为 20 + 15 = 35（需根据实际订单组合计算）。

总结

本题通过动态规划逐步更新每个城市的最大收益，结合直接移动和接订单两种操作，最终得到最优解。需注意状态转移的顺序和边界条件，确保所有可能路径均被覆盖。

I and J

要为实验室节约电 easy版和 hard版问题题解

（参考数学问题一百盏灯问题）

问题分析

核心观察：当灯被摁了奇数次后，也就是说电源的编号有奇数个因数时，最终状态为关闭
数学原理：非平方数的因数成对出现，只有平方数的因数个数为奇数
问题转化：求前n个数中的平方数个数

代码实现方案

方法一：暴力遍历

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() 
{
    int n, ans = 1;
    cin >> n;
    while (ans * ans <= n) 
        ans++;
    cout << ans - 1 << endl;
}

方法二：二分查找

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() 
{
    int n;
    cin >> n;
    double l = 0.0, r = 1e18, mid;
    while (r - l >= 1e-6) 
    { // 精度控制
        mid = (l + r) / 2;
        (mid * mid <= (double)n) ? l = mid : r = mid;
    }
    cout << (int)l << endl; // 输出整数部分
}

方法三：直接开方（最优解）

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() 
{
    int n;
    cin >> n;
    cout << (int)sqrtl(n) << endl; // 必须使用sqrtl保证精度
}

关键注意事项

必须使用 long long：处理大数时防止溢出
精度问题：
- 二分法需要设置精度阈值（1e-6）
- 直接开方必须使用sqrtl而非sqrt
算法选择：
- 暴力法时间复杂度 O(√n)
- 二分法时间复杂度 O(log(max_value))
- 直接开方时间复杂度 O(1)
- 其实第一种方法是要被卡的，但又仔细一想这场比赛好像没几个简单题了，遂放过了第一种题解

L and M and N

L Easy 版本：暴力枚举

题解：

直接暴力枚举所有逆序对，计算它们的和，并存储起来，从小到大排序后取前 k 个和。

时间复杂度：

O(n^2)

代码：

#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"
#define int long long 
using namespace std;
void solve()
{
	int n,k;
	cin>>n>>k;
	vector<int>a(n+1),t;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)if(a[i]>a[j])t.push_back(a[i]+a[j]);
	int ans=0;
	sort(t.begin(),t.end());
	for(int i=0;i<k;i++)ans+=t[i];
	cout<<ans<<endl;
}
signed main()
{
    IOS
   	int T=1;
   	//cin>>T;
   	while(T--)solve();
    return 0;
}

M Mid 版本：二分答案 + 前缀和

题解：

由于n的范围很大，暴力枚举会超时，同时逆序对个数会超时，数组存储范围过大也会导致内存超限，运行超时，不能使用暴力枚举。题目中要求前k小之和，对于第k(小/大)问题首先考虑二分答案。

我们可以二分第k小值，由于数组是单调递减的，我们在 check 函数中枚举每一个数，同时来统计这个数能与多少个数，组成的逆序对之和小于等于mid。满足条件的逆序对符合 ai + aj <= mid && i < j，所以在枚举每一个数时，由于数组有序，我们可以二分 mid - ai 找到这个数的位置，并且要保证 mid - ai <= a[pos]，其中 pos 是二分查找的位置。然后 pos 后面的数与 ai 相加都满足 ai + aj <= mid && i < j，因为数组是递减的。

最后可以在 O(n log n) 中统计出符合 ai + aj <= mid && i < j 的逆序对个数，并与 k 比较，即可二分出第k小值。接下来我们通过这个值来计算前k个数之和。在二分过程中，可以发现每个数与符合条件的数的和为 ai + aj1 + ai + aj2 + ... + ai + ajlen。我们可以使用前缀和快速求出这个和，等于 s[区间末尾] - s[区间起始-1] + len(区间长度) * ai。

由于第k小值可能有很多个，我们可以先计算出前第k-1小值的和，然后剩余的用 (k - cnt) * 第k小值 补全即可。

时间复杂度：

O(n log n * log C)，其中 C 为二分上界

代码：

#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define endl "\n"
#define int long long
using namespace std;

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n), s(n + 1, 0);
    for (int i = 1; i <= n; i++)
        cin >> a[i - 1];
    sort(a.begin(), a.end());
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i - 1];
    auto check = [&](int x) -> pair<int, int>
    {
        int cnt = 0, sum = 0;
        for (int i = n - 1; i > 0; i--)
        {
            if (x - a[i] < 0)continue;
            auto it = lower_bound(a.begin(), a.begin() + i - 1, x - a[i]);
            if (it == a.begin() && *it > x - a[i])continue;
            if (*it > x - a[i])it--;
            int len = it - a.begin() + 1;
            cnt += len;
            sum += s[len] + a[i] * len;
            if (cnt >= k)return {cnt, sum};
        }
        return {cnt, sum};
    };
    int ans = 0;
    int l = 0, r = 2e9;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        auto [cnt, sum] = check(mid);
        if (cnt >= k)
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    auto [cnt, sum] = check(ans - 1);
    cout << sum + (k - cnt) * ans << endl;
}
signed main()
{
    IOS int T = 1;
    while (T--)solve();
    return 0;
}

N Hard 版本：归并排序 + 二分 + 前缀和（可持久化线段树，树状数组也可）

题解：

接续 mid 思路，同样是使用二分答案，找到第k小值，然后求和操作同理。不同的是，现在数组是无序的，要求逆序对个数可以想到使用归并排序。

归并排序的分治思想可以在合并两个有序数组的过程中使用。我们可以遍历右边的数组，通过二分查找在左边有序数组中找到符合条件的逆序对个数，使用 mid 的思路来判断。为了快速求和，可以继续利用前缀和的技巧。此版本也可以使用可持久化线段树或树状数组来优化求逆序对的操作。

时间复杂度：

大约O(n (log n)^2 log C)，其中 C 为二分上界，具体时间复杂度可能较为玄学

归并排序做法：

#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define endl "\n"
#define int long long
using namespace std;

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    auto check = [&](int x) -> pair<int, int>
    {
        int cnt = 0, sum = 0;
        auto merge_sort = [&](auto &merge_sort, int l, int r) -> vector<int>
        {
            if (l == r)return {a[l]};
            int mid = (l + r) / 2;
            auto la = merge_sort(merge_sort, l, mid);
            auto ra = merge_sort(merge_sort, mid + 1, r);
            int na = la.size();
            vector<int> tmp, s;
            s.resize(na + 1);
            s[0] = 0;
            for (int i = 1; i <= na; i++)s[i] = s[i - 1] + la[i - 1];
            int i = 0, j = 0;
            while (i < la.size() && j < ra.size())
            {
                if (la[i] <= ra[j])tmp.push_back(la[i++]);
                else
                {
                    auto it = upper_bound(la.begin() + i, la.end() - 1, x - ra[j]);
                    if (it == la.begin() + i && *it > x - ra[j])
                    {
                        tmp.push_back(ra[j++]);
                        continue;
                    }
                    if (*it > x - ra[j])it--;
                    int len = it - la.begin() - i + 1;
                    cnt += len;
                    sum += s[it-la.begin()+1] - s[i] + len * ra[j];
                    tmp.push_back(ra[j++]);
                }
            }
            while (i < la.size())tmp.push_back(la[i++]);
            while (j < ra.size())tmp.push_back(ra[j++]);
            return tmp;
        };
        merge_sort(merge_sort, 0, n - 1);
        return {cnt, sum};
    };
    int ans = 0;
    int l = 0, r = 2e9;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        auto [cnt, sum] = check(mid);
        if (cnt >= k)
        {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    auto [cnt, sum] = check(ans - 1);
    cout << sum + (k - cnt) * ans << endl;
}
signed main()
{
    IOS int T = 1;
    while (T--)solve();
    return 0;
}

可持久化线段树解法

//先对a数组进行离散化  
//然用可持久化值域线段树维护每个版本值域在[l,r]内的数的个数和值域在[l,r]内数的和。 
//从后到前遍历a[i]，创建每个版本.
//二分逆序对和的值域。 
//check函数 从小到大枚举sorta数组内的数,查询对应版本的线段树,把所有小于sorta[i]且两数之和小于mid的逆序对加上。
//最后二分的答案是逆序对个数>=k的情况,因为l-1对应 逆序对个数<=k
//所以我们先计算出check(l-1)的sum与cnt，然后答案就是 check(l-1).sum + (k-check(l-1).cnt)*l;
//时间复杂度 n*logn *log(2e9)
#include<bits/stdc++.h>
#define int long long
#define all(x) (x).begin(), (x).end()


using namespace std;
typedef long long ll;
using i64 =long long;
using i128 =__int128;
using PII =pair<int,int>;
template<class T>void debug(const vector<T> & v,int l,int r){for(int i=l;i<=r;i++){cout<<v[i]<<' ';}cout<<'\n';}
template<class T>void debug(const vector<T> & v){for(int i=1;i<v.size();i++){cout<<v[i]<<' ';}cout<<'\n';}
template<class T>void debug(const T & v){cout<<v<<'\n';}
template<class T>bool chmax(T &a,const T& b) {if(a >= b) return false;a = b; return true;}
template<class T>bool chmin(T &a,const T& b) {if(a <= b) return false;a = b; return true;}
mt19937 rng(time(0));
mt19937_64 rng64((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5+10;
int n,k;
int a[N];
PII sorta[N];
vector<int> b;
int ls[N*22],rs[N*22],sum[N*22],cnt[N*22];
int root[N];
int tot;

int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}

void pushup(int u){
	sum[u]=sum[ls[u]]+sum[rs[u]];
    cnt[u]=cnt[ls[u]]+cnt[rs[u]];
}
void change(int &u,int v,int l,int r,int p,int k){
	u = ++tot;
	ls[u]=ls[v];rs[u]=rs[v],sum[u]=sum[v],cnt[u]=cnt[v];
	if(l==r){
        sum[u]+=k;
        cnt[u]++;
		return;
	}
	int mid =l+r>>1;
	if(p<=mid)change(ls[u],ls[v],l,mid,p,k);
	else change(rs[u],rs[v],mid+1,r,p,k);
    pushup(u);
}
struct Result {
    ll sum,cnt;
};

Result query(int u, int l, int r, int ql, int qr) {
    if (r <ql || l>qr) {
        return {0, 0};
    }
    if (ql<=l &&r<=qr) {
        return {sum[u], cnt[u]};
    }
    int mid = (l + r) >> 1;
    Result left = {0,0};
    Result right = {0,0};
    if (ls[u]) {
        left =query(ls[u], l, mid, ql, qr);
    }
    if (rs[u]) {
        right =query(rs[u], mid + 1, r, ql, qr);
    }
    return {left.sum + right.sum, left.cnt + right.cnt};
}

int find(int x){
	return lower_bound(b.begin(),b.end(),x)-b.begin() +1; 
}

void Main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++){
        sorta[i].first=a[i]=read();
        sorta[i].second=i;
        b.push_back(a[i]);
    }
    sort(sorta+1,sorta+n+1);
    sort(b.begin(),b.end());
	b.erase(unique(b.begin(),b.end()),b.end());
	for(int i=n;i>=1;i--){
		change(root[i],root[i+1],1,n,find(a[i]),a[i]);
	}
    
    
    auto check = [&](ll x)->Result{
        ll cont =0,s=0;  
        for(int i=1;i<=n;i++){
            int fdi = find(sorta[i].first);
            if(2*sorta[i].first<=x){
                auto rt = query(root[sorta[i].second],1,n,1,fdi-1);
                cont+=rt.cnt;
                s+=rt.sum + sorta[i].first*rt.cnt;
            }
            else if(sorta[i].first<x){
                ll l=0,r=n;
                while(l<r){
                    int mid =l+r+1>>1;
                    if(sorta[mid].first<=min(x-sorta[i].first,sorta[i].first-1))l=mid;
                    else r=mid-1;
                }
                if(l==0)continue;
                int fdn=find(sorta[l].first);
                Result rt =query(root[sorta[i].second],1,n,1,fdn);
                 
                cont+=rt.cnt;
                s+=rt.sum+sorta[i].first*rt.cnt;
            }
            else if(sorta[i].first>=x){
                break;
            }
        }
        return {s,cont};
    };
    
    
    
    ll l=1,r=2e9;
    ll ans =0,cntt = 0;
    while(l<r){
        int mid = l+r>>1;
        Result t =check(mid);
        if(t.cnt>=k){
            r=mid;
            ans=mid;
            cntt=t.cnt;
        }
        else l=mid+1;

    }
    auto rt = check(l-1);
    cout<<rt.sum + (k-rt.cnt)*ans;
}



int32_t main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    
    int _ = 1;
//     cin>>_;
    while(_--)Main();
    
    return 0;
}

树状数组解法

题目大意

给定一个长为 $n$ 的数组 $a$ ，计算数字中前k小逆序对和的和。

题解

我们记第 $k$ 小的逆序对和为 $x$ ，显然 $x$ 具有二分性( $x$ 越大，逆序对和小于等于 $x$ 的数量也会更多)，那么我们可以二分 $x$ ，然后 $check()$ 里面统计有多少逆序对和小于等于 $x$ 。逆序对我们用树状数组维护即可，值得注意的是由于 $a_i$ 最大为 $10^9$ ，所以记得先离散化。树状数组的复杂度为 $O(\log (n))$ ，所以 $check()$ 的复杂度为 $O(n \log (n))$ ，加上二分整体复杂度为 $O(n \log^2(n))$ 。

在 $check()$ 中计算得到了逆序对和小于 $x$ 的逆序对数量 $c$ ，以及这些数的和 $s$ ，由于逆序对和小于等于 $x$ 的数量可能大于 $k$ ，所以最终的答案为 $s - (c - k) * x$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

struct BIT{
    vector<ll> tr;
    ll n;
    BIT(){tr.resize(N,0);};
    BIT(ll m){tr.resize(m + 10,0),n = m + 1;};
    void update(ll p,ll x){
        for(int i = p;i <= n;i += i & -i)
            tr[i] += x;
    }
    
    ll query(ll p){
        ll res = 0;
        for(int i = p;i >= 1;i -= i & -i)
            res += tr[i];
        return res;
    }
    
    void clear(){
        for(int i = 0;i <= n;i++)
            tr[i] = 0;
    }
};

int main(){
	ll T = 1;
	// cin >> T;
	while(T--){
		ll n,k,ans = 0;
		cin >> n >> k;
		vector<ll> a(n + 1),t,index(n + 3);
        map<ll,ll> mp;
		for(int i = 1;i <= n;i++){
			cin >> a[i];
            mp[a[i]]++;
		}
        
        //离散化
        ll idx = 0;
		mp[0] = 1;
		mp[1e10] = 1;  
        for(auto i : mp){
            mp[i.first] = ++idx;
			index[idx] = i.first;
        }
        
        BIT sum(n + 10),cnt(n + 10);

		auto check = [&](ll mid) -> array<ll,2>{
			sum.clear(),cnt.clear();
			ll c = 0,s = 0;
			for(int i = n;i >= 1;i--){
				if(mid > a[i]){
                    // mid - a[i]没有离散化，所以需要二分找到对应的离散化值
					ll temp = *(upper_bound(index.begin(),index.end(),mid - a[i]) - 1);
					ll tc = cnt.query(min(mp[temp],mp[a[i]] - 1));
					c += tc;
					s += sum.query(min(mp[temp],mp[a[i]] - 1)) + tc * a[i];
				}
				
				sum.update(mp[a[i]],a[i]);
				cnt.update(mp[a[i]],1);
			}
			return {c,s};
		};
        
        ll l = 0,r = 2e9 + 10;
		while(l <= r){
			ll mid = (l + r) / 2;
			auto [c,s] = check(mid);
			// cout << c << "\n";
 			if(c >= k){
				r = mid - 1;
				ans = s - (c - k) * mid;
			}
			else l = mid + 1;
		}
		cout << ans << "\n";
	}
	return 0;
}

题解 | B and I and J and L and M and N

B

标准题解代码

关键逻辑解析

状态定义

状态转移

边界条件

优化点分析

时间复杂度

空间优化

常见错误

测试用例示例

总结

I and J

要为实验室节约电 easy版 和 hard版 问题题解

（参考数学问题一百盏灯问题）

问题分析

代码实现方案

方法一：暴力遍历

方法二：二分查找

方法三：直接开方（最优解）

关键注意事项

L and M and N

L Easy 版本：暴力枚举

题解：

时间复杂度：

代码：

M Mid 版本：二分答案 + 前缀和

题解：

时间复杂度：

代码：

N Hard 版本：归并排序 + 二分 + 前缀和（可持久化线段树，树状数组也可）

题解：

时间复杂度：

归并排序做法：

可持久化线段树解法

树状数组解法

题目大意

题解

要为实验室节约电 easy版和 hard版问题题解