真（ru）的（yi）是（ke）签（ai）到（miao）。

看到 $n$ 大得吓人，于是我们不乱想，考虑贪心。具体来说就是我们发现每次从根结点往下走一定是走到一个叶子的地方，具体来说就是我们可以把树上的一堆边看作一条条链之后贪心的选。

具体来说就是对于一个结点记录以它为起点往下走到叶子能够得到的最优价值，所以我们可以遍历每个结点的时候可以更新其父结点能够得到的最优价值，因为当前父结点已经确定了除去走向当前结点的那条路径的最优价值，我们只需要看一下走向当前结点的是不是更优就可以了，注意要是我们成功更新了，就

........................................................................

该题解待审

[COGS 4161] hope I can sort 题目解析

 引入

 注意到本题的01序列的排序过程可简化为错位数 k（前 c0 个位置中 1 的个数）的链。

 因此可以考虑动态规划。

 分析

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

const int MOD=998244353,N=5005;
int a[N],dp[N],nd[N];

int qp(int a,int b){
	int r=1;
	while(b){
		if(b&1)r=1ll*r*a%MOD;
		a=1ll*a*a%MOD;
		b>>=1;
	}
	return r;
}

int main(){
    freopen("hopeicansort.in","r",stdin);
    freopen("hopeicansort.out","w",stdout); 
	int n,m;
	cin>>n>>m;
	int c0=0;
	for(int i=1;i<=n;++i)
    {
		cin>>a[i];
		if(!a[i]) ++c0;
	}
	int k0=0;
	for(int i=1;i<=c0;++i) 
        if(a[i]) 
            ++k0;
	int mx=k0<c0?k0:n-c0;
	if(mx<k0) mx=k0;
	int T=1ll*n*(n-1)/2%MOD,invT=qp(T,MOD-2);
	dp[k0]=1;
	for(int t=0;t<m;++t)
    {
		for(int k=0;k<=mx;++k) nd[k]=0;
		nd[0]=(dp[0]+1ll*dp[1]*invT)%MOD;
		for(int k=1;k<=mx;++k)
        {
			int d=1ll*k*k%MOD*invT%MOD;
			nd[k]=(1ll*dp[k]*(1-d+MOD)+1ll*dp[k+1]*(k+1)%MOD*(k+1)%MOD*invT)%MOD;
		}
		for(int k=0;k<=mx;++k) dp[k]=nd[k];
	}
	cout<<dp[0];
	return 0;
}

T4 - Constructive 题解

题目简述

题目大意：
给定 $N$ 种二维向量 $v_i = (a_i, b_i)$ 及其代价 $c_i$，每种向量可无限次使用。求构造出目标向量 $u = (x, y)$ 的最小总代价。

• 向量数量 $N \le 90$
• 目标坐标 $x, y \le 10^9$
• 向量分量 $a_i, b_i \le 10$
• 向量代价 $c_i \le 10^9$

子任务简析

从简单情况到一般情况的思考过程：

• Subtask 1: 步长为 1 的坐标移动，结果显而易见。
• Subtask 2 & 3: 坐标范围小，直接建图跑 Dijkstra。
• Subtask 4: 降维打击，转化为一维无界背包。
• Subtask 5: 大坐标直线路径，引入同余类 BFS/DP 思想。

正解

解法 1：分治（官方题解）

几何中点引理：
如果一组短向量的和为 $(x, y)$，那么我们通过调整顺序，一定可以把他们分成两半，使得每一半的和都在 $(\frac{x}{2}, \frac{y}{2})$ 的常数范围内。

转移方程：

$f(x, y) = \min_{\delta_x, \delta_y} \{ f(\lfloor \frac{x}{2} \rfloor + \delta_x, \lfloor \frac{y}{2} \rfloor + \delta_y) + f(\lceil \frac{x}{2} \rceil - \delta_x, \lceil \frac{y}{2} \rceil - \delta_y) \}$

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

const long long INF = 4e18;
const int MAX_LENGTH = 10;
long long one_vec[MAX_LENGTH + 1][MAX_LENGTH + 1];
unordered_map <long long, long long> dp;
const int MAX_X = 1000000001;

