php开源企业网站系统,今天特大军事新闻,雅安交通建设集团网站,建设网站建设什么挣钱link.
突然很想写这篇题解。虽然题目不算难。
考场只有30分是为什么呢#xff1f;看来是我没有完全理解这道题目吧#xff01;
首先很明显的转换是#xff0c;把 T 型覆盖看成十字形#xff0c;再考虑最后减去某一块的贡献。
然后然后直接往原图上面放十字形!对于每一个…link.
突然很想写这篇题解。虽然题目不算难。
考场只有30分是为什么呢看来是我没有完全理解这道题目吧
首先很明显的转换是把 T 型覆盖看成十字形再考虑最后减去某一块的贡献。
然后然后直接往原图上面放十字形!对于每一个十字的中心来说实际上它只需要三个相邻的方块就可以了。而我们发现两个十字重合的部分不会超过两个方块也就是说把这两个方块任意分配给两个人就能保证这两个每个人都只会舍弃一个方块。
因为每次两个十字的重合最多只能让每个点丢弃一个方块并且每次重合至少有一个十字会丢弃掉一个方块所以惊天的结论是我们可以直接计算整个十字连通块的中心点和非中心点的个数。如果非中心点的个数大于等于中心点的个数的三倍那么当前连通块一定合法否则不能保证每个十字的中心点都能分配到刚好三个非中心点即无解。
但是可能有非中心点的个数大于中心点的个数的三倍。这种情况说明所有的十字都只重合了一个点那么必须要丢掉一个非中心点。因为要权值最大所以丢掉最小权值的就好了。
其实这个的实现方式有很多但是我使用了并查集。为什么呢因为其他题解就是用的并查集啊
然后并查集需要注意的点就是不能选择中心点啊。中心点的权值设为最大值好不好。
#includebits/stdc.h
using namespace std;int n,m,k;
int a[1000005];
int ID(int x,int y){return (x-1)*my;
}
int pre[1000005],dp[1000005];
int sz[1000005][2];
long long sum[1000005];bool vis[1000005];struct zz{int x,y;
}t[1000005];int Find(int x){if(pre[x]!x) pre[x]Find(pre[x]);return pre[x];
}
void Join(int x,int y){int fxFind(x),fyFind(y);if(fxfy) return ;pre[fy]fx,sum[fx]sum[fy],dp[fx]min(dp[fx],dp[fy]),sz[fx][0]sz[fy][0],sz[fx][1]sz[fy][1];
}int fx[5]{0,1,-1,0,0};
int fy[5]{0,0,0,1,-1};int main(){
// freopen(t-covering.in,r,stdin);
// freopen(t-covering.out,w,stdout);cinnm;for(int i1;in;i) for(int j1;jm;j) scanf(%d,a[ID(i,j)]);cink;for(int i1,x,y;ik;i) scanf(%d%d,x,y),t[i](zz){x1,y1};for(int i1;ik;i) vis[ID(t[i].x,t[i].y)]1;for(int i1;in*m;i){pre[i]i,sum[i]a[i],dp[i]a[i],sz[i][vis[i]]1;if(vis[i]) dp[i]0x3f3f3f3f; }for(int i1;ik;i) for(int j1;j4;j){int xt[i].x,yt[i].y;int dxxfx[j],dyyfy[j];if(dx0||dxn||dy0||dym) continue;Join(ID(x,y),ID(dx,dy)); }long long ans0;memset(vis,0,sizeof vis);for(int i1;in;i) for(int j1;jm;j){int x(ID(i,j));int fxFind(x);if(vis[fx]) continue; vis[fx]1;if(sz[fx][0]sz[fx][1]*3) return printf(No\n),0;else if(sz[fx][0]sz[fx][1]*3) anssum[fx];else anssum[fx]-dp[fx];}coutansendl;return 0;
}
