2019寒假培训第二天

A - Diverse Team

There are $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 k

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 n

and

k

) — the number of students and the size of the team you have to form.

The second line contains n

k

-th student.

k

If it is impossible to form a suitable team, print "NO" (without quotes). Otherwise print "YES", and then print k

k

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 1

k

k

Input

5 3
15 13 15 15 12

Output

YES
1 2 5

Input

5 4
15 13 15 15 12

Output

NO

Input

4 4
20 10 40 30

Output

YES
1 2 3 4

k

All possible answers for the first example:

{1 2 5}
{2 3 5}
{2 4 5}

Note that the order does not matter.

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int n,k,z,m=0,a[105],b[105];
 6     bool flag;
 7     
 8     cin>>n>>k;
 9     for(int i=1; i<=n; ++i)
10     {
11         cin>>z;
12         flag=false;
13         for(int j=0; j<m; ++j)
14             if(a[j]==z)
15             {
16                 flag=true;
17                 break;
18             }
19         if(!flag)
20         {
21             b[m]=i;
22             a[m++]=z;
23         }
24     }
25     if(m>=k)
26     {
27         cout<<"YES"<<endl;
28         for(int i=0; i<k-1; ++i)
29             cout<<b[i]<<" ";
30         cout<<b[k-1]<<endl;
31     }
32     else cout<<"NO"<<endl;
33     return 0;
34 }

View Code

G - Remove Duplicates

Petya has an array $a$

integers. He wants to remove duplicate (equal) elements.

Petya wants to leave only the rightmost entry (occurrence) for each element of the array. The relative order of the remaining unique elements should not be changed.

$a$

The first line contains a single integer n

$a$

) — the number of elements in Petya's array.

The following line contains a sequence n

$a$

) — the Petya's array.

$a$

In the first line print integer x

— the number of elements which will be left in Petya's array after he removed the duplicates.

In the second line print x

integers separated with a space — Petya's array after he removed the duplicates. For each unique element only the rightmost entry should be left.

$a$

Input

6
1 5 5 1 6 1

Output

3
5 6 1

Input

5
2 4 2 4 4

Output

2
2 4

Input

5
6 6 6 6 6

Output

1
6

$a$

In the first example you should remove two integers 1

$a$

In the second example you should remove integer 2

$a$

In the third example you should remove four integers 6

$a$

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int n;
 6     int v[1100]={0};
 7     int a[1100],b[1100];
 8     cin>>n;
 9     for(int i=0;i<n;i++)
10     {
11         cin>>a[i];
12     }
13     int j=0;
14     for(int i=n-1;i>=0;i--)
15     {
16         if(v[a[i]]==0)
17         {
18             v[a[i]]=1;
19             b[j++]=a[i];
20         }
21     }
22     cout<<j<<endl;
23     for(int k=j-1;k>=1;k--)
24     {
25         cout<<b[k]<<" ";
26     }
27     cout<<b[0]<<endl;
28     return 0;
29 }

B - Substrings Sort

You are given $n$

strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are its substrings.

String a

$n$

. For example, string "for" is contained as a substring in strings "codeforces", "for" and "therefore", but is not contained as a substring in strings "four", "fofo" and "rof".

Input

The first line contains an integer n

(

1 \leq n \leq 100

) — the number of strings.

The next n

1 \leq n \leq 100

, inclusive. Each string consists of lowercase English letters.

Some strings might be equal.

1 \leq n \leq 100

If it is impossible to reorder n

given strings in required order, print "NO" (without quotes).

Otherwise print "YES" (without quotes) and n

given strings in required order.

1 \leq n \leq 100

Input

5
a
aba
abacaba
ba
aba

Output

YES
a
ba
aba
aba
abacaba

Input

5
a
abacaba
ba
aba
abab

Output

NO

Input

3
qwerty
qwerty
qwerty

Output

YES
qwerty
qwerty
qwerty

1 \leq n \leq 100

In the second example you cannot reorder the strings because the string "abab" is not a substring of the string "abacaba".

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 bool cmp(string a,string b)
 4 {
 5     return a.size()<b.size();
 6 }
 7 int main()
 8 {
 9     int n;
10     cin>>n;
11     string s[110];
12     for(int i=0; i<n; i++)
13     {
14         cin>>s[i];
15     }
16     sort(s,s+n,cmp);
17     bool flag=true;
18     for(int i=0; i<n-1; i++)
19     {
20         if(s[i+1].find(s[i])==string::npos)//找不到
21             flag=false;
22     }
23     if(!flag)
24         cout<<"NO"<<endl;
25     else
26     {
27         cout<<"YES"<<endl;
28         for(int i=0; i<n; i++)
29         {
30 
31             cout<<s[i]<<endl;
32         }
33     }
34     return 0;
35 }

View Code

I - Letters

There are $n$
.

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 n
$n$
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 2
$n$
of the second dormitory.

For each of m
$n$
dormitories, determine the particular dormitory and the room number in a dormitory where this letter should be delivered.
$n$
The first line contains two integers n
$n$
— the number of dormitories and the number of letters.

The second line contains a sequence n
$n$
are given in increasing order.
$n$
Print m
$n$
to deliver the letter.
$n$
Input
```
3 6
10 15 12
1 9 12 23 26 37
```
Output
```
1 1
1 9
2 2
2 13
3 1
3 12
```
Input
```
2 3
5 10000000000
5 6 9999999999
```
Output
```
1 5
2 1
2 9999999994
```
$n$
In the first example letters should be delivered in the following order:
- the first letter in room 1
of the first dormitory
the second letter in room 9
of the first dormitory
the third letter in room 2
of the second dormitory
the fourth letter in room 13
of the second dormitory
the fifth letter in room 1
of the third dormitory
the sixth letter in room 12

知识点：前缀和+lower_bound(begin,end,b)

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define MAXN 200010
 4 typedef long long ll;
 5     int n,m;
 6     ll a[MAXN],b;
 7     ll c[MAXN];
 8 int main()
 9 {
10 
11     cin>>n>>m;
12     memset(c,0,sizeof c);
13     for(int i=1;i<=n;i++)
14     {
15         cin>>a[i];
16         c[i]=c[i-1]+a[i];
17     }
18     for(int i=1;i<=m;i++)
19     {
20          cin>>b;
21          int pos=lower_bound(c+1,c+1+n,b)-(c);
22          cout<<pos<<" "<<b-c[pos-1]<<endl;
23     }
24     return 0;
25 }

A - Diverse Team

G - Remove Duplicates

B - Substrings Sort

I - Letters

相关推荐