long long DP(long long x, long long y){
    long long pos = x * MAX_X + y;
    if(dp.count(pos)) return dp[pos];

    long long tmp = INF;
    if(x <= MAX_LENGTH && y <= MAX_LENGTH) tmp = one_vec[x][y];

    for (long long dx = -MAX_LENGTH; dx <= MAX_LENGTH; dx++){
        for (long long dy = -MAX_LENGTH; dy <= MAX_LENGTH; dy++){
            long long x1 = x / 2 + dx, y1 = y / 2 + dy;
            long long x2 = x - x1, y2 = y - y1;
            if(min({x1, x2, y1, y2}) < 0) continue;
            if(x1 + y1 == 0 || x2 + y2 == 0) continue;
            tmp = min(tmp, DP(x1, y1) + DP(x2, y2));
        }
    }
    return dp[pos] = tmp;
}

int main(){
    int N; long long x, y;
    cin >> N >> x >> y;
    for (int i = 0; i <= MAX_LENGTH; i++)
        for (int j = 0; j <= MAX_LENGTH; j++) one_vec[i][j] = INF;

    for (int a, b, c; N--;){
        cin >> a >> b >> c;
        one_vec[a][b] = min(one_vec[a][b], (long long)c);
    }
    long long ans = DP(x, y);
    if(ans >= INF) cout << "-1\n";
    else cout << ans << '\n';
    return 0;
}

解法 2：基底 + 小范围微调

核心逻辑：我们先在原点附近进行小范围的精确搜索（微调），然后通过解二元一次方程组，利用“性价比”最高的基底向量组快速跨越远距离。

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll INF = 4e18;

struct vec { int a, b; ll c; } v[105];
struct node {
    int x, y; ll d;
    bool operator > (const node& o) const { return d > o.d; }
};

int n; ll tx, ty, res = INF;
ll dp[205][205];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> tx >> ty;
    for(int i = 1; i <= n; i++) cin >> v[i].a >> v[i].b >> v[i].c;
    
    for(int i = 0; i <= 30; i++)
        for(int j = 0; j <= 30; j++) dp[i][j] = INF;

    priority_queue<node, vector<node>, greater<node>> pq;
    dp[0][0] = 0; pq.push({0, 0, 0});
    while(!pq.empty()){
        node cur = pq.top(); pq.pop();
        if(cur.d > dp[cur.x][cur.y]) continue;
        for(int i = 1; i <= n; i++){
            int nx = cur.x + v[i].a, ny = cur.y + v[i].b;
            if(nx <= 30 && ny <= 30 && dp[nx][ny] > cur.d + v[i].c){
                dp[nx][ny] = cur.d + v[i].c;
                pq.push({nx, ny, dp[nx][ny]});
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            ll det = 1LL * v[i].a * v[j].b - 1LL * v[j].a * v[i].b;
            for(int dx = 0; dx <= 30; dx++){
                for(int dy = 0; dy <= 30; dy++){
                    if(dp[dx][dy] == INF) continue;
                    ll rx = tx - dx, ry = ty - dy;
                    if(rx < 0 || ry < 0) continue;
                    if(det != 0){
                        ll na = rx * v[j].b - ry * v[j].a;
                        ll nb = ry * v[i].a - rx * v[i].b;
                        ll d = det;
                        if(d < 0) { d = -d; na = -na; nb = -nb; }
                        if(na >= 0 && nb >= 0 && na % d == 0 && nb % d == 0)
                            res = min(res, dp[dx][dy] + (na / d) * v[i].c + (nb / d) * v[j].c);
                    } else if(1LL * v[i].a * ry == 1LL * v[i].b * rx){
                        ll k = -1;
                        if(v[i].a != 0 && rx % v[i].a == 0) k = rx / v[i].a;
                        else if(v[i].b != 0 && ry % v[i].b == 0) k = ry / v[i].b;
                        else if(v[i].a == 0 && v[i].b == 0 && rx == 0 && ry == 0) k = 0;
                        if(k >= 0) res = min(res, dp[dx][dy] + k * v[i].c);
                    }
                }
            }
        }
    }
    if(res >= INF) cout << -1 << '\n';
    else cout << res << '\n';
    return 0;
}