企业官网建设流程全解析

建站平台 iis,建设外贸网站注意什么,在线做网站需要什么,可以先做网站后备案么题目描述 本题源于历史考试评分问题。学生需要将若干历史事件按时间顺序排序。完全正确的排序得满分#xff0c;但对于部分排序错误的情况#xff0c;需要给予部分分数。题目要求采用第二种评分方式#xff1a; 计算学生答案中最长的相对顺序正确的子序列的长度#xff08…题目描述本题源于历史考试评分问题。学生需要将若干历史事件按时间顺序排序。完全正确的排序得满分但对于部分排序错误的情况需要给予部分分数。题目要求采用第二种评分方式计算学生答案中最长的相对顺序正确的子序列的长度子序列不必连续但需保持事件间的相对顺序与正确答案一致。输入包含多组测试数据。第一行为事件数n nn2 ≤ n ≤ 20 2 \leq n \leq 202≤n≤20。第二行给出n nn个整数表示正确答案的事件排序注意这里是排名顺序表示事件i ii的正确排名为c i c_ici​。随后每行是学生的答案格式同正确答案。输出每个学生答案的得分即最长符合相对顺序的子序列长度。注意题目中涉及两个关键概念顺序Ordering \texttt{Ordering}Ordering事件按时间排列的顺序。排名Ranking \texttt{Ranking}Ranking事件在顺序中的位置第几位。例如正确答案为1 2 3 4学生答案为1 3 2 4则最长符合的子序列为1 2 4或1 3 4长度为3 33。解题思路问题的本质是求最长公共子序列LCS \texttt{LCS}LCS但经过转换可变为求最长上升子序列LIS \texttt{LIS}LIS从而降低复杂度。关键转换设正确答案的顺序为c 1 , c 2 , . . . , c n c_1, c_2, ..., c_nc1​,c2​,...,cn​c i c_ici​表示事件i ii的正确排名。学生给出的排名序列为r 1 , r 2 , . . . , r n r_1, r_2, ..., r_nr1​,r2​,...,rn​r i r_iri​表示学生给事件i ii的排名。我们要找的是学生序列中相对顺序与正确答案一致的子序列。如果我们将正确答案看作一个从事件到其正确排名的映射即“事件i ii的正确排名为c i c_ici​”那么学生答案中的每个事件i ii对应的正确排名就是c i c_ici​。若学生答案中事件i ii出现在第p o s pospos位则其正确排名为c i c_ici​。我们想找学生序列中一个子序列使得这些事件的正确排名是递增的。因此我们将学生答案的每个位置转换为其事件的正确排名然后在该转换后的序列中求最长上升子序列LIS \texttt{LIS}LIS的长度即为所求得分。算法步骤读入正确答案建立数组o r d e r orderorder使得o r d e r [ r a n k ] e v e n t order[rank] eventorder[rank]event即排名r a n k rankrank对应的事件编号。对每个学生答案将学生答案中每个位置i ii的事件编号转换为该事件的正确排名得到新序列e v e n t s eventsevents。在e v e n t s eventsevents序列上计算最长上升子序列的长度。输出每个学生答案的LIS \texttt{LIS}LIS长度。时间复杂度事件数n ≤ 20 n \leq 20n≤20直接O ( n 2 ) O(n^2)O(n2)的LIS \texttt{LIS}LIS算法完全可行。也可使用O ( n log ⁡ n ) O(n \log n)O(nlogn)的优化算法。参考代码以下是三种实现它们核心思路相同但在数据结构和LIS \texttt{LIS}LIS实现细节上略有差异。实现一此版本使用数组存储LIS \texttt{LIS}LIS采用O ( n 2 ) O(n^2)O(n2)的DP \texttt{DP}DP方法。数组order[rank] event存储正确顺序。getIndex函数用于根据事件编号查找其正确排名。lis函数用动态规划计算最长上升子序列。// History Grading// UVa ID: 111// Verdict: Accepted// Submission Date: 2011-11-25// UVa Run Time: 0.052s//// 版权所有C2011邱秋。metaphysis # yeah dot net//// [解题方法]// 可以将问题转化为求最长上升子序列的问题。#includebits/stdc.husingnamespacestd;#defineMAXN25intorder[MAXN],events[MAXN],length[MAXN],n;intlis(void){for(inti1;in;i)length[i]1;for(inti1;in;i)for(intj1;ji;j)if(events[j]events[i](length[j]1)length[i])length[i]length[j]1;intmaxLength1;for(inti1;in;i)maxLengthmax(maxLength,length[i]);returnmaxLength;}intgetIndex(intindex){for(inti1;in;i)if(order[i]index)returni;}intmain(intargc,char*argv[]){string line;intindex;cinn;for(inti1;in;i){cinindex;order[index]i;}cin.ignore(1024,\n);while(getline(cin,line)){istringstreamiss(line);for(inti1;in;i){issindex;events[index]getIndex(i);}coutlis()endl;}return0;}实现二与实现一类似但使用STL \texttt{STL}STL的find函数替代getIndex代码更简洁。// History Grading// UVa ID: 111// Verdict: Accepted// Submission Date: 2016-02-29// UVa Run Time: 0.003s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN25;intorder[MAXN],events[MAXN],length[MAXN],n;intlis(){for(inti1;in;i)length[i]1;for(inti1;in;i)for(intj1;ji;j)if(events[j]events[i](length[j]1)length[i])length[i]length[j]1;intmaxLength1;for(inti1;in;i)maxLengthmax(maxLength,length[i]);returnmaxLength;}intmain(intargc,char*argv[]){string line;intindex;order[0]0;cinn;for(inti1;in;i){cinindex;order[index]i;}cin.ignore(1024,\n);while(getline(cin,line)){istringstreamiss(line);for(inti1;in;i){issindex;events[index]find(order,ordern,i)-order;}coutlis()endl;}return0;}实现三此版本使用O ( n log ⁡ n ) O(n \log n)O(nlogn)的LIS \texttt{LIS}LIS算法并采用vector存储数据代码更现代化。// History Grading// UVa ID: 111// Verdict: Accepted// Submission Date: 2016-05-10// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorintorder,events;intlis(){vectorintM;M.push_back(events.front());for(autoitevents.begin()1;it!events.end();it)if(*itM.back())M.push_back(*it);else{autolocationupper_bound(M.begin(),M.end(),*it);*location*it;}returnM.size();}intmain(intargc,char*argv[]){intn,index;string line;cinn;order.resize(n);events.resize(n);for(inti1;in;i){cinindex;order[index-1]i;}cin.ignore(1024,\n);while(getline(cin,line)){istringstreamiss(line);for(inti1;in;i){issindex;events[index-1]find(order.begin(),order.end(),i)-order.begin();}coutlis()\n;}return0;}总结本题的关键在于理解“相对顺序正确”等价于“正确排名递增”从而将问题转化为LIS \texttt{LIS}LIS问题。三种实现方法核心相同差异主要在于实现一和实现二使用O ( n 2 ) O(n^2)O(n2)的DP \texttt{DP}DP计算LIS \texttt{LIS}LIS代码清晰易懂。实现三使用O ( n log ⁡ n ) O(n \log n)O(nlogn)的贪心二分优化效率更高且使用STL \texttt{STL}STL容器和算法代码更简洁。