T1 改造二叉树
洛谷上的数据有水，过了不代表正确；
这题还是比较难想的（至少我是这么认为的）
首先如果我们对一颗平衡树进行中序遍历，得到的一个遍历的序列是单调上升的。
于是我们这道题就转化成一个这样的问题：
给一棵二叉树，让它的中序遍历序列变为严格单调上升序列，最少需要多少次修改
《算法竞赛进阶指南（第二版）》的263面提过一个思考题：
把一个序列A变成非严格单调递增的（单调不下降的），至少需要修改多少个数？
比如2 3 1 4 它变成单调不降的就是2 3 3 4，修改一个数，可以发现，A的最长不降子序列是不需要被修改的，而其他的值需要增加或减小来和原来的最长不下降子序列构成一个新的最长不下降子序列，答案就是A的长度减去A的最长不下降子序列的长度。
把一个序列A变成严格单调递增的，至少需要修改多少个数？
如果2 3 1 4 它变成单调递增的就是2 3 4 5，修改两个数，这是因为3和4之间（从自然数的意义上）有0个自然数，而3和4之间（在数列上）有1个自然数，显然，你无法找到一个自然数它既大于3又小于4，我们定义两个数的差值-1为容量，而下标的差值-1我们定义为装载量。
显然如果两个数之间能存在严格单调上升的序列仅当容量>=装载量成立，即容量-装载量>=0
设序列\(a\)，
容量>=装载量即为\(a_i-a_j\ge i-j\)
移项得\(a_i-i\ge a_j-j\)
由于对于任意项都要成立，所以我们只要用每一项的值减去下标，答案就是长度-最长不降子序列的长度
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include<bits/stdc++.h> using namespace std; const int MAXN=100005; int ch[MAXN][2],a[MAXN],n,now,key[MAXN]; int f[MAXN],d[MAXN],len=1; void dfs(int x){ if(ch[x][0]) dfs(ch[x][0]); a[++now]=key[x]; if(ch[x][1]) dfs(ch[x][1]); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&key[i]); int x,fa; for(int i=2;i<=n;i++){scanf("%d%d",&fa,&x);ch[fa][x]=i;} dfs(1); for(int i=1;i<=n;i++)a[i]-=i; d[1]=a[1]; for(int i=2;i<=n;i++){//nlogn if(a[i]>=d[len])d[++len]=a[i]; else { int j=upper_bound(d+1,d+len+1,a[i])-d; d[j]=a[i]; } } printf("%d\n",n-len); return 0; } |
T2 数字对
这题真的就是乱搞也能过，数据是全随机的，然而考试的时候还是写的是暴力，虽然优化成了\(O(n^3logn)\)但是和\(O(n^4)\)的分数一样．
有两种乱搞方法，一种是枚举每个点向两边拓展，另一种是枚举两个端点（这种方法等下会放代码），前者意外跑的很快．．．
第二种乱搞方法是上届学长留下来的：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
/* @author:dpj */ #include<set> #include<cstdio> #include<iostream> using namespace std; const int MAXN=500001; int n,a[MAXN]; struct Node{ int l,r; }ans[MAXN]; int main(){ freopen("pair.in","r",stdin); freopen("pair.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int Max=0; for(int i=1;i<=n;i++){ for(int j=i;j>=1;j--){ if(a[j]%a[i]) break; ans[i].l=j; } for(int j=i;j<=n;j++){ if(a[j]%a[i]) break; ans[i].r=j; } Max=max(Max,ans[i].r-ans[i].l); } int tot=0; multiset<int>s; int last=0; for(int i=1;i<=n;i++){ if(ans[i].r-ans[i].l==Max){ if(ans[i].l==last) continue; last=ans[i].l; tot++; s.insert(ans[i].l); } } printf("%d %dn",tot,Max); multiset<int>::iterator it; for(it=s.begin();it!=s.end();it++) printf("%d ",(*it)); fclose(stdin); fclose(stdout); return 0; } |
对于每一个特殊区间，它的特殊点一定满足的条件是ＧＣＤ＝最小值
于是我们可以维护区间的GCD和最小值，
区间长度我们也可以不用暴力枚举，直接二分即可．
此时我们只二分出来了最大的长度，要想知道具体的答案，还得根据算出来的长度扫一遍数组，合法性的判定和上面是一样的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<bits/stdc++.h> using namespace std; const int MAXN=500003,M=21; int n,m; int a[MAXN],f[MAXN][M],g[MAXN][M],p[M]; int gcd(int a,int b){ return b?gcd(b,a%b):a; } inline char nc(){ static char buf[MAXN],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++; } inline int read(){ char ch='[';int x=0,f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=nc();} while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=nc();} return x*f; } bool check(int len){ int q=log2(len),k=n+1-p[q]; for(int i=1;i<=k;i++){ int j=i+len-1; if(min(f[i][q],f[j-p[q]+1][q])==gcd(g[i][q],g[j-p[q]+1][q]))return true;//如果区间最小值=区间gcd,合法 } return 0; } int main(){ freopen("pair.in","r",stdin); freopen("pair.out","w",stdout); n=read();m=log2(n); for(int i=1;i<=n;i++){ int tmp=read(); f[i][0]=g[i][0]=tmp; } for(int i=0;i<=m;i++)p[i]=1<<i; for(int j=1;j<=m;j++){//预处理ST表 int k=n+1-p[j]; for(int i=1;i<=k;i++){ f[i][j]=min(f[i][j-1],f[i+p[j-1]][j-1]); g[i][j]=gcd(g[i][j-1],g[i+p[j-1]][j-1]); } } int l=1,r=n,ans=0; while(l<=r){//二分最大区间长度 int mid=(l+r)>>1; if(check(mid)){l=mid+1;} else {r=mid-1;} } ans=r; if(ans==1){//最大长度为1,全部为单独的数字 printf("%d %dn", n, 0); for(int i=1;i<n;++i)printf("%d ",i); printf("%dn", n); } else { int q=log2(ans),k=n+1-p[q],tot=0; for(int i=1;i<=k;++i){//枚举最大长度的所有区间,统计个数，记录答案 int j=i+ans-1; if(min(f[i][q],f[j-p[q]+1][q])==gcd(g[i][q],g[j-p[q]+1][q]))a[++tot]=i; } printf("%d %dn",tot,ans-1); for (int i=1;i<tot;++i)printf("%d ",a[i]); printf("%dn",a[tot]); } return 0; } |