Round（12）
题意:n*m矩阵,a[i][j]=1代表禁止的格子.现在有一个h*w的矩形,其左上角为(sx,sy).
操作:每次可以将该矩形整个向4个方向移动,注意移动后 矩形不能包含禁止的格子 不能超出界外.
n,m&=1e3,问矩形移动到左上为(tx,ty)时的最小操作次数?
跑bfs,用二维前缀和判断矩阵是否包含1即可.
#include &bits/stdc++.h&
const int N=2e3+20,inf=0x3f3f3f3f;
int n,m,a[N][N],f[N][N];
int h,w,sx,sy,tx,
struct node{
node(int a,int b,int c)
x=a,y=b,dis=c;
queue&node&
int vis[N][N];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
bool check(int x,int y)
if(x&=0||x&n||y&=0||y&m)
if(x+h-1&n||y+w-1&m)
if(vis[x][y])
int x2=x+h-1,y2=y+w-1;
int num=f[x2][y2]-f[x2][y-1]-f[x-1][y2]+f[x-1][y-1];
void bfs()
q.push(node(sx,sy,0));
vis[sx][sy]=1;
while(!q.empty())
node t=q.front();
int x=t.x,y=t.y,d=t.
if(x==tx&&y==ty)
printf(&%d\n&,d);
for(int i=0;i&4;i++)
int a=x+dx[i],b=y+dy[i];
if(check(a,b))
q.push(node(a,b,d+1)),vis[a][b]=1;
puts(&-1&);
int main()
scanf(&%d%d&,&n,&m);
for(int i=1;i&=n;i++)
for(int j=1;j&=m;j++)
scanf(&%d&,&a[i][j]),f[i][j]=a[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];
cin&&h&&w&&sx&&sy&&tx&&
}Prbolem D
题意:给出[1..n]排列a,找到最长的子序列满足:子序列开头和结尾大于该子序列的其余元素.n&=1e5.
枚举左右端点 然后中间小于端点的加入序列O(n^3)....
核心:我们可以固定中间元素的最大值.
枚举当中间元素最大为x时(端点&x),找到最左和最右边大于x的位置.
x从小到大枚举,则L只会越来越大,R只会越来越小&
然后求[L,R]有多少个&=x元素 用BIT标记元素位置 前缀和减一减即可.
#include &bits/stdc++.h&
const int N=2e5+20;
int n,a[N],pos[N];
int lowbit(int x)
return x&-x;
void update(int x,int val)
for(int i=x;i&N;i+=lowbit(i))
int query(int x)
int res=0;
for(int i=x;i&0;i-=lowbit(i))
res+=c[i];
int main()
for(int i=1;i&=n;i++)
scanf(&%d&,&a[i]),pos[a[i]]=i;
int L=1,R=n;
int ans=1;
for(int i=1;i&=n;i++)//mid ele can not exceed i.
int x=pos[i];
update(x,1);
while(L&=n&&a[L]&=i)
while(R&0&&a[R]&=i)
int res=query(R)-query(L-1)+2;
// printf(&%d %d %d %d\n&,i,L,R,res);
ans=max(ans,res);
cout&&ans&&
}Problem E
题意:n*m 01矩阵,初始只有包含0的联通分量只有一个,并且该联通分量和某个边界相连(头尾行/列).
操作:把一个0变成1之后,不和边界相连的联通分量都变为1.
n,m&=1e3,只操作一次的情况下,格子颜色为1的个数最多为多少?
两个白色相邻则连接一条边,然后设置一个特殊点,所有和在边界上的白点都和特殊点链接一条边.
现在在某个白点变黑 也就是在图上删除一个点.只有该点为割点时,才会有联通分量和特殊点分离,产生黑色点的个数才会大于1.
从特殊点开始dfs 找到产生分离个数最多的割点即可.
#include &bits/stdc++.h&
const int N=2e3+20,M=1e6+5,inf=0x3f3f3f3f;
int row,col,a[N][N],id[N][N];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
vector&int& e[M];
void add_edge(int u,int v)
e[u].push_back(v);
e[v].push_back(u);
int low[M],dep[M],sz[M],
bool vis[M];
void dfs(int u,int fa)
low[u]=dep[u];
int now=1;
for(int i=0;i&e[u].size();i++)
int v=e[u][i];
if(vis[v])
low[u]=min(low[u],dep[v]);//回边.
dep[v]=dep[u]+1;
sz[u]+=sz[v];
if(low[v]&=dep[u])//
cut=true,now+=sz[v];
low[u]=min(low[u],low[v]);
if(cut&&u!=0)
res=max(res,now);
int main()
cin&&row&&
int add=0,n=0;
for(int i=0;i&i++)
for(int j=0;j&j++)
scanf(&%d&,&a[i][j]);
if(a[i][j])
id[i][j]=++n;
for(int i=0;i&i++)
for(int j=0;j&j++)
if(a[i][j]==0)
if(i==0||j==0||i==row-1||j==col-1)
add_edge(id[i][j],0);
for(int k=0;k&4;k++)
int x=i+dx[k],y=j+dy[k];
if(x&=0&&x&row&&y&=0&&y&col&&a[x][y]==0)
add_edge(id[x][y],id[i][j]);
printf(&%d\n&,res+add);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：2700次
积分：1110
积分：1110
排名：千里之外
原创：111篇
(48)(42)(21)
(window.slotbydup = window.slotbydup || []).push({
id: '4740887',
container: s,
size: '250,250',
display: 'inlay-fix'君，已阅读到文档的结尾了呢~~
广告剩余8秒
文档加载中
构词法前后缀分类总结
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
构词法前后缀分类总结
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口