老师说要向泰山挑夫那样一步一步。
今天的练习赛似乎又回到了上个暑假的时候，只是感觉少了点什么。
题目大都很基础，只挑几个没有解决的问题说一下吧。
6E Exposition 6D Lizards and Basements 2 6C Alice, Bob and Chocolate 6B President's Office 6A Triangle brute 4D Mysterious Present 4C Registration System 4B Before an Exam 4A Watermelon math
题目大意： 给出一些信封的长和宽，还有一个礼物。现在要把礼物装到信封中。可以将信封嵌套装到信封中。要求嵌套的层数最多。求解最多的层数。一件物品（礼物和信封）要被装到信封里，长和宽必须严格小于外面的信封。
大体思路： 先将信封按照长排序，长相等的可以按照宽排序。然后就可以类似于【最长上升子序列】一样进行dp求解。
遇到的问题： 首先是只从能开始装到礼物那个信封开始dp的，而且只把那个信封的层数设为了1，这就导致起点的位置不正确。保存解的时候，也只是考虑了一个，最后把所有的数组都设为了 -1 。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
struct node
{
int id;
ll x,y;
}p[5005];
int head[5005];
int f[5005];
int ans[5005];
int n;
ll w,h;
int beg;
int cmp(node a,node b)
{
if(a.x==b.x) return a.y<b.y;
else return a.x<b.x;
}
void printfs(int now)
{
if(now==-1) return ;
printfs(head[now]);
cout<<p[now].id<<" ";
}
void getans(int beginx)
{
int tmp=beginx;
int nn=0;
while(tmp!=-1)
{
ans[nn++]=tmp;
tmp=head[tmp];
}
cout<<p[ans[nn-1]].id;
for(int i=nn-2;i>=0;i--)
{
cout<<" "<<p[ans[i]].id;
}
cout<<endl;
}
int main()
{
cin>>n>>w>>h;
for(int i=0;i<n;i++)
{
cin>>p[i].x>>p[i].y;
p[i].id=i+1;
}
sort(p,p+n,cmp);
// for(int i=0;i<n;i++)
// {
// cout<<p[i].x<<" "<<p[i].y<<endl;
// }
beg=-1;
for(int i=0;i<n;i++)
{
if(p[i].x>w&&p[i].y>h)
{
beg=i;
break;
}
}
//cout<<"--"<<beg<<endl;
if(beg==-1)
{
cout<<"0"<<endl;
}
else
{
memset(f,0,sizeof(f));
memset(head,-1,sizeof(head));
head[beg]=-1;
//f[beg]=1;
for(int i=0;i<n;i++)
{
if(p[i].x>w&&p[i].y>h)
{
f[i]=1;
}
}
for(int i=0;i<n;i++)
{
if(!(p[i].x>w&&p[i].y>h)) continue;
for(int j=0;j<i;j++)
{
if(!(p[j].x>w&&p[j].y>h)) continue;
if((p[i].x>p[j].x)&&(p[i].y>p[j].y)&&(f[i]<f[j]+1))
{
head[i]=j;
f[i]=f[j]+1;
}
}
}
int max=-1;
int tmp;
for(int i=beg;i<n;i++)
{
if(f[i]>max)
{
max=f[i];
tmp=i;
}
}
cout<<f[tmp]<<endl;
//printfs(tmp);
getans(tmp);
// cout<<endl;
}
return 0;
}题意： 给出一些书，这些书已经固定了次序。从中选出一个区间，保证这个区间最长，而且不超过设定的值 k 。只输出最长区间的书的范围。
大体思路： 考虑到记录每个区间最大值和最小值的问题，我想到了用单调队列，两个单调队列分别用来保存最大值和最小值。然后如果最大值和最小值超过了 k ，就两个队列中编号最小的那个值，并根据区间的长度保存区间的范围（用了无数个 vector ）。最后输出最长区间的区间范围即可。
遇到的问题： 感觉就是题意没理解好，最后看着数据才慢慢理解了题意。这道题算是根据数据水过的吧。。。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct node
{
int id;
int h;
}p[100005];
int n,k;
deque<node>Qinc;
deque<node>Qdec;
vector<int>ans[100005];
int maxlen;
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>p[i].h;
p[i].id=i+1;
}
maxlen=0;
Qinc.clear();
Qdec.clear();
for(int i=0;i<100000;i++) ans[i].clear();
Qinc.push_back(p[0]);
Qdec.push_back(p[0]);
int begins,ends;
begins=1;ends=1;
for(int i=1;i<n;i++)
{
//cout<<Qinc.size()<<endl;
//cout<<Qdec.size()<<endl;
while((!Qinc.empty())&&(p[i].h<Qinc.back().h)) Qinc.pop_back();
while((!Qdec.empty())&&(p[i].h>Qdec.back().h)) Qdec.pop_back();
Qinc.push_back(p[i]);
Qdec.push_back(p[i]);
if(Qdec.front().h-Qinc.front().h>k)
{
ends=i;
//cout<<begins<<" "<<ends<<endl;
if(ends-begins>0)
{
ans[ends-begins].push_back(begins);
ans[ends-begins].push_back(ends);
if(ends-begins>maxlen) maxlen=ends-begins;
}
// if(ends-begins==0&&p[begins-1].h<=k)
// {
// ans.push_back(begins);
// ans.push_back(ends);
// if(ends-begins>maxlen) maxlen=ends-begins;
// }
while(Qdec.front().h-Qinc.front().h>k)
{
if(Qinc.front().id<Qdec.front().id)
{
begins=Qinc.front().id+1;
Qinc.pop_front();
}
else if(Qinc.front().id>Qdec.front().id)
{
begins=Qdec.front().id+1;
Qdec.pop_front();
}
}
}
}
if(Qdec.front().h-Qinc.front().h<=k)
{
//cout<<begins<<" "<<n<<endl;
if(n-begins>0)
{
ans[n-begins].push_back(begins);
ans[n-begins].push_back(n);
if(n-begins>maxlen) maxlen=n-begins;
}
// if(n-begins==0&&p[n-1].h<=k)
// {
// ans.push_back(begins);
// ans.push_back(n);
// if(n-begins>maxlen) maxlen=n-begins;
// }
}
if(maxlen!=0)
{
cout<<maxlen+1<<" "<<ans[maxlen].size()/2<<endl;
for(int i=0;i<ans[maxlen].size();i+=2)
{
cout<<ans[maxlen][i]<<" "<<ans[maxlen][i+1]<<endl;
}
}
else
{
cout<<1<<" "<<n<<endl;
for(int i=1;i<=n;i++)
{
cout<<i<<" "<<i<<endl;
}
}
return 0;
}贴个几个简单的代码理解一下吧，比我的代码简单多了。
代码1：
#include <stdio.h>
#include <set>
#define forn(i, n) for(int i=0;i<(n);i++)
int n, k, h[100000];
int a, b, r[100000];
int main() {
scanf("%d%d", &n, &k);
forn(i, n) scanf("%d", h+i);
std::multiset<int> s;
int t=0;
forn(i, n) {
s.insert(h[i]);
while((*s.rbegin()-*s.begin())>k) s.erase(s.find(h[t++]));
if(i-t+1>a) { a=i-t+1; r[0]=t; b=1; }
else if(i-t+1==a) { r[b++]=t; }
}
printf("%d %d\n", a, b);
forn(i, b) printf("%d %d\n", r[i]+1, r[i]+a);
return 0;
}
//by varwat代码2：
#include <deque>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector <pair<int, int> > seg;
deque <pair<int, int> > mx, mn;
int main() {
ios_base::sync_with_stdio(false);
int n, k, h;
int len = 0, p = 1;
cin >> n >> k;
for (int i=1; i<=n; ++i) {
cin >> h;
while (!mx.empty() && h > mx.back().first) mx.pop_back();
mx.push_back(make_pair(h, i));
while (!mn.empty() && h < mn.back().first) mn.pop_back();
mn.push_back(make_pair(h, i));
while (mx.front().first - mn.front().first > k) {
while (!mn.empty() && mn.front().second <= p) mn.pop_front();
while (!mx.empty() && mx.front().second <= p) mx.pop_front();
++p;
}
if (i - p > len) {
len = i - p;
seg.clear();
}
if (i - p == len) {
seg.push_back(make_pair(p, i));
}
}
cout << len + 1 << ' ' << seg.size() << endl;
for (int i=0; i<(int)seg.size(); ++i) cout << seg[i].first << ' ' << seg[i].second << endl;
return 0;
}
//by delta_4d