视频题解

A

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[15];

int main()
{
    for (int i = 1; i <= 13; i++) cin >> a[i];
    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= 13; i++) {
        int x; cin >> x;
        int t = x + a[i] - 4;
        if (t > 0) ans1 += t;
        else       ans2 += -t;
    }
    if (ans1 > ans2) cout << -1;
    else             cout << ans1;
    return 0;
}

B

整体思路一定是将前 $k$ 个中的一个较小数与后续 $n-k$ 个中的较大数进行交换，就能使得最后的前 $k$ 个之和的结果更大。

若选取的前 $k$ 个数的位置为 $i$，后 $n-k$ 个数的位置为 $j$，则此时的交换次数即为 $j-i$。

对于 $60\% pts$，可以枚举 $j$ 的位置，再寻找从 $[k\sim 1]$ 中第一个 $< a_j$ 的 $a_i$，$O(n^2)$

为了优化时间，需要在枚举 $a_j$ 时候，快速寻找到适合的 $a_i$ 的位置。预处理 $i\sim k$ 的后缀最小值，这个数组满足单调性，可在这个数组上进行二分，寻找合适的 $a_i$ 的位置，$O(nlgn)$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e5 + 5;
int n, k, a[N], u[N], ans = INT_MAX; //a即为原数组，u是用来二分的具有单调性的序列
void init() //预处理
{
    for (int i = 1; i <= k + 1; i++)
        u[i] = INT_MAX;
    for (int i = k; i > 0; i--)
        u[i] = min(a[i], u[i + 1]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    init();
    for (int i = k + 1; i <= n; i++)
    {
        int l = 1, r = k, mid, res = 0;
        while (l <= r)
        {
            mid = (l + r) / 2;
            if (u[mid] >= a[i])
                r = mid - 1;
            else
                l = mid + 1, res = mid;
        }
        if (!res)
            continue;
        ans = min(ans, i - res);
    }
    cout << (ans == INT_MAX ? -1 : ans) << '\n'; //特判&输出
    return 0;
}

C

如果 $n$ 为奇数，每次都选取连叶子的边，并将其 $siz=1$ 异或，那么删除完所有的边，会进行偶数次 $1$ 的异或，最后最小结果为 $0$

如果 $n$ 为偶数，也执行上述策略，直到只剩下 $4$ 个节点的联通块，然后依旧每次选取连叶子的边，但此时选择非叶节点的 $siz$，即依次异或 $3\oplus 2\oplus1=0$

即无论 $n$ 如何，最后最小花费均为 $0$ ($n=2$ 为特殊情况)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
vector<int> g[N];
int n;
int main() {
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if (n == 2) {
        cout << 1 << endl;
        cout << 1 << " " << 2 << " " << 1 << endl;
        return 0;
    }

    vector<ll> ord;
    queue<ll> q;
    vector<ll> fa(n + 5, -1);
    vector<bool> vis(n + 5);
    q.push(1);
    vis[1] = 1;

    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        ord.push_back(u);

        for(auto v : g[u]) {
            if (vis[v]) continue;
            q.push(v);
            vis[v] = 1;
            fa[v] = u;
        }
    }

    cout << 0 << endl;

    if (n & 1) {
        for (int i = n - 1; i >= 1; i--) {
            int u = ord[i], p = fa[u];
            cout << u << " " << p << " " << u << endl;
        }
        return 0;
    }

    for (int i = n - 1; i >= 1; i--) {
        int u = ord[i], p = fa[u];
        int x = u;
        if (i <= 3)
            x = p;
        cout << u << " " << p << " " << x << endl;
    }
    return 0;
}

D

先找找有没有贪心策略，由于采摘后速度减慢，因此如果多次经过一棵树苗，一定是最后一次经过的时候采摘。

那么第一次采摘一定是第一个或者最后一个，并且任意时刻没采摘的区间是连续的，即已采摘的部分一定是前缀与后缀。

