企业官网建设流程全解析

网站模板素材,广告店需要学什么技术,免费行情软件网站下载大全爱,前端网页设计样例【题目描述】童年的我们#xff0c;将和朋友分享美好的事物作为自己的快乐。这天#xff0c;C小朋友得到了Plenty of candies#xff0c;将要把这些糖果分给要好的朋友们。已知糖果从一个人传给另一个人需要1 秒的时间#xff0c;同一个小朋友不会重复接受糖果。由于糖果足…【题目描述】童年的我们将和朋友分享美好的事物作为自己的快乐。这天C小朋友得到了Plenty of candies将要把这些糖果分给要好的朋友们。已知糖果从一个人传给另一个人需要1 秒的时间同一个小朋友不会重复接受糖果。由于糖果足够多如果某时刻某小朋友接受了糖果他会将糖果分成若干份分给那些在他身旁且还没有得到糖果的小朋友们而且自己会吃一些糖果。由于嘴馋小朋友们等不及将糖果发完会在得到糖果后边吃边发。每个小朋友从接受糖果到吃完糖果需要m秒的时间。那么如果第一秒C小朋友开始发糖第多少秒所有小朋友都吃完了糖呢?【输入】第一行为三个数n、p、c为小朋友数、关系数和C小朋友的编号。第二行为一个数m表示小朋友吃糖的时间。下面p行每行两个整数表示某两个小朋友在彼此身旁。【输出】一个数为所有小朋友都吃完了糖的时间。【输入样例】4 3 1 2 1 2 2 3 1 4【输出样例】5【提示】【样例解释】第一秒糖在1手上。第二秒糖传到了2、3的手中。第三秒糖传到了4的手中此时1吃完了。第四秒2、3吃完了。第五秒4吃完了。所以答案是5。【限制】40%的数据满足1≤n≤100;60%的数据满足1≤n≤1000;100%的数据满足1≤n≤100000;m≤n×(n−1)2,不会有同一个关系被描述多次的情况。0. 题目概要有N个小朋友N100,000和P条好友关系。糖果从起点C开始传递每一秒传给相邻的朋友。每个人吃糖需要m秒。求所有人都吃完糖果的时刻。核心转化所有人吃完的时刻 max(每个人拿到糖的时刻m)。问题转化为求起点C到其他所有点的最短路径距离即为时间。1. 算法选型题目中传递时间固定为 1 秒即所有边权均为 1。BFS无权图最优解复杂度O(NP)。Dijkstra (邻接表堆优化)通用性强复杂度O(P log N)本题解采用此方法作为模板练习。2. 深度解析为什么不能开 100 亿数组这是本题最大的思维陷阱。有同学看到N10^5第一反应是“边数上限M最多可能是完全图 N^2 10^10 吗”于是反手开了一个 long long vtex[10000000000] —— 虽然这道题没问题但别的编译器可能将直接导致 MLE或者 CE。这里要讲一个信奥赛场上的“数据规模跷跷板定律”2.1 内存与时间的物理极限如果真的有10^10条边内存10^10*4B *3(数组)约等于120GB。普通比赛限制仅 256MB根本存不下。时间光是cin读取100亿个数就需要好几个小时而比赛时限通常只有1秒。2.2 出题人的平衡在算法题中N点和 M边永远是动态平衡的情形 A稠密图 (M约等于N^2)出题人为了不超时一定会把N限制得很小通常N2000。此时才需要考虑邻接矩阵。情形 B稀疏图 (M与N同量级)当N达到10^5级别时出题人必须限制M的大小通常M只会是N的几倍或几十倍如2*10^5或 50 *10^5。2.3 为什么开100*maxn常规开2*maxn导致tle说明测试数据中边数不少半稠密图。为了防止数组越界我们直接开到100*maxn约 1000 万容量。2.4 为什么没炸内存理论计算1000 万的int数组*3约等于114MB64MB。实际情况利用操作系统的按需分配机制。只要idx指针没有真正推到 1000 万未使用的数组空间就不会占用物理内存。结果既防住了边数过多的RE本题还会造成TLE又利用系统特性躲过了 MLE。结论看到N10^5不要害怕N^2的边数。边数组 (vtex, nxt, wt) 开到 5000000 到 10000000 基本上足够且安全。3. 完整代码//点数10^5量级 用Dijkstra #include iostream #include cstring #include queue using namespace std; int n,p,c,m; const int maxn100010; int h[maxn]; int vtex[100*maxn]; int nxt[100*maxn]; int wt[100*maxn]; int vis[maxn]; int dis[maxn]; int idx; struct node{ int id;//小朋友编号 int w;//到c小朋友的距离 //优先队列默认大根堆重载运算符修改为小根堆 friend bool operator (node a,node b){ return a.wb.w; } }; priority_queuenode q; void dijkstra(int s){ dis[s]1;//这个不能丢 node tmp; tmp.ids; tmp.w1;//第一秒糖在1手上起始就是1秒 q.push(tmp);//起点入队 while(!q.empty()){ tmpq.top(); q.pop(); int nidtmp.id; if(vis[nid]1) continue;//如果tmp已经出队过就跳过 vis[nid]1;//如果没有出队过就打上标记 int ph[nid]; while(p!-1){ if(vis[vtex[p]]0){ if(dis[vtex[p]]dis[nid]wt[p]){ dis[vtex[p]]dis[nid]wt[p]; q.push({vtex[p],dis[vtex[p]]}); } } pnxt[p]; } } } void addedge(int u,int v,int w){ vtex[idx]v; nxt[idx]h[u]; wt[idx]w; h[u]idx; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnpc;//小朋友数 关系数边数 起点 cinm;//吃糖时间 memset(h,-1,sizeof(h));//初始化头指针数组 //邻接表存图 for(int i1;ip;i){ int u,v,w; cinuv; w1;//小朋友传给小朋友需要1s addedge(u,v,w);//双向的 addedge(v,u,w); } for(int i1;in;i) dis[i]0x3f3f3f3f;//初始化每个小朋友到c小朋友距离为无穷 dijkstra(c); int ma0; for(int i1;in;i){//遍历所有朋友找最长时间 if(dis[i]!0x3f3f3f3f) mamax(ma,dis[i]); } coutmam;//输出最长传递时间那个人吃糖果时间 return 0; }