思路
答案就是长度为$l$的区间最小的区间和，设其为$k$。
若答案$ans$大于$k$，因为最多只有$k$只青蛙能越过区间和为$k$的区间，一定不成立。
设$pi$为第$i$个石头的位置，因为最小的区间和为$k$,所以$p{i+k}-p_i\le l$，一定有方法过河。
向上向下取整的不等式运算
向下取整（floor）
以下各式中除法默认为向下取整的整数除法（$\lceil\quad \rceil$标注的除外)
$${a\over b}\ge c \implies \begin{cases}a\ge b\times c\\ b\le {a\over c}\end{cases} \\
{a\over b}\le c \implies \begin{cases}a\le b\times c+b-1\\ b\ge {a\over {c+1}}+1\end{cases}$$
向上取整（ceil）
对于$$\lceil {a\over b}\rceil$$可以转化成$${a+b-1}\over b$$利用向下取整的方法运算
ZOJ-4029
题解
对这种带取整的式子，要考虑是不是很多情况取整后都是一样的值，此题
$$\lceil log_pa \rceil=i\qquad p^{i-1}<a\le p^i$$
由于$a\le 1e9$ $i$最大的取值为$30$，排序预处理出前缀和，对每个p二分即可
代码
1 |
|
Codeforces-960F
题解
对每个节点开一个树状数组维护前缀最大值(即区间$[1,n]$的最大值)BIT[i][j]表示存在一条指向$i$点的路径，路径中最后一个边的权值为$j$
那么对每条边$u,v,w$，查询指向$i$的路径中，最大权值不超过$w-1$，长度最大的路径的长度（即BIT[u][w-1]），再加一即为以$v$结尾，最大权值为$w$的路径的长度，同时把这个值更新到BIT[v][w]中，因为是按读入边的顺序处理的，所以可以满足边的编号递增的条件，查询的最大值即为答案。
注意直接开所有的树状数组内存是不够的，使用map就可以了
代码
1 | //4 24 |
Codeforces-960E
题解
奇数个点组成的路径才对答案有贡献
具体的解法是对每个点计算它对答案的贡献
每个点（设为$u$）对答案的贡献有两部分
- 路径中除$u$外所有点都是在$u$的子孙节点中
即在$u$的任意两个子树中各取一个点$v_1,v_2$，使$v_1,v_2$到$u$组成的路径同时有奇数个点或同时为偶数个点。这样从$v_1$到$v_2$，经过$u$的路径中含有奇数个点，能对答案有贡献，到$u$路径为奇数个点的做正贡献，为偶数的做负贡献。通过dfs可处理，（语言不好描述，详见代码）
设$odd[i]$为$i$点 自身 和的子孙节点中由该点到$i$组成的路径含有奇数个点的个数
$even[i]$为$i$点的子孙节点中由该点到$i$组成的路径含有偶数个点的个数 - 路径中一部分是$u$的祖先节点，一部分是$u$的子孙节点
这里有个重要结论
设$allodd[i],alleven[i]$为图中所有点中到该点组成路径含有奇数点（偶数点）的个数
设$1$为根节点,则
$$allodd[1]=odd[1]\\alleven[1]=odd[1]$$
同时若$u,v$为相邻的两个点
$$allodd[u]=alleven[v]\\alleven[u]=allodd[v]$$
设节点高度为$level[i],level[1]=1$
则$$\begin{cases}
allodd[i]=allodd[1]=odd[1],alleven[i]=alleven[i]=even[1] & level[i]\%2=1\\
allodd[i]=alleven[1]=even[1],alleven[i]=allodd[i]=odd[1] & level[i]\%2=0\\
\end{cases}$$
设 $upo,upe$：该点自身和祖先节点中到该点组成的路径含奇数（偶数）个点的点的个数。
$$upo=allodd[i]-odd[i]+1\\upe=alleven[i]-even[i]$$
此点的贡献为
$$
(allodd[i]\times odd[i]-alleven[i]\times even[i])\times 2\times val[i]-val[i]
$$
注意当路径长度为1时，只能做一次贡献，而式子中是乘以2的，答案最后应减去一个$val[i]$代码
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96//4 18
using namespace std;
typedef long long ll;
const ll MAXN=2e5+100;
const ll MOD=1e9+7;
struct Edge{
ll from,to,nxt;
}edge[MAXN*2];
ll eidx;
ll head[MAXN];
void addedge(ll from,ll to)
{
edge[eidx].from=from; edge[eidx].to=to;
edge[eidx].nxt=head[from]; head[from]=eidx++;
}
void einit()
{
eidx=0;
memset(head,-1,sizeof head);
}
ll val[MAXN];
ll o[MAXN],e[MAXN],lev[MAXN];
ll ans;
bool vis[MAXN];
void dfs(ll u,ll h,ll fa){
lev[u]=h;
vis[u]=1;
o[u]=e[u]=0;
for(ll i=head[u];i!=-1;i=edge[i].nxt)
{
ll v=edge[i].to;
if(vis[v]) continue;
dfs(v,h+1,u);
ll ta=2*(o[u]*e[v]%MOD-o[v]*e[u]%MOD)%MOD*val[u]%MOD;
ta=(ta%MOD+MOD)%MOD;
if(u==1)
{
//printf("ou %lld eu %lld ta %lld\n",o[u],e[u],ta);
}
ans=(ans+ta)%MOD;
o[u]+=e[v];
e[u]+=o[v];
}
o[u]++;
}
void init()
{
memset(vis,0,sizeof vis);
}
int main()
{
//freopen("input.txt","r",stdin);
ll n;
//while(cin>>n)
{
cin>>n;
einit();
init();
for(int i=1;i<=n;++i){
scanf("%lld",&val[i]);
}
for(int i=1;i<n;++i)
{
ll p1,p2;
scanf("%lld%lld",&p1,&p2);
addedge(p1,p2);
addedge(p2,p1);
}
ans=0;
dfs(1,1,-1);
for(int i=1;i<=n;++i)
{
ll upo,upe,ta;
if(lev[i]%2)
{
upo=o[1]-o[i]+1;
upe=e[1]-e[i];
}else{
upo=e[1]-o[i]+1;
upe=o[1]-e[i];
}
ta=2*(upo*o[i]%MOD-upe*e[i]%MOD)%MOD*val[i]%MOD;
ta-=val[i];
ta=(ta%MOD+MOD)%MOD;
ans=(ans+ta)%MOD;
}
cout<<ans<<endl;
}
return 0;
}