20191016
前言
- 虽然还是不行，但状态稍有回升？？
- T1又出现了做达哥的「周」时的情况，就是觉得太简单了而不敢轻易结束。
- 考试10分钟就打完了T1，然而又花了近20分钟验证一个结论，而且也不敢交，考试快结束时才怼了上去……
- 啊还得感谢出题人，太良心了，三个题代码竟然都都不上K，T1T2甚至没上500B，出题人rp++。
T1
- 如果n>a*b或n<a+b-1直接puts("No")。
- 否则我们先分出b段，每段只有1个数。
- 然后我们将剩下的n-b个数插入段，从前往后扫描段，如果当前段的数量不是a并且还有剩余的数就一直加。
- 然后保证段内元素递增，段间元素递减即可。
- 具体做法是从前往后扫描段，设当前段的数量为k，那么把最大的k个数从小到大输出，然后将最大的数n变为n-k即可。
- 比如n=8,a=4,b=3，那么三段的数量为4,3,1，最终得到的序列是5,6,7,8,2,3,4,1。
- 时间复杂度$Theta(TN)$，空间复杂度$Theta(1)$。代码复杂度O(0)。
#include<cstdio> int main(){ int T,n,a,b,la; scanf("%d",&T); while(T--){ scanf("%d%d%d",&n,&a,&b); if(n<a+b-1 || n>1ll*a*b){puts("No");continue;} puts("Yes"),la=n-b; for(register int i=1,now;i<=b;++i){ now=1; while(now<a&&la)--la,++now; for(register int j=n-now+1;j<=n;++j)printf("%d ",j); n-=now; } puts(""); } return 0; }
T2
- 先将给出的a数组从小到大排序。
- 设前缀和为sum，则当$frac{a_i}{2}>sum_{i-1}$时，$(sum_{i-1},frac{a_i}{2}]$区间中的值一定不美妙。
- 那么我们只需证明$[frac{a_i}{2},sum_i]$区间中的值都是美妙的就可以线性递推了对吧。
- 首先区间T$[frac{sum_i}{2},sum_i]$,区间Q$[frac{sum_{i-1}}{2},sum_{i-1}]$和区间L$[frac{a_i}{2},a_i]$中的值一定美妙。
- 当$frac{a_i}{2}geqslant sum_{i-1}$时$a_igeqslantfrac{sum_i}{2}$，将T和L合并得证。
- 当$frac{a_i}{2}<sum_{i-1}$时$sum_{i-1}>frac{sum_i}{2}$，将T和Q合并后就成了$[frac{a_{i-1}}{2},sum_{i-1}]$的子问题了。
- 看上去可以？
- 那么直接线性递推即可，时间复杂度$Theta(NlogN)$，空间复杂度$Theta(N)$。
#include<cstdio> #include<algorithm> int n; int a[100000]; inline int read(){ int ss(0);char bb(getchar()); while(bb<48||bb>57)bb=getchar(); while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar(); return ss; } int main(){ n=read(); for(register int i=0;i<n;++i)a[i]=read(); std::sort(a,a+n); long long w=0,ans=0; for(register int i=0;i<n;++i){ if((a[i]+1>>1)>w)ans-=(a[i]+1>>1)-w-1; w+=a[i]; } printf("%lld",ans+w); return 0; }