news 2026/4/7 12:46:59

UVa 111 History Grading

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
UVa 111 History Grading

题目描述

本题源于历史考试评分问题。学生需要将若干历史事件按时间顺序排序。完全正确的排序得满分，但对于部分排序错误的情况，需要给予部分分数。题目要求采用第二种评分方式：
计算学生答案中最长的相对顺序正确的子序列的长度（子序列不必连续，但需保持事件间的相对顺序与正确答案一致）。

输入包含多组测试数据。第一行为事件数n nn（2 ≤ 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）的长度，即为所求得分。

算法步骤

  1. 读入正确答案，建立数组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对应的事件编号。
  2. 对每个学生答案：
    • 将学生答案中每个位置i ii的事件编号转换为该事件的正确排名，得到新序列e v e n t s eventsevents。
    • 在e v e n t s eventsevents序列上计算最长上升子序列的长度。
  3. 输出每个学生答案的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//// 版权所有（C）2011，邱秋。metaphysis # yeah dot net//// [解题方法]// 可以将问题转化为求最长上升子序列的问题。#include<bits/stdc++.h>usingnamespacestd;#defineMAXN25intorder[MAXN],events[MAXN],length[MAXN],n;intlis(void){for(inti=1;i<=n;i++)length[i]=1;for(inti=1;i<=n;i++)for(intj=1;j<i;j++)if(events[j]<events[i]&&(length[j]+1)>length[i])length[i]=length[j]+1;intmaxLength=1;for(inti=1;i<=n;i++)maxLength=max(maxLength,length[i]);returnmaxLength;}intgetIndex(intindex){for(inti=1;i<=n;i++)if(order[i]==index)returni;}intmain(intargc,char*argv[]){string line;intindex;cin>>n;for(inti=1;i<=n;i++){cin>>index;order[index]=i;}cin.ignore(1024,'\n');while(getline(cin,line)){istringstreamiss(line);for(inti=1;i<=n;i++){iss>>index;events[index]=getIndex(i);}cout<<lis()<<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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXN=25;intorder[MAXN],events[MAXN],length[MAXN],n;intlis(){for(inti=1;i<=n;i++)length[i]=1;for(inti=1;i<=n;i++)for(intj=1;j<i;j++)if(events[j]<events[i]&&(length[j]+1)>length[i])length[i]=length[j]+1;intmaxLength=1;for(inti=1;i<=n;i++)maxLength=max(maxLength,length[i]);returnmaxLength;}intmain(intargc,char*argv[]){string line;intindex;order[0]=0;cin>>n;for(inti=1;i<=n;i++){cin>>index;order[index]=i;}cin.ignore(1024,'\n');while(getline(cin,line)){istringstreamiss(line);for(inti=1;i<=n;i++){iss>>index;events[index]=find(order,order+n,i)-order;}cout<<lis()<<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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;vector<int>order,events;intlis(){vector<int>M;M.push_back(events.front());for(autoit=events.begin()+1;it!=events.end();it++)if(*it>M.back())M.push_back(*it);else{autolocation=upper_bound(M.begin(),M.end(),*it);*location=*it;}returnM.size();}intmain(intargc,char*argv[]){intn,index;string line;cin>>n;order.resize(n);events.resize(n);for(inti=1;i<=n;i++){cin>>index;order[index-1]=i;}cin.ignore(1024,'\n');while(getline(cin,line)){istringstreamiss(line);for(inti=1;i<=n;i++){iss>>index;events[index-1]=find(order.begin(),order.end(),i)-order.begin();}cout<<lis()<<'\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容器和算法，代码更简洁。
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/4/1 22:27:45

沙箱环境部署建议：防止恶意代码执行的安全措施

沙箱环境部署建议&#xff1a;防止恶意代码执行的安全措施 在当今 AI 快速渗透到编程与教育领域的背景下&#xff0c;语言模型不仅能回答问题&#xff0c;还能写出可运行的代码。这种能力带来了极大的便利——比如自动解题、智能辅导、即时验证算法思路。但与此同时&#xff0c…

作者头像 李华
网站建设 2026/4/5 12:48:57

爱奇艺影视数据可视化分析|基于Python + Flask爱奇艺影视数据可视化分析系统(源码+数据库+文档)

爱奇艺影视数据可视化分析 目录 基于PythonFlask爱奇艺影视数据可视化分析系统 一、前言 二、系统功能演示 三、技术选型 四、其他项目参考 五、代码参考 六、测试参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 基于PythonFlask爱奇艺影视数据可视化分析…

作者头像 李华
网站建设 2026/3/31 2:30:35

图书管理系统|基于python+Django图书管理系统(源码+数据库+文档)

图书管理系统 目录 基于pythonDjango图书管理系统 一、前言 二、系统功能演示 三、技术选型 四、其他项目参考 五、代码参考 六、测试参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 基于pythonDjango图书管理系统 一、前言 博主介绍&#xff1a;✌️大厂…

作者头像 李华
网站建设 2026/4/2 14:22:24

2.16 关联规则核心概念：支持度、置信度、提升度，3个指标搞定关联分析

2.16 关联规则核心概念：支持度、置信度、提升度，3个指标搞定关联分析 引言 支持度、置信度和提升度是关联规则分析的三个核心指标。理解这三个指标，就能掌握关联规则分析的精髓。本文将深入解析这三个指标的含义、计算方法和应用场景。 一、三个核心指标 1.1 指标定义 #…

作者头像 李华
网站建设 2026/3/31 17:35:37

2.27 集成学习原理深度解析：为什么集成学习是机器学习的终极武器

2.27 集成学习原理深度解析：为什么集成学习是机器学习的终极武器 引言 集成学习通过组合多个模型，往往能获得比单个模型更好的效果。XGBoost、LightGBM、随机森林等都是集成学习的代表。本文将深入解析集成学习的原理，解释为什么它是机器学习的"终极武器"。 一…

作者头像 李华
网站建设 2026/3/29 11:23:57

Swagger UI集成：提供交互式文档体验

Swagger UI集成&#xff1a;提供交互式文档体验 在人工智能模型服务日益普及的今天&#xff0c;一个关键挑战浮出水面&#xff1a;如何让开发者、研究人员甚至非技术用户快速理解并使用复杂的推理模型&#xff1f;尤其是像 VibeThinker-1.5B-APP 这类专注于高难度数学与编程任务…

作者头像 李华