为了1天4题的flag不倒所以开新坑...
B.
考虑把这棵树直接建出来，f[i]表示i最少的比赛次数，然后按照定义转移就行了。
//Love and Freedom. #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ll long long #define inf 20021225 #define N 100010 using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return f*s; } struct edge{int to,lt;}e[N]; int in[N],cnt,f[N],tmp[N]; void add(int x,int y) { e[++cnt].to=y; e[cnt].lt=in[x]; in[x]=cnt; } void dfs(int x) { if(!in[x]) return; int t=0; for(int i=in[x];i;i=e[i].lt) dfs(e[i].to); for(int i=in[x];i;i=e[i].lt) tmp[++t]=f[e[i].to]; sort(tmp+1,tmp+t+1); for(int i=2;i<=t;i++) if(tmp[i]<=tmp[i-1]) tmp[i]=tmp[i-1]+1; f[x]=tmp[t]+1;// printf("%d %d ",x,f[x]); } int main() { int n=read(),x; for(int i=2;i<=n;i++) x=read(),add(x,i); dfs(1); printf("%d ",f[1]); return 0; }
C.
简单DP，每次从区间转移。有一些细节需要考虑一下。qwq。
//Love and Freedom. #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ll long long #define inf 20021225 #define N 100010 #define mdn 1000000007 using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return f*s; } void upd(int &x,int y){x+=x+y>=mdn?y-mdn:y;} int pre[N],n,f[N]; ll a[N],A,B; int get(int l,int r) { if(l>r) return 0; return !l?pre[r]:(pre[r]-pre[l-1]+mdn)%mdn; } int main() { int n=read(); scanf("%lld%lld",&A,&B); if(A<B) swap(A,B); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); pre[0]=f[0]=1; int l=0,r=0; a[0]=-1e18; a[n+1]=(2e18)+1; for(int i=1;i<=n+1;i++) { while(r<i&&a[i]>=a[r]+A) r++; r--; if(a[i]-a[i-1]>=A) f[i]=f[i-1]; upd(f[i],get(l,min(r,i-2))); pre[i]=pre[i-1]; if(a[i+1]-a[i-1]>=B) upd(pre[i],f[i]); if(a[i]-a[i-1]<B) l=i-1; } printf("%d ",f[n+1]); return 0; }