ARC169-AB
wflengxuenong
·
·
个人记录
A:
思考的时候通过矩阵思考的。
题目翻译
给你一棵以 1为根的树，i 号点的父亲是 Pi，点权是 Ai，重复无限次，从 1∼N 分别将 i 号点的点权加进其父亲的点权。请判断1 号点点权的正负性。
推导：
设一个小的矩阵A,大小为N*N，变换10^{10}次，求变换后的矩阵%P
翻译题解：
如果我们遵循P_j→P_i→⋯P_1的顺序，我们最终会到达1。设i的深度di为从i到达1所需要的→个数。
对于每一个j(0≤j<N)，设B_j为A_i对所有i的和，使d_i =j。
首先，a_1 = b_0。
有一个运算可以表示为 B_j+= B_{j+1} (0 \leq j < N)。
如果所有的b_j都是0，那么不管我们操作多少次，b_0都是0，所以答案是0。
假设有一个不为零的B_j。现在，我们取最大的j使得B_j !=0，我们称它为k.
首先，因为B_j (j>k)都是0，所以B_k的值是常数。
接下来，考虑$B_{k-1} $。这个值随着每次操作增加$B_k$，所以即使初始值是负的，在足够数量的操作之后，它总是正的。接下来，考虑$B_{k-2}$。由前面的讨论可知，经过足够次数的运算后，$B_{k-1} $总是正的。因为这个$B_{k-1} $被加到$B_{k-2} $，最终$B_{k-2} $也会变成正数。重复这个论点，我们可以看到，在足够多的操作之后，即使$B_0$也会变成正数。
因此，在这种情况下，答案是$+$。
- 对于$B_k <0$的情况.可以类似地进行讨论，我们可以看到答案是$-$。
这里，我们使用了表达式“a enough number of times”，但是如果我们正确地计算，我们可以看到$10^{100}$是足够的。
它可以通过使用二项式系数计算每个$A_i$的贡献来完成，尽管细节被省略了。如果我们按照上面的判断执行，我们可以在$O(N)$时间内解决问题。
官方题解，以上翻译结果来自有道神经网络翻译（YNMT）·
在思考过程中，我们可以把矩阵变换写下来，发现变换的系数二项式定理的展开项。
随着系数的增大，后面的项权值变大，原始的ai值所占比重越来越小。可以推导出前面的转移关系。
```cpp
/*
1<=pi<i， api +=ai,
首先明确了这是一颗树，不存在环。而且都是下标小的数累加上下标大的数
因为是进行无限次变换。
那么树最底层的累加会依次向上传递。每个数都收到下一层的影响。因此从最底层开始判断
如果为0那决定不了影响
如果非零那就最后影响到A1为正，为负则A1为负。
因为小的受大的影响，实际为一个拓扑。可以写dfs，也可以写逆序循环。
可以先写一个矩阵转移变换，建立一个实际印象。
转换时候的系数变换类似二项式定理。实际是矩阵的次方的形式。
5
1 -1 1 -1 1
1 1 2 2
0 1 1 2 2 后移到一个。正好把需要处理的数加上。
A1+=A[2] A1+=A[3]
A[2]+=A4,A2+=A[5]
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2.5e5 + 5;
int a[MAXN], p[MAXN], dep[MAXN];
ll bak[MAXN];
int main(void)
{
int n;
scanf("%d",&n);
for(int i=1; i<=n; ++i)
scanf("%d",&a[i]);
for(int i=2; i<=n; ++i)
scanf("%d",&p[i]);
for(int i=2; i<=n; ++i)
dep[i] = dep[p[i]] + 1;
for(int i=1; i<=n; ++i)//每层的变换可以打包合并在一起。
bak[dep[i]] += a[i];
for(int i=n; i>=0; --i)
if(bak[i] != 0)
{
if(bak[i] > 0)
printf("+");
else
printf("-");
return 0;
}
printf("0");
return 0;
}
```
## B
要计算单个区间的$f$，用贪心算法，从左端尽可能多地获取。
要计算所有区间的$f$，从每个左端点$l$开始。
对每个端点$i$,还要找出最右侧的$r$使得$\sum_{j=i}^{j<=r}a_j<S
对于每一个
定义dp[i]=\sum_{j=i}^N f(A[i,j])。为方便起见，设dp[N+1]=0。
因此我们要倒着求dp[i],i=N,N-1,...1
对于一个左端点i，设其右侧的端点r为划分到和\leq S的最右侧位置。i,i+1,...,r,r+1,... n
因此，总的动态规划方程为 dp[i]=dp[r+1]+N-r+1+r-i
dp[i]=dp[r+1]+N+1-i
最终的答案是\sum_{i=1}^{i<=n} dp[i]
参考代码
/*
考虑一段的贡献
l r ,以l为左端点，这段和和<=s最右侧的位置为j
如果这段被计数，那么r+1到n都统计上了。
或者右端点不超过r的这段区间
f[l]=f[r]+(r-l)+n-l+1;
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2.5e5 + 5;
ll a[MAXN];
ll sum[MAXN], dp[MAXN];
int main(void)
{
int n; ll S;
scanf("%d%lld",&n,&S);
for(int i=1; i<=n; ++i)
scanf("%lld",&a[i]);
for(int i=1; i<=n; ++i)
sum[i] = sum[i-1] + a[i];
ll ans = 0;
for(int i=n; i>=1; --i)
{
int j = upper_bound(sum+i, sum+n+1, sum[i-1] + S) - sum;
dp[i] = (j-i) + dp[j] + (n-j+1);
ans += dp[i];
}
printf("%lld\n",ans);
return 0;
}