A 选彩笔（rgb）
一眼转三维坐标系搞。
但是最开始想歪了，以为要转曼哈顿距离，但是发现三维切比雪夫距离不支持转曼哈顿距离。
补充一个知识点
\(x\) 维的曼哈顿距离支持转到 \(2^{x-1}\) 维的切比雪夫距离
所以一维和二维可以直接转化，但是三维及以上就不行了。三维曼哈顿距离等同于某种坐标系下的四维切比雪夫距离。
然后想到题目就是在求最最的一个立方体满足立方体中点的个数为 \(k\) 个。
然后就想到了三维前缀和，值域 \([0，255]\) 可做。
但是总体复杂度是 \(O(n^2)\) 的，没多少分。
其实在三维前缀和的基础上改成二分答案，每次 check 搜索值域内全部边长为 \(mid\) 的立方体，用三维前缀和查个数是否大于等于 \(k\) 即可。
点击查看代码
//自己的没调出来崩溃了，这个是别人的。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5,INF=1E9;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
inline void write(ll x)
{
if(x<0)x=-x,putchar('-');
if(x>9)write(x/10);
putchar((x%10)|48);
}
inline void write(ll x,char p){
write(x);putchar(p);
}
int n,K;
struct ac
{
int r,g,b;
}a[N];
int c[260][260][260];
inline int get(int a,int b,int C,int x,int y,int z){
return c[x][y][z]-c[a-1][y][z]-c[x][b-1][z]-c[x][y][C-1]+c[a-1][b-1][z]+c[a-1][y][C-1]+c[x][b-1][C-1]-c[a-1][b-1][C-1];
}
inline bool check(int mid){
for(int i=1;i+mid<=256;i++){
for(int j=1;j+mid<=256;j++){
for(int k=1;k+mid<=256;k++){
if(get(i,j,k,i+mid,j+mid,k+mid)>=K){return 1;}
}
}
}
return 0;
}
inline void fen(int l,int r){
int ans=0;
while(l<=r){
int mid=l+r>>1;
if(check(mid)){
ans=mid;r=mid-1;
}else l=mid+1;
}
write(ans);
}
int main()
{
freopen("rgb.in","r",stdin),freopen("rgb.out","w",stdout);
n=read();K=read();
for(int i=1;i<=n;i++){
a[i]={read()+1,read()+1,read()+1};
// v[a[i].r][a[i].g][a[i].b].pb(i);
c[a[i].r][a[i].g][a[i].b]++;
}
for(int i=1;i<=256;i++){
for(int j=1;j<=256;j++){
for(int k=1;k<=256;k++){
c[i][j][k]+=c[i-1][j][k];
}
}
}
for(int i=1;i<=256;i++){
for(int j=1;j<=256;j++){
for(int k=1;k<=256;k++){
c[i][j][k]+=c[i][j-1][k];
}
}
}
for(int i=1;i<=256;i++){
for(int j=1;j<=256;j++){
for(int k=1;k<=256;k++){
c[i][j][k]+=c[i][j][k-1];
}
}
}
fen(0,255);
return 0;
}
B 兵蚁排序（sort）
非常好 \(gxyz OJ\) 我随便写的 \(dfs\) 都有 \(65\)。
这个题正解已经想出来了，但是没敢打。
考虑每一对失配的点，如果合法，一定是到最终位置为逆序，那么每次 swap 保证其它点相对位置不变，对于一个点最多移动 \(O(n)\)，类似于冒泡排序。
意思就是忽略题目给的排序条件，每次只进行 swap 来保证正确性，然后每个点 \(O(n)\)，总复杂度 \(O(n^2)\)。
其实我是考虑到移动次数会大于 \(n^2\)，但是不会，最大才会 \(\frac{n^2}{2}\) 次左右（就是倒序转顺序的类型）