为了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=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-; ch=getchar();}
while(ch>=''&&ch<='') s=s*+ch-'',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=;
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+,tmp+t+);
for(int i=;i<=t;i++) if(tmp[i]<=tmp[i-])
tmp[i]=tmp[i-]+;
f[x]=tmp[t]+;// printf("%d %d\n",x,f[x]);
}
int main()
{
int n=read(),x;
for(int i=;i<=n;i++) x=read(),add(x,i);
dfs(); printf("%d\n",f[]);
return ;
}

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=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-; ch=getchar();}
while(ch>=''&&ch<='') s=s*+ch-'',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 ;
return !l?pre[r]:(pre[r]-pre[l-]+mdn)%mdn;
}
int main()
{
int n=read(); scanf("%lld%lld",&A,&B);
if(A<B) swap(A,B);
for(int i=;i<=n;i++) scanf("%lld",&a[i]);
pre[]=f[]=; int l=,r=;
a[]=-1e18; a[n+]=(2e18)+;
for(int i=;i<=n+;i++)
{
while(r<i&&a[i]>=a[r]+A) r++; r--;
if(a[i]-a[i-]>=A) f[i]=f[i-];
upd(f[i],get(l,min(r,i-)));
pre[i]=pre[i-];
if(a[i+]-a[i-]>=B) upd(pre[i],f[i]);
if(a[i]-a[i-]<B) l=i-;
}
printf("%d\n",f[n+]);
return ;
}

最新文章

  1. CSS Hack
  2. 《JavaScript高级程序设计》学习笔记12篇
  3. xshell 5连接linux服务器的技巧
  4. Unity3D研究院之IOS本地消息通知LocalNotification的使用
  5. Hacking Secret Ciphers with Python翻译序言
  6. c++基础语法 构造函数 析构函数 类的组合
  7. VS2010 Web项目需要缺少的Web组件才能加载
  8. &amp;lt;源代码&amp;gt;FTPclient追加方式上传自己定义信息
  9. 深入浅出畅谈Zigbee
  10. VMware ESXI4.1 常用命令
  11. CSS中float属性和clear属性的一些笔记
  12. [Leetcode] Binary tree level order traversal二叉树层次遍历
  13. Android笔记: fragment简单例子
  14. Head First Java设计模式思维导图总结
  15. spring MVC 的MultipartFile转File读取
  16. [Compression] Hadoop 压缩
  17. 12.12 Daily Scrum
  18. System.arraycopy和arrays.copyOf
  19. EUI组件之EditableText
  20. SQL空和NULL的区别

热门文章

  1. loj#6034 「雅礼集训 2017 Day2」线段游戏
  2. Vue项目移动端滚动穿透问题
  3. fiddler之数据分析和查看(inspectors)-抓包
  4. Web Service自动化测试知识点导图
  5. Charles抓包过滤的四种方式
  6. python字符串-方法
  7. JavaScript Return Object.Type
  8. Kinect V2入门之数据获取步骤
  9. Distributed Deep Learning
  10. C++函数声明与定义