(D.)
- 题目链接D - Grid Repainting 3
- 感觉非常巧妙的一道题
- 首先依然考虑将红点看作从行到列连的一条边,注意这是一张二分图,且会分成若干个连通块
- 我们考虑原问题可以等价于什么,我们每选一行或者一列染色,相当于把边全部破坏掉,那么就等价于删掉这个点,注意到删的顺序不同,结果也是不同的(突破点)
- 于是我们把原问题等价于每次删一个非孤立点,最小化最后两边点的成绩
- 考虑每个连通块的生成树,我们可以从下往上删,只保留根,那么就只有两种情况,根在左边或者右边
- 考虑原来左边孤立点为(X),右边为(Y),根据二次函数那套理论,我们只要把根全部保留在(X,Y)中较小的那个即可(即让小的尽可能小,大的尽可能大,则乘积最小)
#include<bits/stdc++.h>
using namespace std;
int read(){
char c = getchar();
int x = 0;
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - 48,c = getchar();
return x;
}
const int _ = 5e3 + 7;
char s[_][_];
vector<int>E[_];
#define pb push_back
typedef pair<int,int> pii;
#define mp make_pair
#define fi first
#define se second
vector<pii>ans;bool vis[_];
void dfs(int u){
vis[u] = 1;
for(auto v :E[u]){
if(!vis[v]){
dfs(v);
ans.pb(mp(v,u));
}
}
}
int main(){
int n = read(),m = read();
int X = 0,Y = 0;
for(int i = 1; i <= n; ++i) scanf("%s",s[i]+1) ;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j){
if(s[i][j] == 'R'){
E[i].pb(j + n);
E[j+n].pb(i);vis[i] = vis[j + n] = 1;
}
}
for(int i = 1; i <= n; ++i) X += (!vis[i]);
for(int i = 1; i <= m; ++i) Y += (!vis[i+n]);
memset(vis,0,sizeof(vis));
if(X > Y){
for(int i = 1; i <= n; ++i){
if(!vis[i]) dfs(i);
}
}
else{
for(int i = 1; i <= m; ++i){
if(!vis[i+n]) dfs(i + n);
}
}
cout<<ans.size()<<endl;
for(auto now : ans){
if(now.fi <= n) {
printf("X %d %d
",now.fi,now.se - n);
}
else{
printf("Y %d %d
",now.se,now.fi - n);
}
}
return 0;
}
(E.)
- 憨憨题
- 题意简述:给定一个长为(n)的序列(A),你可以选择一个区间([l,r]),将其中的元素反转,求最小化(sum_{i = 1}^{n-1}|A_i - A_{i+1}|)
- (n leq 1e5,A_i leq 1e9)
- 我们注意到每次反转后之后改变端点处的值,讨论一下可以发现当且仅当包含的时候,反转才会变得更优,于是转成二维偏序问题,排序后树状数组即可