[省选联考 2020 A 卷] 魔法商店 (保序回归)
- 一、前言
- 二、题目
- 三、讲解
- （一）、科技：保序回归
- 1.问题提出
- 2.探寻解决方法
- (1).一般问题的算法 p=1
- (2).一般问题的算法 2<=p<+inf
- （二）、正题
- （一）、科技：保序回归
- 四、代码
- 五、后记
一、前言
小游把这道题分到了图论里面，但是我感觉怪怪的，所以我把它分到了算法里面。
毕竟算法啥都能装，而且其实这篇博客其实是抄论文+小游ppt。
有些地方不严谨，甚至跳过证明部分，作者水平有限，望谅解。
二、题目
洛谷
LOJ
三、讲解
（一）、科技：保序回归
1.问题提出
图片传上去不知道为啥就这样了，将就看吧。
注意 \(v_i\preceq v_j\) 是一种偏序关系，而并非 \(v_i\le v_j\) 这种简单的大小关系。
2.探寻解决方法
整体二分：用数据结构等方法判断答案与\(mid=\frac{l+r}{2}\) 的大小关系，从而分治求解。用函数 \(solve(l,r,pt)\) 实现，其中 \(pt\) 是待解决的编号集合。
(1).一般问题的算法 p=1
我们使用整体二分，怎么确定 \(f_i\) 与 \(mid=\frac{l+r}{2}\) 的大小关系呢？
定义原问题的 \(S=\{a,b\}(a
假设 \(\forall i, y_i\notin(a,b)\)，\(f_i^′\) 为原问题的一个最优解满足 \(f_i^′\notin(a,b)\)，那么我们通过将所有小于 \(a\) 的 \(f_i^′\) 变成 \(a\)，大于 \(b\) 的 \(f_i^′\) 变成 \(b\)，也可以得到原问题的 \(S\) 问题的一个最优解。
简单来说就是我们强行限制答案范围在 \([a,b]\) 那么如果我们知道无限制的答案，可以通过将小于 \(a\) 和大于 \(b\) 的部分平移过来以得到有限制问题的最优解。
因此，反过来，我们如果知道了有限制问题的最优解，就可以知道哪些值在 \((a,b)\)，哪些小于 \(a\)，哪些大于 \(b\)。
特别的，如果 \(y_i\) 都是整数，那么一定存在 \(f_i\) 都是整数的最优解。此时我们令 \(S=\{mid,mid+1\}\)，然后就可以整体二分了。
其实这里还有个问题是如何得到 \(S=\{mid,mid+1\}\) 问题的最优解，考虑此时 \(f_i\) 其实是两种取值二选一，所以我们可以考虑网络流。
而我们又要保证偏序关系 \(\forall v_i\preceq v_j(i,j\in[1,n])\) 均有 \(f_i\le f_j\)，说明 \(f_i\) 选 \(mid+1\) 的时候 \(f_j\) 也必须选 \(mid+1\)，此时的偏序关系我们可以用最大权闭合子图解决。
把每个点 \(i\) 的权值设置为 \(-(w(i,mid+1)-w(i,mid))\)，有个负号是因为我们原题求最小值但是用的是最大权闭合子图，可以发现与S(源点)在一个块里的就是选 \(mid+1\) 的，反之就是选 \(mid\)。
复杂度由于是分治后跑网络流，所以不大会算，大概是网络流复杂度乘上 \(log_2C\) 吧。
(2).一般问题的算法 2<=p<+inf
对于 \(p\ge 2\) 的情况，就算 \(y_i\) 是整数，也可能存在 \(f_i\) 不是整数的最优解，这个时候 \(1\) 不能作为最小单位。
因此考虑 \(S=\{mid,mid+\epsilon\}\)，直接做会有精度问题，但是显然权值同除 \(\epsilon\) 之后，问题的解不会改变。\(\frac{w(i,mid+\epsilon)-w(i,mid)}{\epsilon}\) 是啥？导！(这里为方便讲解就没有管上文因最大最小值而需要区分的正负号)
因此考虑将网络流建模中的边权设为 \(w_i|x-y_i|^p\) 在 \(mid+\) 处的导数。如果在加限制的问题上，不选点 \(i(f_i=mid)\)，那么说明原问题的 \(f_i\le mid\)，否则说明 \(f_i>mid\)。
如果求精确解就这么在实数上二分即可，如果求整数解其实可以套用 \(p=1\) 的解法。
值得注意的是在 \(mid+\) 处的导数取法，这种做法不会受绝对值符号导致函数不连续的影响。
比如 \(y=|x|\)，在 \(0\) 处取导数不是很怪吗？但是如果在 \(0+\) 处取那就是显然的 \(1\)。
（二）、正题
好了，我们回到这道题，我们发现题目给的 \(A,B\) 都是极大线性无关向量组（线性基）。考虑让它们最大/小意味着什么？由于问题转换后差不多，所以这里只讨论 \(A\)，即转换后价值最小意味着什么？
考虑一个向量 \(x\in A\)，如果存在一个向量 \(y\notin A\)，且 \(y\) 能够加入 \(A-x\)，那么 \(A-x+y\) 会组成一个新的线性基，由于 \(A\) 是最小的，那么我们显然可以得出调整后的价格 \(f_x\le f_y\)，\(B\) 同理分析即可。
好了，偏序关系已经得出，接下来套用 \(p=2\) 的做法求解即可，注意这道题只需求整数解。
四、代码
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 1005;
const LL INF = 1ll << 60;
int n,m,val[MAXN],a[MAXN],b[MAXN];
ULL c[MAXN],ans;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
ULL ID[64],B[64];
bool vis[MAXN];
ULL ins(ULL x,ULL id){
for(int i = 63;i >= 0;-- i){
if(x >> i & 1){
if(ID[i]) x ^= B[i],id ^= ID[i];
else {B[i] = x;ID[i] = id;return id;}//In this case,id is useless.
}
}
return id;
}
vector G[MAXN];//u ---> v means f_u <= f_v
LL sq(LL x){return x*x;}
int head[MAXN],tot = 1;
struct edge{
int v; LL w; int nxt;
}e[MAXN*MAXN<<1];
void Add_Edge(int u,int v,LL w){
e[++tot] = edge{v,w,head[u]};
head[u] = tot;
}
void Add_Double_Edge(int u,int v,LL w){
Add_Edge(u,v,w);
Add_Edge(v,u,0);
}
int dis[MAXN],cur[MAXN],tmp[MAXN],f[MAXN];
bool bfs(int l,int S,int T){
for(int i = l;i <= T;++ i) dis[tmp[i]] = n<<1;
queue q; q.push(tmp[S]); dis[tmp[S]] = 0;
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = head[x],v; i ;i = e[i].nxt)
if(e[i].w && dis[x] + 1 < dis[v = e[i].v])
dis[v] = dis[x]+1,q.push(v);
}
return dis[tmp[T]] < (n<<1);
}
LL dfs(int x,LL flow,int T){
if(x == T) return flow;
LL ret = 0;
for(int &i = cur[x],v; i ;i = e[i].nxt)
if(dis[x] + 1 == dis[v = e[i].v] && e[i].w){
LL dz = dfs(v,Min(flow-ret,e[i].w),T);
e[i].w -= dz; e[i^1].w += dz;
if((ret += dz) == flow) break;
}
return ret;
}
LL dinic(int l,int S,int T){
LL ret = 0;
while(bfs(l,S,T)){
for(int i = l;i <= T;++ i) cur[tmp[i]] = head[tmp[i]];
ret += dfs(tmp[S],INF,tmp[T]);
}
for(int i = l;i <= T;++ i) head[tmp[i]] = 0; tot = 1;
return ret;
}
LL w[MAXN];
bool tag[MAXN];
int le[MAXN],ri[MAXN];
void solve(int ql,int qr,int l,int r){
if(ql > qr) return;
if(l == r){
for(int i = ql;i <= qr;++ i) f[tmp[i]] = l;
return;
}
int mid = (l+r) >> 1,S = tmp[qr+1],T = tmp[qr+2];
for(int i = ql;i <= qr;++ i) w[i] = -(sq(val[tmp[i]]-(mid+1))-sq(val[tmp[i]]-mid)),tag[tmp[i]] = 1;
for(int i = ql;i <= qr;++ i){
if(w[i] > 0) Add_Double_Edge(S,tmp[i],w[i]);
else Add_Double_Edge(tmp[i],T,-w[i]);
for(auto A : G[tmp[i]]) if(tag[A]) Add_Double_Edge(tmp[i],A,INF);
}
for(int i = ql;i <= qr;++ i) tag[tmp[i]] = 0;
dinic(ql,qr+1,qr+2);
int ltot = 0,rtot = 0;
for(int i = ql;i <= qr;++ i)
if(dis[tmp[i]] < (n<<1)) ri[++rtot] = tmp[i];
else le[++ltot] = tmp[i];
for(int i = ql;i <= qr;++ i)
if(i-ql+1 <= ltot) tmp[i] = le[i-ql+1];
else tmp[i] = ri[i-ql-ltot+1];
solve(ql,ql+ltot-1,l,mid); solve(ql+ltot,qr,mid+1,r);
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); m = Read();
for(int i = 0;i < n;++ i) scanf("%llu",&c[i]);
for(int i = 0;i < n;++ i) val[i] = Read();
for(int i = 0;i < m;++ i) vis[a[i] = Read()-1] = 1,ins(c[a[i]],1ull<> j & 1) G[a[j]].emplace_back(i);
}
else vis[i] = 0;
}
for(int i = 0;i < 64;++ i) ID[i] = B[i] = 0;
for(int i = 0;i < m;++ i) vis[b[i] = Read()-1] = 1,ins(c[b[i]],1ull<> j & 1) G[i].emplace_back(b[j]);
}
else vis[i] = 0;
}
for(int i = 0;i <= n+1;++ i) tmp[i] = i;
solve(0,n-1,0,1e6);
for(int i = 0;i < n;++ i) ans += sq(f[i]-val[i]);
Put(ans,'\n');
return 0;
}
五、后记
是不是已经有人发现前言和后记都是吐槽部分了/yiw
保序回归这东西很牛逼，不会确实就是不会，但是会了也多半不考，你说前年锴皇他们模拟赛做了保序回归然后省选就考了这个直接导致BZ杀穿并且有人被卡1/3，难道两年之后的今年还会考吗？
这还真说不准。
总之保序回归是个挺有意思的东西，当然最重要的是我学得懂。