• 欢迎光临~

# HNOI 2014-2017 泛做

## 2017 大佬

[F_1+F_2leq c_i and c_i-F_1-F_2leq MaxDay-day_1-day_2 ]

``````#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
const int M = 1005;
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,mc,up,Day,a[M],b[M],c[M],dp[M][M];
struct node{int d,f,l;};map<pair<int,int>,int> mp;
struct shit
{
int x,y;
bool operator < (const shit &b) const
{return y<b.y;}
}s[10000005];
void bfs()
{
queue<node> q;q.push(node{1,1,0});
while(!q.empty())
{
node u=q.front();q.pop();
if(u.d==Day) continue;
q.push(node{u.d+1,u.f,u.l+1});
long long t=1ll*u.f*u.l;
if(u.l>1 && t<=up && !mp.count(make_pair(t,u.l)))
{
mp[make_pair(t,u.l)]=1;s[++k]=shit{u.d+1,t};
q.push(node{u.d+1,t,u.l});
}
}
}
signed main()
{
for(int i=1;i<=n;i++)
for(int j=a[i];j<=mc;j++)
{
int id=min(j-a[i]+b[i],mc);
dp[i][j-a[i]]=max(dp[i][j-a[i]],dp[i-1][j]+1);
dp[i][id]=max(dp[i][id],dp[i-1][j]);
}
for(int i=1;i<=n;i++)
for(int j=0;j<=mc;j++)
Day=max(Day,dp[i][j]);
bfs();sort(s+1,s+1+k);
for(int i=1;i<=m;i++)
{
if(c[i]<=Day) {puts("1");continue;}
int fl=0,mn=0;
for(int j=k,p=1;j>=1;j--)
{
while(p<=k && s[j].y+s[p].y<=c[i])
mn=min(mn,s[p].x-s[p].y),p++;
if(s[j].y<=c[i] && mn+c[i]-s[j].y<=Day-s[j].x)
{fl=1;break;}
}
printf("%dn",fl);
}
}
``````

## 2017 单旋

``````#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int M = 100005;
#define sit set<int>::iterator
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
void write(int x)
{
if(x>=10) write(x/10);
putchar(x%10+'0');
}
int n,m,a[M],b[M],c[M];
//namespace segment-tree
void down(int i)
{
}
void add(int i,int l,int r,int L,int R,int c)
{
if(l>R || L>r) return ;
int mid=(l+r)>>1;down(i);
tr[i]=tr[i<<1]+tr[i<<1|1];
}
void ins(int i,int l,int r,int id,int c)
{
if(l==r) {tr[i]=c;return ;}
int mid=(l+r)>>1;down(i);
if(mid>=id) ins(i<<1,l,mid,id,c);
else ins(i<<1|1,mid+1,r,id,c);
tr[i]=tr[i<<1]+tr[i<<1|1];
}
int ask(int i,int l,int r,int id)
{
if(l==r) return tr[i];
int mid=(l+r)>>1;down(i);
}
//using set to maintain spaly
set<int> s;int rt,fa[M],ch[M][2];
int fuck(int x)
{
if(!rt) {rt=x;s.insert(x);ins(1,1,n,x,1);return 1;}
sit it=s.lower_bound(x);int ans=0;
if(it!=s.end() && !ch[*it][0])
{
ch[*it][0]=x;fa[x]=*it;
s.insert(x);return ans;
}
it--;ch[*it][1]=x;fa[x]=*it;
s.insert(x);return ans;
}
int spmin()
{
int v=*s.begin();
if(v==rt) return 1;
ch[fa[v]][0]=ch[v][1];fa[ch[v][1]]=fa[v];
fa[v]=0;ch[v][1]=rt;fa[rt]=v;rt=v;return d;
}
int spmax()
{
int v=*s.rbegin();
if(v==rt) return 1;
ch[fa[v]][1]=ch[v][0];fa[ch[v][0]]=fa[v];
fa[v]=0;ch[v][0]=rt;fa[rt]=v;rt=v;return d;
}
int delmin()
{
int d=spmin();s.erase(rt);
int tmp=rt;rt=ch[tmp][1];ch[tmp][1]=0;
}
int delmax()
{
int d=spmax();s.erase(rt);
int tmp=rt;rt=ch[tmp][0];ch[tmp][0]=0;
}
signed main()
{
for(int i=1;i<=m;i++)
{
}
sort(c+1,c+1+n);n=unique(c+1,c+1+n)-c-1;
for(int i=1;i<=m;i++) if(a[i]==1)
b[i]=lower_bound(c+1,c+1+n,b[i])-c;
for(int i=1;i<=m;i++)
{
if(a[i]==1) write(fuck(b[i]));
if(a[i]==2) write(spmin());
if(a[i]==3) write(spmax());
if(a[i]==4) write(delmin());
if(a[i]==5) write(delmax());
puts("");
}
}
``````