改造二叉树
【题目描述】
小Y在学树论时看到了有关二叉树的介绍：在计算机科学中，二叉树是每个结点最多有两个子结点的有序树。通常子结点被称作“左孩子”和“右孩子” 。二叉树被用作二叉搜索树和二叉堆。随后他又和他人讨论起了二叉搜索树。
什么是二叉搜索树呢？二叉搜索树首先是一棵二叉树。设key[p]表示结点p上的数值。对于其中的每个结点p，若其存在左孩子lch，则key[p]>key[lch]；若其存在右孩子rch， 则key[p]<key[rch]；注意，本题中的二叉搜索树应满足对于所有结点，其左子树中的key小于当前结点的key，其右子树中的key大于当前结点的key。
小Y与他人讨论的内容则是，现在给定一棵二叉树，可以任意修改结点的数值。修改一个结点的数值算作一次修改，且这个结点不能再被修改。若要将其变成一棵二叉搜索树， 且任意时刻结点的数值必须是整数（可以是负整数或0） ，所要的最少修改次数。
相信这一定难不倒你！请帮助小Y解决这个问题吧。
【输入格式】
第一行一个正整数 n表示二叉树结点数。结点从 1~n 进行编号。
第二行 n 个正整数用空格分隔开，第 i 个数 ai 表示结点 i 的原始数值。
此后 n - 1 行每行两个非负整数 fa, ch，第 i + 2行描述结点 i + 1 的父亲编号 fa，以及父
子关系 ch，(ch = 0 表示 i + 1 为左儿子，ch = 1表示 i + 1为右儿子)。
结点 1一定是二叉树的根。
【输出格式】
仅一行包含一个整数，表示最少的修改次数。
【样例输入】
3
2 2 2
1 0
1 1
【样例输出】
2
【数据范围】
20 % ：n <= 10 , ai <= 100.
40 % ：n <= 100 , ai <= 200
60 % ：n <= 2000 .
100 % ：n <= 10 ^ 5 , ai < 2 ^ 31.
分析
中序遍历 + 最长不下降序列
错误代码如下
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100000+9;
#define lowbit(x) (x&-x)
int n;
int a[N], b[N], tot, c[N];
int lch[N], rch[N];
int mn = 2147483647, mx = -1;
void dfs(int x) {
if(!x) return ;
dfs(lch[x]);
b[++tot] = x;
dfs(rch[x]);
}
int ft[N], ans;
void add(int x, int k) {while(x <= mx) {ft[x] = max(ft[x], k); x += lowbit(x);} }
int query(int x) {//最长不下降
int mxx = -1;
while(x) {
mxx = max(ft[x], mxx);
x -= lowbit(x);
}
return mxx;
}
int main() {
// freopen("binary13.in", "r", stdin);
// freopen("binary5.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
int fa, ch;
for(int i = 2; i <= n; i++) {
scanf("%d%d",&fa, &ch);
if(ch == 0) lch[fa] = i;
else rch[fa] = i;
}
dfs(1);
// for(int i = 1; i <= tot; i++) printf("%d ", b[i]);
// printf("
");
for(int i = 1; i <= tot; i++) c[i] = a[b[i]], c[i] -= i, mn = min(mn, c[i]);
for(int i = 1; i <= tot; i++) {
c[i] = c[i] - mn + 1;//都变成大于等于1的， 才能用树状数组做
mx = max(c[i], mx);//找树状数组下标最大值
}
// for(int i = 1; i <= tot; i++) printf("%d ", c[i]);
ans = -1;
for(int i = 1; i <= tot; i++) {
ft[c[i]] = query(c[i]) + 1;
ans = max(ft[c[i]], ans);
add(c[i], ft[c[i]]);
}
printf("%d", tot - ans);//“最长不下降”是要保留下来的
}
正确代码： 二分
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=100000+20;
int n,p[maxn],lch[maxn],rch[maxn];
int order[maxn],tot=0;
int f[maxn],ans;
inline void read(int& n){
n=0;
char ch=getchar();
while(ch<'0' || ch>'9') ch=getchar();
do{
n=n*10+ch-'0';
ch=getchar();
}while(ch>='0' && ch<='9');
return;
}
void init(){
memset(lch,-1,sizeof(lch));
memset(rch,-1,sizeof(rch));
read(n);
for(int i=1;i<=n;i++) read(p[i]);
for(int i=2;i<=n;i++){
int fa,ff;
read(fa);
read(ff);
if(ff==0) lch[fa]=i;
else rch[fa]=i;
}
return;
}
void dfs(int node){
if(node==-1) return;
dfs(lch[node]);
++tot;
order[tot]=p[node]-tot;
dfs(rch[node]);
return;
}
void solve(){
dfs(1);
for(int i=1;i<=tot;i++){
f[i]=2100000000;
}
f[1]=order[1];ans=1;
for(int i=2;i<=tot;i++){
if(order[i]>=f[ans])
f[++ans]=order[i];
else{
int l = 1,r = ans, xxx;//注意右边界为r
while (l <= r) {
int mid = (l + r) >> 1;
if (f[mid] < order[i]) {
l = mid + 1;
} else {
xxx = mid;
r = mid - 1;
}
}
f[xxx] = order[i];
}
}
ans=n-ans;
printf("%d",ans);
return;
}
int main(){
init();
solve();
return 0;
}
数字对
【题目描述】
小 H 是个善于思考的学生，现在她又在思考一个有关序列的问题。
她的面前浮现出一个长度为 n的序列{ai}，她想找出一段区间[L, R](1 <= L <= R <= n)。
这个特殊区间满足，存在一个 k(L <= k <= R)，并且对于任意的 i(L <= i <= R)，ai 都能
被 ak 整除。这样的一个特殊区间 [L, R]价值为 R - L。
小 H 想知道序列中所有特殊区间的最大价值是多少，而有多少个这样的区间呢？这些
区间又分别是哪些呢？你能帮助她吧。
【输入格式】
第一行，一个整数 n.
第二行，n个整数，代表 ai.
【输出格式】
第一行两个整数，num和 val,表示价值最大的特殊区间的个数以及最大价值。
第二行 num 个整数，按升序输出每个价值最大的特殊区间的 L.
【样例输入 1】
5
4 6 9 3 6
【样例输出 1】
1 3
2
【样例输入 2】
5
2 3 5 7 11
【样例输出 2】
5 0
1 2 3 4 5
【数据范围】
30%: 1 <= n <= 30 , 1 <= ai <= 32.
60%: 1 <= n <= 3000 , 1 <= ai <= 1024.
80%: 1 <= n <= 300000 , 1 <= ai <= 1048576.
100%: 1 <= n <= 500000 , 1 <= ai < 2 ^ 31.
分析
等下再具体的打...
RMQ的思想， 求区间gcd和最小值， 二分找答案
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 500000+9;
inline int gcd(int x, int y) {return !y ? x : gcd(y, x%y);}
int n;
int f[N][20], g[N][20];
void init() {
for(int k = 1; (1<<k) <= n; k++) {
for(int i = 1; i+(1<<k)-1 <= n; i++) {
f[i][k] = min(f[i][k-1], f[i+(1<<(k-1))][k-1]);
g[i][k] = gcd(g[i][k-1], g[i+(1<<(k-1))][k-1]);
}
}
}
int RMQ_gcd(int l, int r) {
int m = r - l + 1;
int k = 0;
while(1<<k <= m) k++;
k--;
return gcd(g[l][k], g[r-(1<<k)+1][k]);
}
int RMQ(int l, int r) {
int m = r - l + 1;
int k = 0;
while(1<<(k+1) <= m) k++;
return min(f[l][k], f[r-(1<<k)+1][k]);
}
int num;
int ans[N], tot;
int check(int Len) {
int r, is = 0;
for(int l = 1; l <= n && l + Len - 1 <= n; l++) {
r = l+Len-1;
if(RMQ(l, r) == RMQ_gcd(l, r)) {
if(is == 0) tot = 0;
is = 1;
ans[++tot] = l;
}
}
return is;
}
int main() {
// freopen("pair.in", "r", stdin);
// freopen("pair.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &f[i][0]), g[i][0] = f[i][0];
init();
int l = 1, r = n, mid, Len;
while(l <= r) {//左闭右闭
mid = (l+r)>>1;
if(check(mid)) {
Len = mid;
l = mid+1;
num = tot;
} else {
r = mid - 1;
}
}
printf("%d %d
", num, Len - 1);
for(int i = 1; i <= tot; i++) printf("%d ",ans[i]);
}
/*
7
6 3 9 18 4 8 2
*/