单调栈&单调队列&尺取
Passing the Message
题意：给定n个数，找每一个数左边比它小的最大的数，右边比它小的最大的数，每个数不能越过一个比它大数数去找后面的数。
解法：当找左边比它小的最大的数时，从右到左维护一个单调递减的单调栈，当每插入一个数前，此时这个数一定小于栈顶的元素，则这个数是栈顶元素的一个可能答案，最后不断更新答案即可。找右边的同理。
#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
题意：找建筑物最小可能数量，把建筑物分为n个部分，每一部分有一个高度，一个建筑物可以跨越几个连续的部分，但每个部分只能包含一个可见的建筑物。
解法：从左到右维护一个严格递增的单调栈，当碰到一个比栈顶元素小的高度时，若该高度不等于该状态下上一次弹出的高度，并且不等于栈顶元素的高度，则ans++。注意当高度为0时没有建筑物，此时不用入栈。
#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
题意：在长度为m的区间中，初始maxrating=-1，count=0，当遇到一个比maxrating大的数更新maxrating，同时count+1。
解法：从后往前用单调队列维护一个严格递减的序列，此时队首就是最大值，count就是队列大小。
#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
题意：给顶一个长度为n的序列，两个正整数m，k。在序列中寻找一个区间长度，使得最大值减最小值不小于m并且不大于k，问这样的长度最长能为多少。
解法：分别维护两个单调增队列和单调减队列，此时差值d就是两个队首的差。若d在范围内，更新答案；若d<m，不进行操作；若d>k，删掉两个队列中队首靠前的元素。
#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
题意：有n有奶牛，每一头奶牛都有一个身高，奶牛只能看见右边比它矮的奶牛，问n头奶牛能看见的奶牛的总数量。
解法：从右到左维护一个单调减栈，当每插入一个高于栈顶元素的奶牛时，其能看见奶牛的数量就是栈中比他矮的奶牛能看见的数量和自身的总和。
#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
题意：给定三个整数n，a，b。定义序列Si= ai ，Ti是一个长度为a的区间长度中找到最小的Si，求每一项Ti mod b的积。
解法：先求出长度为n的序列S，用单调递增队列维护，队首元素即为该区间的最小值，注意开long long会爆内存。
#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
题意：有n个订单，商店营业时间m，对于每个订单包含年，月，日，小时，月饼数量。接下来两个整数t，s，分别表示月饼最长能储存的时间和一个月饼储存一个小时的成本。接下来m行，每行表示当前时间制作一个月饼的成本。问满足所有订单要求的最小花费是多少。
解法：将每个订单的时间都转化为小时为单位，维护一个单调递增序列，栈顶元素即为在时间长度为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
题意：有n块木板，和m个工人刷木板，每块木板最多只能被刷一次，每个工人可以不刷木板，或刷连续不超过长度L的一段木板，每刷一块木板的报酬是P，在刷的木板当中要包含S木板。问最大总报酬是多少。
解法：先对工人按S递增排序，引入dp[i,j]表示前i个工人刷前j块木板的最大总报酬。
对于第i个工人不刷，$dp[i][j]=dp[i-1][j]$
对于第j块木板不刷，$dp[i][j]=dp[i][j-1]$
对于第i个工人刷第$k+1$到$j$块木板，$dp[i][j]=max(dp[i][j],dp[i-1][k]+Pi*(j-k))$
用单调队列维护一个决策点k单调递增，$dp[i−1,k]−Pi∗k$单调递减的队列。其操作如下：
1.当 j 变大时,检查队头元素,把小于 j-Li 的决策出队。
2.需要查询最优决策时,队头即为所求。
3.有一个新的决策需要加入队列时,在队尾检查$ dp[i-1,k]-Pi*k$ 的单调性,把无用决策从队尾直接出队,最后把新决策加入队列。
#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
题意：给出n个数字，找到每个数字右边最远比它小的数字，求它们中间有多少个数字，若没有比它小的数字就输出-1。
解法：用单调队列维护一个从后往前的单调递减的数组，当遇到一个小于队首的元素是入队，此时该数字右边没有比它还小的数，则这个个答案为-1。否则就二分去找队列中第一个比它小的数，得到的就是最右边比它小的数。
#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
题意：在街道上有n段区域，每段区域的间隔为1。现在有m次烟火表演，其中第$i$次次表演在时刻ti，位置ai，如果位于位置$x$，会得到$b_i-|a_i-x|$的快乐值。每一个单位的时间可以位移d个单位长度。起初(在1时刻)，可以处于在任意位置，问最大总快乐值。
解法：这是一道动态规划问题，我们用数组$dp[i][j]$表示前$i$场烟花为于$j$位置的最大快乐值。每个时刻可以位移d个单位长度，相邻两场烟花相隔时间$t$，时间t内可以位移长度为$dt$,转移态方程可以写为$dp[i][j]=max(dp[i-1][k]+b_i-|a_i-j|)$其中$j-dt<=k<=j+dt$，此时我们就转化为了在区间长度$2d*t$的范围内求最大值，此时我们就可以引入单调递减队列维护。同时还要通过滚动数组优化，防止爆内存。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll ,ll > pll;
const int maxn = 150010;
ll dp[2][maxn]; //通过异或操作表示上一次状态
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
题意：有n堆豆子编号为(1~n)，选择连续的几堆豆子，装进大小为p的袋子中，且被选择的豆子余数不能超过k，问最多可以装几个袋子。
解法：求(sum[i] - sum[j]) % p <= k && 使得（sum[i] - sum[j]）/p最大，首先前缀和sum%p从小到大给数组排列。用单调递增队列维护前缀和，因为我们的选择是连续的，只有前缀和单调递增才能保证是连续的。同时用队首和队尾元素余数的差距判断是否出队，此时队中的头尾元素即为我们所选豆子的左右区间，不断更新答案即可。
#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;// 设为-1考虑怎样余数都大于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++) //从0开始考虑一袋也装不了的情况。
{
while(head<=tail&&s[i].first<s[b[tail]].first)
{
tail--;
}
b[++tail]=i; //下面式子等价于(b[tail].first%p-b[head].first%p)>k，保证所选区间余数小于k。
while (head<=tail&&s[b[tail]].second-s[b[head]].second>k)
{
head++;
}
if(head<tail) //当队列大小大于1时计算。
ans=max(ans,(s[b[tail]].first-s[b[head]].first)/p);
}
printf("Case %d: %d\n",tt,ans);
}
}
Cornfields
题意：有一个行列都为n的矩阵，两个正整数b，k。对于k次询问，每次都有一个坐标x，y，以该坐标为左上角求边长b的矩阵内，最大值和最小值的差。
解法：单调队列求解。对于最大值，先找出每一行中区间为b的最大值，然后再找出没一列区间b的最大值，最后就能求出b*b矩阵大小的最大值。求最小值同理。
#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
题意：有一个大小为n的序列x，和一个值k，问序列中有对少对<a,b>存在$abs(x[b]-x[a])<=k (a<b)$
解法：尺取法。先对序列排序，设置头尾节点，当尾节点减头结点值小于等于k时，尾结点加一；当大于k时，头尾节点间的长度即满足条件，然后再让头结点加一，重复上面操作。(也可以用二分写)
#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
题意：有一个字符串S，问有多少个子串包含k个不同的字母。
解法：尺取法。
#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
题意：问一个数n，可以由多少段连续的质数表示。
解法：先对素数打表然后尺取。
#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
题意：给出一个数n。你要求一段连续的数，这些数的平方和等n。
解法：尺取法。注意循环结束条件，不然会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
题意：有一个大小为n的数组，求出总和不小于s的连续元素的子数组长度的最小值。
解法：尺取法。
#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
题意：有大小为n的数列，m次询问，每次询问有一个目标数，从数列中找出连续序列，使得和的绝对值与目标数之差最小，每次查询输出三个整数sum,l,r，分别表示其绝对值与目标数之差最小的连续序列值与此连续序列的左右端点。
解法：前缀和＋尺取法。首先把问题转化在一个单调的区间内才能用尺取，所以我们预处理出前缀和并进行排序(排序要加上0的位置),此时我们用尺取求两个区间端点作差从而得到最接近目标数的值。
#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
题意：求给定长度为n的序列，求其中s表示ai到aj的和。
解法：数学+尺取。
#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
题意：有一个环，$a_1,a_2,a_3...a_n$要求从环上找出一段长度不超过 K 的连续序列，使其和最大，并找出起始位置和终止位置。
解法：题目求环中连续k长度序列的最大值，先预处理出n+k-1项的前缀和，从1到n+k-1遍历找每一段最大的前缀和，每一段的前缀和是s[i]-s[j]，此时我们只要将s[j]最小便可得到当遍历到i时最大的序列，则为问题便装化成了维护一个单调递增队列的问题。
#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
题意：有一个行列为r,c的矩阵，其中'.'表示空位，在矩阵中找k个相邻位置(对角线也算相邻)并且占用面积最小，求面积最小是多少。
解法：对每一行维护一个前缀和，记录座位的个数。枚举列区间的大小，对行进行尺取。
#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);
}
}