catalogue
A - Jessica's Reading Problem
Meaning:
Jessica Huang is facing the severe challenge of the final exam. She usually doesn't listen carefully, but a boy who pursues her helped her draw the scope and knowledge points, so the relationship between the two is further.
Now there are P pages in the book, and there is a knowledge point about a[i] on each page, which may be repeated.
Jessica needs at least a few pages to review.
Idea:
First, find a way to calculate the total number of knowledge points.
Then the ruler is taken to find the shortest sequence to meet the conditions.
-
Inspection points: ruler taking, thinking
code:
//Card input, must be scanf or fast read
//Close input stream + "\ n" or T
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
map<int,int> mp;
int a[maxn];
int main()
{
int n,k=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(mp[a[i]]==0) k++;
mp[a[i]]=1;
}
mp.clear();
int l=1,r=1;
int cnt=0,len=inf;
while(l<=n){
while(r<=n&&cnt<k){
if(mp[a[r]]==0) cnt++;
mp[a[r++]]++;
}
if(cnt<k) break;
len=min(len,r-l);
mp[a[l]]--;
if(mp[a[l++]]==0) cnt--;
}
printf("%d\n",len);
}
B - Bound Found
Meaning:
Now let me give you a sequence of length n, a, a [i] < = 10000.
Next, there will be k queries, and each query will give a value t.
Find a subsequence of a so that the absolute value of the sum of this subsequence is as close to t as possible.
Output the sequence of this subsequence and its start and end positions.
Idea:
Firstly, all prefixes and sums of 1~r are calculated and stored.
Next, take the ruler. Please refer to the code Notes for the specific process.
-
Inspection points: ruler taking, sorting, thinking
code:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e5+500;
struct node
{
int x,r; ///x: Prefix and R represent: the sum of numbers before 1~r is X
node(){}
node(int xx,int rr):x(xx),r(rr){}
};
bool cmp(node z,node c){
return z.x<c.x;
}
node a[maxn];
int main()
{
int n,k,t;
ios::sync_with_stdio(false);
while(cin>>n>>k&&n&&k){
a[0].x=0;a[0].r=0;
for(int i=1;i<=n;i++){
cin>>a[i].x;
a[i].x=a[i].x+a[i-1].x;
a[i].r=i;
}
sort(a,a+1+n,cmp);
// for(int i=1;i<=n;i++){
// cout<<a[i].x<<" "<<a[i].r<<endl;
// }
for(int i=0;i<k;i++){
cin>>t;
int l=0,r=1;
int finl,finr;
int mint=inf;
int ans;
while(mint&&r<=n){ //Mint = 0 = > there are completely consistent answers. Just output them directly
int chazhi=a[r].x-a[l].x;
//cout<<a[r].r<<" "<<a[l].r<<" "<<chazhi<<" "<<mint<<endl;
if(abs(chazhi-t)<=mint){
ans=chazhi;
finl=a[l].r;
finr=a[r].r;
mint=abs(chazhi-t);
}
if(chazhi>t) l++;
if(chazhi<t) r++;
if(l==r) r++;
}
if(finl>finr) swap(finl,finr);
cout<<ans<<" "<<finl+1<<" "<<finr<<endl;
}
}
}
C - Subsequence
Meaning:
Given a sequence a with a length of n, find the length of a shortest subsequence of a that satisfies:
The subsequence sum > = s
Idea:
Take it with a naked ruler and it's over!
-
Inspection point: ruler
code:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e5+500;
int a[maxn];
int main()
{
int t,n,s;
ios::sync_with_stdio(false);
cin>>t;
while(t--){
cin>>n>>s;
for(int i=1;i<=n;i++)
cin>>a[i];
int l=1,r=1;
int ans=inf;
int sum=0;
while(l<=n){
while(sum<s&&r<=n){
sum+=a[r++];
}
if(sum<s)
break;
ans=min(ans,r-l);
sum-=a[l++];
}
if(ans==inf) cout<<"0\n";
else cout<<ans<<"\n";
}
}
D - Tallest Cow
Meaning:
FJ has N cows. First give the number and height of the highest cow. (the height of cattle is an integer)
Next, r sets of data will be given:
x y
It represents x cattle and y cattle. The cattle numbered (x+1)~(y-1) will be shorter than both sides (I don't know how short they are, anyway)
What is the maximum for each cow?
Idea:
Using the characteristics of the difference score group: it is very simple to deal with the problem of interval increase and decrease.
-
Investigation point: differential array
-
Pit: there will be duplicate data
code:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=1e4+500;
int a[maxn];
int main()
{
int n,i,h,r,x,y;
map<pair<int,int>,int> mp;
cin>>n>>i>>h>>r;
memset(a,0,sizeof(a));
a[0]=h;
for(int i=0; i<r; i++)
{
cin>>x>>y;
if(x>y) swap(x,y);
if(mp[make_pair(x,y)])
continue;
mp[make_pair(x,y)]=1;
a[x+1]-=1;
a[y]+=1;
// for(int i=1; i<=n; i++)
// {
// if(i!=1)
// cout<<" ";
// cout<<a[i];
// }
// cout<<endl;
}
for(int i=1; i<=n; i++)
{
a[i]=a[i]+a[i-1];
}
for(int i=1; i<=n; i++)
{
if(i!=1)
cout<<" ";
cout<<a[i];
}
cout<<endl;
}
E - Straight Master
Meaning:
Give you an array with a length of n. each time you can select an interval with a length of 3, 4 and 5 to reduce the value by 1.
Ask if you can change all numbers to 0.
Idea:
Using differential array properties:
For the differential array B generated by array a, make all a[l]~a[r] of array a minus 1 = > b [l] - 1 b[r+1]+1
Next is the key:
- b[1]==a[1], so b[1] must be positive.
- If b[2] and b[3] are less than 0, there is no data within the valid range to fill in both. (if b[2] wants to become a positive number, it needs b[2-1-3] to subtract one, but it does not exist, and b[3] is the same.)
- Finally, add a b[len+1]==0-a[len] after b[len], which is used to subtract the last element a[len].
Next, it's very simple to take the positive number in front to make up for the negative number in the back. If it is exactly 0, it means yes, otherwise it is not.
We should also pay attention to boundary judgment.
-
Investigation points: mathematics, thinking, difference
code:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
ll a[maxn],b[maxn];
int main()
{
ios::sync_with_stdio(false);
int t,n;
cin>>t;
for(int c=1;c<=t;c++){
cin>>n;
a[0]=0;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
b[i]=a[i]-a[i-1];
b[n+1]=0-a[n];
if(b[2]<0||b[3]<0){
cout<<"Case #"<<c<<": No\n";
continue;
}
ll sum=0;
for(int i=1;i<=n;i++)
{
sum+=b[i];
int pos=i+3;
if(pos>n+1) //boundary
break;
if(b[pos]<0){
sum+=b[pos];
b[pos]=0;
}
if(sum<0) break;
}
if(sum==0) cout<<"Case #"<<c<<": Yes\n";
else cout<<"Case #"<<c<<": No\n";
}
}
F - very male and female
Meaning:
Chinese you me? Understand?
Idea:
01 may not be very convenient for us to count the number of people. If we replace 0 representing girls with - 1, then this problem will be transformed into finding a longest subsequence to satisfy the sequence sum of 0.
-
Inspection points: prefix and, thinking
code:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=1e5+500;
int a[maxn];
int sum[maxn];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==0) a[i]=-1;
}
sum[0]=0;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
}
map<int,int> mp;
int len=-1;
for(int i=1;i<=n;i++){
if(sum[i]==0){
len=max(len,i);
}
else{
if(mp[sum[i]]&&len<i-mp[sum[i]])
len=i-mp[sum[i]];
else if(!mp[sum[i]])
mp[sum[i]]=i;
}
}
cout<<len<<endl;
}
G - rectangle A + B
Meaning:
Chinese you me? Understand?
Idea:
In the permutation and combination problem, there are (n+1) horizontal lines and (m+1) vertical lines. How many rectangles can be generated?
-
Investigation points: mathematics, thinking, arrangement and combination
code:
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
cout<<((n+1)*n/2)*((m+1)*m/2)<<endl; //C[2](n+1) * C2(m+1)
}
}