前来观摩zhy女装
by Ln_YJIn @ 2019-10-16 17:04:42
前排前排
zhy女装
by DUO_JIaMInG @ 2019-10-16 17:05:32
前来观摩zhy女装
by 婷菡 @ 2019-10-16 17:07:37
# 前来观摩zhy女装
by you_xiao @ 2019-10-16 17:08:11
by you_xiao @ 2019-10-16 17:12:57
以上请无视
by therehello @ 2019-10-16 17:13:54
草，洛谷评测鸡真是闹鬼啊QAQ，我也测了好久，还以为是错哪，结果没想到随便把下面乱改了一下就a了，理论上对结果是没有影响的啊！
```cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define endl '\n'
#define lowbit(x) x&-x
using namespace std;
const int maxv=1e6+100;
const int mod=2008;
const int maxNum=0x7fffffff-10;
const double eps=1e-8;
const double PI=3.1415926535;
typedef long long LL;
inline int read(){
int x=0, f=1;
char ch=getchar();
while (ch < '0' || ch > '9'){
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
// return x;
}
inline void write(__int128 x){
if (!x) putchar('0');
char F[200];
__int128 tmp = x > 0 ? x : -x;
if (x < 0) putchar('-');
int cnt = 0;
while (tmp > 0) F[cnt++] = tmp % 10 + '0',tmp /= 10;
while (cnt > 0) putchar(F[--cnt]);
// putchar('\n');
// putchar(' ')
}
struct Node{
int l,r;
Node(){l=r=0;}
}t[maxv];
int a[maxv],s[maxv],b[maxv],blen;
void inOrder(int p){
if(!p) return;
inOrder(t[p].l);
b[++blen]=a[p];
inOrder(t[p].r);
}
signed main(){
int n,ans=0,p=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=2,fa,ch;i<=n;i++) scanf("%d%d",&fa,&ch),(ch?(t[fa].r=i):(t[fa].l=i));
inOrder(1);
for(int i=1;i<=n;i++) b[i]-=i; //区别
for(int i=1;i<=n;i++){
if(p==0||s[p]<=b[i]) s[++p]=b[i],ans=max(ans,p);
else{
int x=upper_bound(s+1,s+p+1,b[i])-s;
s[x]=b[i],ans=max(ans,x);
}
}
printf("%d",n-ans);
return 0;
}
```
```cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define endl '\n'
#define lowbit(x) x&-x
using namespace std;
const int maxv=1e6+100;
const int mod=2008;
const int maxNum=0x7fffffff-10;
const double eps=1e-8;
const double PI=3.1415926535;
typedef long long LL;
inline int read(){
int x=0, f=1;
char ch=getchar();
while (ch < '0' || ch > '9'){
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
// return x;
}
inline void write(__int128 x){
if (!x) putchar('0');
char F[200];
__int128 tmp = x > 0 ? x : -x;
if (x < 0) putchar('-');
int cnt = 0;
while (tmp > 0) F[cnt++] = tmp % 10 + '0',tmp /= 10;
while (cnt > 0) putchar(F[--cnt]);
// putchar('\n');
// putchar(' ')
}
struct Node{
int l,r;
Node(){l=r=0;}
}t[maxv];
int a[maxv],s[maxv],b[maxv],blen;
void inOrder(int p){
if(!p) return;
inOrder(t[p].l);
b[++blen]=a[p]-blen; //区别
inOrder(t[p].r);
}
signed main(){
int n,ans=0,p=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=2,fa,ch;i<=n;i++) scanf("%d%d",&fa,&ch),(ch?(t[fa].r=i):(t[fa].l=i));
inOrder(1);
for(int i=1;i<=n;i++){
if(p==0||s[p]<=b[i]) s[++p]=b[i],ans=max(ans,p);
else{
int x=upper_bound(s+1,s+p+1,b[i])-s;
s[x]=b[i],ans=max(ans,x);
}
}
printf("%d",n-ans);
return 0;
}
```
上面是ac代码，下面是20分代码，区别只有把b[i]-i的过程分别在b[i]数组赋值过程和之后的单独过程。（见注释）
by Butane @ 2022-07-16 11:31:59