广州做手机网站咨询,商城分销系统,青岛外贸推广,赚钱的网站平台解析
本题做的过程大概是#xff1a;到了正解门口决定回头#xff0c;绕了地球一圈最后从另一边走到正解了…
我的分析#xff1a; 首先 easy version 很简单#xff0c;如果从一列最大值可以走到另一列最大值#xff0c;那么后者就没用了。缩完点所有的零度点就是答案。…解析
本题做的过程大概是到了正解门口决定回头绕了地球一圈最后从另一边走到正解了…
我的分析 首先 easy version 很简单如果从一列最大值可以走到另一列最大值那么后者就没用了。缩完点所有的零度点就是答案。
hard version 的问题就是选的点是最大值但要求走到的点不一定是最大值。 要求走到的点如果互相可达那么可以被到达的也没用了所以有用的点满足互不可达。 如果到一个要求点的时候够不到要求高度了后面的要求点必然更达不到所以选择每一列后可以满足的点必然是连续的区间。 而且不难发现我选的列右移的时候其满足的点的区间两端点必然都单调不降。
现在的问题就是如何求出这些区间剩下的就是一个贪心问题了。 然后我的大脑就当机了觉得这玩意不可求于是就尝试贪心拓展区间再利用缩点判定合法很费劲的也搞出来了。 但这样求可达区间的问题其实就和炸弹那个题一样维护可达的 l,rl,rl,r 取取 max,min\max,\minmax,min 就行了。
代码
当然再敲一遍正解是不可能的
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N4e5100;
const int inf1e9;
const int mod998244353;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m;
bool flag0;
vectorintmp[N],pt[N];
int a[N],h[N],mx[N];
vectorinte[N];
int tot;
int dfn[N],low[N],zhan[N],col[N],tim,top;
void tarjan(int x){dfn[x]low[x]tim;zhan[top]x;for(int to:e[x]){if(!dfn[to]){tarjan(to);low[x]min(low[x],low[to]);}else if(!col[to]) low[x]min(low[x],dfn[to]);}if(low[x]dfn[x]){col[x]tot;while(zhan[top]!x) col[zhan[top--]]tot;top--;}return;
}int cnt;
signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifnread();mread();for(int i0;in1;i){mp[i].resize(m2);pt[i].resize(m2);}char c;for(int in;i1;i--){for(int j1;jm;j){scanf( %c,c);mp[i][j](c#);} }for(int j1;jm;j) a[j]read(),cnta[j];if(!cnt){printf(0);return 0;}for(int j1;jm;j){for(int i1;in;i){if(mp[i][j]) pt[i][j]tot;}}for(int j1;jm;j){int lst0;for(int i1;in;i){if(!mp[i][j]) continue;if(mp[i1][j]) e[pt[i][j]].push_back(pt[i1][j]);for(int ki;klst;k--){if(mp[k][j-1]) e[pt[i][j]].push_back(pt[k][j-1]);if(mp[k][j1]) e[pt[i][j]].push_back(pt[k][j1]);}if(lst) e[pt[i][j]].push_back(pt[lst][j]);lsti;}mx[j]lst;}int stot;for(int i1;is;i){if(!dfn[i]) tarjan(i);}for(int j1;jm;j){int lfta[j];for(int i0;in;i){lft-mp[i][j];if(lft0){h[j]i;break;}}for(int i0;in;i){if(col[pt[i][j]]col[pt[h[j]][j]]){h[j]i;break;}}}int ans(0),pl1;while(plm){int j,nedh[pl],pos0;for(jpl1;jm;j){ if(ned){pos0;for(int i1;in;i){if(mp[i][j]){if(ined||col[pt[i][j]]col[pt[ned][j-1]]){posi;break;}}} if(!pos) break;nedpos;}nedmax(ned,h[j]);}j--;while(j!mx[j]) j--;int ocol[pt[mx[j]][j]];while(jmcol[pt[h[j1]][j1]]o) j;plj1;ans;}printf(%d\n,ans);return 0;
}
/*
*/
