• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 杭电多校(1)

3小时前 1次浏览

1008Problem – 6957 (hdu.edu.cn)

``````int n,m;
int a[N][N],b[N][N];
int l[N],r[N],h[N];

void work() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
scanf("%d",&a[i][j]);
if(i==1)b[i][j] = 1;
else b[i][j]=(a[i][j]>=a[i-1][j])?1:0;
}
}
int ans = 0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(i == 1)h[j]=1;
else h[j]= b[i][j]==1?h[j]+1:1;
l[j] = r[j] = j;
}
for(int j=1; j<=m; j++) {
while(l[j]>1&&h[j]<=h[l[j]-1])l[j] = l[l[j]-1];
}
for(int j=m; j>=1; j--) {
while(r[j]<m&&h[j]<=h[r[j]+1])r[j] = r[r[j]+1];
}
for(int j=1; j<=m; j++) {
ans = max(ans,(r[j]-l[j]+1)*h[j]);
}
}
printf("%dn",ans);
}
``````

1009 Problem – 6958 (hdu.edu.cn)

``````const int N = 1e5 + 50,M = 5e5 + 50;

struct node {
int u,v,w;
} p[M];

int n,m,k;
int fa[N];

void init() {for(int i=1; i<=n; i++)fa[i] = i;}

bool cmp(node a,node b) {return a.w < b.w;}

int find_set(int x) {
if(fa[x] != x)fa[x]=find_set(fa[x]);
return fa[x];
}

void work() {
scanf("%d%d%d",&n,&m,&k);
init();
for(int i=1; i<=m; i++) {
scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w);
}
sort(p+1,p+1+m,cmp);

int ans = 0;
for(int i=1; i<=m; i++) {
if(p[i].w != p[i-1].w) {
if(n == k) {
printf("%dn",ans);
return ;
}
}
int x=find_set(p[i].u),y=find_set(p[i].v);
if(x == y)continue;
n--;
fa[x] = y;
ans = p[i].w;
}
if(n == k)printf("%dn",ans);
else printf("-1n");
}
``````

1006.01字典树 Problem – 6955 (hdu.edu.cn)

``````const int N = 3e6 + 50,M = 5e5 + 50;

int n,k;
int a[N];
int tr[N][2],idx;
int ed[N];
int maxn,res;

int v = 0,f = 1;
char c = getchar();
while(c < 48 || 57 < c) {
if(c == '-') f = -1;
c = getchar();
}
while(48 <= c && c <= 57) v = (v<<3) + v + v + c - 48,c = getchar();
return v * f;
}

struct trie {
void insert(int x,int pos) {
int now=0;
for(int i=29; i>=0; i--) {
int c=(x>>i)&1;
if(!tr[now][c]) {
tr[now][c]=++idx;
ed[idx]=-1;
tr[idx][0]=tr[idx][1]=0;
}
now = tr[now][c];
ed[now]=max(ed[now],pos);
}
}
int find(int x) {
int now = 0;
for(int i=29; i>=0; i--) {
int c=(x>>i)&1;
int op=(k>>i)&1;
//k的j位是0,那如果存在1,这个前缀就大于k,更新
if(!(op&1)) {
if(tr[now][c^1])
res = max(res,ed[tr[now][c^1]]);
now=tr[now][c];
} else {//k的第j位是1
now = tr[now][c^1];
}
if(now==0)return -1;
}
return ed[now];
}
} tree;

void init() {
for(int i=0; i<=idx; i++) {
tr[i][0]=tr[i][1] = 0;
ed[i] = 0;
}
idx=0;
}

void work() {

for(int i=1; i<=n; i++) {
if(i!=1)a[i]^=a[i-1];
}
init();
int ansl=-1,ansr=n+1;
for(int i=1; i<=n; i++) {
res = -1;
int p = tree.find(a[i]);

if(p != -1)res=max(res,p);

if(res > 0 && i - res < ansr - ansl) {
ansl = res;
ansr = i;
}
tree.insert(a[i],i);
}
if(ansl > 0) {
printf("%d %dn",ansl+1,ansr);
} else printf("-1n");

}
``````