Một bài sử dụng cấu trúc dữ liệu hay (Mảng hai chiều)

Đề bài:

A country X consists of N cities numbered 0 through $N-1$. The map of this country can be represented as a cycle — for each valid i, city i has exactly two neighboring cities $(i+1)\mathrm{\%}N$ and $(i-1+N)\mathrm{\%}N$.
The cities in the country are broadly categorized into different types. For each valid i, the type of city i is denoted by $A_i$.
A person called Suarez wants to travel between some pairs of the cities. You are given Q queries. In each query, Suarez wants to travel from city number Y to a city of type Z. Also, he wants to travel only in a given direction along the cycle.
The direction is represented by a letter — L or R. If it's L, Suarez may only move from city i to city $(i-1+N)\mathrm{\%}N$ for each valid i. If it's R, he may only move from city i to city $(i+1)\mathrm{\%}N$.
You need to find the minimum number of steps Suarez needs to take to reach a city of type Z if he starts moving from city Y in the given direction (he can take zero steps). In one step, Suarez can move from his current city to a neighboring city.
If Suarez can never reach a city of type Z for a given query, print 1 instead.
Constraints

• $1\le N\le 3,000$
• $1\le Q\le 500,000$
• $0\le Y<N$
• $1\le A_i,Z\le 200,000$

Input format
The first line of the input contains two space-separated integers N and Q. The next line contains N space-separated integers, where the i-th of these integers represents $A_i$.
Each of the following Q lines describes a query in the format $YZD$, where Y is an integer denoting the number of the starting city, Z is an integer denoting the type of a target city and D is a letter ('L' or 'R') denoting the direction along the cycle.
Output format
For each query, print a single line containing one integer — the answer to the query.

SAMPLE INPUT

 

3 4
1 2 3
0 1 L
1 3 L
2 1 R
1 5 L

SAMPLE OUTPUT

 

0
2
1
-1

Explanation

For the first query, Suarez is already standing in a city of the required type, hence 0 steps taken.
For the second query, Suarez will take the path 1 -> 0 -> 2, hence 2 steps taken.
For the third query, Suarez will take the path 2 -> 0, hence 1 step taken.
For the fourth query, there is no city of type 5, so the answer is 1.

Lời giải:

#include<bits/stdc++.h>
using namespace std;
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   int n,q;
   cin>>n>>q;
   vector<int> v[200002];
   int arr[n];
   for(int i=0;i<n;i++){
      cin>>arr[i];
      v[arr[i]].push_back(i);
   }
   while(q--){
      int y,z;
      char d;
      cin>>y>>z>>d;
      int ans=INT_MAX;
      if(v[z].size()==0){
        cout<<"-1\n";
      }
      else{
        if(d=='L'){
            for(int i=0;i<v[z].size();i++)
                if(v[z][i]<=y) ans=min(ans,abs(v[z][i]-y));
            else
                ans=min(ans,abs(n-abs(v[z][i]-y)));
        }
        else{
            for(int i=0;i<v[z].size();i++)
                 if(v[z][i]>=y)
                   ans=min(ans,abs(v[z][i]-y));
            else
                ans=min(ans,abs(n-abs(v[z][i]-y)));
        }
        cout<<ans<<endl;
      }
   }
   return 0;
}

Một bài sử dụng Stack hay

Đề bài:
https://www.hackerearth.com/fr/practice/data-structures/arrays/1-d/practice-problems/algorithm/the-amazing-race-1/
Lời giải:

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define m 1000000007
#define input() for(i=1;i<=n;i++){scanf("%lld",&a[i]);}
int main()
{
ios::sync_with_stdio(false);
ll i,n,t;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
ll a[n+1],r[n+1],l[n+1],index[n+1];
input();
stack <ll> s,si;
for(i=n;i>0;i--)
{
while((!s.empty())&&(s.top()<a[i]))
{
s.pop();
si.pop();
}
if(s.empty())
{
r[i]=(n-i);
}
else
{
r[i]=abs(si.top()-i);
}
s.push(a[i]);
si.push(i);
}
while(!s.empty())
{
s.pop();
}
while(!si.empty())
{
si.pop();
}
for(i=1;i<=n;i++)
{
while((!s.empty())&&(s.top()<a[i]))
{
s.pop();
si.pop();
}
if(s.empty())
{
l[i]=(i-1);
}
else
{
l[i]=abs(si.top()-i);
}
s.push(a[i]);
si.push(i);
}
for(i=1;i<=n;i++)
{
index[i] = abs(r[i]+l[i]);

index[i]=(index[i]%m * i%m)%m;
}
ll z=-1;
for(i=1;i<=n;i++)
{
z=max(z,index[i])%m;;
}
for(i=1;i<=n;i++)
{
if(index[i]==z)
break;
}
cout<<i<<endl;
}
return 0;
}

Một bài sử dụng multiset hay

Đề bài:

Given an array $A$ of size $N$, you can jump from an index $i$ to another index $j$ if $A[j]-A[i]$ >= $K$, for $j$ > $i$. Find the length of the longest sequence of jumps that can be possible in the array. You can start at any index.
Input Format:
First line contains an integer $K$.
Second line contains the integer $N$.
Third line contains $N$ space separated integers (The array $A$)
Output Format:
Print the required length.
Constrains:
$1$ ≤ $N,A[i],K$ ≤ $10$ ^$6$

SAMPLE INPUT

 

2 
7
1 3 1 4 5 7 10

SAMPLE OUTPUT

 

5

Explanation

1 3 5 7 10 - Length 5

Lời giải:

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define MAX5 1000005
int arr[MAX5];
int n,k;
int dp[MAX5];
int n2(){
   int ans=0;
   for(int i=0;i<n;i++) dp[i]=1;
   for(int i=1;i<n;i++){
       for(int j=0;j<i;j++){
        if(arr[i]>=arr[j]+k){
            dp[i]=max(dp[i],1+dp[j]);
        }
       }
   }
   for(int i=0;i<n;i++){
      ans=max(ans,dp[i]);
   }
   return ans;
}
multiset<int> p;
multiset<int>:: iterator it;
int nlogn(){
    p.clear();
    for(int i=0;i<n;i++){
        int tmp=arr[i];
        it= p.upper_bound(tmp-k);
        if(it==p.end()){
            p.insert(tmp);
            continue;
        }
        if(*it>tmp){
            p.erase(it);
            p.insert(tmp);
        }
    }
    return p.size();
}
int main(){
   cin>>k>>n;
   for(int i=0;i<n;i++){
    cin>>arr[i];
   }
   cout<<nlogn()<<endl;
   return 0;
}