当前位置：网站首页>Winter vacation water test 1 Summary
Winter vacation water test 1 Summary
2022-07-05 06:17:00 【SDAU cross current】
Catalog
Need to master STL
1:map：
map yes STL An associated container of , It offers one-on-one （ The first box is called keyword , Each keyword can only be in map Once in , The second value may be called the keyword ） Data processing power , Because of this feature ：
map The internal implementation builds a red black tree （ A balanced binary tree in a non strict sense ）, This tree has the function of sorting data automatically .
For example, in a class , There is a one-to-one correspondence between each student's student number and its name , This model can be used map Easy description , Obviously, the student number is int describe , Names are described as strings （ This article does not use char* To describe a string , instead STL Medium String To describe ）.
a： Declaration method ：
map<int,string>mapStudent; or map<String,int>mapStudent;b: Data insertion ：
The first one is ： use insert Function insertion pair data
map<int;string>mapStudent;
mapStudent.insert(pair<int,string>(1,"student-one"));The second kind ： use insert Function insertion value-type data ：
map<int,string>mapStudent;
mapStudent.insert(map<int,string>::value_type(1,"student_one"));The third kind of ： Insert data in an array
map<int,string>mapStudent;
mapStudent[1]="student_one";
map<int,string>mapStudent;
sting s; Just insert m[s]=1 perhaps m[s]++ And so on ;The above three methods , Although it can achieve data insertion , But they are different , Of course, the first and the second are the same in effect , use insert Function inserts data , The concept of uniqueness of sets is involved in data insertion , The box map When using this keyword ,insert You can't insert this data anymore , But the way of using arrays is different , It can overwrite the value corresponding to the previous keyword .
c：map Size
To know how much data has been inserted , It can be used size function ：
int size = Student.size();
d: Data search （ This includes determining whether the keyword is in map It appears that ）：
The first one is ： use count Function to determine whether the keyword appears , But it is impossible to determine where the data appears
The second kind ： use find Function to locate the first iterator it returns where the data appears , When data appears , It returns the iterator where the function is located , If map No data to find in , It returns an iterator equal to end Iterator returned by function .
The third kind of ：
lower_bound The usage function , This function returns the lower bound of the keyword to be searched .
upper_bound The usage function , This function returns the upper bound of the keyword to be searched .
for example ：map Has been inserted in 1,2,3,4 Words , If lower_bound(2) Words , Back to 2, and upper_bound(2) Words , It's back 3.
equal_ranger The function returns a pair,pair The first variable is Lower_bound Iterator returned ,pair The second iterator inside is Upper_bound Iterator returned , If these two iterators are equal , shows map This keyword doesn't appear in , Program description ：
mapPair = mapStudent.equal_range（2）;
if（mapPair.first==mapPair.second）
cout<<"Dont find "<<endl;e： Data clearing and judging empty
Empty map The data in can be used clear function , determine map Is there any data available in empty（） function , It returns true shows map empty
f： Deletion of data ：
Here want to use erase function , It has three overloaded functions
Iterators delete
iter = mapStudent.find("123");
mapStudent.erase(iter);
Delete... With keywords
int n = mapStudent.erase("123"); // If deleted, it will return 1, Otherwise return 0
Delete with iterator scope : The whole map Empty , Delete in pieces
mapStudent.erase(mapStudent.begin(), mapStudent.end());
Equate to mapStudent.clear(）
What we need to pay attention to is , It's also STL Characteristics of , The deleted interval is a set of left closed and right open .
g:map The basic operation function of ：
C++ maps It's an associative container , contain “ keyword / value ” Yes
begin() Return to point map The iterator of the head
clear(） Delete all elements
count() Returns the number of occurrences of the specified element , ( Help the comment area understand ： because key Values don't repeat , So it can only be 1 or 0)
empty() If map If it is blank, return true
end() Return to point map Iterator at the end
equal_range() Returns the iterator pair for a particular entry
erase() Delete an element
find() Find an element
get_allocator() return map Configurator for
insert() Insert elements
key_comp() Returns the comparison element key Function of
lower_bound() Return key value >= Given the first position of the element
max_size() Returns the maximum number of elements that can be accommodated
rbegin() Return a point map The backward iterator of the tail
rend() Return a point map The reverse iterator of the head
size() return map The number of elements in
swap() Two exchanges map
upper_bound() Return key value > Given the first position of the element
value_comp() Returns the comparison element value Function of
Water test question A
A Questions can be used map answer
A. Diverse Team
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
There are nn students in a school class, the rating of the ii-th student on Codehorses is aiai. You have to form a team consisting of kk students (1≤k≤n1≤k≤n) such that the ratings of all team members are distinct.
If it is impossible to form a suitable team, print "NO" (without quotes). Otherwise print "YES", and then print kk distinct numbers which should be the indices of students in the team you form. If there are multiple answers, print any of them.
Input
The first line contains two integers nn and kk (1≤k≤n≤1001≤k≤n≤100) — the number of students and the size of the team you have to form.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1001≤ai≤100), where aiai is the rating of ii-th student.
Output
If it is impossible to form a suitable team, print "NO" (without quotes). Otherwise print "YES", and then print kk distinct integers from 11 to nn which should be the indices of students in the team you form. All the ratings of the students in the team should be distinct. You may print the indices in any order. If there are multiple answers, print any of them.
Assume that the students are numbered from 11 to nn.
Examples
input
Copy
5 3 15 13 15 15 12
output
Copy
YES 1 2 5
input
Copy
5 4 15 13 15 15 12
output
Copy
NO
input
Copy
4 4 20 10 40 30
output
Copy
YES 1 2 3 4
Note
All possible answers for the first example:
- {1 2 5}
- {2 3 5}
- {2 4 5}
Note that the order does not matter.
Water test question A topic map Answer key ：
#include<iostream>
#include<map>
using namespace std;
map<int, int> p;
int main()
{
int n,k;
cin >> n >> k;
for(int i = 1; i <= n; i++){
int a;
cin >> a;
p[a] = i;
}
if(p.size() < k){
cout << "NO";
}
else{
cout <<"YES"<<endl;
map<int, int>::iterator it;
for(it = p.begin();it!=p.end(); it++)
{
cout << (it->second) <<" ";
if(--k == 0)
{
break;
}
}
}
}Water test question B:
B Question use map Relatively easy
Equal Sums
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given kk sequences of integers. The length of the ii-th sequence equals to nini.
You have to choose exactly two sequences ii and jj (i≠ji≠j) such that you can remove exactly one element in each of them in such a way that the sum of the changed sequence ii (its length will be equal to ni−1ni−1) equals to the sum of the changed sequence jj (its length will be equal to nj−1nj−1).
Note that it's required to remove exactly one element in each of the two chosen sequences.
Assume that the sum of the empty (of the length equals 00) sequence is 00.
Input
The first line contains an integer kk (2≤k≤2⋅1052≤k≤2⋅105) — the number of sequences.
Then kk pairs of lines follow, each pair containing a sequence.
The first line in the ii-th pair contains one integer nini (1≤ni<2⋅1051≤ni<2⋅105) — the length of the ii-th sequence. The second line of the ii-th pair contains a sequence of nini integers ai,1,ai,2,…,ai,niai,1,ai,2,…,ai,ni.
The elements of sequences are integer numbers from −104−104 to 104104.
The sum of lengths of all given sequences don't exceed 2⋅1052⋅105, i.e. n1+n2+⋯+nk≤2⋅105n1+n2+⋯+nk≤2⋅105.
Output
If it is impossible to choose two sequences such that they satisfy given conditions, print "NO" (without quotes). Otherwise in the first line print "YES" (without quotes), in the second line — two integers ii, xx (1≤i≤k,1≤x≤ni1≤i≤k,1≤x≤ni), in the third line — two integers jj, yy (1≤j≤k,1≤y≤nj1≤j≤k,1≤y≤nj). It means that the sum of the elements of the ii-th sequence without the element with index xx equals to the sum of the elements of the jj-th sequence without the element with index yy.
Two chosen sequences must be distinct, i.e. i≠ji≠j. You can print them in any order.
If there are multiple possible answers, print any of them.
Examples
input
Copy
2 5 2 3 1 3 2 6 1 1 2 2 2 1
output
Copy
YES 2 6 1 2
input
Copy
3 1 5 5 1 1 1 1 1 2 2 3
output
Copy
NO
input
Copy
4 6 2 2 2 2 2 2 5 2 2 2 2 2 3 2 2 2 5 2 2 2 2 2
output
Copy
YES 2 2 4 1
Note
In the first example there are two sequences [2,3,1,3,2][2,3,1,3,2] and [1,1,2,2,2,1][1,1,2,2,2,1]. You can remove the second element from the first sequence to get [2,1,3,2][2,1,3,2] and you can remove the sixth element from the second sequence to get [1,1,2,2,2][1,1,2,2,2]. The sums of the both resulting sequences equal to 88, i.e. the sums are equal
to n An array , Find two arrays , Delete a number from each of these two arrays , Make the sum of two arrays the same .
map Answer key ：
#include <iostream>
#include<map>
typedef long long ll;
using namespace std;
struct node
{
int x,y;
};
ll a[300000];
int main()
{
ll n,m,i,j,sum,x,k,a1,a2,a3,a4;
node w;
map<ll,node> q;
cin>>n;
int f = 0;
for(k=1;k<=n;k++)
{
scanf("%lld",&m);
sum=0;
for(i=1;i<=m;i++)
{
scanf("%lld",&a[i]);
sum+=a[i];
}
for(i=1;i<=m;i++)
{
if(f) break;
x = sum - a[i];
if(q.count(x))
{
w = q[x];
if(w.x != k)
{
f=1;
a1 = k;
a2 = i;
a3 = w.x;
a4 = w.y;
}
}
else
{
w.x = k;
w.y = i;
q[x] = w;
}
}
}
if(f)
{
printf("YES\n");
printf("%lld %lld\n%lld %lld\n",a1,a2,a3,a4);
}
else
printf("NO\n");
return 0;
}Water test question C
Portal - Water test question C
Personally, this question is relatively simple, just a string question
Answer key
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
int l;
char a[110];
} q[110];
int cmp(node x,node y)
{
return x.l<y.l;
}
int main()
{
int n;
while(scanf("%d",&n))
{
int flag=0;
for(int i=0; i<n; i++)
{
scanf("%s",&q[i].a);
q[i].l=strlen(q[i].a);
}
sort(q,q+n,cmp);
for(int i=0; i<n-1; i++)
{
if(strstr(q[i+1].a,q[i].a)==NULL)
{
flag=1;
break;
}
}
if(flag==1)
printf("NO\n");
else
{
printf("YES\n");
for(int i=0; i<n; i++)
printf("%s\n",q[i].a);
}
return 0;
}
return 0;
}
Water test question D:
This topic is also relatively simple , It's the simplest question for me , It is also a string question
#include<iostream>
#include<string>
using namespace std;
char string1[100];
int main()
{
int i=0;
int n = 0;
int ans = 0;
scanf("%d", &n);
scanf("%s", string1);
for (i = 0; i<n - 2; i++)
{
if (string1[i] == 'x' && string1[i + 1] == 'x' && string1[i + 2] == 'x')
{
ans++;
}
}
printf("%d\n", ans);
return 0;
}Water test question E:
C. Letters
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
There are nn dormitories in Berland State University, they are numbered with integers from 11 to nn. Each dormitory consists of rooms, there are aiai rooms in ii-th dormitory. The rooms in ii-th dormitory are numbered from 11 to aiai.
A postman delivers letters. Sometimes there is no specific dormitory and room number in it on an envelope. Instead of it only a room number among all rooms of all nn dormitories is written on an envelope. In this case, assume that all the rooms are numbered from 11 to a1+a2+⋯+ana1+a2+⋯+an and the rooms of the first dormitory go first, the rooms of the second dormitory go after them and so on.
For example, in case n=2n=2, a1=3a1=3 and a2=5a2=5 an envelope can have any integer from 11 to 88 written on it. If the number 77 is written on an envelope, it means that the letter should be delivered to the room number 44 of the second dormitory.
For each of mm letters by the room number among all nn dormitories, determine the particular dormitory and the room number in a dormitory where this letter should be delivered.
Input
The first line contains two integers nn and mm (1≤n,m≤2⋅105)(1≤n,m≤2⋅105) — the number of dormitories and the number of letters.
The second line contains a sequence a1,a2,…,ana1,a2,…,an (1≤ai≤1010)(1≤ai≤1010), where aiai equals to the number of rooms in the ii-th dormitory. The third line contains a sequence b1,b2,…,bmb1,b2,…,bm (1≤bj≤a1+a2+⋯+an)(1≤bj≤a1+a2+⋯+an), where bjbj equals to the room number (among all rooms of all dormitories) for the jj-th letter. All bjbj are given in increasing order.
Output
Print mm lines. For each letter print two integers ff and kk — the dormitory number ff (1≤f≤n)(1≤f≤n) and the room number kk in this dormitory (1≤k≤af)(1≤k≤af) to deliver the letter.
Examples
input
Copy
3 6 10 15 12 1 9 12 23 26 37
output
Copy
1 1 1 9 2 2 2 13 3 1 3 12
input
Copy
2 3 5 10000000000 5 6 9999999999
output
Copy
1 5 2 1 2 9999999994
Note
In the first example letters should be delivered in the following order:
- the first letter in room 11 of the first dormitory
- the second letter in room 99 of the first dormitory
- the third letter in room 22 of the second dormitory
- the fourth letter in room 1313 of the second dormitory
- the fifth letter in room 11 of the third dormitory
- the sixth letter in room 1212 of the third dormitory
Use STL Medium lower_bound, Although the code is short , But it's hard to do
// This content is reproduced to http://m.biancheng.net/view/7521.html
lower_bound() The function is used to find the first element not less than the target value in the specified area . in other words , When using this function to find a target value within the specified range , The final finding is not necessarily an element equal to the target value , It may also be an element larger than the target value .
lower_bound() Function defined in <algorithm> Header file , Its grammatical format is 2 Kind of , Respectively ：
// stay [first, last) Find no less than... In the area val The elements of
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val);
// stay [first, last) Find the first non conformance in the area comp Elements of rules
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
among ,first and last All forward iterators ,[first, last) Used to specify the scope of the function ;val Used to specify the target element ;comp Used to customize comparison rules , This parameter can receive a containing 2 Parameters （ The second parameter value is always val） And the return value is bool Function of type , It can be an ordinary function , It can also be a function object .
actually , The first syntax format also has comparison rules , But this rule cannot be changed , That is to use < The less than sign compares [first, last) Some elements in the area and val Size , Until you find one that is not less than val The elements of . It also means that , If you use the first syntax format , be [first,last) The element type of the scope must support < Operator .
Besides , This function also returns a forward iterator , When the search is successful , The iterator points to the element found ; conversely , If the search fails , The direction and of the iterator last Same iterator .
Again , This function is only applicable to ordered sequences . So-called “ The order has been arranged ”, refer to [first, last) All orders in the area element<val（ perhaps comp(element,val), among element For the elements in the specified range ） The established elements are in front of the non established elements .
AC Code
Ideas ： use a The array stores the maximum dormitory number of each dormitory building , then lower_bound Find out in the dormitory , Subtract the maximum number of the previous dormitory
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Max=2e5+100;
ll a[Max];
int main()
{
ll n,m,x,pos;
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>x;
a[i]=a[i-1]+x;
}
while(m--)
{
cin>>x;
pos=lower_bound(a+1,a+1+n,x)-a-1;
cout<<pos+1<<" "<<x-a[pos]<<endl;
}
return 0;
}Water test question F:
Remove Duplicates - CodeForces 978A - Virtual Judge
Relatively easy , Sequence de duplication , Write down the order and order in which each number appears , Finally, output
AC Code
#include<iostream>
using namespace std;
int main()
{
int n;
while(cin>>n)
{ int b[10000]={0};
int a[10000];
int ans[100];
int c=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
b[a[i]]++;
}
for(int i=0;i<n;i++)
{
if(b[a[i]]==1)
{
ans[c++]=a[i];
}
else
b[a[i]]--;
}
cout<<c<<endl;
for(int j=0;j<c;j++)
{
cout<<ans[j]<<" ";
}
cout<<endl;
}
return 0;
}边栏推荐
猜你喜欢
随机推荐
高斯消元 AcWing 884. 高斯消元解异或线性方程组
Presentation of attribute value of an item
Real time clock (RTC)
Appium基础 — 使用Appium的第一个Demo
LeetCode 0107. Sequence traversal of binary tree II - another method
1040 Longest Symmetric String
Nested method, calculation attribute is not applicable, use methods
leetcode-6110：网格图中递增路径的数目
SPI details
LeetCode 0107.二叉树的层序遍历II - 另一种方法
1040 Longest Symmetric String
【LeetCode】Day95-有效的数独＆矩阵置零
LVS简介【暂未完成（半成品）】
Leetcode divide and conquer / dichotomy
Sqlmap tutorial (II) practical skills I
In depth analysis of for (VaR I = 0; I < 5; i++) {settimeout (() => console.log (I), 1000)}
How to generate an image from text on fly at runtime
leetcode-6111：螺旋矩阵 IV
927. 三等分 模拟
Leetcode-556: the next larger element III