preface
Enumeration and simulation are the most common contents of the Blue Bridge Cup. Then, if you sort, you won't investigate the handwriting of the quick row, but you will check, merge and sort. When the Blue Bridge Cup inspected the line segment tree, most of them were written with violence. Greed and number theory have been investigated more in the Blue Bridge Cup.
1, Consecutive interval number (enumeration)
Arbitrary gate
Judge whether a number is a continuous interval: the maximum number - the minimum number = R-L. in this way, you can judge whether it is a continuous interval.
When doing this kind of topic, we first think about how to write the pure violence method of this topic, and then we think about how to optimize it.
#include <iostream>
#include <cstdio>
#include<algorithm>
using namespace std;
const int N=10010,INF=100000000;
int n;
int a[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int res=0;
for(int i=0;i<n;i++)
{
int minv=INF,maxv=-INF;//Here is the general initialization maximum value is negative infinity and the initialization minimum value is positive infinity
for(int j=i;j<n;j++)
{
minv=min(minv,a[j]);
maxv=max(maxv,a[j]);
if(maxv-minv==j-i)res++;
}
}
cout<<res<<endl;
return 0;
}
In fact, I feel that the thinking of this is also very clever!
2, Incrementing triples (prefix and / sort + bisection / double pointer)
Arbitrary gate
That is, how many AI < Bi, how many Bi < CI.
bi centered
Method 1: prefix and (the idea is to trade space for time)
Method 2: sort + dichotomy
Method 3: double pointer
Prefix and
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
typedef long long LL;
int n;
int a[N],b[N],c[N];
int as[N];//as[i] indicates how many numbers in A [] are less than b[i]
int cs[N];//cs[i] indicates how many numbers in C [] are greater than b[i]
int cnt[N],s[N];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]),a[i]++;//a[i] is strictly greater than 0
for(int i=0;i<n;i++)
scanf("%d",&b[i]),b[i]++;
for(int i=0;i<n;i++)
scanf("%d",&c[i]),c[i]++;
//as []
for(int i=0;i<n;i++)cnt[a[i]]++;
for(int i=1;i<N;i++)s[i]=s[i-1]+cnt[i];
for(int i=0;i<n;i++)as[i]=s[b[i]-1];
//Find cs []
memset(cnt,0,sizeof cnt);
memset(s,0,sizeof s);
for(int i=0;i<n;i++)cnt[c[i]]++;
for(int i=1;i<N;i++)s[i]=s[i-1]+cnt[i];
for(int i=0;i<n;i++)cs[i]=s[N-1]-s[b[i]];
//Enumerate each b[i]
LL res=0;
for(int i=0;i<n;i++)res+=(LL)as[i]*cs[i];
cout<<res<<endl;
return 0;
}
Dichotomy
lower_bound find the first subscript in a that is greater than or equal to the current element
upper_bound find the first subscript in c that is greater than the current element
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
typedef long long LL;
int n;
int a[N],b[N],c[N];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
scanf("%d",&b[i]);
for(int i=0;i<n;i++)
scanf("%d",&c[i]);
sort(a,a+n);
sort(c,c+n);
LL ans=0;
for(int i=0;i<n;i++)
{
LL aa=0,cc=0;
if(b[i]>a[0])aa=lower_bound(a,a+n,b[i])-a;
else continue;
if(b[i]<c[n-1])cc=upper_bound(c,c+n,b[i])-c;
else continue;
ans+=aa*(n-cc);
}
cout<<ans;
return 0;
}
3, Sum of special numbers (simulation)
Arbitrary gate
The n of this question is relatively small, so it can be written with mindless violence, but if n is relatively large, it can be written in digital dp, but it is very troublesome.
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int ans=0;
bool judge(int i)
{
while(i)
{
int k=i%10;
if(k==2||k==0||k==1||k==9)
return true;
i/=10;
}
return false;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
if(judge(i)==true)
ans+=i;
}
cout<<ans;
return 0;
}
4, Wrong ticket (sorting, simulation)
Arbitrary gate
1. This question is not how many numbers, but how many lines!
2. The idea of violence is simple.
3. Here is the way of sorting. set is a dynamic ordered sequence
4. We can also ignore the first line number. We can read it until it is empty. It will be easier. while(scanf(,,,)!= EOF)
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
const int N=10010;
int n;
int a[N];
int main()
{
int cnt;
cin>>cnt;
string line;
getline(cin,line);//Ignore the carriage return in the first line!!!
while(cnt--)
{
getline(cin,line);
stringstream ssin(line);//Equivalent to scanf
while(ssin>>a[n])n++;
}
sort(a,a+n);
int res1,res2;
for(int i=1;i<n;i++)
{
if(a[i]==a[i-1])res2=a[i];//Duplicate sign
else if(a[i]>=a[i-1]+2)res1=a[i]-1;//Broken sign
}
cout<<res1<<" "<<res2<<endl;
return 0;
}
5, Palindrome date (enumeration, simulation)
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check_valid(int date)
{
int year=date/10000;
int month=date%10000/100;
int day=date%100;
if(month==0||month>12)return false;
if(day==0||month!=2&&day>days[month])return false;
if(month==2)
{
int leap=year%100&&year%4||year%400;
if(day>28+leap)return false;
}
return true;
}
int main()
{
int date1,date2;
cin>>date1>>date2;
int res=0;
for(int i=1000;i<10000;i++)
{
int date=i,x=i;
for(int j=0;j<4;j++)
date=date*10+x%10,x/=10;
if(date1<=date&&date<=date2&&check_valid(date))res++;
}
cout<<res;
return 0;
}
Of course, I don't think this method is the best. I think the best thing is to judge the year and then judge whether it works.
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check_valid(int date)
{
int year=date/10000;
int month=date%10000/100;
int day=date%100;
if(month==0||month>12)return false;
if(day==0||month!=2&&day>days[month])return false;
if(month==2)
{
int leap=year%100&&year%4||year%400;
if(day>28+leap)return false;
}
return true;
}
int transfer(int i)
{
int m=i,n;
while(m)
{
n=m%10;
i=i*10+n;
m/=10;
}
return i;
}
int main()
{
int date1,date2;
cin>>date1>>date2;
int s=date1/10000,e=date2/10000;
int res=0;
for(int i=s;i<=e;i++)
{
int x=transfer(i);
// cout<<x<<endl;
if(date1<=x&&date2>=x&&check_valid(x))res++;
}
cout<<res;
return 0;
}
6, Merge sort
Arbitrary gate
Merge sort – divide and conquer
① Determine the cut-off point mid / / what's different from fast platoon here is
② Recursive sorting, left, right
③ Merge – merge into one ★
(actually)
It is also a double pointer algorithm
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
const int N=10000010;
int n;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r)
{
if(l>=r)return;
int mid=l+r>>1;
merge_sort(q,l,mid),merge_sort(q,mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r)
if(q[i]<=q[j])tmp[k++]=q[i++];
else tmp[k++]=q[j++];
while(i<=mid)tmp[k++]=q[i++];
while(j<=r)tmp[k++]=q[j++];
for(i =l,j=0;i<=r;i++,j++)q[i]=tmp[j];
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&q[i]);
merge_sort(q,0,n-1);
for(int i=0;i<n;i++)printf("%d ",q[i]);
return 0;
}
7, Moving distance (Analog)
Arbitrary gate
Ask us what is the Manhattan distance between the two numbers (the distance between broken lines and Euclidean distance is the distance between straight lines)
Let's put every number here - 1. In this way, we can get: line number n/w m/w
------Column number n%w m%w if(n/w is odd) w-1-n%w
It's essentially a one-dimensional array. We find its real coordinates.
At least give the sample during the exam, and then manually write some code you give.
ps: the priority of bit operations (&, |) is relatively low
+, - greater than > >, < < greater than &|
C + + operator priority
sizeof is an operator, not a function, so you don't need parentheses
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
int main()
{
int w,m,n;
cin>>w>>m>>n;
m--;n--;
int x1=m/w,x2=n/w;
int y1=m%w,y2=n%w;
if((x1&1)==1)y1=w-1-y1;
if(x2%2)y2=w-1-y2;
cout<<abs(x1-x2)+abs(y1-y2)<<endl;
return 0;
}
8, Date issue (enumeration)
Arbitrary gate
cin/cout is streaming I / O and printf/scanf is formatted I / O
For example, when there is a fixed format, it will be more convenient for us to use formatted input and output
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check_valid(int year,int month,int day)
{
if(month==0||month>12)return false;
if(day==0)return false;
if(month!=2)
{if(day>days[month])return false;}
else {
int leap=year%100&&year%4==0||year%400==0;//Judge whether it is a normal year or a leap year
if(day>28+leap)return false;
}
return true;
}
int main()
{
int a,b,c;
scanf("%d/%d/%d",&a,&b,&c);//Format input
for(int date=19600101;date<=20591231;date++)
{
int year=date/10000,month=date%10000/100,day=date%100;
if(check_valid(year,month,day))
{
// if(year==2045&&month==12)cout<<date<<endl;
if(year%100==a&&month==b&&day==c||//specific date
month==a&&day==b&&year%100==c||//Month day year
day==a&&month==b&&year%100==c) //Sun Moon year
printf("%d-%02d-%02d\n",year,month,day);//The output format is two digits, which is not enough to be supplemented with 0
}
}
return 0;
}
9, Flight time
Arbitrary gate
Flying west, the flight duration is difference + time difference. Flying east, the length of flight is time difference - time difference
Calculated area time = known area time - (time zone of known area time - time zone of area time to be calculated)
Elapsed time t1=t + △ h
Flying back time t2=t - △ h
So the real flying time = (t1+t2)/2
c_str() returns a representation of an array of strings
sscanf he is formatted to read
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
int get_second(int h,int m,int s)
{
return h*3600+m*60+s;
}
int get_time()
{
string line;
getline(cin,line);
if(line.back()!=')')line+="(+0)";//At the end of this string
int h1,m1,s1,h2,m2,s2,d;
sscanf(line.c_str(),"%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);
return get_second(h2,m2,s2)-get_second(h1,m1,s1)+d*24*3600;//Count their time seconds
}
int main()
{
int n;
scanf("%d",&n);
string line;
getline(cin,line);
while(n--)
{
int time=(get_time()+get_time())/2;
int hour=time/3600,minute=time%3600/60,second=time%60;
printf("%02d:%02d:%02d\n",hour,minute,second);
}
return 0;
}
10, Takeout priority (simulation)
·We can handle all the problems between the two orders until the next purchase order appears. If it is the last paragraph, we agree to deal with it at the last T moment.
·The advantage of this way is that we can only consider the stores with orders every time, and we can handle the stores without orders in a unified way, so that we have less general scale.
·Sort all orders in chronological order, enumerate each order, and process one batch of orders at a time, id,t,cnt
score[i] indicates the current priority of the ith store
last[i] indicates the last order time of the ith store
st[i] indicates whether the ith store is currently in the priority cache
T moment here is the last time
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=100010;
int n,m,T;
int score[N],last[N];
bool st[N];
PII order[N];
int main()
{
scanf("%d%d%d",&n,&m,&T);
for(int i=0;i<m;i++)scanf("%d%d",&order[i].x,&order[i].y);
sort(order,order+m);
for(int i=0;i<m;)
{
int j=i;
while(j<m&&order[j]==order[i])j++;
int t=order[i].x,id=order[i].y,cnt=j-i;
i=j;
score[id]-=t-last[id]-1;
if(score[id]<0)score[id]=0;
if(score[id]<=3)st[id]=false;
score[id]+=cnt*2;
if(score[id]>5)st[id]=true;
last[id]=t;
}
for(int i=1;i<=n;i++)
if(last[i]<T)
{
score[i]-=T-last[i];
if(score[i]<=3)st[i]=false;
}
int res=0;
for(int i=1;i<=n;i++)
res+=st[i];
printf("%d\n",res);
return 0;
}
11, Quantity in reverse order (merge sort)
Arbitrary gate
1
0
5
10^5
105
∗
1
0
5
*10^5
∗105
/
2
=
5
∗
1
0
9
/2=5*10^9
/2=5∗109
This will explode int, so we still need to use long long to save
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
const int N=100010;
long long int res=0;
int cmp[N];
long long merge_sort(int q[],int l,int r)
{
if(l>=r)return 0;
int mid=l+r>>1;
merge_sort(q,l,mid),merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r)
{
if(q[i]<=q[j])
{
cmp[k++]=q[i++];
}
else
{
res+=mid-i+1;
cmp[k++]=q[j++];
}
}
while(i<=mid)cmp[k++]=q[i++];
while(j<=r)cmp[k++]=q[j++];
for(int i=l,j=0;i<=r;i++,j++)
q[i]=cmp[j];
}
int main()
{
int n;
cin>>n;
int q[N];
for(int i=0;i<n;i++)
scanf("%d",&q[i]);
merge_sort(q,0,n-1);
cout<<res<<endl;
return 0;
}