牛子老师问我为什么
\[\lim_{x\to\infty}\sqrt{\frac{x^3}{x-1}}-x=\frac 12 \]wolfram alpha 告诉我直接 Laurent 级数展开发现没有正项。于是你如果加个 \(a\) 直接泰勒展开事实上会发现是个无穷项。
这个东西和拉马努金的那个“所有自然数加和是 \(-\dfrac 1{12}\)” 的结论好像是类似的。但我不会复分析，告辞。不过这个东西陶哲轩在博客里写过一个纯实变的方法，然而更看不懂。告辞。
怎么又在 jdw 的博客一言里看到原神。
挑战 NPC Ⅱ 交一发 68 分以为复刻牛子老师了，本地调大样例发现 vector RE 了。
今天题是 Ignotus 老师的互测。
斗篷
原题：[ICPC2018 WF] Triangles。
不太懂为啥是黑。不太懂为啥没题解。
考虑在底边位置算正的三角形的个数，然后倒过来再算一遍。
给每个点设个权值 \((val_1,val_2)\) 表示作为三角形的左下角和右下角向上分别最长能延伸多长距离，那么转移可以看和上一行对应点有没有边，从上一行简单转移过来。
考虑在三角形的右下角进行统计，对于点 \(i\)，能匹配的左下角 \(j\) 满足 \(i,j\) 距离不超过 \(i\) 的 \(val_2\) 和 \(j\) 的 \(val_1\)。那么相当于每次把所有 \(i\) 左边的点的 \(val_1\) 减掉 \(1\)，查询 \([i-val_2,i-1]\) 中有多少个点满足 \(val_1\ge 0\)。那么把每个点看做二维平面上的点 \((i,i+val_1)\)，实际上就是数满足 \(x\in[i-val_2,i-1],y\ge i\) 的点的个数，树状数组扫描线即可。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int inf=65536;
int n,m,lim,val1[6010][12010],val2[6010][12010];
long long ans;
char s[6010][12010];
void reverse(){
for(int i=1;i<=(n>>1);i++)swap(s[i],s[n-i+1]);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
if(s[i][j]=='/')s[i][j]='\\';
else if(s[i][j]=='\\')s[i][j]='/';
}
}
struct BIT{
int n,c[12010];
#define lowbit(x) (x&-x)
void update(int x,int val){
while(x)c[x]+=val,x-=lowbit(x);
}
int query(int x){
int sum=0;
while(x<=n)sum+=c[x],x+=lowbit(x);
return sum;
}
void clear(){
for(int i=1;i<=n;i++)c[i]=0;
}
}c;
vector<int>p[3010];
vector<pair<int,int> >q[3010];
void solve(int id){
for(int i=1;i<=n;i+=2){
c.clear();
int pre=1;
for(int j=(i+id)%4,x=1;j<=m;j+=4,x++){
if(s[i-1][j+1]=='/')val1[i][j]=val1[i-2][j+2]+1;
else val1[i][j]=0;
if(s[i-1][j-1]=='\\')val2[i][j]=val2[i-2][j-2]+1;
else val2[i][j]=0;
if(s[i][j-1]!='-')pre=x;
p[x].clear();q[x].clear();
p[x].push_back(x+val1[i][j]);
if(max(pre,x-val2[i][j])-1>0)q[max(pre,x-val2[i][j])-1].push_back(make_pair(x,-1));
if(x-1>0)q[x-1].push_back(make_pair(x,1));
}
for(int j=(i+id)%4,x=1;j<=m;j+=4,x++){
for(int i:p[x])c.update(i,1);
for(pair<int,int> i:q[x])ans+=i.second*c.query(i.first);
}
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;c.n=n+m;
n=(n<<1)-1,m=(m<<1)-1;
string tmp;getline(cin,tmp);
for(int i=1;i<=n;i++){
getline(cin,tmp);
for(int j=1;j<=m;j++)s[i][j]=tmp[j-1];
}
solve(0);
reverse();
solve(s[1][1]=='x'?0:2);
cout<<ans<<'\n';
return 0;
}
故事
原题：CF1753E。
怎么一场两黑一 IOI。赛时数据水得到 98 分。
显然加放开头乘放结尾。一个合理的骗分逻辑是要么全选 \(+\) 要么全选 \(\times\)，简单算权值贪心即可。虽然这样会有几个大样例过不去但是可以得到 94 分。然后加上特殊性质实际上可以切掉，我写的丑点挂了 2 分。
那么为了通过原题补一下正解。先把 \(\times 1\) 去掉。
一个显然的性质是乘法很少，因为初始答案不超过 \(A=2\times 10^9\)，因此最多只有 \(\log A=31\) 个乘法。但是爆搜是显然不能过的。
之后的想法赛时没出：仍然考虑爆搜，但是加个剪枝。有个性质是对于乘数相同的乘法，挪前边的比挪后边的优。这样听说状态数不超过 \(5000\)。然而每次算仍然是 \(O(n\log n)\)，不是很能过。
考虑另一个性质：把加法按照乘法分段，那么每段肯定选 \(a_i\) 大的。于是把所有段的加数排序，二分贡献 \(mid\) 并在每段二分得到贡献不小于 \(mid\) 的加数个数即可。这样一次计算变成了 \(O(\log n\log A)\)，可以通过。
摆烂不想写。
迷宫
原题：IOI2017 D1T1 Nowruz。提答不改了。摆烂。
感觉提答这种东西不是随机化就是小游戏。
标签：log,val,原题,int,29,国赛,冲刺,include,乘法 From： https://www.cnblogs.com/gtm1514/p/17523842.html