Double Pointer Optimization
Why am I tearing up over OI? Because I'm ridiculously good at cooking ......
pull into
Double pointers are a simple yet flexible technique and idea that can be used alone to easily solve specific problems, and in combination with other algorithms can be used in a variety of ways.
Dual pointers, as the name suggests, use two pointers at the same time, pointing to locations on sequence and chained list structures, and nodes on tree and graph structures, to maintain and count information by either moving in the same direction, or moving in opposite directions. -- from OI wiki
To be clear, a double pointer is a greedy-like algorithm for maintaining intervals in theBattle explosion in interval problems with monotonicity, which also solves the problem of chained lists judging rings.
Let Konjac explain next.
title
sum of the consecutive natural numbers (math.)P1147 Orange - Portal
Title Description
For a given positive integer M, find all consecutive segments of positive integers (with at least two numbers in each segment), the sum of all numbers in these consecutive segments of natural numbers is M.
Example: 1998+1999+2000+2001+2002 = 10000, so a natural number segment from 1998 to 2002 is a solution to M=10000.
input format
A separate line containing an integer gives the value of M (10 <= M <= 2,000,000).
output format
Two positive integers per line, giving the first and last numbers in a segment of consecutive positive integers that satisfy the condition, with a space separating the two numbers, and the first of all output lines in ascending order from smallest to largest, with at least one solution guaranteed for the given input data.
Sample #1
Sample Input #1
10000
Sample Output #1
18 142
297 328
388 412
1998 2002
analyze
Obviously, the question is asking us to find a sum Mi~j
interval of natural numbers, but this interval is large and violently enumeratedi
together withj
The complexity of then^2
So one can only think of another way (althoughn^2
It's also passable, the data for this question is toowater
)
Let's start with a sample with smaller data1 2 3 4 5 6 7 M==12 Let S be the sum of this i~j interval
we have an opportunityi
directional[1]
,j
directional[0]
whichi
denotes the left end and takes this value (a[i]
),j
denotes the right end and takes this value (a[j]
)。
If the resultingS<M e.g. the moment i=1,j=1
disappointj++
Right endpoint+1
,S
Also expanded.
If the resultingS>=M e.g. moment i=1,j=5
disappointi++
left endpoint+1
,S
Reduction.
This way the answer will gradually approach the correct solutionSo it's similar to greed
If the resultingS==M For example, the moment i=3,j=5.
Just output the left and right endpoints of the answer, and at this point don't forget to set thei++
maybej++
, in preparation for updating the next solution.
(coll.) fail (a student)j>n
when it is OK to end the loop.
Did you get a blue phone?
The latter will be analyzed veryAbbreviated ~~~~~~~~~~~。
CODE
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0),(0),(0);
#ifndef ONLINE_JUDGE
freopen("","r",stdin);
freopen("","w",stdout);
#endif
long long m;
cin>>m;
__int128 tans=0;
int i=1,j=0;while(1)//[i,j]
{
if(i>m/2) return 0;
if(tans>m) tans-=i,i++;
if(tans<m) j++,tans+=j;
if(tans==m) cout<<i<<" "<<j<<endl,tans-=i,i++;
}
return 0;
}
visit a painting exhibitionP1638 Yellow - Portal
Title Description
The Pavilion is displaying paintings by the world's best m painters.
The visitor must specify two numbers, a and b, when purchasing a ticket, representing that he wants to see all the drawings in the exhibition between drawing a and drawing b (inclusive of a,b), and that the price of the ticket is one dollar per drawing.
Sept would like to be admitted to see all the drawings of the famous masters. Of course, he wanted to minimize the price of buying tickets.
Find the a,b that he should choose when he buys the tickets, and the data guarantees that there must be a solution.
If there exists more than one set of solutions, theOutput the group with the smallest a。
input format
The two integers n,m in the first line represent the total number of pictures in the gallery and the number of paintings by the famous artists, respectively.
The second line contains n integers a_i, representing the number of the master who painted the ith painting.
output format
A line of two integers a,b.
Sample #1
Sample Input #1
12 5
2 5 3 1 3 2 4 1 1 5 4 3
Sample Output #1
2 7
draw attention to sth.
Data size and conventions
- For 30% of the data, there are n<=200 and m<=20.
- For 60% of the data, there are n<=10^5 and m<=10^3 .
- For 100% of the data, there is 1<=q n<=10^6 and 1 <=q a_i <=q m<=2*10^3.
notes
expense or outlayi
j
Maintain the left and right intervals with atong[]
The array bucket is computed with anint alls
to maintain the elements of the current bucket.add: element to add
,era: element deletion
,
honorific titlei=1,j=0
Next up.i
Whether there are duplicates of the element you are pointing to, and if so, move the left endpoint right.i++
"abandonmenta[i]
This element, otherwise move the right endpoint leftj++
Increasea[j]
This element.
If the current interval matchesalls==m
, then add it to thevector<pair<int,int>> ans
In the answer array, the
final scanans
, just come up with the best answer.
CODE
#pragma
#include<bits/stdc++.h>
// #include<>
using namespace std;
const int tsn=1e6+5;
const int tstong=1e3+5;
int a[tsn];
int tong[tstong],alls=0;
vector<pair<int,int> >ans;
void add(int k)
{
alls+=(!tong[k]),tong[k]++;
}
void era(int k)
{
if(tong[k]==1) alls--;
if(tong[k]) tong[k]--;
}
int main()
{
ios::sync_with_stdio(0),(0),(0);
#ifndef ONLINE_JUDGE
freopen("","r",stdin);freopen("","w",stdout);
#endif
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int mi=1,mj=0;while(mj<=n+1)
{
if(alls==m) ans.push_back({mi,mj});
if(tong[a[mi]]>=2) era(a[mi]),mi++;
else mj++,add(a[mj]);//Remember to update the endpoints,add(a[mj])!
}
pair<int,int>lans={tsn,INT_MAX};
for(int i=0;i<();i++)
{
if((ans[i].second-ans[i].first)<()) lans=ans[i];
if((ans[i].second-ans[i].first)==()&&ans[i].first<) lans=ans[i];
}
cout<<<<" "<<<<endl;
return 0;
}
[Blue Bridge Cup 2020 Province A1] Integer Small SpliceP8708 Yellow - Portal
Title Description
Given an array A_1,A_2,...,A_n of length n. A_n, you can pick two numbers, A_i and A_j (i!= j), and put A_i and A_j together to form a new integer. For example12
cap (a poem)345
can be put together12345
maybe34512
The following is an example of how to do this. Note that the order of exchanging A_i and A_j is always considered as 2 spellings, even when A_i=A_j.
Count the number of spellings that satisfy the requirement that the number of integers spelled out is less than or equal to K.
input format
The first line contains 2 integers n and K. The first line contains 2 integers n and K.
The second line contains n integers A_1,A_2,... A_n.
output format
An integer represents the answer.
Sample #1
Sample Input #1
4 33
1 2 3 4
Sample Output #1
8
draw attention to sth.
For 30% of the reviewed use cases 1<= n<=1000, 1<= k<=10^8, 1<= A_i<=10^4.
For all review use cases, 1<= n<=10^5, 1<= k<=10^{10}, 1<= A_i<=10^9.
Bluebridge Cup 2020 First Round Provincial Competition, Group A, Question H.
notes
Think for yourself. Go to LUOGU if you can't.
West River Moon - Proof
I.e., it is easy to see the mundane, modeled after the above example obviously.
The answers to the questions left as exercises are omitted, and the reader will be able to prove to himself that it is not difficult.
The converse is also true for the same reason, the inference is naturally established, omitting the process QED, from the above can be proved.
CODE
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int tsn=1e6+5;
long long a[tsn];
long long n,k;
int X(int a,int b)
{
if(b==0) return 0;
int wei=0;
int kb=b;
while(b) b/=10,wei++;
long long ans=a*(pow(10,wei)/1)+kb;
if(ans>k) return 0;
return 1;
}
vector<pair<int,int> >v;
signed main()
{
ios::sync_with_stdio(0),(0),(0);
#ifndef ONLINE_JUDGE
freopen("","r",stdin);
freopen("","w",stdout);
#endif
cin>>n>>k;
long long lans=0;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
// for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
int i=1,j=n;while(j>0&&i<=n)
{
if(X(a[i],a[j])) v.push_back({i,j}),i++;
else j--;
}
for(int x=0;x<();x++)
{
if(v[x].second>=v[x].first) lans+=v[x].second-1;
else lans+=v[x].second;
//Special attention to the extent of the border!
// cout<<v[x].first<<" "<<v[x].second<<endl;
}
cout<<lans;
return 0;
}
[USACO11NOV] Cow Lineup S P3209 Yellow - Portal
headline translation
Description of the problem
Farmer John hires a professional photographer to take pictures of some of his cattle. Since John has so many breeds of cattle, he likes his photos to include every
At least one cow of each breed.
John's cows are all standing at different places along a line, and each cow is represented by an integer position X_i and an integer breed number ID_i.
John wanted to take a photograph which consisted of a continuous range of cows along a line. The cost of the photograph is comparable to the size, which means that in a
The difference between the maximum and minimum X-coordinate in a series of photos determines the cost of the photo.
Please help John calculate the minimum cost of photos that have at least one cow of each different breed in them, with no two cows willing to stand
in the same location.
input format
Row 1: Number of cows N;
Rows 2...1+N: each row contains 2 space-separated positive integers X_i and ID_i; the meaning is as described in the title;
output format
The output consists of a total of one line containing the lowest cost for each of the different varieties \rm ID of the photo.
Title Description
Farmer John has hired a professional photographer to take a picture of some of his cows. Since FJ's cows represent a variety of different breeds, he would like the photo to contain at least one cow from each distinct breed present in his herd.
FJ's N cows are all standing at various positions along a line, each described by an integer position (., its x coordinate) as well as an integer breed ID. FJ plans to take a photograph of a contiguous range of cows along the line. The cost of this photograph is equal its size -- that is, the difference between the maximum and minimum x coordinates of the cows in the range of the photograph.
Please help FJ by computing the minimum cost of a photograph in which there is at least one cow of each distinct breed appearing in FJ's herd.
input format
* Line 1: The number of cows, N (1 <= N <= 50,000).
* Lines 2..1+N: Each line contains two space-separated positive integers specifying the x coordinate and breed ID of a single cow. Both numbers are at most 1 billion (i.e., 1e10)
.
output format
* Line 1: The smallest cost of a photograph containing each distinct breed ID.
Sample #1
Sample Input #1
6
25 7
26 1
15 1
22 3
20 1
30 1
Sample Output #1
4
draw attention to sth.
There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs 7,1,1,3,1,1.
The range from x=22 up through x=26 (of total size 4) contains each of the distinct breed IDs 1, 3, and 7 represented in FJ's herd.
notes
Think for yourself. Go to LUOGU if you can't.
West River Moon - Proof
I.e., it is easy to see the mundane, modeled after the above example obviously.
The answers to the questions left as exercises are omitted, and the reader will be able to prove to himself that it is not difficult.
The converse is also true for the same reason, the inference is naturally established, omitting the process QED, from the above can be proved.
CODE
#pragma
#include<bits/stdc++.h>
using namespace std;
const int tsn=5e5+5;
#define int long long
pair<int,int>a[tsn]={{0,0}};//first->where second->id
map<int,int>tong;
int alls=0;
int n;
int lans=INT_MAX;
void add(int k)
{
if(tong[k]==0) alls++;
tong[k]++;
}
void era(int k)
{
if(tong[k]==1) alls--;
if(tong[k]) tong[k]--;
}
int get_K()
{
for(int i=1;i<=n;i++) add(a[i].second);
int getk=alls;alls=0;();
return getk;
}
signed main()
{
ios::sync_with_stdio(0),(0),(0);
#ifndef ONLINE_JUDGE
freopen("","r",stdin);
freopen("","w",stdout);
#endif
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
sort(a+1,a+n+1);
int K=get_K();
// for(int i=1;i<=n;i++) cout<<"a:"<<a[i].first<<" "<<a[i].second<<endl;
int i=1,j=0;while(j<=n)
{
// cout<<i<<" "<<j<<endl;
if(alls==K)
{
int tans=a[j].first-a[i].first;
if(tans<lans) lans=tans;
j++,add(a[j].second);//Pay attention.,There must be an add operation here!
}
if(tong[a[i].second]>=2) era(a[i].second),i++;
else j++,add(a[j].second);
}
cout<<lans;
return 0;
}