终于杂题选讲恢复成省选难度了, 个个都放飞自我??
SP19997
看到这个式子以及吓人的数据范围, 能猜到拉格朗日插值, 我们尝试证明.
考虑朴素的扰动法, 给式子乘个 \(a\):
\[ \begin{align*} aS(n)&=\sum_{i=1}^{n+1} a^i (i-1)^{r} \end{align*} \]
于是我们就有
\[ (1-a)S(n)=\sum_{i=1}^{n} a^i (i^r-(i-1)^r)-a^{n+1}n^r\S(n)=\frac 1 {1-a}\sum_{i=1}^{n} a^i (i^r-(i-1)^r)-\frac{a^{n+1}n^r}{1-a} \]
然而 \(n\)在指数上比较不爽, 所以除个 \(a^{n+1}\):
\[ S'(n)=\frac {S(n)} {a^{n+1}}=\frac 1 {a^{n+1}(1-a)}\sum_{i=1}^{n} a^i (i^r-(i-1)^r)-\frac{n^r}{1-a} \]
容易发现这已经完成归纳法的第二步了, 我们只需要证出第一步, 即 \(r=0\)时这个式子是一个关于 \(n\)的多项式:
\[ S'(n)=\frac{1}{a^{n+1}}\times \frac{1-a^{n+1}}{1-a}=\frac 1 {1-a}(\frac 1 {a^{n+1}}-1) \]
痛苦的事情来了: 这东西其实并不是常数, 还带着一个 \(\frac 1 {a^{n+1}}\)......
然而, 显然可以看出,\(\frac 1 {a^{n+1}}\)的系数恰好是 \(n^0\)的系数的相反数, 并且在 \(r>0\)的推导中会保持这个样子.
于是我们假设除去 \(\frac 1 {a^{n+1}}\)的关于 \(n\)的 \(r\)次多项式是 \(g(n)\), 那么就有
\[ S'=g(n)-\frac 1 {a^{n+1}}g(0) \]
只需要求出 \(g(0)\), 就可以插值搞出 \(g(n)\)了.
考虑多项式的性质: 只需要做 \(r+1\)阶差分, 它就没了.
于是差分的时候存一下常数和 \(g(0)\)的系数, 就可以解出 \(g(0)\)了.
容易证明 \(g(0)\)的系数不为 0, 只需要把差分的式子摆出来就可以了.
AGC040D
首先显然合法的点构成一个前缀.
画出两人从起点开始走的 t-s 图像 (即横坐标是 s, 纵坐标是 t), 放在一个坐标系内. 考虑 Snuke 什么时候会胜利: Ringo 选了个点 \(x\), 那么把 Ringo 的图像向下平移, 使得 \(x\) 的纵坐标变成 0. 此时如果两人图像有交点就合法.
于是我们可以直接把 Ringo 的图像往下一点一点平移直到两人图像不再有交点, 此时 Ringo 与 \(x\)轴的交点就是那个前缀的终止位置.
我们以两人最后的交点为界, 右边用 Snuke 的线, 左边用 Ringo 平移后的线, 可以组成一条折线 C. 容易发现 C 的终点必然是 \((n,S),S=\sum a_i\).
为了让与 \(x\)轴的交点横坐标尽可能大, 我们会想要尽可能地快速往上跑达到 \(S\). 容易发现通过把线放在交点左右, 每条线的贡献都可以达到上界:\(\max(a_i,b_i)\), 除了与 \(x\)轴有交点的线的贡献至多 \(b_i\).
枚举与 \(x\)轴有交的线是第 \(k\)条, 二分需要几条线才能到达 \(S\), 然后就可以算出答案了.
- (这什么神仙思路啊??)
- CometOJ 4203
设 \(p=a^{-1}\).
考虑暴力. 枚举有几个人过了题, 尝试把假榜里的人往终榜填. 从左往右扫, 分两种情况.
当 AC 人数还不够时:
如果 \(i\)过了题, 那么 \(p_i\)必须恰好在没人的位置的最前面. 否则 \(i\)肯定 fst 了, 那么他必须比之前 fst 的人更靠后.
当 AC 人数够了时:
如果让他没有交题, 排在第一个没有人的位置, 显然是合法的, 但这意味着后面的人都没有交题.
如果现在这个人还可以令他是交了题的, 那么还有一种选择, 就是让他 fst, 只要位置比之前 fst 的人更靠后. 显然能 fst 就不要不交题.
有点懵, 把代码放上来:
- int check(int cnt)
- {
- rep(i,1,n) vis[i]=0;
- int l=0,mx=cnt,pos=cnt+1,flg=0;
- rep(i,1,n)
- {
- if (l<cnt)
- {
- if (p[i]==l+1) vis[++l]=1;
- else if (p[i]>mx) vis[mx=p[i]]=1;
- else return 1;
- }
- else
- {
- while (pos<=n&&vis[pos]) ++pos;
- if (p[i]!=pos&&(flg||p[i]<mx)) return 1;
- vis[p[i]]=1;
- if (p[i]<mx||flg) flg=1; else mx=p[i];
- }
- }
- return 0;
- }
于是 \(O(n^2)\)做法就出来了.
考虑如何优化. 有一个显而易见的性质:\(a[1...cnt]\)必须单调上升, 并且如果 \(cnt=i\)合法且 \(a_{i+1}>a_i\), 那么 \(cnt=i+1\)也合法.
于是看一下单调上升的长度, 在这里面合法的人数是一个后缀, 可以直接二分.
- void work()
- {
- read(n);
- rep(i,1,n) read(a[i]),p[a[i]]=i;
- int mn=1e9,mx=-1e9;
- rep(i,1,n) if (a[i]>a[i-1]) mx=i; else break;
- int l=0,r=mx;
- while (l<=r)
- {
- int mid=(l+r)>>1;
- if (!check(mid)) mn=mid,r=mid-1;
- else l=mid+1;
- }
- if (mn>mx) mn=mx=-1;
- printf("%d %d\n",mn,mx);
- }
- CF1261E
首先把 \(a_i\)从小到大排序.
不知道怎么的观察样例可以受到启发: 留一条对角线不填.
假设 \(a_i< n\)且只用 \(n\)个集合, 那么有这样一种构造方法: 每一列从留空的一个点上面开始往上填, 不够就继续从最底下开始. 可以证明这样一定是合法的.
如果有 \(a_i=n\)呢? 我们把它这一列的最后一个也填上, 那么最后一行显然只有一个后缀是填了 1 的.
此时会发现最后一行可能会和上面的一行 (且仅有那一行) 起冲突, 咋办呢?
把 \((n+1,n)\)的 1 填到 \((n,n)\)去, 你发现这样就合法了.
为啥? 画画图反证一下就可以了吧.
- (这怎么想到的啊??)
- int n;
- pii aa[sz];int a[sz],p[sz];
- int pre(int x){if (x==1) return n;return x-1;}
- int ans[sz][sz],cnt[sz];
- int main()
- {
- file();
- read(n);
- rep(i,1,n) read(aa[i].fir),aa[i].sec=i;
- sort(aa+1,aa+n+1);rep(i,1,n) a[i]=aa[i].fir,p[aa[i].sec]=i;
- rep(i,1,n)
- {
- int x=min(a[i],n-1);
- if (a[i]==n) ans[n+1][i]=1,++cnt[n+1];
- for (int j=pre(i),k=1;k<=x;k++,j=pre(j)) ans[j][i]=1,++cnt[j];
- }
- int cc=cnt[n+1];
- int flg=0;rep(i,1,n-cc) flg|=ans[n-cc][i];
- if (cc&&cc!=n&&!flg) swap(ans[n][n],ans[n+1][n]),--cnt[n+1],++cnt[n];
- printf("%d\n",n+bool(cnt[n+1]));
- rep(i,1,n+bool(cnt[n+1])) { rep(j,1,n) putchar(ans[i][p[j]]+'0'); puts(""); }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3309283.html