AcWing第53场周赛

给定一个正整数 x，你可以对其各个数位上的数字进行反转操作。

反转操作是指将一个数 t 替换为 9−t。

请你计算，通过一系列的反转操作（也可以不进行任何操作），能够将 x 转换为的最小可能正整数。

注意，最终数字不能以 0 开头。

输入格式
一个正整数 x。

输出格式
一个正整数，表示可以得到的最小可能正整数。

数据范围
所有测试点满足 1≤x≤10¹⁸
输入样例1：
27
输出样例1：
22
输入样例2：
9
输出样例2：
9
输入样例3：
91730629
输出样例3：
91230320

要考虑每个位置上的数t是否要替换为9 - t，使得最后的整数最小。也就是在9 - t < t的时候进行替换，即t > 4.5，又t是整数，所以t不小于5时进行替换即可。由于首位不能是0，所以单独判断首位，在首位是9时，不进行替换。

#include 
#include 
#include 
using namespace std;
int main(){
    string s;
    getline(cin,s);
    if(s[0] != '9' && s[0] >= '5')  s[0] = '0' + '9' - s[0];
    for(int i = 1;i < s.size();i++) {
        if(s[i] >= '5') s[i] = '0' + '9' - s[i];
    }
    cout< 
B AcWing 4426. 整除子串 
题目描述 
给定一个由数字组成的字符串 s，请你计算能够被 4 整除的 s 的子串数量。
 
子串可以包含前导 0。
 
例如，如果 s 为 124，则满足条件的子串有 4 个：12，4，24，124；如果 s 为 04，则满足条件的子串有 3 个：0，4，04。
 
输入格式
 一个由数字组成的字符串 s。
 
输出格式
 一个整数，表示满足条件的子串数量。
 
数据范围
 前 4 个测试点满足 1≤|s|≤10。
 所有测试点满足 1≤|s|≤3×105。
 
输入样例1：
 124
 输出样例1：
 4
 输入样例2：
 04
 输出样例2：
 3
 输入样例3：
 5810438174
 输出样例3：
 9
 
分析 
题目要求一个字符串中能被4整除的子串数量，我们分两部分来考虑这个问题。
 首先，子串表示连续序列，子序列可以不连续，比如123的子串有1， 2 12， 3 23 123。注意这是以末尾元素的不同进行划分的，也就是说，123的子串可以划分为以1为末尾的子串、以2为末尾的子串和以3为末尾的子串，这样划分符合线性DP里面状态表示的习惯。
 然后就要考虑什么样的数能被4整除，我们首先枚举下能被4整除的数：
 0 4 8 ，12 16， 20 24 28， 32 36 40
 很容易发现，对于两位数而言，如果十位数是奇数，那么个位数是2或者6就能被4整除了；如果十位数是偶数，个位数是0,4或者8就能被4整除了。一位数也可以看作十位数是0的两位数，0到9这十个数中，0, 4，8可以被4整除，2和6模4余数是2.所以可以根据余数来一起判断。
 设f[i]表示字符串中以第i个字符为末尾的能被4整除的子串数量，则问题的解等于sum(f[i])。t表示第i 个字符的数字，如果t % 4 == 0，则说明以第i个字符单独构成的子串是能被4整除的。我们再来考虑前一位数last，如果last是偶数，方案数res可以加i。如果t % 4 == 2并且last是奇数，res += i。
 以124为例，首先单独考察首位字符1，不能被4整除，所以不合法；然后考察以2位末尾的子串，由于2自身不能被4整除，但是前面的1是奇数，所以12是可以被4整除的，2所在的下标是1，res++。再考察4，首先单独4是可以被4整除的，res++，然后4前面的2是偶数，所以以4为末尾的子串也是可以被4整除的，res += 2。这里所说的以每个元素为末尾的子串数量暂且不包括自身，比如4前面有两个元素，就有两个子串24和124，子串的个数就是4所在的下标。至于包括自身的单个元素，单独判断加上即可。
 
代码 
#include 
#include 
#include 
using namespace std;
int main(){
    string s;
    getline(cin,s);
    long long res = 0;
    int last = (s[0] - '0') & 1;
    if((s[0] - '0') % 4 == 0)  res++;
    for(int i = 1;i < s.size();i++) {
        int t = s[i] - '0';
        if(t % 4 == 0) {
            res++;
            if(!last)   res += i;
        }
        if(last && (t == 2 || t == 6))    res += i;
        last = t & 1;
    }
    cout< 
C AcWing 4427. 树中节点和 
题目描述 
给定一棵 n 个节点组成的树。
 
树中节点编号为 1∼n。
 
1 号节点为树的根节点。
 
树中的每个节点 v 都具有一个非负整数权值 av。
 
我们用 sv 来表示从节点 v 到根节点的路径上经过的所有节点（包括两端节点）的权值之和；用 hv 来表示从节点 v 到根节点的路径上经过的所有节点（包括两端节点）的数量。
 
显然，s1=a1，h1=1。
 
现在，我们只知道树的具体结构以及所有 h 值为奇数的节点的 s 值。
 
请你为树中的每个节点 v 赋予一个非负整数权值 av，要求在满足已知信息的情况下，所有节点的权值之和 ∑i=1nai 尽可能小。
 
输出 ∑i=1nai 的最小可能值。
 
输入格式
 第一行包含一个整数 n。
 
第二行包含 n−1 个整数 p2,p3,…,pn，其中 pi 表示节点 i 的父节点编号。
 
第三行包含 n 个整数 s1,s2,…,sn，注意，由于所有 h 值为偶数的节点的 s 值都是未知的，所以这些节点的 s 值并未直接给出，而是用 −1 来代替。
 
输出格式
 一个整数，表示 ∑i=1nai 的最小可能值。
 
如果不存在任何满足已知信息的合理赋值方案，则输出 −1。
 
数据范围
 前 4 个测试点满足 2≤n≤5。
 所有测试点满足 2≤n≤105，1≤pi9。
 
输入样例1：
 5
 1 1 1 1
 1 -1 -1 -1 -1
 输出样例1：
 1
 输入样例2：
 5
 1 2 3 1
 1 -1 2 -1 -1
 输出样例2：
 2
 输入样例3：
 3
 1 2
 2 -1 1
 输出样例3：
 -1
 
分析 
题目给定了一棵树，每个节点都有个非负权值，知道部分节点的累计权值信息，对于某节点v而言，累计权值s[v]表示从v到根节点上所有节点的权重之和，并且奇数层节点知道累计权值信息，但是偶数层的累计权值未知，用-1表示，他们让我们给这些未知权重的节点赋值，使得整棵树的权值和最小。看起来题目描述的信息很复杂，实际上很简单，举个例子：
 
 如图所示，一棵普通的二叉树，奇数层比如第一层和第三层的节点累计权值已知，偶数层比如第二层的累计权值未知。首先可以注意到的是，作为1的左右子树，2和3两棵子树的权重是互不影响的，所以我们只需要分别计算出1左右子树的权重，统计下就知道整棵树的权值和了。考察左子树的权值和，是不是s4 + s5 + s6呢？显然不是，s4是1 2 4号节点的权值之和，其他两个节点也类似，所以s4 + s5 + s6 = (v1+v2+v4)+(v1+v2+v5)+(v1+v2+v6) ，也就是1 2号节点的权值加了三遍，减去两遍v1和v2就可以了，而2号节点未知的累计权值和s2恰好等于v1 + v2，所以1号节点加上其左子树节点的权值和sl = s4 + s5 + s6 - 2*s2，而第三层节点的累计权值和是固定的，sl的大小就与s2的值成反比，也就是s2越大，sl越小。此时需要注意题目中所有节点的权值都是非负数，这意味着父节点的累计权值和一定不会超过孩子节点的权值和，也就是s2 <= min(s4,s5,s6)，s2越大越好，所以取孩子节点中的最小累计权值和即可。
 从上面的例子中可以总结出一个结论，对于偶数层的节点，其累计权值和的取值取孩子节点中最小的累计权值和时，整棵树的权值和最小。推导过程看似不简单，实际只有随便画棵数，列下权值和的公式，就能够推出这个结论。本题最重要的结论推出来了，下面要做的就是给未知累计权值的节点赋值了。开始写代码前想清楚哪些工作是需要做的，周赛时我是一边写代码一边捋思路，还是花了点时间才ac本题的。
 首先，对树的dfs遍历肯定是少不了的，遍历过程中需要根据节点层数的奇偶性分开讨论，对于偶数层节点，其累计权值和未知，我们遍历完就给它们赋上孩子节点中累计权值和的最小值。
 第二个问题是如何求出整棵树的权值和？本题的累计权值和相当于树上的前缀和，对于某个节点u，其父节点是p，那么u的权值就等于s[u] - s[p]，这和一维前缀和的公式基本是一样的。dfs的过程中我们已经给每个未知累计权值和的节点赋值了，自然可以顺带求出每个节点的权值，加起来就是整棵树的权值和了。
 第三个问题是dfs的返回值和参数如何设计，参数当前遍历的节点u必不可少，我们在判断是否存在合法赋值方案时，只要父节点的累计权值和小于孩子节点的累计权值和，说明孩子节点中出现了负权值，自然不合法。所以u的父节点的累计权值和也需要作为参数，计算节点u的权值时也需要用到父节点的累计权值和ps。dfs的返回值设置为bool类型即可，出现不合法的现象直接返回false。
 最后总结下dfs的过程：
 
首先是边界情况，如果叶子节点是偶数层节点，由于其累计权值和未知，他们父节点的累计权值和是已知的，所以给他们的权值全部赋为0即可，在dfs中无需考虑，直接返回。
然后在当前遍历节点u的累计权值和未知时，遍历下u的孩子节点，求出u的累计权值和，同时与u的父节点的累计权值和比较，不合法就返回false。
计算u的权值，给总的权值和累加上去。
递归的遍历u的子树。
 
代码 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 100005;
int s[N],idx,e[N],ne[N],h[N];
long long ans = 0;
int add(int a,int b) {
    e[idx] = b,ne[idx]=h[a],h[a] = idx++;
}
bool dfs(int u,int ps) {
    int res = 1e9;
    if(h[u] == -1 && s[u] == -1) return true;//叶子是偶数层节点，无需考虑
    if(s[u] == -1) {
        for(int i = h[u];~i;i = ne[i]){
            int j = e[i];
            res = min(res,s[j]);
        }
        if(res < ps){//不合理
            return false;
        }
        s[u] = res;
    }
    ans = ans + s[u] - ps;
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(!dfs(j,s[u]))    return false;
    }
    return true;
}
int main(){
    int n,p;
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i = 2;i <= n;i++) {
        scanf("%d",&p);
        add(p,i);//父节点指向孩子的单向边
    }
    for(int i = 1;i <= n;i++)   scanf("%d",&s[i]);
    if(dfs(1,0)) cout<