本文主要是介绍Xtu2024程设第三次练习题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1544.中位数
经过尝试每次pop前sort是会超时的（doge）
双堆维护中位数区域，一个大根堆一个小根堆，自己思考一下就知道思路了
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
priority_queue<int>little;
priority_queue<int,vector<int>,greater<int>>bigger;
void check(){if(bigger.size()>little.size()){little.push(bigger.top());bigger.pop();}else if(little.size()>bigger.size()+1){bigger.push(little.top());little.pop();}if(little.empty()){little.push(bigger.top());bigger.pop();}
}
int main(){char op[6];while(scanf("%s",op)!=EOF){int x;if(op[1] == 'u'){scanf("%d",&x);if(little.empty() || x<little.top())little.push(x);else bigger.push(x);check();}else{int res = little.top();little.pop();check();printf("%d\n",res);}}
}1551.二叉树合并
这里对于建树的节点不能用的时候才创建，因为需要提前根据下标进行左右孩子的指向，所以提前为两棵树的100个节点进行内存分配初始化。
其次，在对于储存前序中序结果的数组中，数组大小一定要能够容纳合并前两棵树所有节点的大小（有可能两棵树除了根节点相同，其它点都错位分布）
#include<iostream>
using namespace std;
struct node {int var;node*l;node*r;node(int x): var(x), l(nullptr), r(nullptr) {}
};
node* tree1[110];
node* tree2[110];
node* root;
node* solve(node*a, node*b) {if(a == nullptr)return b;if(b == nullptr)return a;a->var += b->var;a->l = solve(a->l, b->l);a->r = solve(a->r, b->r);return a;
}
void init(){for(int i = 1;i<=100;i++){tree1[i] = new node(0);tree2[i] = new node(0);}
}
int cnt;
int arr[210][2];
void pre(node* x){if(x == nullptr)return ;
// printf("%d\n",x->var);arr[cnt++][0] = x->var;pre(x->l);pre(x->r);
}
void mid(node* x){if(x == nullptr)return ;mid(x->l);arr[cnt++][1] = x->var;mid(x->r);
}
void output(int k){printf("%d",arr[0][k]);for(int i = 1;i<cnt;i++)printf(" %d",arr[i][k]);printf("\n");
}
int main() {init();int t;scanf("%d", &t);while (t--) {int n;cnt = 0;scanf("%d", &n);for (int i = 1; i <= n; i++) {int l, r;scanf("%d%d%d", &tree1[i]->var, &l, &r);if (l)tree1[i]->l = tree1[l];else tree1[i]->l = nullptr;if (r)tree1[i]->r = tree1[r];else tree1[i]->r = nullptr;}
// for(int i = 1;i<=n;i++){
// printf("%d->%d,%d\n",i,tree1[i]->l==nullptr?0:tree1[i]->l->var,tree2[i]->r==nullptr?0:tree1[i]->r->var);
// }scanf("%d", &n);for (int i = 1; i <= n; i++) {int l, r;scanf("%d%d%d", &tree2[i]->var, &l, &r);if (l)tree2[i]->l = tree2[l];else tree2[i]->l = nullptr;if (r)tree2[i]->r = tree2[r];else tree2[i]->r = nullptr;}root = solve(tree1[1], tree2[1]);pre(root);cnt = 0;mid(root);output(0);output(1);}
}1554.二叉查找树
与其说高度，其实不如说成深度更好理解，因为高度来看根节点应该是最高的，对于这题不是最优思路。
根节点视作深度为1，那么很容易想到新增的深度就是它父节点的深度+1，其他操作就是建一棵BST的基本操作吧，没什么思考量
#include<iostream>
using namespace std;
struct node{int var,h;node *l;node *r;node(int v,int h):var(v),h(h),l(nullptr),r(nullptr){}
};
int ans , n;
node *root;
void insert(int cur,node *fa){if(cur<fa->var){if(fa->l)insert(cur,fa->l);else {ans += fa->h+1;fa->l = new node(cur,fa->h+1);}}else{if(fa->r)insert(cur,fa->r);else {ans += fa->h+1;fa->r = new node(cur,fa->h+1);}}
}
void build(){int x;scanf("%d",&x);root = new node(x,1);for(int i = 1;i<n;i++){scanf("%d",&x);insert(x,root);}
}
int main(){int t;scanf("%d",&t);while(t--){ans = 1;scanf("%d",&n);build();printf("%d\n",ans);}
}1557.树
我个人喜欢prim算法一些，只用排序、然后找连通分支，最后取边（最小生成树的套路，只不过每次取边都从大的开始取。）
#include<iostream>
#include<algorithm>
using namespace std;
struct node{int a,b,w;
};
node v[20010];
int fa[2010];
bool cmp(node a,node b){return a.w>b.w;
}
int find(int a){ //找连通分支
//并查集中的递归写法if(fa[a] == a)return a;fa[a] = find(fa[a]);return fa[a];
}
int n,m,all,maxTree;
int main(){int t;scanf("%d",&t);while(t--){all = maxTree = 0;scanf("%d%d",&n,&m);for(int i = 0;i<m;i++){int a,b,w;scanf("%d%d%d",&a,&b,&w);all+=w;v[i].a = a;v[i].b = b;v[i].w = w;fa[a] = a;fa[b] = b;// 初始化每个点的连通分支根为自己（没取这条边的话，这两个点显然暂时不是一个分支）}sort(v,v+m,cmp);int k = 0,cnt = 0;while(cnt<n-1){int fx = find(v[k].a),fy = find(v[k].b);if(fx!=fy){// 每次找分支都是递归查询，只需要改根节点间的连通关系，其他相关点在之后的查询中会自动更新fa[fy] = fa[fx];cnt++;maxTree += v[k].w;}k++;}printf("%d\n",all-maxTree);}
}1563.名次
这题一开始是真没看出floyd，但能擦点边
（要能知道每个点两两间的关系，因为对于一个点，我们要确定它的名次上下限，我们只需要知道他一定比谁高，一定比谁低就行，其他的我们不在乎，那么其实floyd也呼之欲出了）
#include<iostream>
#include<memory.h>
using namespace std;
bool v[210][210];
int to[210], in[210], n, m;
void init() {scanf("%d%d", &n, &m);memset(v,0,sizeof v);for (int i = 1; i <= n; i++)to[i] = in[i] = 0;for (int i = 0; i < m; i++) {int a, b;scanf("%d%d", &a, &b);v[a][b] = 1;to[a]++;in[b]++;}
}
int main() {int t;scanf("%d", &t);while (t--) {init();for(int k = 1;k<=n;k++){for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){if(!v[i][j] && v[i][k] && v[k][j]){to[i]++;in[j]++;v[i][j] = 1;}}}}for(int i = 1;i<=n;i++)printf("%d %d\n",1+in[i],n-to[i]);if(t)printf("\n");}
}1564.黑白树
其实就是一个基于二叉查找树和后序遍历二叉树的套壳题
首先根据题目数字序列将树建出来（注意给节点标上id，或者用数组节点的办法）
然后分析一下怎么判断一个点作为根节点是否能作为一棵黑白树，它只需要满足下面两个条件：
1.左右子树均为黑白树（如果左右子节点为空则无需判断）
2.加上当前根节点的颜色后，黑白颜色数之差仍然不超过1
那显而易见的，要判根得先判“子根”，根据树的遍历方法，毫无疑问选择后序遍历，那么这题就结束了
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
//这里的white和black都是包含当前节点颜色的
//val为该节点的值，在建树时用到
//id为该点序号，用于输出结果int white,black,id,val;bool sign;node* left;node* right;node(int x,int id):white(0),black(0),id(id),val(x),sign(true),left(nullptr),right(nullptr){}
};
char color[1010];
node* root;
int n,ans[1010],cnt,maxn;
void insert(int x,int id,node *var){if(x<var->val){if(!var->left)var->left = new node(x,id);else insert(x,id,var->left);}if(x>var->val){if(!var->right)var->right = new node(x,id);else insert(x,id,var->right);}
}
void init(){scanf("%d",&n);int x;scanf("%d",&x);root = new node(x,1);for(int i = 1;i<n;i++){scanf("%d",&x);insert(x,i+1,root);}scanf("%s",color);cnt = maxn = 0;
}
void afterOrder_find(node*cur){if(!cur)return;afterOrder_find(cur->left);afterOrder_find(cur->right);int w = 0,b = 0;if(cur->left){w += cur->left->white;b += cur->left->black;}if(cur->right){w += cur->right->white;b += cur->right->black;}
// printf("%d节点，该节点以下的白：%d,黑：%d\n",cur->id,w,b);if(color[cur->id-1] == '0')b++;else w++;cur->white = w;cur->black = b;bool s1 = cur->left ? cur->left->sign:true,s2 = cur->right?cur->right->sign:true;
// printf("%d节点，该节点以下的白：%d,黑：%d\n",cur->id,w,b);if(s1&&s2&&abs(w-b)<2){int res = w+b;if(res == maxn)ans[cnt++] = cur->id;else if(res>maxn){maxn = res;ans[0] = cur->id;cnt = 1;}}else cur->sign = false;
}
int main() {int t;scanf("%d", &t);while (t--) {init();afterOrder_find(root);sort(ans,ans+cnt);printf("%d\n%d",maxn,ans[0]);for(int i = 1;i<cnt;i++)printf(" %d",ans[i]);printf("\n");}
}1579.完全二叉排序树
个人感觉和练习二那个差不太多。改成建树的写法试一试，也是很短的代码就能过
#include<iostream>
using namespace std;
struct node{int var;node*l;node*r;node(int a):var(a),l(nullptr),r(nullptr){}
};
node* root;
int n,x,maxn;
void insert(node*v,int d){if(x<v->var){if(v->l)insert(v->l,d<<1);else maxn = max(d<<1,maxn),v->l = new node(x);}if(x>v->var){if(v->r)insert(v->r,d<<1|1);else maxn = max(d<<1|1,maxn),v->r = new node(x);}
}
void init(){
//初始化一定要为1，不然只有一个节点的时候会WAmaxn = 1;scanf("%d%d",&n,&x);root = new node(x);for(int i = 1;i<n;i++){scanf("%d",&x);insert(root,1);}
}
int main(){int t;scanf("%d",&t);while(t--){init();printf("%d\n",maxn-n);}
}1580.病毒
堆优化后的dijkstra，花了一会看了几篇博客学习了一下。比较推荐的cpp模版博客
基本原理就是每次从源点可到达边中选最小的，不再枚举，而是用优先队列，每次被更新距离的边都添加到优先队列中，（没被添加到优先队列中的边一律视为不可到达），有的边可能被多次添加到队列中，但由于这个最小堆的缘故，从队头取的一定目前所有情况中能到这个点的最短边。
（因为可能到某个点的距离被若干点同时更新，理论上也就是越后更新的，距离是越小的，也就是说其实如果存在多条边到同一个点，我们要取的正是最后添加到队列的那一个，优先队列很好的帮我们解决了这个问题，同时我们每次取的也是所有可到达边中的最小边，满足了dijkstra的算法原理）
代码相对于原始的dijkstra写法，主要在于邻接矩阵改写为邻接表，需要创建一个表示点到边的结构体（表示当前点到目标点[to]的距离[w]），结构体中需要重载小于运算符（用于改写优先队列的排序方式）
由于我们结构体只是表示当前点到目标点的距离，所以在邻接图中添加边时，两个点要互换各自添加一遍
!dist[i]表示i点当前无法通过源点达到
#include<iostream>
#include<queue>
#include<vector>
#include<memory.h>
using namespace std;
struct node{int to,w;node(int _to,int _w):to(_to),w(_w){}inline bool operator<(const node &x)const{return w>x.w;}
};
int dist[10010],vis[10010];
int n,e,k;
void dijkstra(){priority_queue<node>q;scanf("%d%d%d",&n,&e,&k);vector<vector<node>>v(n+1);memset(dist,0,sizeof dist);for(int i = 1;i<=e;i++){int a,b,w;scanf("%d%d%d",&a,&b,&w);v[a].push_back(node(b,w));v[b].push_back(node(a,w));}for(int i = 1;i<=k;i++){int x;scanf("%d",&x);q.push(node(x,0));}while(!q.empty()){node cur = q.top();q.pop();if(vis[cur.to])continue;int aim = cur.to;vis[aim] = 1;dist[aim] = cur.w;for(node i:v[aim])if(!dist[i.to] || dist[i.to]>dist[aim]+i.w)q.push(node(i.to,dist[aim]+i.w));}printf("%d",dist[1]);for(int i = 2;i<=n;i++)printf(" %d",dist[i]);printf("\n");
}
int main(){dijkstra();
}1582.篮球与足球
我感觉是要反复想一下状态转移，主要思考点：
1.当天开的场馆，如果要训练该项目，是如何受到前两天训练的影响的？
2.当天训练项目是如何影响后续的？后续练习能否影响当天训练？
3.如果两个场馆都开放，对后续是否一定有影响？有的话该怎么处理？没有又该如何处理？
#include<iostream>
#include<string.h>
#include<memory.h>
using namespace std;
int dp[10010][2];
char str[10010];
// dp[i][j]，i表示第i天,j=0表示练足球，j=1表示练篮球,dp[i][j]表示已经练了多少天的篮球/足球
// 能练就练，今天能不能练只取决于前两天是否练了同一个项目和场地是否开放
void influence(int i,int k,bool s){if(s)dp[i][k]++,dp[i+1][k]++,dp[i+2][k]++;
}
int main(){int t;scanf("%d",&t);while(t--){memset(dp,0,sizeof dp);scanf("%s",str);int ans = 0,len = strlen(str);for(int i = 0;i<len;i++){bool s0 = dp[i][0] == 2?false:true,s1 = dp[i][1] == 2?false:true;if(i)dp[i][0] = dp[i-1][0],dp[i][1] = dp[i-1][1];if(str[i] == '1')influence(i,1,s1);if(str[i] == '2')influence(i,0,s0);if(str[i] == '3'){//如果当前不受前面任何约束，那么也不会影响后面的 01X** 如果星号是两个1或者两个0，其实X可以灵活切换，此时将锻炼天数直接+1//如果受了前面约束，那么就相当于今天只开放了一个馆，按只开了一个馆的处理来if(s0&&s1)ans++;else{if(s0)influence(i,0,s0);if(s1)influence(i,1,s1);}}}printf("%d\n",ans+dp[len-1][0]+dp[len-1][1]);}
}1245.Lisa's Puzzle
看了下居然是去年自己做过的题。。已然全部忘记。。后缀前缀这种用字典树做，以后一定记得（doge）
这题直接用hash也能水过去，慢但不至于TLE（doge）
#include<iostream>
#include<unordered_map>
using namespace std;
int arr[1000100];
int pre[34];
unordered_map<int, int>mp;
int main() {pre[0] = 1;for (int i = 1; i <= 31; i++)pre[i] = pre[i - 1] << 1;pre[31]--;
// for(int i = 1;i<=31;i++)printf("%d-%d\n",i,pre[i]);int n;scanf("%d", &n);for (int i = 0; i < n; i++) {int x, cnt = 0, tmp = 0;scanf("%d", &x);arr[i] = x;if (x > 1 && !(x & 1))mp[0]++;while (x > 1) {if (x & 1) {tmp += pre[cnt];mp[tmp]++;}x >>= 1;cnt++;}}for (int i = 0; i < n; i++)printf("%d\n", mp[arr[i]]);
}1473.通讯网络
这题是真的很难绷。是我目前唯一一个看详细题解的图论题。
因为题目中没有说，在不建立无限电站的情况下也能保证图的连通性，就导致这个问题要一边连一边考虑无限电站的情况，然后就越想越复杂，然后就破防看题解（bushi）
实现题解的做法是很容易的，但是重新加上上面那个连通性条件，仍然应该好好想想为什么这么做
1.为什么无线电站的出现会让我们增加一个源点？
2.为什么要分有无无线电站，分别跑两次最小生成树算法？
3.为什么与源点连接路径大于1就一定是在有无线电站时取得答案？反之则是无无线电站时？
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node {int u,v,w;
};
bool cmp(node a,node b){return a.w<b.w;
}
node way[60010];
int n, m,fa[10010];
int find(int x){if(x==fa[x])return x;fa[x] = find(fa[x]);return fa[x];
}
int mst(int num,int end) {sort(way,way+end,cmp);//[0,end)区间上取边int ans = 0,p = 0;for(int i = 1;i<num;i++){while(1){int u = way[p].u,v = way[p].v;int fx = find(u),fy = find(v);if(fx!=fy){fa[fy] = fx;ans += way[p].w;break;}else p++;}p++;}return ans;
}
int main() {int t;scanf("%d", &t);while (t--) {scanf("%d%d", &n, &m);for(int i = 0;i<n;i++){int w;scanf("%d",&w);way[m+i].u = 0;way[m+i].v = i+1;way[m+i].w = w;fa[i+1] = i+1;}for (int i = 0; i < m; i++)scanf("%d%d%d", &way[i].u, &way[i].v, &way[i].w);int a = mst(n,m);for(int i = 0;i<=n;i++)fa[i] = i;int b = mst(n+1,n+m);printf("%d\n",min(a,b));}
}1533.Longest Peak Sequence
这题一眼dp，然后其实就是找两个单调最长子序列，用双指针可以只跑一个循环便得出所有点的左右最长单调序列。
#include<iostream>
using namespace std;
int arr[1010], l[1010],r[1010];
int main() {int t;scanf("%d", &t);while (t--) {int n,ans = 0;scanf("%d",&n);for(int i = 0;i<n;i++)scanf("%d",&arr[i]),l[i] = r[i] = 0;for(int i = 0;i<n;i++){for(int j = 0;j<i;j++){int p = n-i-1,q = n-j-1;if(arr[j]<arr[i]) l[i] = max(l[i],l[j]+1);if(arr[q]<arr[p])r[p] = max(r[p],r[q]+1);if(l[i]&&r[i])ans = max(ans,l[i]+r[i]+1);if(l[p]&&r[p])ans = max(ans,l[p]+r[p]+1);}}printf("%d\n",ans);}
}1540.String
思路很简单，在B串中选前i个字符，C串中选前j个字符，判断当前是否能构成A串的第i+j位，如果可以那么标记dp[i+1][j] = 1或者 dp[i][j+1] = 1
dp[i][j]的意义，我这里觉得表示为在A串的（i+j-1）个字符可由B+C构成，也就是A串a[i+j]能否被判断的大前提。。。
总之很绕，感觉循环写起来总感觉怪怪的，，，按自己理解来写吧
#include<iostream>
#include<memory.h>
#include<string.h>
using namespace std;
bool dp[210][210];
char a[205],b[205],c[205];
int main() {while(scanf("%s%s%s",a,b,c)!=EOF){memset(dp,0,sizeof dp);int l1 = strlen(a),l2 = strlen(b),l3 = strlen(c);dp[0][0] = 1;for(int i = 0;i<=l2;i++){for(int j = 0;j<=l3;j++){if(dp[i][j]){if(a[i+j] == b[i])dp[i+1][j] = 1;if(a[i+j] == c[j])dp[i][j+1] = 1;}}}if(l1==l2+l3 && dp[l2][l3])printf("Yes\n");else printf("No\n");}
}1562.最长单调上升子区间（补题）
补题自然是看了题解，会普通的单调子区间之类的问题应该就能做出来
#include<iostream>
#include<vector>
using namespace std;
vector<int> arr1(220), arr2(220) ;
vector<int> cnt1(220), cnt2(220) ;
vector<int> dp1(220), dp2(220) ;
int n, maxn, ans;
void count(vector<int>&nums,vector<int>&true_cnt,vector<int>&true_dp, int s, int e) {
//每个判断区间使用全新的dp和cnt数组，避免区间之间的干扰vector<int>dp(2*n + 1, 1);vector<int>cnt(2*n + 1, 1);for (int i = s; i <= e; i++) {for (int j = s; j < i; j++) {if (nums[j] < nums[i]) {if (dp[j] + 1 > dp[i]) {cnt[i] = cnt[j];dp[i] = dp[j] + 1;} else if (dp[j] + 1 == dp[i]) {cnt[i] += cnt[j];}}}
//汇总当前区间与全局之间的关系
//对于每一个点保证当前的true_cnt都来自于一个区间，同时也对应了这个区间的true_dpif(dp[i] > true_dp[i]){true_dp[i] = dp[i];true_cnt[i] = cnt[i];}maxn = max(maxn,true_dp[i]);}
}void solve() {for (int i = 1; i <= n; i++) {int x;scanf("%d", &x);dp1[i] = dp2[i] = cnt1[i] = cnt2[i] = dp1[i+n] = dp2[i+n] = cnt1[i+n] = cnt2[i+n] = 0;arr1[i] = arr1[n + i] = x;arr2[n - i + 1] = arr2[2 * n - i + 1] = x;}
//枚举n个区间，顺时针逆时针写一起for (int i = 1; i <= n; i++) {count(arr1, cnt1,dp1, i, i + n);count(arr2, cnt2,dp2, i, i + n);}
//枚举所有点位，统计全局结果for(int i = 1;i<=2*n-1;i++){if(dp1[i] == maxn)ans += cnt1[i];if(dp2[i] == maxn)ans += cnt2[i];}
}
int main() {int t;scanf("%d", &t);while (t--) {ans = maxn = 0;scanf("%d", &n);solve();printf("%d %d\n", maxn, ans);}
}1569.禁区
这题算法其实和1580病毒没什么差别，但是也暴露了我那份代码的一个bug，优先队列应该按当前距离源点的距离进行排序，也就是其实应该插入dist的距离，而不是插入边的距离（这个bug是我记录里wa的主要原因）
另外代码修改上，改掉了结构体写法，感觉确实不如pair简洁易懂
pair的比较原则是先比较first，如果first相等则比较second，那么我们就需要把权值放在frist，而连通的点放在second，那么其他地方就没什么区别了
#include<iostream>
#include<queue>
#include<vector>
#include<memory.h>
#define maxn 1010
using namespace std;;
typedef pair<int, int> PII;
// 权值，点
vector<vector<PII>>v(maxn);
vector<int>ans(maxn);
vector<int>org_dist;
//change记录当前变化量，cnt记录答案个数，RES用来传递dijkstra中记录的1到除禁区之外的其他城市的最短路权值和，避免再次枚举求和
int n, m, cost, RES, change = 0, cnt = 0;
// 一个不经过x点，并返回最终堆优化dijkstra的dist数组
vector<int> solve(int x) {priority_queue<PII, vector<PII>, greater<PII>>q;vector<int>dist(n + 1, INT_MAX);vector<bool>vis(n+1,0);//不再经过x点，也不往队列中添加任何x有关的边vis[x] = 1;dist[x] = 0;//一个临时的表示到各点最短路距离的数组int res = 0, p = 0;//res记录最短路的和，p记录目前连通点的数目，用于判断是否连通q.push({0, 1});dist[1] = 0;while (!q.empty()) {PII var = q.top();q.pop();int to1 = var.second;if (vis[to1])continue;p++;vis[to1] = 1;res += dist[to1];//如果最短距离被更新，那么加入优先队列for (auto i : v[to1]) {int to2 = i.second;if (dist[to2] > dist[to1] + i.first)dist[to2] = dist[to1] + i.first, q.push({dist[to2], to2});}}if (p < n - 1)RES = INT_MAX;else RES = res;//连通的点不足n-1时RES为INT_MAXreturn dist;
}
int main() {scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {int a, b, w;scanf("%d%d%d", &a, &b, &w);v[a].push_back({w, b});v[b].push_back({w, a});}//org_dist用于记录原通路下1到每个点的最短路权值//禁区为0相当于不禁用任何点org_dist = solve(0);
// int a = 0;
// for(int i = 1;i<=n;i++)a+=org_dist[i],printf("-----当前节点%d，最短路为%d\n",i,org_dist[i]);cost = RES;
// printf("%d\n",a==cost);
// return 0;for (int i = 2; i <= n; i++) {solve(i);if (RES == INT_MAX) {if (change != INT_MAX)change = INT_MAX, cnt = 0;ans[cnt++] = i;} else {int res = cost - org_dist[i];//去掉到禁区的最短路权值int ch = abs(res - RES);//计算最短路权值和的变化量if (ch > change)cnt = 0, change = ch;if (ch == change)ans[cnt++] = i;}}if (change == 0)printf("None\n");else {//由于是从小到大枚举禁区，所以答案数组无需排序printf("%d", ans[0]);for (int i = 1; i < cnt; i++)printf(" %d", ans[i]);}return 0;
}1571.天平（补题）
搜了下是某年蓝桥杯改编题，典型01背包
#include<iostream>
#include<vector>
using namespace std;
int fm[110] , n , k, limit;
int solve(){int ans = 0;vector<bool>vis(limit+1,0);vector<int>dp(limit+1,k+1);vector<int>tmp(limit+1);dp[0] = 0;
//这里为什么引入tmp保留上一行数据请自己参考滚动数组优化内存的原理
//我觉得仅仅将内层循环改为逆序也是不太对的。。。不知道为什么能过（但这个代码同样能过）for(int i = 1;i<=n;i++){for(int j = 1;j<=limit;j++)tmp[j] = dp[j];for(int j = limit;j>=1;j--){dp[j] = min(dp[j],tmp[abs(j-fm[i])]+1);if(j+fm[i]<=limit)dp[j] = min(dp[j],tmp[j+fm[i]]+1);if(dp[j] <= k && !vis[j])ans ++,vis[j] = 1;}}return ans;
}
int main() {int t;scanf("%d",&t);while(t--){limit = 0;scanf("%d%d",&n,&k);for(int i = 1;i<=n;i++)scanf("%d",&fm[i]),limit += fm[i];printf("%d\n",solve());}
}1588.火车与汽车
谢大这里题解写的很明白了，但不看我是真没想到。。
原先我们读入一组边，只需要往邻接图插两次，现在需要插8次。。。（这里建议自己想，因为题解唯一的思考点且不难，所以..）
#include<iostream>
#include<queue>
#include<vector>
#define to second
#define w first
using namespace std;
typedef pair<int,int> PII;
int n, m;
void add(vector<vector<PII>>&v,int s,int e,int dis1,int dis2){v[s].push_back({dis1,e});v[s+n].push_back({dis2,e});v[e].push_back({dis1,s});v[e].push_back({dis2,s+n});
}
void dijk() {scanf("%d%d", &n, &m);priority_queue<PII,vector<PII>,greater<PII>>q;vector<vector<PII>>v(2*n+1);vector<int>dist(2* n + 1, 1e9);vector<bool>vis(2 *n + 1, 0);for (int i = 0; i < m; i++) {int a, b, d, k;scanf("%d%d%d%d", &a, &b, &d, &k);if(k)add(v,a,b+n,d+1,d),add(v,b,a+n,d+1,d);else add(v,a,b,d,d+1),add(v,b,a,d,d+1);}q.push({0,1});q.push({0,1+n});dist[1]=0;dist[1+n]=0;while (!q.empty()) {PII var = q.top();q.pop();int to1 = var.to;if (vis[to1])continue;vis[to1] = 1;for (PII i : v[to1]) {int to2 = i.to;if (dist[to2] > dist[to1] + i.w)dist[to2] = dist[to1] + i.w, q.push({dist[to2],to2});}}printf("%d",min(dist[2],dist[2+n]));for(int i = 3;i<=n;i++)printf(" %d",min(dist[i],dist[i+n]));printf("\n");
}
int main() {int t;scanf("%d", &t);while (t--)dijk();return 0;
}这篇关于Xtu2024程设第三次练习题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
