本文共 2689 字，大约阅读时间需要 8 分钟。
***有机会补充一组cnt代码 以及完整连续子序列的代码***
对于最长连续子序列 它其实是最长上升子序列的一个变形
首先,我们要知道的一点是,对于诸如
1 2 4 5 3 这样的 ,那么也就是比他大的连上一条边,比如1连了 2 4 5 3过去, 2连了4 5 3 4就是5 5和3 没连 这样,然后构成了一张图
dfs写实现过程....
(现在知道为什么dfs只加一个参数,而且一般是void了吧!!!!)
如果dfs(i,cnt);
return cnt这个cnt传不过来啊
跑完上一个return的仅仅是 你传进来的cnt罢了 无效
可以定义一个maxn记录
然后复杂度最多是O (N^2)的
最多是每个地方都连了(就是 1连了所有边 2也是 一共查询n次)
如果你不加记忆化搜索 每一次还都要重新跑 会多好多复杂度
只要加这两句话
d[i] = ans;
if (d[i] != -1) return d[i];
这一句小小的代码看起来不多 但是关键是要理解了呀
不然那你就要写出o(3^n)的东西了
每次都要再次重新跑了一次
还有就是 是倒着的
比如 1 2 3 4连着 连通度(?)
就是 4 3 2 1
你真的理解了吗?
然后最长连续的就是...
别的都不管
还是找联通的边 但是只需要一次 因为肯定最多也只有一条边
//get position of all a[i]
/**/省略代码
// p[i] i的位置
if (p[i + 1] > p[i]) g[i].pb(i + 1);
//比如5 7 6 g[i] 5 6
//6 7 9 8 // 7 is not pb 9
//
还是如果连通得来就串一串 很可能下面那个题其实也可以写的...就dfs
这样只要把n跑一一遍点就可以了 n足够
你看啊 第一个最长上升是n方 2000足够
二分那些都是骚操作了....nlogn的
但是最长连续就完全有办法优化的呀
//好的吧 下面一个是对的代码ac的 然后不加记忆华搜索要超时 第二个不用看了(zj源码)
#include #include #include
#include #include #include using namespace std;#define pb push_backint a[] = { 0,1,6,2,4,5,3 };const int mn = 1e5 + 5;vector g[mn];int maxi = 0;int d[mn];int dfs(int i) { if (d[i] != -1) return d[i]; int ans = 1; for (int j = 0; j p[i]) g[i].pb(i + 1); //5 7 6 g[i] 5 6 //6 7 9 8 // 7 is not pb 9 // // n manx n is 1 //复杂度是n 了 } g[1].pb(2); g[2].pb(3); g[3].pb(4); g[1].pb(5); memset(d, -1, sizeof d); int ans = 0; for (int i = 1; i <= n; i++) { ans=max(ans,) } /* int cnt=0; if (1){ dfs(i,cnt); cnt++; }*/ //printf("%d\n",cnt);}
//上面代码不太对 下面是题
万能头文件要用gcc clang不行!
我的代码风格大为改观....
....然后
这个是要用最长连续上升子序列 我写了个最长上升子序列
然后下面代码是错的 待我补充个对的上来(只过了样例hhhh)
(然后其实不用加那个1的)
#include using namespace std;int a[200005];int b[200005];#define maxn 200010int main() { int n; cin>>n; for(int i=0; i >b[i]; a[i]=maxn; }//fill (a,a+n,maxn); for(int i=0; i
竟然A了 我十分震惊
懒得写了 就是找连通块
竟然思路还emmm对了 还0(n) 也是很神奇了→_→ 这一周的高数没白旷课啊
#include #include using namespace std;int m,n;int a[100005];//int g[200005];int fa[100005];int sf(int x){return fa[x]==x?x:fa[x]=sf(fa[x]);}int main(){ while(cin>>n>>m){ for(int i=1;i<=n;i++){ fa[i]=i; cin>>a[i]; } int u;int v; for(int i=1;i<=m;i++){ cin>>u>>v; fa[sf(a[u])]=sf(a[v]); }// for(int i=1;i<=2*m;i++){ // cout<
转载地址：http://mquti.baihongyu.com/