说在后面:
因为此次考试, 不晓得是哪位信安的大哥把学校的 OJ 平台给黑掉了, 导致咱们 100 来人同时登陆不上 OJ, 考试被迫终止半小时. 然而因为少部分同学刚开始登录下来了一小会, 看到了题目 (比方我), 所以为了偏心起见, 学校从新换了一套题.
上面我把两套题以及相应题解放在上面, 供大家学习参考!
A 卷:
1. 凯撒加密法
题目形容:
凯撒加密法，或称恺撒加密、恺撒变换、变换加密，是一种最简略且最广为人知的加密技术。它是一种替换加密的技术，明文中的所有字母都在字母表上向后（或向前）依照一个固定数目进行偏移后被替换成密文。
例如，当偏移量是左移 3 的时候：明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC
应用时，加密者查找明文字母表中须要加密的音讯中的每一个字母所在位置，并且写下密文字母表中对应的字母。须要解密的人则依据当时已知的密钥反过来操作，失去原来的明文。例如：
明文：THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
密文：WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ
当初给定你一个字符串 S（长度不会超过 1000000）和一个整数 k（-1000000000<=k<=1000000000），别离代表接受者收到的密文和在加密该密文时向后的偏移量，你的工作是计算出原来的明文
留神：只有字母在加密时才会产生偏移，其它字符放弃不变.
输出:
输出蕴含多组数据，其中第一行为数据组数 T（T<=10）
每组数据第一行为一个字符串 S，由数字、字母以及常见字符组成（不含空格），第二行为一个整数 k 代表加密时向后的偏移量（|S|<=1000000,-1000000000<=k<=1000000000）
输入:
对每组数据，输入一行字符串，代表输出中的密文对应的明文。
样例输出:
1
DEFGHIJKLMNOPQRSTUVWXYZABC
3样例输入:
ABCDEFGHIJKLMNOPQRSTUVWXYZ题解:
水题, 只须要简略变换一下字符的地位即可.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
string str;
cin>>str;
int k;
cin>>k;
int n = str.size();
for(int i=0; i<n; i++)
{str[i] = 'A' + (str[i]-'A'-k+26)%26;
}
cout<<str<<endl;
}
return 0;
}2. 跳跃游戏Ⅱ
题目形容:
给定一个非负整数数组，假设你的初始地位为数组第一个下标。数组中的每个元素代表你在那个地位可能跳跃的最大长度。你的指标是达到最初一个下标，并且应用起码的跳跃次数。例如：A = [2,3,1,1,4]，达到最初一个下标的起码跳跃次数为 2。（先跳跃 11 步，从下标 0 到 1，而后跳跃 3 步，达到最初一个下标。一共两次）
输出:
第一行输出一个正整数 n(1≤n≤100)，接下来的一行，输出 n 个整数，示意数组 A。
输入:
最初输入起码的跳跃次数。
样例输出:
5
3 1 1 1 1样例输入:
2题解:
这道题和之前在力扣上做过的题一样的, 比较简单. 如果某一个作为 起跳点 的格子能够跳跃的间隔是 3，那么示意前面 3 个格子都能够作为 起跳点. 能够对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的间隔不断更新。
如果从这个 起跳点 起跳叫做第 1 次 跳跃，那么从前面 3 个格子起跳 都 能够叫做第 2 次 跳跃。
所以，当一次 跳跃 完结时，从下一个格子开始，到当初能跳到最远的间隔，都 是下一次 跳跃 的 起跳点。
对每一次 跳跃 用 for 循环来模仿。跳完一次之后，更新下一次 起跳点 的范畴。在新的范畴内跳，更新 能跳到最远的间隔. 记录 跳跃 次数，如果跳到了起点，就失去了后果。
#include<bits/stdc++.h>
using namespace std;
int Jump(vector<int> &nums)
{int n = nums.size();
int start = 0; // 每一轮起跳的起跳点
int end = 0; // 每一轮跳跃可能达到的最远
int Max_pos = 0;
int ans = 0; // 记录跳跃次数
while(Max_pos < n-1)
{for(int i=start; i<=end; i++) // 不断更新可能跳跃的最远距离
{Max_pos = max(Max_pos, i+nums[i]);
}
start = end+1; // 上一轮跳跃达到起点之后, 从新赋值给起跳点
end = Max_pos; // 更新此次跳跃最远可能达到的间隔
ans++;
}
return ans;
}
int main()
{
int n;
cin>>n;
vector<int> nums(n);
for(int i=0; i<n; i++) cin>>nums[i];
cout<<Jump(nums)<<endl;
return 0;
}3.LongestMatch
题目形容:
一家新成立的侦探事务所正在利用无限的情报搜集侦探之间的机密情报传递技术。因为他们是这个行业的新人，他们很分明本人的信息很容易被其余群体捕捉并批改。他们想通过查看音讯的更改局部来猜想其余组的用意。首先，他们必须失去最长匹配的长度。你要帮忙他们。
输出:
输出文件可能蕴含多个测试用例。每个 case 将蕴含两个间断的字符串行。可能呈现空白行和非字母打印标点字符。每一行字符串将不超过 1000 个字符。每个单词的长度不能超过 20 个字符。
输入:
对于每一种输出，您都必须输入一行，以字段宽度为 2 的无右对齐大小写结尾，而后是最长的匹配，如示例输入所示。如果每个输出至多有一个空行，则输入 ’ blank !’。将非字母标点字符视为空白。
样例输出:
This is a test.
test
Hello!
The document provides late-breaking information
late breaking.样例输入:
1. Length of longest match: 1
2. Blank!
3. Length of longest match: 2题解:
我最后的想法很简略, 那就是先把两个字符串宰割贮存到两个容器中, 而后对于其中一个容器, 顺次取出其中一个元素, 查找是否存在于另一个容器中. 最初失去答案.
#include<bits/stdc++.h>
using namespace std;
vector<string> split(string str) // 将一个字符串从空格处离开, 非字符也算作空格
{
vector<string> vec;
int len = str.length();
bool flag = true; // 示意一个新单词开始与否
int start = 0; // 每个单词开始的下标
for(int i=0; i<len; ++i)
{if(flag && isalpha(str[i]))
{
flag = false;
start = i;
}
else if(!isalpha(str[i]))
{
flag = true;
vec.push_back(str.substr(start, i-start));
}
}
if(flag == false) vec.push_back(str.substr(start, len-start)); // 最初一个为字母的话
return vec;
}
int LongestMatch(vector<string> vec1, vector<string> vec2)
{
int ans = 0;
int size = vec2.size();
for(int i=0; i<size; i++)
{if(find(vec1.begin(), vec1.end(), vec2[i]) != vec1.end()) ans++;
}
return ans;
}
int main()
{
string str1, str2;
int i=1;
while(getline(cin, str1) && getline(cin, str2))
{if(str1.empty() || str2=="")
{printf("%2d.", i++);
cout<<"Blank!"<<endl;
continue;
}
vector<string> vec1, vec2;
vec1 = split(str1);
vec2 = split(str2);
printf("%2.d", i++);
cout<<"Length of longest match:"<<LongestMatch(vec1, vec2)<<endl;
}
return 0;
}4.Schedule
题目形容:
有 N 个时间表，第 i 个时间表有开始工夫 si 和完结工夫 ei (1 <= i <= N)。每两个重叠的时间表不能在同一台机器上执行。对于每台机器，工作工夫定义为 timeend 和 timestart 之间的差值，其中 time_{end}是敞开机器的工夫，timestart 是关上机器的工夫。咱们假如机器不能在工夫开始和工夫完结之间敞开。打印执行所有打算的最小机器数 K，当只应用 K 台机器时，打印所有工作工夫的最小总和。
输出:
第一行蕴含一个整数 T (1 <= T <= 100)，示意测试用例的数量。每一种状况都以蕴含一个整数 N (0<N<=100000)。接下来的 N 行蕴含两个整数 si 和 ei (0<=si<ei<=1e9)。
输入:
对于每个测试用例，打印最小可能的机器数量和所有工作工夫的最小总和
样例输出:
1
3
1 3
4 6
2 5样例输入:
2 8题解:
贪婪算法, 思路:
咱们要晓得, 本题不仅要求所须要的机器数, 还要求总工夫. 总工夫由每个工作的工夫加上机器期待的工夫.
咱们先进行一个非凡的排序, 首先将每个工作的开始工夫和完结工夫都拆分掉, 如果一共有 n 个工作, 那么咱们将失去 2 * n 个节点. 每个节点有两个信息, 一个是工夫 Time, 一个是标记 Flag(用来表明该节点是开始工夫还是完结工夫). 而后进行从小到大的排序, 咱们还要留神一点的是, 如果有两个节点的工夫雷同, 那么是完结工夫的那个放后面. 这很显然, 因为
每次新增加一个工作时, 都抉择当初已有机器中完结工夫最晚的(用一个栈来实现), 这样咱们就会失去最短的等待时间.
// Schedule
// 贪婪算法
// 题目粗心: 有 N 个时间表，他们别离有本人的开始工夫和完结工夫，// 同时，也有很多机器，时间表上的工夫是应用机器的工夫，然而，// 一台机器不能在反复的工夫被应用，所以，要实现时间表的工作，可能须要多台机器，// 题目要求的就是符合要求的起码机器数和相应工夫之和(机器期待的工夫也算)。#include<bits/stdc++.h>
using namespace std;
struct Node
{
int T;
int flag; // 1 示意该节点是开始工夫,2 示意是完结工夫
}nodes[3000];
bool cmp(Node &a, Node &b)
{if(a.T != b.T) return a.T<b.T;
else return a.flag > b.flag; // 如果两个工夫雷同, 是完结工夫的那个放后面. 很显然, 在这之前必定有一个与它对应的开始工夫. 这个工作曾经实现.
}
int main()
{
int x;
scanf("%d", &x);
while(x--)
{
int count;
int pos = 0; // 示意节点数组的地位
int machine = 0;
int ans_mach = 0;
long long ans_sum = 0;
stack<int> endtime; // 完结时刻寄存在栈中
scanf("%d", &count);
while(!endtime.empty()) endtime.pop(); // 保障 endtime 数组清空
for(int i=0; i<count; i++)
{scanf("%d", &nodes[pos].T);
scanf("%d", &nodes[pos+1].T);
nodes[pos].flag = 1;
nodes[pos+1].flag = 2;
ans_sum = ans_sum + (nodes[pos+1].T - nodes[pos].T); // 先把所有工作工作的工夫累加
pos += 2;
}
sort(nodes, nodes+pos, cmp); // 从小到大排序
for(int i=0; i<pos; i++)
{if(nodes[i].flag == 1)
{
machine++;
if(!endtime.empty())
{int t = endtime.top();
endtime.pop();
ans_sum += (nodes[i].T - t); // 咱们并不关怀位于栈顶这个完结工夫所对应的开始工夫是哪个, 因为计算等待时间只须要晓得完结工夫即可. 而且依据大小排序之后, 能够保障, 新退出的这个开始工夫肯定能够在任意一台曾经有的机器上工作!(因为目前所有的完结工夫都是小于该开始工夫的, 所以这也是一个咱们不须要关怀 (开始_完结) 对应的一个起因.)
}
}
else
{
machine--;
endtime.push(nodes[i].T);
}
ans_mach = max(ans_mach, machine); // 更新最大机器数
}
printf("%d %lld\n", ans_mach, ans_sum);
}
return 0;
} 5.Wavio Sequence
题目形容:
题目粗心是给出一个数组, 找出该数组中存在的最大 Wavio Sequence 序列长度.
Wavio Sequence 是什么? 很简略, 你看看上面两个例子就明确了!
Wavio 是一个整数序列，具备以下个性：
- Wavio 序列的长度是奇数，即 L = 2 * n + 1
- Wavio 序列前 n+1 个整数是递增序列
- Wavio 序列后 n+1 个整数是递加序列
如示例 1 2 3 4 5 4 3 2 1 10
最长的 Wavio 序列 为 1 2 3 4 5 4 3 2 1，所以答案为 9
输出:
输出文件蕴含少于 75 个测试用例。每个测试用例的形容如下:
每个汇合从一个正整数 N(1<=N<=10000)开始。在接下来的几行中有 N 个整数。
输入:
对于每一组输出，在一行中打印最长的 wavio 序列的长度。
样例输出:
10
1 2 3 4 5 4 3 2 1 10
19
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1
5
1 2 3 4 5样例输入:
9
9
1题解:
1. 奢侈暴力
一看这题, 不就是求最长回升子序列吗? 正着来一遍, 倒着来一遍就能够了.
而后看看哪个地位上二者之和最大, 那么就是答案.
工夫复杂度:0(n^2)
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int inf = 10000;
// 奢侈算法,0(n^2)
vector<int> Compute(vector<int> &nums)
{int n = nums.size();
vector<int> dp(n, 1);
for(int i=0; i<n; i++)
{for(int j=0; j<i; j++)
{if(nums[i]>nums[j])
{dp[i] = max(dp[j]+1, dp[i]);
}
}
}
for(int &x:dp) // 基于范畴的 for 循环中可通过援用批改数组元素中的值，间接批改只是批改正本，原始数组数据不变。{if(x == 1) x = -inf;
}
return dp;
}
int main()
{
int n;
while(cin>>n && n)
{vector<int> nums(n);
for(int i=0; i<n; i++) cin>>nums[i];
vector<int> vec1 = Compute(nums);
reverse(nums.begin(), nums.end());
vector<int> vec2 = Compute(nums);
int max_ans = 1;
for(int i=0; i<n; i++)
{max_ans = max(max_ans, vec1[i]+vec2[n-i-1]-1);
}
cout<<max_ans<<endl;
}
return 0;
}然而可能的话, 会卡工夫.TLE
2. 贪婪算法 + 二分查找
所以想到另一种优化的办法, 通过二分查找和贪婪算法来实现最长回升子序列长度的计算.
这与力扣主站第 300 题 — 最长递增子序列雷同. 咱们次要关注题解的第二种办法, 传送门在这里, 看完之后就很容易了解这一道题目了!
工夫复杂度:O(nlogn)
代码如下:
// 贪婪算法 + 二分查找 求最长回升子序列的长度 O(nlogn)
// 思考一个简略的贪婪，如果咱们要使回升子序列尽可能的长，则咱们须要让序列回升得尽可能慢，因而咱们心愿每次在回升子序列最初加上的那个数尽可能的小。// 保护一个一维数组 B，并且这个数组是动静扩大的，初始大小为 1,B[i]示意最长回升子序列长度是 i 的所有子串中开端最小的那个数，// 咱们顺次遍历数组 nums 中的每个元素，并更新数组 B 和 len 的值。如果 nums[j] > B[len] 则更新 len = len + 1
// 否则在 B[1...len] 中 找到 B[i-1] < nums[j] < B[i]的 pos 值, 而后更新 B[i] = nums[j]
#include<bits/stdc++.h>
using namespace std;
const int inf = 10000;
int lengthOfLIS(vector<int> &nums, int end) // 失去数组 nums[1..end]的最大回升子序列长度
{int n = nums.size();
if(n == 0) return 0;
vector<int> B(n+1, 0);
B[1] = nums[0];
int len = 1; // 记录最长回升子序列的长度
for(int i=1; i<end; ++i)
{if(nums[i] > B[len]) B[++len] = nums[i];
else
{
int l = 1, r = len, pos = 0;
while(l <= r)
{int mid = (l+r) >> 1;
if(B[mid] < nums[i])
{
pos = mid;
l = mid+1;
}
else r = mid-1;
}
B[pos+1] = nums[i];
}
}
return len;
}
int Ans(vector<int> &nums)
{int n = nums.size();
vector<int> LIS_length;
vector<int> LIS_length_Reverse;
for(int i=1; i<=n; i++)
LIS_length.push_back(lengthOfLIS(nums, i)); // i 为 end, 所以 i <=n
reverse(nums.begin(), nums.end()); // 反转数组
for(int i=1; i<=n; i++)
LIS_length_Reverse.push_back(lengthOfLIS(nums, i));
for(int i=0; i<n; ++i)
{if(LIS_length[i]==1) LIS_length[i] = -inf;
if(LIS_length_Reverse[i]==1) LIS_length_Reverse[i] = -inf;
}
int max_ans = 1;
for(int i=0; i<n; ++i)
max_ans = max(max_ans, LIS_length[i]+LIS_length_Reverse[n-i-1]-1);
return max_ans;
}
int main()
{
int n;
while(cin>>n && n)
{vector<int> nums(n);
for(int i=0; i<n; i++) cin>>nums[i];
cout<<Ans(nums)<<endl;
}
return 0;
}以上就是全副五道题, 其实说实话, 我感觉有点难度. 幸好有大哥黑了 OJ 平台😀, 所以换了一套简略的题目.
如果你感觉本篇文章对你有所帮忙, 欢送大家去我的集体博客 — 乔治的编程小屋逛逛.