gjoi 10.18

模拟赛不通知，模拟赛巨大绑包，素质有待降低。

---

T1 向量

不难发现操作次数固定，操作其实相当于在有两位的前提下减少一位，如果和 \(\geq 10\) 花费 \(9\) 的代价加 \(1\) 位。答案肯定是 \(初始位数+额外位数-1\)，现在问题是额外位数是什么，不妨设序列和为 \(sum\)，额外次数就是 \(\lfloor\frac{sum}{9}\rfloor\)，特判 \(sum\equiv 0\pmod 9\) 的时候最后一次不能拿来贡献额外位数。

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(register int i=l; i<=r; ++i)
#define dn(i,r,l) for(register int i=r; i>=l; --i) using namespace std;const int N=200005;int n, sum;
char s[N];signed main() {ios::sync_with_stdio(0);cin.tie(0);cin >> s, n=strlen(s);up(i,0,n-1) sum+=s[i]-'0';cout << n-1+sum/9-(sum%9==0);return 0;
}

---

T1 顺序

构造题应该先想办法贴上下界。假设知道了根，那么应该想要最大的深度尽量小，我们画出一种最符合这种贪心的图，贴下界的话，我们把 \(dis=0\) 的点放在矩阵尽量中间即可，下界是 \(n-1+m-1+[2|n]\)，因为这个如果初始的 \(m\) 偶 \(n\) 奇要调换一下。