2017.10.28 QB模拟赛 —— 下午
2024-08-28 09:19:34
T1
按x值排序
遇到第二种牌插入 遇到第一种牌 查询<=y 的最小值 删除他
splay multiset
cys大佬说 multiset就是不去重的set,
#include <algorithm> #include <cstdio> #define N 100005 using namespace std; struct node { int x,y,opt; bool operator<(node a)const { if(opt!=a.opt&&x==a.x) return opt>a.opt; else return x<a.x; } }card[N<<]; ]; inline void pushup(int rt) { ],r=ch[rt][]; siz[rt]=siz[l]+siz[r]+cnt[rt]; } inline void ins(int &rt,int x) { if(!rt) { rt=++cn; data[cn]=x; siz[cn]=cnt[cn]=; return; } if(data[rt]==x) { cnt[rt]++; siz[rt]++; return; } if(x<data[rt]) { ins(ch[rt][],x); fa[ch[rt][]]=rt; pushup(rt); } else { ins(ch[rt][],x); fa[ch[rt][]]=rt; pushup(rt); } } int ask_pre(int rt,int x) { int p=rt,ret=0x7fffffff; while(p) { ]; else { ret=data[p]; p=ch[p][]; } } return ret; } inline ]==x;} void rotate(int x) { int y=fa[x],z=fa[y],b=son(x),c=son(y),a=ch[x][!b]; if(z) ch[z][c]=x; else root=x; fa[x]=z; if(a) fa[a]=y; ch[x][!b]=y;ch[y][b]=a; fa[y]=x; pushup(y);pushup(x); } void splay(int x,int i) { while(fa[x]!=i) { int y=fa[x],z=fa[y]; if(z==i) rotate(x); else { if(son(y)==son(x)) rotate(y),rotate(x); else rotate(x),rotate(x); } } } int getmn(int rt) { ,p=rt; while(p) { ret=p; p=ch[p][]; } return ret; } void del(int rt,int x) { if(data[rt]==x) { ) { cnt[rt]--; siz[rt]--; } else { splay(rt,); ]); ) { splay(p,rt); root=p;fa[p]=; ch[p][]=ch[rt][]; fa[ch[rt][]]=p; } else { root=ch[rt][]; fa[ch[rt][]]=; } } return; } if(x<data[rt]) { del(ch[rt][],x); pushup(rt); } else { del(ch[rt][],x); pushup(rt); } } int main(int argc,char *argv[]) { freopen("water.in","r",stdin); freopen("water.out","w",stdout); scanf("%d",&n); ;i<=n;++i) scanf(; ;i<=n<<;++i) scanf(; sort(card+,card++n*); ;i<=n<<;++i) { ) ins(root,card[i].y); else { if(!cn) continue; int v=ask_pre(root,card[i].y); if(v==0x7fffffff) continue; ans++; del(root,v); } } printf("%d\n",ans); fclose(stdin); fclose(stdout); ; }
splay
#include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> #include <set> using namespace std; int n; multiset <int> s; ],b[]; int cmp(node i,node j) {return i.x<j.x;} int main() { freopen("water.in","r",stdin); freopen("water.out","w",stdout); int T; T=; while(T--) { scanf("%d",&n); ;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y); ;i<n;i++) scanf("%d%d",&b[i].x,&b[i].y); sort(a,a+n,cmp); sort(b,b+n,cmp); s.clear(); ,ans=; ;i<n;i++) { while(a[i].x>=b[k].x&&k<n) { s.insert(b[k].y); k++; } if(s.empty())continue; multiset<int>::iterator it=s.upper_bound(a[i].y); if (it==s.begin()) continue; it--; ans++; s.erase(it); } printf("%d\n",ans); } ; }
multiset
T2
最少需要 log(n)/log(2) 个
dp[j][k] 表示 金币和是 j 最大金币是k 的方案总数
枚举下一枚金币是什么
#include <cstdio> #include <cmath> #define N 1005 inline int min(int a,int b) {return a>b?b:a;} int n,s,ans,f[N][N],dp[N][N]; int main(int argc,char *argv[]) { freopen("dream.in","r",stdin); freopen("dream.out","w",stdout); scanf("%d",&n); s=log2(n)+; f[][]=; ;i<s;++i) { ;j<=n;++j) ;k<=n;++k) if(f[j][k]) ;l<=j+;++l) dp[min(n,j+l)][l]+=f[j][k]; ;j<=n;++j) ;k<=n;++k) f[j][k]=dp[j][k],dp[j][k]=; } ;i<=n;++i) ans+=f[n][i]; printf("%d %d\n",s,ans); fclose(stdin); fclose(stdout); ; }
T3
dp[i][j] 表示 1~i 切了j刀的最优解
dp[i][j]=min{dp[k][j-1]+sum(k+1,i)}
从大到小 枚举k 更新sum
复杂度 20*N^2
固定j,随着i的增大,k不会减少
1d1d动态规划优化
20*n^2的简单dp -> 在固定j的情况下 随着i的增大,k不降 -> 分治求dp值
#include <cstdio> #define N 100005 typedef long long LL; int n,k,L,R,a[N],s[N]; LL sum,f[N],g[N]; void update(int x,int type) { ) sum+=s[a[x]],++s[a[x]]; else --s[a[x]],sum-=s[a[x]]; } void move(int l,int r) { ); ); ); ); } void work(int l,int r,int fl,int fr) { if(fl>fr) return; ,mi; LL mx=1LL<<; for(int i=l;i<mid&&i<=r;++i) { move(i+,mid); if(mx>f[i]+sum) mx=f[i]+sum,mi=i; } g[mid]=mx; work(l,mi,fl,mid-); work(mi,r,mid+,fr); } int main(int argc,char *argv[]) { freopen("dp.in","r",stdin); freopen("dp.out","w",stdout); scanf("%d%d",&n,&k); ;i<=n;++i) scanf("%d",&a[i]); f[]=; ;i<=n;++i) f[i]=1LL<<; while(k--) { L=,R=,sum=; ;i<=n;++i) s[i]=; work(,n-,,n); ;i<=n;++i) f[i]=g[i],g[i]=; } printf("%I64d\n",f[n]); fclose(stdin); fclose(stdout); ; }
最新文章
- 【hrbust2294】修建传送门
- [办公自动化]一次制作、多场合多次使用的PPT
- 如何在URL筛选管理器中过滤不需要的URL
- vim代码补全-spf13,YouCompleteMe
- uitableviewcell 和 uibutton
- hdu 3631
- 各种HTTP错误消息含义
- ASP.NET MVC 使用Echarts
- android避免decodeResource图片时占用太大的内存
- 注意:";AspNetPager”的控件“AspNetPager1”必须放在具有 runat=server 的窗体标记内
- Visifire Chart控件设置 柱状图 条的宽窄
- ToDoList-学习中看到的知识盲点
- C#中调用c++的dll
- json文件报expected name at 1 1错误
- 一款值得推荐的shell工具
- Redis + keepalived 高可用群集搭建
- 对于BFS的理解和部分例题(
- GraphQL-前端开发的利剑与桥梁
- 小程序之hover-class
- mssql sql server上如何建一个只读视图–视图锁定的另类解决方案