T1

题目大意

给定一个$n$和$k$，然后求按照一定的要求，在$n$个座位的圆桌上最多坐的人的数量。 要求：1、第一个人选择一号位    \qquad\,\, 2、接下来每个人会坐在离最近的人尽可能远的位置    \qquad\,\, 3、每个人离最近的人之间的空位子数量不得小于$k$

题解

对于$10\%$由于$k=0$，可以直接输出$n$。

---

不知道各位的想法如何，我十分敏感地想到了毕导的这个视频，当场就喊出来了。这实在是太像了。 于是我就顺着毕导的思路做这道题: 答案是在$k$确定的前提下，由长度唯一确定的。 首先，就是分治的思想，可以设$f(x)$表示一条长$x$的线段，在满足上述条件的情况下可以放几个人，即答案。 那么题目中给出的是环，我就直接把环拆成2条线段（毕竟直接用环很难写）。 所以只要用奇偶性判断然后不断分治递归就可以了，每次拆成2段，看起来是可以的样子，于是就写了这么一个函数。

ll dfs(ll x){ if(x<k+2) return 1ll; if(x>=k+2&&x<(k+2)*2-1) return 2ll; if(x&1) return dfs(x/2+1)*2-1; //如果是奇数，那么在最中间放人，这也是条件之一 //此时问题变成都包含中间一个的左右两端，容斥一下，减掉中间那个 else return dfs(x/2+1)+dfs(x/2)-1; //同理，在中间偏左或偏右的位置放 }

于是……TLE了最后的一个点。90分。

---

那么肯定是递归有重复导致的常数过大了。很容易可以想到，将一个很大的数，分成两段，不断除以二，很容易算到同一个地方去。因此要记忆化。 可是$10^{18}$的大数据诶，怎么记忆化呀。 诶，这时候就要用到C++的优势STL了。 MAP可以定义下标类型，直接映射，logn解决。 所以总共是$O(lo{g}^{2}n)$可以接受。

代码

#include<bits/stdc++.h> #define ll long long using namespace std; ll n,k; map<ll,ll> mp; ll dfs(ll x){ if(x<k+2) return mp[x]=1ll; if(x>=k+2&&x<(k+2)*2-1) return mp[x]=2ll; if(mp.find(x)!=mp.end()) return mp[x];//在map中查询 if(x&1) return mp[x]=dfs(x/2+1)*2-1; else return mp[x]=dfs(x/2+1)+dfs(x/2)-1; } int main() { scanf("%lld%lld",&n,&k); if(k==0){ printf("%lld\n",n);return 0; } if(n<=k*2+1){ printf("1\n");return 0; }//特判 if(n&1){ printf("%lld\n",dfs(n/2+2)+dfs(n/2+1)-2); }else{ printf("%lld\n",dfs(n/2+1)*2-2); }//把环拆成两段 }

END

注意以后有什么开不下的可以用map，时间换空间多用用STL，c++党的福利