这题表诉不清,有两种理解
一.:全序列要么满足第一个性质,要么满足第二个性质.
二:全序列中间既有满足第一个性质的又有满足第二个性质的;
std给出的是一,所以那就很明显,nlog(n)算出最长不降子序列和最长不升子序列,比较一下取最大的即可
但二貌似就不那么好想的,但其本质肯定也在一的基础上进行维护操作代码注释处加上就是第二种情况
code by jklover
//%std一定要%std!!!!!!
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int out=0,sgn=1;
char jp=getchar();
while(jp!='-' && (jp<'0' || jp>'9'))
jp=getchar();
if(jp=='-')
sgn=-1,jp=getchar();
while(jp>='0' && jp<='9')
out=out*10+jp-'0',jp=getchar();
return out*sgn;
}
const int MAXN=2e5+10;
int n,a[MAXN],val[MAXN],tot;
struct FenwickTree
{
int bit[MAXN];
#define lowbit(x) x&(-x)
void add(int x,int c)
{
for(;x<=tot;x+=lowbit(x))
bit[x]=max(bit[x],c);
}
int query(int x)
{
int s=0;
for(;x;x-=lowbit(x))
s=max(s,bit[x]);
return s;
}
}Inc,Dec;
int f[MAXN],g[MAXN];
int main()
{
freopen("decoration.in","r",stdin);
freopen("decoration.out","w",stdout);
n=read();
for(int i=1;i<=n;++i)
val[i]=a[i]=read();
sort(val+1,val+1+n);
tot=unique(val+1,val+1+n)-val-1;
int x1,y1,x2,y2;
for(int i=1;i<=n;++i)
{
x1=lower_bound(val+1,val+1+tot,a[i])-val;
y1=Inc.query(x1);
x2=tot+1-x1;
y2=Dec.query(x2);
int t1=f[x1],t2=g[x2];
Inc.add(x1,y1+1);
f[x1]=max(f[x1],y1+1);
Dec.add(x2,y2+1);
g[x2]=max(g[x2],y2+1);
/*Dec.add(x2,t1+1);
g[x2]=max(g[x2],t1+1);
Inc.add(x1,t2+1);
f[x1]=max(f[x1],t2+1);*/
}
int ans=max(Inc.query(tot),Dec.query(tot));
cout<<n-ans<<endl;
return 0;
}
按位或!!!!
考试时看成 异或 了,就导致怎么想都不会
首先题目是最短路,那么十有八九都不会是最短路了
再就是本题是位操作,那么二进制拆分就必不可少
再就是最短路确实说不通的,因为不满足无后效性,只要那一位是1,则所有只要那一位是1的边都不会再为路径产生贡献
但它又是让你求最短路,最短?像此类求最值的,不是dp(最短路算法本质是dp),那就应该是贪心了
还是拆分成二进制,考虑位数越高越为0就嘴好,所有从最高位向后拓展,正如向加粗字体一样,先假定当前这位为0,如果其他这位为0的边使之可以连通那就这位就不会为ans产生贡献,反之ans+=1<<k
并查集维护即可code by jklover
//%std
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int out=0,sgn=1;
char jp=getchar();
while(jp!='-' && (jp<'0' || jp>'9'))
jp=getchar();
if(jp=='-')
sgn=-1,jp=getchar();
while(jp>='0' && jp<='9')
out=out*10+jp-'0',jp=getchar();
return out*sgn;
}
const int MAXN=1e5+10;
struct Edge
{
int u,v,w;
}E[2][MAXN<<1];
int n,m,id=0,fa[MAXN];
int Find(int x)
{
return x==fa[x]?x:fa[x]=Find(fa[x]);
}
void init_fa()
{
for(int i=1;i<=n;++i)
fa[i]=i;
}
int main()
{
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=m;++i)
{
E[id][i].u=read();
E[id][i].v=read();
E[id][i].w=read();
}
int ans=0;
for(int k=29;k>=0;--k)
{
init_fa();
int tp=0;
for(int i=1;i<=m;++i)
if(!(E[id][i].w>>k&1))
{
int x=Find(E[id][i].u),y=Find(E[id][i].v);
if(x!=y)
fa[x]=y;
E[id^1][++tp]=E[id][i];
}
if(Find(1)==Find(n))
id^=1,m=tp;
else
ans+=1<<k;
}
cout<<ans<<endl;
return 0;
}
本题是一道好题