这题表诉不清,有两种理解
一.:全序列要么满足第一个性质,要么满足第二个性质.
二:全序列中间既有满足第一个性质的又有满足第二个性质的;
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;
}
本题是一道好题
首先要考虑无限的情况(也是本题的难点所在)
注:以下条件均在边不为0的情况下(特判掉)
一:如果1在一个强连通分量内,只要有边权大于2的边,则为无限
二:如果1在一个强连通分量内,环中有自环,则为无限
三:如果有经过一个强连通分量到达1的,则为无限
其实也比较好理解,就是能否在考试时想的全,敢去往下想
经过一系列的特判,如果有三种情况的一种,则输出无限(实际上只输出无限你就有90分了,因为数据比较水)
如果没有这三种情况,则tarjan缩点,DAG路径dp计数就行