概述
A题
A题链接
A team of three programmers is going to play a contest. The contest consists of n problems, numbered from 1 to n. Each problem is printed on a separate sheet of paper. The participants have decided to divide the problem statements into three parts: the first programmer took some prefix of the statements (some number of first paper sheets), the third contestant took some suffix of the statements (some number of last paper sheets), and the second contestant took all remaining problems. But something went wrong — the statements were printed in the wrong order, so the contestants have received the problems in some random order.
The first contestant has received problems a1,1,a1,2,…,a1,k1. The second one has received problems a2,1,a2,2,…,a2,k2. The third one has received all remaining problems (a3,1,a3,2,…,a3,k3).
The contestants don’t want to play the contest before they redistribute the statements. They want to redistribute them so that the first contestant receives some prefix of the problemset, the third contestant receives some suffix of the problemset, and the second contestant receives all the remaining problems.
During one move, some contestant may give one of their problems to other contestant. What is the minimum number of moves required to redistribute the problems?
It is possible that after redistribution some participant (or even two of them) will not have any problems.
Input
The first line contains three integers k1,k2 and k3 (1≤k1,k2,k3≤2⋅105,k1+k2+k3≤2⋅105) — the number of problems initially taken by the first, the second and the third participant, respectively.
The second line contains k1 integers a1,1,a1,2,…,a1,k1 — the problems initially taken by the first participant.
The third line contains k2 integers a2,1,a2,2,…,a2,k2 — the problems initially taken by the second participant.
The fourth line contains k3 integers a3,1,a3,2,…,a3,k3 — the problems initially taken by the third participant.
It is guaranteed that no problem has been taken by two (or three) participants, and each integer ai,j meets the condition 1≤ai,j≤n, where n=k1+k2+k3.
Output
Print one integer — the minimum number of moves required to redistribute the problems so that the first participant gets the prefix of the problemset, the third participant gets the suffix of the problemset, and the second participant gets all of the remaining problems.
Examples
Input
2 1 2
3 1
4
2 5
Output
1
Input
3 2 1
3 2 1
5 4
6
Output
0
Input
2 1 3
5 6
4
1 2 3
Output
3
Input
1 5 1
6
5 1 2 4 7
3
Output
2
Note
In the first example the third contestant should give the problem 2 to the first contestant, so the first contestant has 3 first problems, the third contestant has 1 last problem, and the second contestant has 1 remaining problem.
In the second example the distribution of problems is already valid: the first contestant has 3 first problems, the third contestant has 1 last problem, and the second contestant has 2 remaining problems.
The best course of action in the third example is to give all problems to the third contestant.
The best course of action in the fourth example is to give all problems to the second contestant.
题意：三个人参加了比赛，然后每个人都有分配的题目1到n，一共n个元素。k1个元素在集合1，k2个元素在集合2，k3个元素在集合3。每次操作可以令一个元素从原来的集合到任意的集合。要求使得集合1中的数最小，集合3中的数最大，剩下的数在集合2中的最小操作次数。
感觉读题就读的费劲啊！！！！！！我都不知道是这个意思呢
思路：看了下别人的思路，他们是分别把三个序列都排好，然后并在一起，求最长上升序列的长度，因为这些数字位置固定，符合题意，剩下的那些是需要移动的数目，然后减掉这个长度输出的就是答案！。然后我写了一个 超时了
代码：--------------------------------------------------------------------------------------------
超时代码：超时的很明显就是后面求最长上升序列的方法是n*n，时间太长
超时代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[200005], b[200005], c[200005], s[200005],d[200005];
int main()
{
int k1, k2, k3; cin >> k1 >> k2 >> k3;
memset(a, 0, sizeof a); memset(b, 0, sizeof b); memset(c, 0, sizeof c);
memset(s, 0, sizeof s);
for (int i = 1; i <= k1; i++)
{
cin >> a[i];
// s[i] = a[i];
}
for (int i = 1; i <= k2; i++)
{
cin >> b[i];
// s[k1 + i] = b[i];
}
for (int i = 1; i <= k3; i++)
{
cin >> c[i];
// s[k1 + k2 + i] = c[i];
}
sort(a + 1, a + 1 + k1);
sort(b + 1, b + 1 + k2);
sort(c + 1, c + 1 + k3);
for (int i = 1; i <= k1; i++)
s[i] = a[i];
for (int i = 1; i <= k2; i++)
s[k1 + i] = b[i];
for (int i = 1; i <= k3; i++)
s[k1 + k2 + i] = c[i];
for (int i = 1; i <= k1 + k2 + k3; i++)
{
d[i] = 1;
for (int j = 1; j < i; j++)
{
if (s[i] > s[j])
{
d[i] = max(d[i], d[j] + 1);
}
}
}
int ans = -1;
for (int i = 1; i <= k1 + k2 + k3; i++)
ans = max(ans, d[i]);
cout << k1 + k2 + k3 - ans << endl;
}
AC代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int s[200005];
int main()
{
int k1, k2, k3; cin >> k1 >> k2 >> k3;
for (int i = 1; i <= k1 + k2 + k3; i++)
cin >> s[i];
sort(s+ 1, s + 1 + k1);
sort(s + 1+k1, s+ 1 + k2+k1);
sort(s + 1 + k1 + k2, s + 1 + k3 + k1 + k2); int ans = 1;
vector<int>dp;
dp.push_back(s[1]);
int n = k1 + k2 + k3;
for (int i = 1; i <= n; i++)
{
int d = lower_bound(dp.begin(), dp.end(), s[i]) - dp.begin();
if (d <= 0)
{
d = 0;
dp[d] = s[i];
}
else if (d == ans)
{
ans++;
dp.push_back(s[i]);
}
else dp[d] = s[i];
}
cout << n-ans << endl;
}
B题
Let’s call an array t dominated by value v in the next situation.
At first, array t should have at least 2 elements. Now, let’s calculate number of occurrences of each number num in t and define it as occ(num). Then t is dominated (by v) if (and only if) occ(v)>occ(v′) for any other number v′. For example, arrays [1,2,3,4,5,2], [11,11] and [3,2,3,2,3] are dominated (by 2, 11 and 3 respectevitely) but arrays [3], [1,2] and [3,3,2,2,1] are not.
Small remark: since any array can be dominated only by one number, we can not specify this number and just say that array is either dominated or not.
You are given array a1,a2,…,an. Calculate its shortest dominated subarray or say that there are no such subarrays.
The subarray of a is a contiguous part of the array a, i. e. the array ai,ai+1,…,aj for some 1≤i≤j≤n.
Input
The first line contains single integer T (1≤T≤1000) — the number of test cases. Each test case consists of two lines.
The first line contains single integer n (1≤n≤2⋅105) — the length of the array a.
The second line contains n integers a1,a2,…,an (1≤ai≤n) — the corresponding values of the array a.
It’s guaranteed that the total length of all arrays in one test doesn’t exceed 2⋅105.
Output
Print T integers — one per test case. For each test case print the only integer — the length of the shortest dominated subarray, or −1 if there are no such subarrays.
Example
Input
4
1
1
6
1 2 3 4 5 1
9
4 1 2 4 5 4 3 2 1
4
3 3 3 3
Output
-1
6
3
2
Note
In the first test case, there are no subarrays of length at least 2, so the answer is −1.
In the second test case, the whole array is dominated (by 1) and it’s the only dominated subarray.
In the third test case, the subarray a4,a5,a6 is the shortest dominated subarray.
In the fourth test case, all subarrays of length more than one are dominated.
题意：就是给你数列 让你求一段连续序列的长度（任意起点），在这个长度内摸个元素出现次数>=2,在这个长度内仅此一个，求最短的长度！
思路：最短长度，那肯定俩就够了对吧，因为你一个数出现越多，长度就越长，所以两个相同就够了。方法就是找一个数组记录上一次出现这个数的坐标然后 跟ans 比较谁大谁小就可以啦，哦对了记得最后长度+1哦！！！！
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[200001]; int b[200001];
int main()
{
int t; cin >> t;
while (t--)
{
int n; cin >> n;
int ans =200001;
memset(b, 0, sizeof b);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
if (b[a[i]] != 0)
{
ans = min(ans, i - b[a[i]]);
}
b[a[i]] = i;
}
if (ans==200001)
cout <<-1<< endl;
else cout << ans+1<< endl;
}
}
C题
You are the gym teacher in the school.
There are n students in the row. And there are two rivalling students among them. The first one is in position a, the second in position b. Positions are numbered from 1 to n from left to right.
Since they are rivals, you want to maximize the distance between them. If students are in positions p and s respectively, then distance between them is |p−s|.
You can do the following operation at most x times: choose two adjacent (neighbouring) students and swap them.
Calculate the maximum distance between two rivalling students after at most x swaps.
The first line contains one integer t (1≤t≤100) — the number of test cases.
The only line of each test case contains four integers n, x, a and b (2≤n≤100, 0≤x≤100, 1≤a,b≤n, a≠b) — the number of students in the row, the number of swaps which you can do, and positions of first and second rivaling students respectively
.For each test case print one integer — the maximum distance between two rivaling students which you can obtain.
Example
Input
3
5 1 3 2
100 33 100 1
6 0 2 3
Output
2
99
1
Note
In the first test case you can swap students in positions 3 and 4. And then the distance between the rivals is equal to |4−2|=2.
In the second test case you don’t have to swap students.
In the third test case you can’t swap students.
题意：在数轴1-n上有俩坐标a，b，求他俩最大的间距，他俩总共只能移动x步。
思路： 很水的题，就是看距离终点起点的距离大不大于x就行了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
int t; cin >> t;
while (t--)
{
int n, x, a, b;
cin >> n >> x >> a >> b;
int l = min(a, b);
int r = max(a, b);
if ((l - 1 + n - r) <= x)
{
cout << n - 1 << endl;
}
else
{
cout << r - l + x << endl;
}
}
}
D题（没理解透，感觉题不错）
You play a computer game. In this game, you lead a party of m heroes, and you have to clear a dungeon with n monsters. Each monster is characterized by its power ai. Each hero is characterized by his power pi and endurance si.
The heroes clear the dungeon day by day. In the beginning of each day, you choose a hero (exactly one) who is going to enter the dungeon this day.
When the hero enters the dungeon, he is challenged by the first monster which was not defeated during the previous days (so, if the heroes have already defeated k monsters, the hero fights with the monster k+1). When the hero fights the monster, there are two possible outcomes:
if the monster’s power is strictly greater than the hero’s power, the hero retreats from the dungeon. The current day ends;
otherwise, the monster is defeated.
After defeating a monster, the hero either continues fighting with the next monster or leaves the dungeon. He leaves the dungeon either if he has already defeated the number of monsters equal to his endurance during this day (so, the i-th hero cannot defeat more than si monsters during each day), or if all monsters are defeated — otherwise, he fights with the next monster. When the hero leaves the dungeon, the current day ends.
Your goal is to defeat the last monster. What is the minimum number of days that you need to achieve your goal? Each day you have to use exactly one hero; it is possible that some heroes don’t fight the monsters at all. Each hero can be used arbitrary number of times.
Input
The first line contains one integer t (1≤t≤105) — the number of test cases. Then the test cases follow.
The first line of each test case contains one integer n (1≤n≤2⋅105) — the number of monsters in the dungeon.
The second line contains n integers a1, a2, …, an (1≤ai≤109), where ai is the power of the i-th monster.
The third line contains one integer m (1≤m≤2⋅105) — the number of heroes in your party.
Then m lines follow, each describing a hero. Each line contains two integers pi and si (1≤pi≤109, 1≤si≤n) — the power and the endurance of the i-th hero.
It is guaranteed that the sum of n+m over all test cases does not exceed 2⋅105.
Output
For each test case print one integer — the minimum number of days you have to spend to defeat all of the monsters (or −1 if it is impossible).
Example
Input
2
6
2 3 11 14 1 8
2
3 2
100 1
5
3 5 100 2 3
2
30 5
90 1
Output
5
-1
题意：有n个怪兽，每个怪兽的战斗力为a[i]。有m个英雄,每个英雄都有两个属性pi(战斗力)和si(耐力值)，每杀死一个怪兽耐力值-1。每天都需要派一个英雄去杀怪兽，如果该英雄的战斗力低于怪兽或者耐力值没了，则这一天结束。问你最少多少天能杀完怪兽？
刚开始把题目读错了，它是输入力量+耐力，我以为是 先输入所有的力量再输入耐力呢，唉题目都搞错了
思路：贪心，记录每个耐力值下，英雄最大的战斗力。为了快速清理完怪兽，我们需要优先选择战斗力大的并且耐力值高的。
m[i]:表示耐力值为i的情况下，战斗力最高
当有一个怪兽战斗力大于所有英雄战斗力 输出-1
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6 + 100000;
int a[N], m[N], p[N], s[N];//p战斗力，s耐力；
int t, n, k;
int main()
{
cin >> t;
while (t--)
{
for (int i = 0; i <= n; i++) m[i] = 0;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];//怪兽
cin >> k;
for (int i = 1; i <= k; i++)
{
cin >> p[i] >> s[i];
m[s[i]] = max(m[s[i]], p[i]);
}
for (int i = n; i >=0; i--) m[i]=max(m[i],m[i+1]);
int day = 0, f = 0;
for (int i = 1; i <= n;)
{
if (a[i] > m[1])
{
f = 1; cout << -1 << endl;
break;
}
int j = 0; int maxx = 0;
while (j <= n)
{
maxx = max(maxx, a[j + i]);
if (m[j + 1] < maxx) break;
j++;
}
day++;
i = i + j;
}
if (f == 0)
cout << day << endl;
}
}
E题（不明白诶。。。）
Let’s call two numbers similar if their binary representations contain the same number of digits equal to 1. For example:
2 and 4 are similar (binary representations are 10 and 100);
1337 and 4213 are similar (binary representations are 10100111001 and 1000001110101);
3 and 2 are not similar (binary representations are 11 and 10);
42 and 13 are similar (binary representations are 101010 and 1101).
You are given an array of n integers a1, a2, …, an. You may choose a non-negative integer x, and then get another array of n integers b1, b2, …, bn, where bi=ai⊕x (⊕ denotes bitwise XOR).
Is it possible to obtain an array b where all numbers are similar to each other?
Input
The first line contains one integer n (2≤n≤100).
The second line contains n integers a1, a2, …, an (0≤ai≤230−1).
Output
If it is impossible to choose x so that all elements in the resulting array are similar to each other, print one integer −1.
Otherwise, print any non-negative integer not exceeding 230−1 that can be used as x so that all elements in the resulting array are similar.
Examples
Input
2
7 2
Output
1
Input
4
3 17 6 0
Output
5
Input
3
1 2 3
Output
-1
Input
3
43 12 12
Output
1073709057
题意： 给你 n 个数 a[ 1 ] ~ a[ n ]， n <= 100； 让你找一个 x ， 使得 a[ 1 ] = a[ 1 ] ^ x ~ a[ n ] = a[ n ] ^ x；
且 a[ 1 ] ~ a[ n ] 的二进制位上的 1 的个数相等。 每个 a[ i ] <= 2^30；题目虽然很短 但是难度感觉好大啊。。。。。。
思路：题解链接
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
map<vector<int>,int>vis;
int a[N],n;
int Get(int x){//统计1的个数
return __builtin_popcount(x);
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%d",a+i);
}
for(int i = 0;i < (1<<15);i++){
vector<int>b;
for(int j = 1;j <= n;j++){//统计后15位异或之后1的个数
b.push_back(Get((i^a[j])%(1<<15)));
}
for(int j = 1;j < n;j++){
b[j-1] = b[j]-b[j-1];//进行相减
}
b.pop_back();//最后一个元素在此时是多余的，需要删除
if(!vis[b]) vis[b] = i;//做上标记
}
for(int i = 0;i < (1<<15);i++){
vector<int>b;
for(int j = 1;j <= n;j++){//统计前15位异或之后1的个数
b.push_back(Get(i^(a[j]>>15)));
}
for(int j = 1;j < n;j++){
b[j-1] = -1*(b[j]-b[j-1]);//
}
b.pop_back();//多余的删除
if(vis[b]){
int ans = vis[b]|(i<<15);
printf("%dn",ans);
return 0;
}
}
printf("-1n");
return 0;
}
F题
这个题是昨天做的原题诶
题意：给你序列，让你把小的数往前放，只能相邻的数进行交换，而且交换后，i坐标就不能再交换了、
思路：就是暴力翻转就行啊。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[10000], b[10000];
int main()
{
int t; cin >> t;
while (t--)
{
int n; cin >> n;
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
for (int i = 1; i <= n; i++)
cin >> a[i];
int s = n - 1, u = 1;
while (s > 0 && u <= n)
{
for (int i = 1; i <= n; i++)
{
if (a[i] == u)
{
for (int j = i - 1; j >= u; j--)
{
if (b[j])
continue;
if (a[j]>a[j + 1])
{
swap(a[j], a[j + 1]);
b[j] = 1; s--;
}
else break;
} u++; break;
}
}
}
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
}
}
最后
以上就是含蓄铅笔为你收集整理的7.9训练的全部内容，希望文章能够帮你解决7.9训练所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复