Monotonic stack & monotonic queue & fetch
Passing the Message
The meaning of the question: Given n numbers, find the largest number on the left side of each number that is smaller than it, and the largest number on the right side that is smaller than it. Each number cannot go beyond a number larger than it to find the following number.
Solution: When finding the largest number on the left that is smaller than it, maintain a monotonically decreasing monotone stack from right to left. Before inserting a number, this number must be less than the element at the top of the stack, then this number is the stack A possible answer for the top element, and finally keep updating the answer. Find the same on the right.
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
const int maxn = 50010;
typedef long long ll;
int a[maxn];
int ansl[maxn];
int ansr[maxn];
stack <int > s1;
stack <int > s2;
int n;
void getleft()
{
for(int i=n;i>=1;i--)
{
while(!s1.empty()&&a[i]>=a[s1.top()])
{
s1.pop();
}
if(!s1.empty())
{
ansl[s1.top()]=i;
}
s1.push(i);
}
}
void getright()
{
for(int i=1;i<=n;i++)
{
while(!s2.empty()&&a[i]>a[s2.top()])
{
s2.pop();
}
if(!s2.empty())
{
ansr[s2.top()]=i;
}
s2.push(i);
}
}
int main()
{
int t;
scanf("%d",&t);
int tt=1;
while(t--)
{
while(!s1.empty()) s1.pop();
while(!s2.empty()) s2.pop();
printf("Case %d:\n",tt++);
memset(ansl,0,sizeof ansl);
memset(ansr,0,sizeof ansr);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
getleft();getright();
for(int i=1;i<=n;i++)
{
printf("%d %d\n",ansl[i],ansr[i]);
}
}
}
A Famous City
The meaning of the question: Find the minimum possible number of buildings, divide the building into n parts, each part has a height, a building can span several consecutive parts, but each part can only contain one visible building.
Solution: Maintain a strictly increasing monotonic stack from left to right. When encountering a height smaller than the top element of the stack, if the height is not equal to the height of the last popup in this state, and is not equal to the height of the top element of the stack, then ans++. Note that when the height is 0, there is no building, and there is no need to push it into the stack at this time.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int a[maxn];
stack <int > s;
int main()
{
int n;
int tt=1;
while(~scanf("%d",&n))
{
int ans=0;
while(!s.empty()) s.pop();
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int cnt=0;
for(int i=1;i<=n;i++)
{
while(!s.empty()&&a[i]<=a[s.top()])
{
int pre=-1;
int x=a[s.top()];
s.pop();
if(pre!=x&&x!=a[i]) ans++;
pre=x;
}
if(a[i]!=0) s.push(i);
}
ans+=s.size();
printf("Case %d: %d\n",tt++,ans);
}
}
Problem A. Ascending Rating
The meaning of the question: In the interval of length m, the initial maxrating=-1, count=0, when a number larger than maxrating is encountered, maxrating is updated, and count+1 is at the same time.
Solution: Use monotonic queues to maintain a strictly decreasing sequence from back to front. At this time, the head of the queue is the maximum value, and the count is the size of the queue.
#include <cstdio>
#include <algorithm>
#include <queue>
#include <iostream>
#include <cstring>
#include <cmath>
typedef long long ll;
ll mod;
const int maxn = 1e7+10;
ll a[maxn];
std::deque <ll > dq;
ll maxrating;
ll count;
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t;
std::cin>>t;
while(t--)
{
while(!dq.empty()) dq.pop_back();
maxrating=0;
count=0;
ll n,m,k,p,q,r;
std::cin>>n>>m>>k>>p>>q>>r>>mod;
for(int i=1;i<=k;i++)
{
std::cin>>a[i];
}
for(int i=k+1;i<=n;i++)
{
a[i]=(p*a[i-1]+q*i+r)%mod;
}
for(int i=n;i>=1;i--)
{
while(!dq.empty()&&a[i]>=a[dq.back()])
{
dq.pop_back();
}
dq.push_back(i);
if(dq.front()>i+m-1)
{
dq.pop_front();
}
if(i+m-1<=n)
{
count+=(dq.size()^i);
maxrating+=(a[dq.front()]^i);
}
}
std::cout<<maxrating<<" "<<count<<std::endl;
}
}
Subsequence
The meaning of the question: Give a sequence of length n, two positive integers m, k. Find an interval length in the sequence such that the maximum minus the minimum value is not less than m and not greater than k, and ask how long such a length can be.
Solution: maintain two monotonically increasing queues and monotonically decreasing queues respectively, at this time the difference d is the difference between the two team leaders. If d is within the range, update the answer; if d<m, do no operation; if d>k, delete the elements at the head of the two queues.
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1e6+10;
typedef long long ll;
int a[maxn];
deque<int > q1;
deque<int > q2;
int main()
{
int n,m,k;
while(~scanf("%d%d%d",&n,&m,&k))
{
while(!q1.empty()) q1.pop_back();
while(!q2.empty()) q2.pop_back();
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int ans=0;
int be=0;
for(int i=1;i<=n;i++)
{
while(!q1.empty()&&a[i]>a[q1.back()])
{
q1.pop_back();
}
q1.push_back(i);
while(!q2.empty()&&a[i]<a[q2.back()])
{
q2.pop_back();
}
q2.push_back(i);
int d=a[q1.front()]-a[q2.front()];
if(d>=m&&d<=k)
{
ans=max(ans,i-be);
}
else if(d<m)
{
continue;
}
else if(d>k)
{
int idx1=q1.front();
int idx2=q2.front();
if(idx1<idx2)
{
be=idx1;
q1.pop_front();
}
else
{
be=idx2;
q2.pop_front();
}
}
}
cout<<ans<<endl;
}
}
Bad Hair Day
The meaning of the question: There are n cows, each cow has a height, the cow can only see the cow that is shorter than it on the right, ask the total number of cows that can be seen by n cows.
Solution: Maintain a monotonically decreasing stack from right to left. When a cow that is higher than the top element of the stack is inserted, the number of cows it can see is the sum of the number of cows that are shorter than him in the stack and itself.
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int maxn = 80010;
ll a[maxn];
stack <ll> s;
ll ans[maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=n;i>=1;i--)
{
while(!s.empty()&&a[i]>a[s.top()])
{
if(ans[s.top()]!=0)
{
ans[i]+=ans[s.top()];
}
ans[i]++;
s.pop();
}
s.push(i);
}
ll sum=0;
for(int i=1;i<=n;i++)
{
sum+=ans[i];
}
cout<<sum<<endl;
}
Second My Problem First
Question: Given three integers n, a, b. Defining the sequence Si= ai, Ti is the smallest Si found in an interval of length a, and the product of each item Ti mod b is calculated.
Solution: First find the sequence S of length n, and maintain it with a monotonically increasing queue. The first element of the queue is the minimum value of the interval. Note that opening long long will burst the memory.
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1e7+10;
const ll N = 100000;
int n,a,b;
deque <int > q;
int sum[maxn];
int main()
{
while(~scanf("%d%d%d",&n,&a,&b))
{
sum[1]=a%b;
for(int i=2;i<=n;i++)
{
sum[i]=1ll*sum[i-1]*a%b;
}
ll ans=1;
while(!q.empty()) q.pop_back();
for(int i=1;i<=n;i++)
{
while(!q.empty()&&sum[q.back()]>=sum[i])
q.pop_back();
q.push_back(i);
if(q.front()<i-a)
q.pop_front();
ans=ans*sum[q.front()]%b;
}
printf("%lld\n",ans);
}
}
Alice's mooncake shop
The meaning of the question: There are n orders, the store business hours are m, and each order contains the year, month, day, hour, and the number of moon cakes. The next two integers t and s represent the longest storage time of the moon cake and the cost of storing the moon cake for one hour. Next m lines, each line represents the cost of making a moon cake at the current time. Ask what is the minimum cost to satisfy all order requirements.
Solution: Convert the time of each order into hours, maintain a monotonically increasing sequence, and the top element of the stack is the lowest cost in the interval of time length t.
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 100010;
ll t,s;
ll n,m;
deque <ll > q;
map <string ,int > ma;
int d[14]={0,31,28,31,30,31,30,31,31,30,31,30,31};
ll a[maxn];
ll b[maxn];
int check(int x)
{
return (x%4==0&&x%100!=0)||x%400==0;
}
int change(string mon1,int date,int year,int h)
{
int hour=h;
int mon=ma[mon1];
hour+=(date-1)*24;
for(int i=1;i<mon;i++)
{
if(i==2&&check(year))
{
hour+=29*24;
}
else
{
hour+=d[i]*24;
}
}
for(int i=2000;i<year;i++)
{
if(check(i))
{
hour+=366*24;
}
else
{
hour+=365*24;
}
}
return hour;
}
int main()
{
ma["Jan"]=1;ma["Feb"]=2;ma["Mar"]=3;ma["Apr"]=4;
ma["May"]=5;ma["Jun"]=6;ma["Jul"]=7;ma["Aug"]=8;
ma["Sep"]=9;ma["Oct"]=10;ma["Nov"]=11;ma["Dec"]=12;
ios::sync_with_stdio(0);
cin.tie(0);
while(cin>>n>>m,n,m)
{
while(!q.empty()) q.pop_back();
memset(a,0,sizeof a);
for(int i=1;i<=n;i++)
{
string mon1;int date,year,h,r;
cin>>mon1>>date>>year>>h>>r;
int hour=change(mon1,date,year,h);
a[hour+1]+=r;
}
cin>>t>>s;
for(int i=1;i<=m;i++)
{
cin>>b[i];
}
ll ans=0;
for(int i=1;i<=m;i++)
{
while(!q.empty()&&b[i]<=b[q.back()]+s*(i-q.back()))
{
q.pop_back();
}
q.push_back(i);
if(i-t>q.front())
{
q.pop_front();
}
if(a[i])
{
ans=ans+b[q.front()]*a[i]+1ll*(i-q.front())*s*a[i];
}
}
cout<<ans<<endl;
}
}
Fence
The meaning of the question: There are n wooden boards and m workers brushing wooden boards. Each wooden board can only be brushed once at most. Each worker can brush no wooden boards, or brush a continuous piece of wooden boards that does not exceed the length L. The reward for each board is brushed It is P, and S boards should be included in the brushed boards. Ask what the maximum total reward is.
Solution: First, sort the workers according to S, and introduce dp[i,j] to represent the maximum total compensation of the first j boards by the first i workers.
For the i-th worker not to brush, $dp[i][j]=dp[i-1][j]$
For the jth board without brushing, $dp[i][j]=dp[i][j-1]$
For the i-th worker to brush the $k+1$ to $j$ boards, $dp[i][j]=max(dp[i][j],dp[i-1][k]+Pi* (j-k))$
Use a monotonic queue to maintain a monotonically increasing, $dp[i−1,k]−Pi∗k$ monotonically decreasing queue at decision point k. It operates as follows:
1. When j becomes larger, check the element at the head of the queue, and dequeue the decisions less than j-Li.
2. When it is necessary to query the optimal decision, the head of the line is what is required.
3. When a new decision needs to be added to the queue, check the monotonicity of $dp[i-1,k]-Pi*k$ at the end of the queue, dequeue the useless decision directly from the end of the queue, and finally add the new decision to the queue .
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int maxn = 16010;
struct node{
int l,p,s;
}a[200];
int b[maxn];
int dp[110][maxn];
bool cmp(const node& a,const node &b)
{
return a.s<b.s;
}
deque <int > q;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<=k;i++)
{
cin>>a[i].l>>a[i].p>>a[i].s;
}
sort(a+1,a+1+k,cmp);
for(int i=1;i<=k;i++)
{
for(int j=max(0,a[i].s-a[i].l);j<a[i].s;j++)
{
while(!q.empty()&&dp[i-1][q.back()]-a[i].p*q.back()<=dp[i-1][j]-a[i].p*j)
{
q.pop_back();
}
q.push_back(j);
}
for(int j=1;j<=n;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
while(!q.empty()&&q.front()<j-a[i].l) q.pop_front();
if(j>=a[i].s)
{
if(!q.empty())
dp[i][j]=max(dp[i][j],dp[i-1][q.front()]+a[i].p*(j-q.front()));
}
}
}
cout<<dp[k][n]<<endl;
return 0;
}
Queue
The meaning of the question: Given n numbers, find the number farthest to the right of each number that is smaller than it, find how many numbers there are in the middle, and output -1 if there is no number smaller than it.
Solution: use a monotonic queue to maintain a monotonically decreasing array from the back to the front. When an element smaller than the head of the queue is encountered, and there is no number smaller than it to the right of the number, the answer is -1 . Otherwise, it is divided into two to find the first number in the queue that is smaller than it, and the rightmost number is smaller than it.
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int a[maxn];
int b[maxn];
int c[maxn];
int ans[maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
memset(ans,-1,sizeof ans);
int head=1,tail=0;
for(int i=n;i>=1;i--)
{
if(tail==0||a[i]<=a[b[tail]])
{
b[++tail]=i;
c[tail]=a[i];
}
else
{
int id=upper_bound(c+1,c+1+tail,a[i],greater<int >())-c;
ans[i]=max(ans[i],b[id]-i-1);
}
}
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
}
Watching Fireworks is Fun
The meaning of the question: There are n sections on the street, and the interval of each section is 1. Now there are m times of firework shows, of which the $i$ performance is at time ti and at position ai. If it is at position $x$, it will get the happiness value of $b_i-|a_i-x|$. Each unit of time can be shifted by d units of length. At the beginning (at time 1), you can be in any position and ask for the maximum total happiness value.
Solution: This is a dynamic programming problem. We use the array $dp[i][j]$ to represent the first $i$ field of fireworks as the maximum happiness value at the $j$ position. Each moment can be displaced by d unit lengths. The interval between two adjacent fireworks is $t$, and the displacement length in time t is $dt$. The transition state equation can be written as $dp[i][j]=max(dp [i-1][k]+b_i-|a_i-j|)$ where $j-dt<=k<=j+dt$, at this time we convert it to within the range of the interval length $2d*t$ To find the maximum value, at this point we can introduce monotonically decreasing queue maintenance. At the same time, it is necessary to optimize the rolling array to prevent memory explosion.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll ,ll > pll;
const int maxn = 150010;
ll dp[2][maxn]; //Represent the last state by XOR operation
ll n,m,d;
struct node{
ll a,b,t;
}a[maxn];
ll b[maxn];
ll getv(ll b,ll a,ll x)
{
return b-abs(a-x);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>d;
for(int i=1;i<=m;i++)
{
cin>>a[i].a>>a[i].b>>a[i].t;
}
memset(dp,-0x3f3f3f3f,sizeof dp);
for(int i=1;i<=n;i++)
{
dp[0][i]=getv(a[1].b,a[1].a,i);
}
int f=0;
for(int i=2;i<=m;i++)
{
f^=1;
int t=a[i].t-a[i-1].t;
ll x=1ll*d*t;
if(x==0)
{
for(int j=1;j<=n;j++)
{
dp[f][j]=dp[f^1][j]+getv(a[i].b,a[i].a,j);
}
continue;
}
int head=1,tail=0;
int k=1;
for(int j=1;j<=n;j++)
{
while(k<=n&&k<=j+x)
{
while(head<=tail&&dp[f^1][k]>dp[f^1][b[tail]])
{
tail--;
}
b[++tail]=k++;
}
while(head<=tail&&j-x>b[head]) head++;
dp[f][j]=dp[f^1][b[head]]+getv(a[i].b,a[i].a,j);
}
}
ll ans=-1e17;
for(int i=1;i<=n;i++)
{
ans=max(ans,dp[f][i]);
}
cout<<ans<<endl;
}
Beans
The meaning of the question: There are n piles of beans numbered (1~n), select several consecutive piles of beans, put them into bags of size p, and the remainder of the selected beans cannot exceed k, how many bags can be put in at most.
Solution: Find (sum[i] - sum[j]) % p <= k && so that (sum[i] - sum[j])/p is the largest, first, the prefix and sum%p are arranged in order from small to large. Prefix sums are maintained with a monotonically increasing queue, since our selections are continuous, and only a monotonically increasing prefix sum can be guaranteed to be continuous. At the same time, the difference between the remainder of the elements at the head and tail of the team is used to determine whether to leave the team. At this time, the head and tail elements in the team are the left and right intervals of the beans we selected, and the answer can be updated continuously.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair <int,int> pll;
const int maxn = 1000011;
int n,p,k;
int a[maxn];
int b[maxn];
pll s[maxn];
bool cmp(pll a, pll b)
{
if(a.second==b.second)
return a.first<b.first;
else
return a.second<b.second;
}
int main()
{
int t;
scanf("%d",&t);
int tt=0;
while(t--)
{
tt++;
memset(b,0,sizeof b);
int num=0;
int sum=0;
int ans=-1;// Set to -1 to consider the case where the remainder is greater than k.
int head=1,tail=0;
scanf("%d%d%d",&n,&p,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
s[i].first=s[i-1].first+a[i];
s[i].second=s[i].first%p;
}
sort(s,s+1+n,cmp);
for(int i=0;i<=n;i++) //Start from 0 and consider the case where one bag cannot be filled.
{
while(head<=tail&&s[i].first<s[b[tail]].first)
{
tail--;
}
b[++tail]=i; //The following formula is equivalent to (b[tail].first%p-b[head].first%p)>k, ensuring that the remainder of the selected interval is less than k.
while (head<=tail&&s[b[tail]].second-s[b[head]].second>k)
{
head++;
}
if(head<tail) //Calculated when the queue size is greater than 1.
ans=max(ans,(s[b[tail]].first-s[b[head]].first)/p);
}
printf("Case %d: %d\n",tt,ans);
}
}
Cornfields
The meaning of the question: There is a matrix with n rows and columns, two positive integers b, k. For k queries, each time there is a coordinate x, y, and the difference between the maximum value and the minimum value in the matrix of side length b is obtained by taking this coordinate as the upper left corner.
Solution: Monotonic queue solution. For the maximum value, first find the maximum value of the interval b in each row, then find the maximum value of the interval b in each column, and finally find the maximum value of the b*b matrix size. The same is true for finding the minimum value.
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 300;
const int mod = 1e9+7;
int temp[maxn][maxn];
int maxx[maxn][maxn];
int minn[maxn][maxn];
int a[maxn][maxn];
int d[maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
int n,k,m;
cin>>n>>k>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++)
{
int head=1,tail=0;
for(int j=n;j>=1;j--)
{
while(head<=tail&&a[i][j]>=a[i][d[tail]])
{
tail--;
}
d[++tail]=j;
while(head<=tail&&j+k<=d[head])
{
head++;
}
temp[i][j]=a[i][d[head]];
}
}
for(int i=1;i<=n;i++)
{
int head=1,tail=0;
for(int j=n;j>=1;j--)
{
while(head<=tail&&temp[j][i]>=temp[d[tail]][i])
{
tail--;
}
d[++tail]=j;
while(head<=tail&&j+k<=d[head])
{
head++;
}
maxx[j][i]=temp[d[head]][i];
}
}
for(int i=1;i<=n;i++)
{
int head=1,tail=0;
for(int j=n;j>=1;j--)
{
while(head<=tail&&a[i][j]<=a[i][d[tail]])
{
tail--;
}
d[++tail]=j;
while(head<=tail&&j+k<=d[head])
{
head++;
}
temp[i][j]=a[i][d[head]];
}
}
for(int i=1;i<=n;i++)
{
int head=1,tail=0;
for(int j=n;j>=1;j--)
{
while(head<=tail&&temp[j][i]<=temp[d[tail]][i])
{
tail--;
}
d[++tail]=j;
while(head<=tail&&j+k<=d[head])
{
head++;
}
minn[j][i]=temp[d[head]][i];
}
}
while(m--)
{
int x,y;
cin>>x>>y;
int ans=maxx[x][y]-minn[x][y];
cout<<ans<<endl;
}
}
pairs
The meaning of the question: there is a sequence x of size n, and a value k, there are pairs of pairs <a,b> in the sequence, there exists $abs(x[b]-x[a])<=k (a<b )$
Solution: The ruler method. Sort the sequence first, set the head and tail nodes, when the value of the tail node minus the head node is less than or equal to k, add one to the tail node; when it is greater than k, the length between the head and tail nodes satisfies the condition, and then let the head node Add one and repeat the above operation. (can also be written in twos)
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 1e5+10;
typedef long long ll;
ll a[maxn];
ll s[maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
ll ans=0;
int st=1,ed=2;
int sum=0;
while(st<=n)
{
while(ed<=n&&abs(a[ed]-a[st])<=k) ed++;
ans+=ed-st-1;
st++;
}
cout<<ans<<endl;
}
}
String
The meaning of the question: There is a string S, ask how many substrings contain k different letters.
Solution: The ruler method.
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
int vis[30];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
memset(vis,0,sizeof vis);
int len;
string s;
int k;
cin>>s>>k;
len=s.size();
int st=0,ed=0;
int sum=0;
ll ans=0;
while(st<len)
{
while(ed<len&&sum<k) if(vis[s[ed++]-'a']++==0) sum++;
if(sum<k) break;
ans+=len-ed+1;
if(--vis[s[st++]-'a']==0) sum--;
}
cout<<ans<<endl;
}
}
Sum of Consecutive Prime Numbers
The meaning of the question: ask a number n, how many consecutive prime numbers can be represented.
Solution: first make a table for the prime numbers and then take a ruler.
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int a[10010];
int cnt=0;
bool isprime(int x)
{
for(int i=2;i*i<=x;i++)
{
if(x%i==0) return false;
}
return true;
}
int main()
{
for(int i=2;i<=10000;i++)
{
if(isprime(i)) a[cnt++]=i;
}
int n;
while(scanf("%d",&n),n)
{
int st=0,ed=0;
int sum=0;int ans=0;
while(st<cnt)
{
while(ed<cnt&&sum<n) sum+=a[ed++];
if(sum<n) break;
if(sum==n) ans++;
sum-=a[st++];
}
printf("%d\n",ans);
}
}
Graveyard Design
Question: Give a number n. You ask for a series of consecutive numbers whose sum of squares is equal to n.
Solution: The ruler method. Pay attention to the loop end condition, otherwise it will TLE.
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
vector <pair <ll,ll> > g[maxn];
int main()
{
ll n;
scanf("%lld",&n);
int cnt=0;
ll st=1,ed=1;
ll sum=0;
while(st<=n)
{
while(ed*ed<=n&&sum<n) sum+=ed*ed,ed++;
if(sum<n) break;
if(sum==n)
{
g[++cnt].push_back(make_pair(st,ed-1));
}
sum-=st*st,st++;
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
{
ll len=g[i][0].second-g[i][0].first+1;
printf("%lld",len);
for(ll j=g[i][0].first;j<=g[i][0].second;j++)
{
printf(" %lld",j);
}
puts("");
}
}
Subsequence
Question: Given an array of size n, find the minimum length of the subarrays of consecutive elements whose sum is not less than s.
Solution: The ruler method.
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
const int maxn = 100010;
ll a[maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int st=1;int ed=1;
int ans=n+1;
ll sum=0;
while(st<=n)
{
while(ed<=n&&sum<k) sum+=a[ed++];
if(sum<k) break;
ans=min(ans,ed-st);
sum-=a[st++];
}
if(ans==n+1) ans=0;
cout<<ans<<endl;
}
}
Bound Found
The meaning of the question: There is a sequence of size n, m queries, each query has a target number, find a continuous sequence from the sequence, so that the difference between the absolute value of the sum and the target number is the smallest, and each query outputs three integers sum , l,r, respectively represent the continuous sequence value with the smallest difference between its absolute value and the target number and the left and right endpoints of this continuous sequence.
Solution: prefix and + ruler method. First, transform the problem into a monotonic interval to take it with a ruler, so we preprocess the prefix sum and sort it (the position of 0 should be added to the sorting). At this time, we use the ruler to take the difference between the endpoints of the two intervals to get The value closest to the target number.
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 100010;
ll a[maxn];
struct node{
ll s;
int id;
}b[maxn];
bool cmp(node a,node b)
{
return a.s<b.s;
}
ll aabs(ll x)
{
if(x<0) return -x;
else return x;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,k;
while(cin>>n>>k)
{
if(n==0&&k==0) break;
memset(b,0,sizeof b);
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i].id=i;
b[i].s=b[i-1].s+a[i];
}
sort(b,b+1+n,cmp);
while(k--)
{
int x;
cin>>x;
int st=1,ed=1;
int l=0,r=1;
int minn=1e9;
int ans=0;
int ansl,ansr;
while(l<=n&&r<=n)
{
int num=aabs(b[r].s-b[l].s);
if(abs(num-x)<minn)
{
ansl=b[l].id;
ansr=b[r].id;
ans=num;
minn=abs(num-x);
if(minn==0) break;
}
if(num>x) l++;
else if(num<x) r++;
else break;
if(l==r) r++;
}
if(ansl>ansr) swap(ansr,ansl);
cout<<ans<<" "<<ansl+1<<" "<<ansr<<endl;
}
}
}
First One
The meaning of the question: Find a given sequence of length n, where s represents the sum of ai to aj.
Solution: math + ruler.
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
ll a[maxn];
ll s[maxn];
ll l[40],r[40];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
l[0]=0;r[0]=1;
for(int i=1;i<34;i++)
{
l[i]=(1ll<<i);
r[i]=((1ll<<(i+1))-1);
}
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
ll ans=0;
ll num=0;
ll st=1,ed=1;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
for(ll i=1;i<=34;i++)
{
st=1,ed=num=0;
if(s[n]<l[i-1]) break;
for(ll j=1;j<=n;j++)
{
st=max(st,j);
while(st<=n&&s[st]-s[j-1]<l[i-1]) st++;
ed=max(ed,st-1);
while(ed+1<=n&&s[ed+1]-s[j-1]>=l[i-1]&&s[ed+1]-s[j-1]<=r[i-1]) ed++;
if(ed>=st)
num+=(ed-st+1)*j+(ed+st)*(ed-st+1)/2;
}
ans+=num*(i);
}
cout<<ans<<endl;
}
}
Max Sum of Max-K-sub-sequence
The meaning of the question: There is a ring, $a_1,a_2,a_3...a_n$ requires to find a continuous sequence whose length does not exceed K from the ring, make its sum maximum, and find the start position and end position.
Solution: The problem is to find the maximum value of a continuous k-length sequence in the ring. First, preprocess the prefix sum of n+k-1 items, traverse from 1 to n+k-1 to find the maximum prefix sum of each segment, and the prefix sum of each segment. It is s[i]-s[j]. At this time, we only need to minimize s[j] to get the largest sequence when traversing to i, then the problem becomes the problem of maintaining a monotonically increasing queue.
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int maxn = 1e5+10;
typedef long long ll;
ll a[2*maxn];
ll s[2*maxn];
int q[maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
// memset(q,0,sizeof q);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];
}
for(int i=1;i<=n+k-1;i++)
{
s[i]=s[i-1]+a[i];
}
int head=1,tail=0;
ll maxx=-1e9;
int ansl,ansr;
for(int i=1;i<=n+k-1;i++)
{
while(head<=tail&&s[q[tail]]>s[i-1])
tail--;
while(head<=tail&&q[head]<=i-k-1)
head++;
q[++tail]=i-1;
if(s[i]-s[q[head]]>maxx)
{
maxx=s[i]-s[q[head]];
ansl=q[head]+1;
if(i>n)
ansr=i%n;
else
ansr=i;
}
}
cout<<maxx<<" "<<ansl<<" "<<ansr<<endl;
}
}
Finding Seats
The meaning of the question: There is a matrix with rows of r and c, where '.' represents a vacancy. Find k adjacent positions in the matrix (diagonals are also adjacent) and occupy the smallest area. Find the smallest area.
Solution: Maintain a prefix sum for each row and record the number of seats. Enumerate the size of the column interval, and measure the row.
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 310;
char a[maxn][maxn];
int s[maxn][maxn];
int main()
{
int n,m,k;
while(scanf("%d%d%d",&n,&m,&k))
{
if(n==0&&m==0&&k==0) break;
for(int i=1;i<=n;i++)
{
scanf("%s",a[i]+1);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]=='.')
{
s[i][j]=s[i][j-1]+1;
}
else
{
s[i][j]=s[i][j-1];
}
}
}
int ans=1e9;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
int st=1,ed=1;
int sum=0;
while(st<=n)
{
while(ed<=n&&sum<k)
{
sum=sum+s[ed][j]-s[ed][i-1];
ed++;
}
if(sum<k) break;
ans=min(ans,(ed-st)*(j-i+1));
sum=sum-s[st][j]+s[st][i-1];
st++;
}
}
}
printf("%d\n",ans);
}
}