T1:
金秋九月，yukiii来到了大学校园，开启了一段全新的生活。但在此之前，yukiii还要将年久失修的宿舍进行翻新。现在他和他的舍友正在粉刷宿舍的墙壁。
宿舍的墙壁可以抽象为一个有限但足够大的网格，网格中大部分都已经被 yukiii的舍友们粉刷完毕，只剩下n列尚未粉刷，且在第i列中未被粉刷的部分是从地面开始向上的长为 ???? 的连续段。刷墙是一件十分枯燥且消耗体力的工作，因此yukiii也会采用一个十分简单粗暴的方式完成这项工作：将刷子置于某一个格子当中，然后从上、下、左、右中选择一个方向一直刷下去。yukiii将这称作是一次操作。但yukiii的舍友很快便对他的这种工作方式感到反感：yukiii经常会用自己的刷子扫到已经被粉刷过的部分，这会导致已经干掉的油漆再次湿掉，十分影响美观。因此yukiii的舍友HHC要求yukiii在刷墙的过程中不能触碰到其
他人已经粉刷过的部分。
现在yukiii想知道自己至少需要几次操作才能在不碰到别人已经刷过的部分的情况下完成宿舍墙壁的粉刷工作。
题解：
如果不考虑竖着涂的话，不就是noip d1 t1了吗？？？那么考虑怎么处理这个区别，首先有一个性质:显然我们要么不横着涂，要么把 ccc 到区间最小值这一段全部横着涂完（反证即可）
那么通过这个，用分治思想和递归调用，每次找到一段区间中最小值的位置，然后不断递归，找到单个元素，跟上层的最小高度比较，如果大于上层最小高度，说明不能刷完，还需要用一次机会，所以返回1，如果小于等于，就不需要在浪费机会了，合并的时候加上本区间最小高度，减去上层区间的最小高度，跟本区间所有竖着刷比较，取较小的值。
还有怎么过5e5的时间复杂度喃？我们只要尽量快的去查找到最小值的位置，时间就优化了，考虑怎么快速查找区间最小值( RMQ是个好东西啊 )；
代码：
#include<bits/stdc++.h> using namespace std; #define re register #define N 500005 #define ll long long int n,a[N]; int lg[N],st[N][33]; void rmq() { lg[0]=-1; for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1; for(int i=1;i<=n;i++) { st[i][0]=i; } for(int j=1;j<=lg[n];j++) for(int i=1;i+(1<<j)-1<=n;i++)//记住rmq的思想两端区间的最小值的维护 { st[i][j]=a[st[i][j-1]]<a[st[i+(1<<j)-1][j-1]]?st[i][j-1]:st[i+(1<<(j-1))][j-1]; } } int query(int l,int r) { int len=lg[r-l+1]; return a[st[l][len]]<a[st[r-(1<<len)+1][len]]?st[l][len]:st[r-(1<<len)+1][len]; }//在这个区间中是横着涂好还是竖着涂好 ll dfs(int l,int r,int h)//类似于 noip 2018 d1t1，当时就打的分治 { if(l>r) return 0; if(l==r) { if(a[l]<=h) return 0; else return 1; } int pos=query(l,r);//上一层的高度 return min((ll)(r-l+1),dfs(l,pos-1,a[pos])+dfs(pos+1,r,a[pos])+a[pos]-h); } //跟D1T1的唯一区别就是跟竖的比较 int main() { freopen("paint.in","r",stdin); freopen("paint.out","w",stdout); scanf("%d",&n); for(re int i=1;i<=n;++i) scanf("%d",&a[i]); rmq(); printf("%lld",dfs(1,n,0)); return 0; }
T2:
入学考试
进入大学后第一件比较重要的事情就是入学考试。yukiii为了确保自己顺利通过测试在暑假刻苦学习。
在学习代数的过程中，他知道了二元运算在集合上的封闭性。但这并不能
难倒他，于是yukiii便提出了一个全新的概念：反封闭。
对于一个数集 ?? ⊂ ??+，我们称其是反封闭的当且仅当：
现在yukiii想得到一个最大元素恰好为 2?? − 1 的反封闭集，同时他希望
这个集合中的元素个数不超过 。
题解：
首先我想过爆搜，想过数位dp，哇，但是！！！我都没有发现它是个构造序列的题！！
这里给出一个构造：取B={1,2,3,4,? ,2t−1,2t,? ,2n−1}此时集合大小为2n−1。
那么考虑如果不超过k的话，就尽量走得快，那么就考虑倍增，最后是n-1个1，如果现在有了2个1，那就就通过不断左移，去创造出来n-1个1，考虑左移带来的影响，每移动1个相当于倍增在序列中就会出现新的数，就是不断模拟倍增和左移的过程
代码：
#include<bits/stdc++.h> using namespace std; #define ll long long #define N 500003 ll res[1020][1500]; int n,k; template <class T> void read(T &x) { char c;int sign=1; while((c=getchar())>‘9‘||c<‘0‘) if(c==‘-‘) sign=-1; x=c-48; while((c=getchar())>=‘0‘&&c<=‘9‘) x=x*10+c-48; x*=sign; } int main()//把它完全当做模拟来搞 { freopen("exam.in","r",stdin); freopen("exam.out","w",stdout); read(n);read(k); int ans=1; for(int i=1;i<n;++i) res[ans][i]=0;//putchar(‘0‘); res[ans][n]=1; int end=1; int num=1;//每一次要移的位数 int p=1; while(num!=n) { if(end) { if(num*2>n) break; int p=1; while(p<=num)//先就是倍增的跳 { ans++; for(int i=1;i<=n-num-p;i++) res[ans][i]=0; for(int i=n-num-p+1;i<=n-p;i++) res[ans][i]=1; for(int i=n-p+1;i<=n;i++) res[ans][i]=0; p++;//1-position } end=0; } else { num=num*2;//2^n-1,左移 ans++; for(int i=1;i<=n-num;i++) res[ans][i]=0; for(int i=n-num+1;i<=n;i++) res[ans][i]=1; end=1; }//001111 } if(num<n)//倍增到最大了 { int p=1; while(p<=n-num) { //考虑左移对答案造成什么影响，因为倍增就最多进1,无法做到把num长度左移,要占答案 ++ans;//最后还有空缺的时候就要继续跳(左移) for(int i=n-num-p+1;i<=n-p;i++) res[ans][i]=1; for(int i=n-p+1;i<=n;i++) res[ans][i]=0; p++; } } ans++; for(int i=1;i<=n;i++) res[ans][i]=1; printf("%d\n",ans); for(int i=1;i<=ans;i++) { for(int j=1;j<=n;j++) printf("%d",res[i][j]);//对于每一个01串记一下答案 printf("\n"); } }
T3：待更，博主尽量今天晚上就写出来
2019.10.7 机房练习赛（递归+分治，模拟+性质，01分数规划+树上背包）
原文：https://www.cnblogs.com/lkx422/p/11632437.html