由此不难想到维护没采摘的区间，考虑区间 dp 。

状态里先设上区间端点是显然的，由于转移时候肯定要计算距离，所以要记录位置，那么就记录一维表示当前在区间左端点还是右端点。

最后统计答案时候需要计算从起点到第一棵树苗的距离，再加一维表示第一个采摘的是第一棵树苗还是最后一棵树苗。

就有 $f [l][r][0/1][0/1]$ ​ 表示当前 $[l,r]$ 区间的树苗还未采摘，第一个采摘的是第一个/最后一棵树苗，此时在区间的左/右端点。由于只有有树苗的位置需要记录，这里的端点是指树苗的编号（按位置排序后）。

那么区间 $[l,r]$ 由区间 $[l−1,r]$ 和区间 $[l,r+1]$ 转移。

最后统计答案的时候可以二分找到距离终点最近的位置，加上该位置到终点的消耗并在多个位置的答案中取最小值。

注意 $L$ 的范围很大，假设每个位置都存在树苗，那么最少用时 $1+2+...+L=\frac{L\times(L+1)}2$ 已经远远大于 $T\le5\times 10^5$，所以只有当 $n$ 在 $1000$ 以内时，才有可能完成时限的要求。即超过这个范围直接为 No，否则无法通过区间dp复杂度 $O(n^2)$

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=5e5+10;
const int M=1050;
int Q,n,L,s,t,T;
int sum[N],x[N]; 
int f[M][M][2][2];
signed main(){
	cin>>n>>L;
	for(int i=1;i<=n;i++)cin>>x[i],sum[x[i]]++;
	for(int i=1;i<=L;i++)sum[i]+=sum[i-1];
	sort(x+1,x+1+n);
	n=unique(x+1,x+1+n)-x-1;
	cin>>Q;
	if(n>=1000){
		while(Q--){
			cout<<"No"<<endl;
		}
		return 0;
	}
	memset(f,0x3f,sizeof(f));
	f[1][n][0][0]=f[1][n][1][1]=0;
	for(int len=n-1;len>=1;len--){
		for(int l=1;l+len-1<=n;l++){
			int r=l+len-1;
			int s=sum[x[l]-1]+sum[L]-sum[x[r]];
			f[l][r][0][0]=min(f[l-1][r][0][0]+(s+1)*(x[l]-x[l-1]),f[l][r+1][0][1]+(s+1)*(x[r+1]-x[l]));
			f[l][r][0][1]=min(f[l-1][r][0][0]+(s+1)*(x[r]-x[l-1]),f[l][r+1][0][1]+(s+1)*(x[r+1]-x[r]));
			f[l][r][1][0]=min(f[l-1][r][1][0]+(s+1)*(x[l]-x[l-1]),f[l][r+1][1][1]+(s+1)*(x[r+1]-x[l]));
			f[l][r][1][1]=min(f[l-1][r][1][0]+(s+1)*(x[r]-x[l-1]),f[l][r+1][1][1]+(s+1)*(x[r+1]-x[r]));	
		}
	}
	while(Q--){
		cin>>s>>t>>T;
		int ans=0x3f3f3f3f;
		if(x[n]>=t){
			int p=lower_bound(x+1,x+1+n,t)-x;
			ans=min(ans,f[p][p][0][0]+(sum[L]+1)*abs(x[p]-t)+abs(s-x[1]));
			ans=min(ans,f[p][p][1][0]+(sum[L]+1)*abs(x[p]-t)+abs(s-x[n]));		
		}
		if(x[1]<=t){
			int p=upper_bound(x+1,x+1+n,t)-x-1;
			ans=min(ans,f[p][p][0][0]+(sum[L]+1)*abs(x[p]-t)+abs(s-x[1]));
			ans=min(ans,f[p][p][1][0]+(sum[L]+1)*abs(x[p]-t)+abs(s-x[n]));
		}
		ans+=sum[L];
		if(ans>T)cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	}
	return 0;
}