前言
挂分最多的一场。
考虑到之前都无分可挂，这场算是最近很简单的了。
T1 不排序（按理说我的做法不需要排，但挂了），100->40。
T2 二分某个边界时单调性判错，100->30。
T3 原，但没做过。
T4 某人用模拟退火骗到 60 pts orz。
T1 棍子
签到题。
考虑二分答案。显然每次要切的长度应等于二分的这个答案。
代码就不贴了。
T2 数组
签到题 \(\times 2\)。
显然 \(ans=\sum\limits_{i=la}^{ra} \min(rc/i,rb)-\max(\lceil lc/i \rceil,lb)+1\)。
分别整除分块统计即可。
对于向上取整的整除分块，从后往前，每次求左边界。
注意区间可能为负，讨论下单调性，二分下边界即可。
#include<bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
using namespace std;
int la,ra,lb,rb,lc,rc,s1,s2;
inline int d(int a,int b) {return ceil(1.0*a/b);}
main()
{
cin>>la>>ra>>lb>>rb>>lc>>rc;
int t=-1,l=la,r=ra;
while(l<=r)
{
if(rc/mid>=d(lc,mid)&&rc/mid>=lb) t=mid,l=mid+1;
else r=mid-1;
}
ra=min(ra,t);
t=-1,l=la,r=ra;
while(l<=r)
{
if(rb>=d(lc,mid)) t=mid,r=mid-1;
else l=mid+1;
}
if(~t) la=max(la,t);
for(int l=la,r;l<=ra&&rc/l!=0;l=r+1) r=min(rc/(rc/l),ra),s1+=(r-l+1)*min(rc/l,rb);
for(int r=ra,l;r>=la&&d(lc,r)!=0;r=l-1) l=max(d(lc,(d(lc,r))),la),s2+=(r-l+1)*max(d(lc,r),lb);
cout<<s1-s2+ra-la+1<<'\n';
}
T3 十一
不仅是之前模拟赛原题（我没打），还是 CF856C。
其实挺难想的，但不抽象，感觉比 T4 难想。
\(11\) 倍数的特点。
注意到 \(10 \equiv -1 \pmod {11}\)。
考虑一个数 \(\overline{a_1a_2a_3a_4}\) 对 \(11\) 取模。
可以发现 \(-1\) 幂的正负性只与幂次的奇偶性有关，即当前数位的奇偶性相关。
\(10^4a_1+10^3a_2+10^2a_3+10a_4 \equiv a_1-a_2+a_3-a_4 \pmod {11}\)。
定义一个数 \(\overline{a_1a_2...a_n}\) 的值为 \(\sum\limits_{i=1}^{n} (-1)^{i-1}a_{i}\)。
那么每个数的值的贡献可能是正，也可能是负。
为方便，下面奇数指数位为奇数的数，偶数定义类似。
注意到在任何位置插入偶数不会影响之前的贡献。
于是考虑奇偶分别讨论。
对于奇数：
值从前往后显然是 \(...-+-+-+\)，且是固定的。这很显然可以 dp。
设 \(f(i,j,k)\) 表示填到第 \(i\) 个奇数，填了 \(j\) 个正位，对 \(11\) 取模后值为 \(k\) 的方案。
讨论一下第 \(i\) 个数填正位还是负位，记正位共有 \(odd\) 个，负位共有 \(even\) 个，不难得出状态转移方程：
\(f(i,j,k)=f(i-1,j-1,k-a_i)\cdot(odd-j+1)+f(i-1,j,k+a_i)\cdot(even-i+1-j)\)。
对于偶数：
考虑在奇数固定位置上插入偶数。
注意每插入一个数，就会多出一个可以插的位置。
设 \(g(i,j,k)\) 表示填到第 \(i\) 个偶数，\(j,k\) 意义同上。转移与上类似，注意下枚举范围即可。
最后累计下答案即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=52,mod=1e9+7;
int n,lp,lq,p[N],q[N],f[N][N][11],g[N][N][11];
inline int mt(int x) {return (x%11+11)%11;}
main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
string s;cin>>s;
int a=0,t=1;
for(int i:s) a+=t*(i-'0'),t=-t;
if(s.size()&1) p[++lp]=a;
else q[++lq]=a;
}
f[0][0][0]=1;
int odd=ceil(lp/2.0);
for(int i=1;i<=lp;i++)
for(int j=0;j<=odd;j++)
for(int k=0;k<11;k++)
f[i][j][k]=((j?f[i-1][j-1][mt(k-p[i])]*(odd-j+1):0)+f[i-1][j][mt(k+p[i])]*max(0ll,(lp-odd-i+1+j)))%mod;
g[0][0][0]=1;
for(int i=1;i<=lq;i++)
for(int j=0;j<=i;j++)
for(int k=0;k<11;k++)
g[i][j][k]=((j?g[i-1][j-1][mt(k-q[i])]*(odd+j-1):0)+g[i-1][j][mt(k+q[i])]*(lp-odd+i-j))%mod;
int ans=0;
for(int j=0;j<=lq;j++)
for(int k=0;k<11;k++)
ans=(ans+f[lp][odd][k]*g[lq][j][mt(-k)]%mod)%mod;
cout<<ans;
}
T4 棋盘
经典的，于我而言初见的，将曼哈顿距离转化为切比雪夫距离。
切比雪夫距离：对于两个点 \((x_1,y_1),(x_2,y_2)\)，切比雪夫距离为 \(max(|x1-x2|,|y1-y2|)\)。
转化方法：用两种距离距原点分别为 \(1\) 的点作图，观察，旋转即可。
可以发现让 \((x,y)\) 映射为 \((x+y,x-y)\) 即可。
假设映射完后图长这样：
...#....
........
.......#
........
.#.#....
....#...
........
...#....
每次删点，距其最远的点一定在四个边界上。
直觉+脑糊，会发现每次删边界上的点一定是不劣的。这里就不证明了，其实很显然。
且每次会选边界跨度更大的那两个点其中之一删去。
可以考虑记搜，状态为点集。复杂度玄学，跑得很快就是了。
#include<bits/stdc++.h>
using namespace std;
int n;
char c[9][9];
struct node{
int x,y;
bool operator<(const node &a)const{
return x==a.x?y<a.y:x<a.x;
}
};
vector<node> p;
map<vector<node>,int> f;
int dfs(vector<node> s)
{
if(s.size()<=1) return f[s]=0;
if(f.count(s)) return f[s];
int x1=0,x2=0,y1=0,y2=0;
for(int i=0;i<s.size();i++)
{
auto [x,y]=s[i];
if(x<s[x1].x) x1=i;
if(x>s[x2].x) x2=i;
if(y<s[y1].y) y1=i;
if(y>s[y2].y) y2=i;
}
if(s[x2].x-s[x1].x<s[y2].y-s[y1].y) swap(x1,y1),swap(x2,y2);
int v1=0,v2=0;
vector<node> s1,s2;
for(int i=0;i<s.size();i++)
{
if(i!=x1) v1=max(v1,max(abs(s[x1].x-s[i].x),abs(s[x1].y-s[i].y))),s1.push_back(s[i]);
if(i!=x2) v2=max(v2,max(abs(s[x2].x-s[i].x),abs(s[x2].y-s[i].y))),s2.push_back(s[i]);
}
int f1=dfs(s1)+v1,f2=dfs(s2)+v2;
return f[s]=min(f1,f2);
}
int main()
{
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
{
cin>>c[i][j];
if(c[i][j]=='#') p.push_back({i+j,i-j});
}
cout<<dfs(p);
}