这里以dijkstra为例子

先放代码

int ne[N],ans[N];

if(d[w.y]>d[id]+w.x)
{
    d[w.y]=d[id]+w.x;
    ne[id]=w.y;//这里记录路径的，不过路径是倒着的
}

for(int i=n;i;i=ne[i])ans[++k]=i;
for(int i=k;i;i--)cout<<ans[i]<<' ';//这样正序输出路径

牛客练习赛-A

构造题——思维题

既然放在第一题，但却是构造题，那一定是吓唬人的，所以应该大胆去猜，往简单去想。既然要凑出和为n的序列，那最简单的不就是 $n-1$ 和 $1$ 吗？对于刚好符合题目中的公式。

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,k;
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    cout<<2<<endl;
    cout<<n-1<<' '<<1;

    return 0;
}

牛客练习赛——B

这道题有两个目标是双目标优化问题 通过平均数这个切入点，可以巧妙的想到01背包，对于小于b的自然计入答案，01背包用于处理对于超了平均值这样的情况，背包的容量是处理完没有超过b的，即 $k-b$ 的和，这一部分可以用来装那些超了的，由于平均数的性质，对于超了的物品，其价值自然是a，那其体积呢，是超过的部分，即 $b-k$ ,最后1和2步骤的和即为答案。

注意：数组开的大小，动脑子才不会粗心知道吗！

代码

//B题
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define tep(i,a,b) for(int i=(a);i>=(b);i--)
#define x first
#define y second
using namespace std;
typedef pair<int,int>P;
int n,k;
void solve()
{
    int sum=0,V=0;
    cin>>n>>k;
    //总容量是k-b（比平均值少的） 
    //每一个价值是a，容量则是b-k（比平均值多的）
    //非常巧妙，可以想到01背包用于处理超过平均值的包裹
    vector<P>v;
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        if(b<=k)
        {
            sum+=a;
            V+=k-b;
        }
        else v.push_back({a,b-k});
    }
    vector<int>dp(V+1);
    for(auto [a,b]:v)
    {
        for(int j=V;j>=b;j--)
            dp[j]=max(dp[j],dp[j-b]+a);
    }
    cout<<dp[V]+sum<<endl;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
   while(t--)solve();
   return 0;    
}