题目分析

要求求出S最大的值，S其实是一个联通块。所以就是求所有联通块里面值最大的那个。

树形dp

一般使用f[u]表示树形dp
本题中,f[u]表示的是以u为根节点的连通块的sum的最大值
f[u]=w[u]+max(子树的情况，0)

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 100010,M=N*2;
int h[N],e[M],ne[M],w[N],idx;
int n;
LL f[N];
void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u,int father)
{
    f[u]=w[u];
    for(int i=h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(j!=father)
        {
            dfs(j,u);
            f[u]+=max(0ll,f[j]);
        }
    }
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;++i)cin>>w[i];
    for(int i=0;i<n-1;++i){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(2,-1);
    LL res = f[1];
    for(int i=2;i<=n;++i)res = max(res,f[i]);
    cout<<res<<endl;
    return 0;
}

什么是差分

差分是求前缀和的逆操作，对于原数组a[n],构造出一个数组b[n],使a[n]为b[n]的前缀和。一般用于快速对整个数组进行操作，比如对将a数组中[l,r]部分的数据全部加上c。使用暴力方法的话，时间复杂至少为O(n)，而使用差分算法可以将时间复杂度降低到O(1)。

算法思路

拥有数组b[n]后，想要对a数组中所有的数据加上c,只需要将b[1]+c即可，因为a[i]是b[i]的前缀和，a[i]=b[1]+b[1]+b[3]+……+b[n]。b[1]是所有的a[i]都拥有的子元素,将b[0]+c,那么a[n]中所有的数据都会加上c。如果想将a数组中[l,r]部分的数据全部加上c，只需要将b[l]+c,然后b[r+1]-c即可。

差分操作和前缀和一样数组下标都从1开始。

b[l]+c后，l后面的数组都会加c。r后面的数据也会被改变，要改回来就得b[r+1]-c

如何构造b[n]

构造b[n]看起来很难，其实根本就不用刻意去构造它。
如果将a数组中[l,r]部分的数据全部加上c看作一次插入操作，那么构造的过程可以看作是将a进行了n次插入操作。第一次在[1,1]的范围插入了a[1],第二次在[2,2]范围插入a[2]，第二次在[3,3]范围插入a[3]……，以此类推，进行n次插入后，那么数组a就正好是数组b的前缀和了。

例题

原题链接
输入一个长度为n的整数序列。

接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数n和m。

第二行包含n个整数，表示整数序列。

接下来m行，每行包含三个整数l，r，c，表示一个操作。

输出格式

共一行，包含n个整数，表示最终序列。

数据范围

1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000

输入样例：

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例：
3 4 5 3 4 2

java代码

package 差分;

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    static int  N = 100010;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(new BufferedInputStream(System.in));
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        //a为原数组，b为差分数组
        int[] a = new int[N];
        int[] b = new int[N];

        for (int i = 1; i <= n; i++) { 
            a[i] = scanner.nextInt();
        }
        //进行n次插入，初始化差分数组
        for(int i=1;i<=n;i++) {
            insert(b, i, i, a[i]);          
        }

        while(m-->0) {
            int l,r,c;
            l = scanner.nextInt();
            r = scanner.nextInt();
            c = scanner.nextInt();
            insert(b, l, r, c);
        }
        //经过一系列插入操作后，现在答案数组应该是b数组的前缀和，让b数组变成b的前缀和。
        //公式 b[i] = b[i-1] + b[i] 
        for(int i=1;i<=n;i++)b[i] +=b[i-1];

        for(int i=1;i<=n;i++)System.out.print(b[i]+" ");
        System.out.println();
        scanner.close();
    }

    //插入操作函数
    public static void insert(int[] a,int l,int r,int c) {
        a[l]+=c;
        a[r+1]-=c;
    }
}

层序中序建树
为什么只有最后头结点的左右指针有记录呢
参考输入 层序4163572 中序1234567
最后后序输出是164
错误的代码：

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

const int maxn=50;
int n,num=0; 
int pre[maxn],in[maxn],post[maxn];
int level[maxn],temp[maxn];

struct node{
    int data;
    node* leftchild;
    node* rightchild;
};

node* levelin_order(int level[],int levelL,int levelR,int inL,int inR) {
    if(levelL>levelR)  return NULL;
    node* root=new node;
    num=0;
    root->data=level[levelL];
    int k;
    for(k=inL;k<=inR;k++) {
        if(in[k]==root->data)
            break;
    }
    int numL=k-inL;
    int numR=inR-k;
    if(numL){
        for(int i=levelL;i<=levelR;i++) {
            for(int j=inL;j<k;j++) {
                if(in[j]==level[i])
                    temp[num++]=level[i];
            }
        }
        root->leftchild=levelin_order(temp,0,numL-1,inL,k-1);   
    }
    else root->leftchild=NULL;
    if(numR) {
        for(int i=levelL;i<=levelR;i++) {
            for(int j=k+1;j<=inR;j++) {
                if(in[j]==level[i])
                    temp[num++]=level[i];
            }
        }
        root->rightchild=levelin_order(temp,0,numR-1,k+1,inR);  
    }
    else return root->rightchild=NULL;
    return root;
}

void post_order(node* root) {
    if(root==NULL) return;
    post_order(root->leftchild);
    post_order(root->rightchild);
    printf("%d",root->data);
    if(num<n) putchar(' ');
}

int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d",&level[i]);  
    }
    for(int i=0;i<n;i++) {
        scanf("%d",&in[i]);
    }
    node* root=new node;
    root=levelin_order(level,0,n-1,0,n-1);
    num=0;
    post_order(root);
    return 0;
}

include[HTML_REMOVED]

using namespace std;

int a[10],book[10],n;
void dfs(int step)
{
int i;
if(step==n+1)
{
for(i = 1;i<=n;i)
cout << a[i] << ” “;
cout << endl;
return;
}
for(int i=1;i<=n;i)
{
if(book[i]==0)
{
a[step]=i;
book[i]=1;
dfs(step+1);
book[i]=0;
}
}
return;
}

int main()
{
cin >> n;
dfs(1);
return 0;
}

#include<iostream>

using namespace std;

const int N = 100010;

int q[N];

void quick_sort(int q[], int l, int r)
{
    if(l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j+1, r);
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    quick_sort(q, 0, n - 1);

    for(int i = 0;i < n;i++)
    {
        printf("%d ", q[i]);
    }


    return 0;
}

题目描述

在游戏《星际争霸 II》中，高阶圣堂武士作为星灵的重要 AOE 单位，在游戏的中后期发挥着重要的作用，其技能”灵能风暴“可以消耗大量的灵能对一片区域内的敌军造成毁灭性的伤害。

经常用于对抗人类的生化部队和虫族的刺蛇飞龙等低血量单位。

你控制着 n 名高阶圣堂武士，方便起见标为 1,2,⋅⋅⋅,n。

每名高阶圣堂武士需要一定的灵能来战斗，每个人有一个灵能值 ai 表示其拥有的灵能的多少（ai 非负表示这名高阶圣堂武士比在最佳状态下多余了 ai 点灵能，ai 为负则表示这名高阶圣堂武士还需要 −ai 点灵能才能到达最佳战斗状态）。

现在系统赋予了你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个 i∈[2,n−1]，若 ai≥0 则其两旁的高阶圣堂武士，也就是 i−1、i+1 这两名高阶圣堂武士会从 i 这名高阶圣堂武士这里各抽取 ai 点灵能；若 ai<0 则其两旁的高阶圣堂武士，也就是 i−1,i+1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 −ai 点灵能。

形式化来讲就是 ai−1+=ai,ai+1+=ai,ai−=2ai。

灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为 maxni=1|ai|，请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武士的不稳定度最小。

输入格式
本题包含多组询问。输入的第一行包含一个正整数 T 表示询问组数。

接下来依次输入每一组询问。

每组询问的第一行包含一个正整数 n，表示高阶圣堂武士的数量。

接下来一行包含 n 个数 a1,a2,⋅⋅⋅,an。

输出格式
输出 T 行。

每行一个整数依次表示每组询问的答案。

数据范围
1≤T≤3,3≤n≤300000,|ai|≤109,

样例

输入样例1：
3
3
5 -2 3
4
0 0 0 0
3
1 2 3
输出样例1：
3
0
3
输入样例2：
3
4
-1 -2 -3 7
4
2 3 4 -8
5
-1 -1 6 -1 -1
输出样例2：
5
7
4

贪心

a1,a2,……,an
(a[i-1],a[i],a[i+1])->(a[i-1]+a[i],-a[i],a[i+1]+a[i])
前缀和(s[i-1],s[i],s[i+1])->(s[i],s[i-1],s[i+1])

所以s[1]~s[n-1]可以任意排列，且s[1]尽可能接近0，|s[n]-s[n-1]|尽可能小，s[2]~s[n-1]如果是单调的一定最优，如果有任意位置是逆序，那么两点间的差距一定会更大（可以画个图自行体会）。令s[0]=0，且s[0],s[n]一定是不能变的
那么就是使|s[1]-s[0]|,|s[2]-s[1]|,……,|s[n]-s[n-1]|中的最大值最小

单调分两种，单调减和单调增，当s[0][HTML_REMOVED]s[n]，那么进行交换，则依然可以利用递增求解，因为只是要求距离，那么将整个图形进行左右翻转，结果是不会变的。

在s[0]到达s数组的最小值的过程中，如果一步到达，那么差值一定会很大，但是如果分几步到达，再单调上升，再一步一步下降直到s[n]，那么会更好，那么怎样一步一步的下降呢

所以隔一个向前跳是最优的

在拿数的过程中，需要各种判断，会很麻烦
将s[0]在向前跳、s[n]在向后跳的过程中，拿到的数标记为已拿，最后再将没有用过的数串起来就是中间单调的数

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

typedef long long LL;
const int N=300005;

int n;
LL s[N],a[N];
int v[N];

int main(){
    int T;cin>>T;
    while(T--){
        cin>>n;
        s[0]=0;//s[0]一定要放在前面，因为在排序后，s[0]可能变化了，会导致后面的样例出错
        for(int i=1;i<=n;i++){
            cin>>s[i];
            s[i]+=s[i-1];
        }
        LL s0=s[0],sn=s[n];//记录s[0]和s[n]的值，在排序后的序列中找到他们的位置
        if(s0>sn)  swap(s0,sn);
        sort(s,s+n+1);
        memset(v,0,sizeof(v));
        for(int i=0;i<=n;i++){
            if(s[i]==s0){
                s0=i;//记录下标
                v[i]=1;
                break;
            }
        }
        for(int i=0;i<=n;i++){
            if(s[i]==sn&&!v[i]){
                sn=i;//记录下标
                break;
            }
        }
        memset(v,0,sizeof(v));//初始所有都没有拿过
        int l=0,r=n;//把s数组整合为应有的顺序
        for(int i=s0;i>=0;i-=2){
            a[l++]=s[i];
            v[i]=1;
        }
        for(int i=sn;i<=n;i+=2){
            a[r--]=s[i];
            v[i]=1;
        }
        for(int i=0;i<=n;i++){
            if(!v[i]){
                a[l++]=s[i];
            }
        }
        LL ans=0;
        for(int i=1;i<=n;i++)  ans=max(ans,abs(a[i]-a[i-1]));
        cout<<ans<<endl;
    }
    return 0;
}

#include <iostream>
#include <map>

#define x first
#define y second
typedef long long LL;
using namespace std;

long long n, b;
map<LL, LL> m;
void resolve(long long n){
    for(LL i = 2; i * i <= n; ++ i){
        if(n % i == 0){
            while(n % i == 0){
                n /= i;
                m[i] ++;
            }
        }
    }
    if(n != 1){
        m[n] ++;
    }
}

int main(){
    cin >> n >> b;

    resolve(b);

    LL ans = 1LL << 62;
    for(auto factor : m){
        LL x = factor.x;
        LL y = factor.y;
        // cout << x << " " << y << endl; 
        LL s = 0;
        for(LL j = n; j; j /= x){
            s += j / x;
        }
        ans = min(ans, s / y);
    }
    cout << ans << endl;
    return 0;
}

什么是前缀和

原数组: a[1], a[2], a[3], a[4], a[5], …, a[n]
前缀和 S[i]为数组的前i项和
前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i]

s[0] = 0
s[1] = a[1]
s[2] = a[1] + a[2]
s[i] = a[1] + a[2] + a[3] +……+ a[i] 
s[i] = s[i-1] + a[i]

注意: 原数组的下标一定要从 1开始, 避免进行下标的转换

前缀和的作用

快速求出元素组中某段区间的和

一维数组前缀和

利用S[i]=S[i-1]+a[i]
for循环求出 每个S[i] (将 S[0] 定义为 0, 避免下标的转换)
求[l, r]中的和, 即为 S[r] - S[l-1]

公式

s[i] = s[i-1] + a[i]

例题1

题目链接
输入一个长度为n的整数序列。

接下来再输入m个询问，每个询问输入一对l, r。

对于每个询问，输出原序列中从第l个数到第r个数的和。

输入格式

第一行包含两个整数n和m。

第二行包含n个整数，表示整数数列。

接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。

输出格式

共m行，每行输出一个询问的结果。

数据范围

1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000

输入样例：

5 3
2 1 3 6 4
1 2
1 3
2 4
````
### 输出样例：
``` java
3
6
10

java代码

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(new BufferedInputStream(System.in));
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int a[] = new int[n+1];
        int s[] = new int[n+1];

        for(int i= 1;i<=n;i++) a[i] = scanner.nextInt();
        //直接利用公式将前缀和保存在数组`s[n]`里面
        for (int i = 1; i <= n; i++) s[i] = s[i-1] + a[i];

        while(m-->0) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            System.out.println(s[r]-s[l-1]);
        }
        scanner.close();
    }
}

二维数组前缀项和

s[i][j]以及(x1,y1),(x2,y2)子矩阵代表的含义如图

公式

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]
上图中(x1,y2)(x2,y2)子矩阵部分求和公式为：
s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]

例题2

输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数n，m，q。

接下来n行，每行包含m个整数，表示整数矩阵。

接下来q行，每行包含四个整数x1, y1, x2, y2，表示一组询问。

输出格式

共q行，每行输出一个询问的结果。

数据范围

1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,

−1000≤矩阵内元素的值≤1000

输入样例：

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例：

17
27
21

java代码

import java.util.Scanner;

public class Main3 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int q = scanner.nextInt();
        int[][] a = new int[n + 1][m + 1];
        int[][] s = new int[n + 1][m + 1];

        // 读入原数组数据,注意所以的下标都从1开始
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                a[i][j] = scanner.nextInt();

        // 利用公式一初始化前缀和数组,注意所以的下标都从1开始
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

        while (q-- > 0) {
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();

            // 利用公式二输出答案
            System.out.println(s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);

        }

        scanner.close();
    }

}

/**
1. dfs: 首先收集所有起点, 对所有起点进行dfs
2. 搜索顺序: 判断4个方向合法并向下扩展, 直到最深
3. 搜索状态: index,  || board, word, visit
4. 剪枝: ~
*/

class Solution {
    public boolean exist(char[][] board, String word) {
        List<Integer> roots = new ArrayList<>();
        char start = word.charAt(0);
        int n = board.length, m = board[0].length;
        boolean[][] visit = new boolean[n][m];
        for (int i = 0 ; i < n ; i ++){
            for (int j = 0; j < m ; j ++){
                if (board[i][j] != start) continue;
                for (int k = 0 ; k < n ; k++) Arrays.fill(visit[k], false);
                if (dfs(i, j, 0, visit, board, word)) return true;
            }
        }
        return false;
    }

    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public  boolean dfs(int x ,int y, int depth, boolean[][] visit, char[][] board, String word){
        if (depth == word.length() - 1) return true;
        visit[x][y] = true;
        int n =  board.length ,m =  board[0].length;
        for (int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny <m && !visit[nx][ny] && board[nx][ny] == word.charAt(depth+1)){
                if (dfs(nx, ny, depth + 1, visit, board, word)) return true;
            }
        }
        visit[x][y] = false;
        return false;
    }
}

Python代码

其实就是二叉树变成了多叉树，写法跟二叉树完全一模一样！！

import sys
class TreeNode():
    def __init__(self):
        self.next = [None]*26
        self.val = 0

table = {'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'g':6,'h':7,'i':8,'j':9,
'k':10,'l':11,'m':12,'n':13,'o':14,'p':15,'q':16,'r':17,'s':18,'t':19,'u':20,'v':21,'w':22,'x':23,'y':24,'z':25}
root = TreeNode()
def Add(root,string):
    # string分配完则截止
    if len(string) == 0:
        root.val+=1
        return
    if root.next[table[string[0]]] == None:
        # 需要创建
        root.next[table[string[0]]] = TreeNode()
        Add(root.next[table[string[0]]],string[1:])
    else:
        # 已经存在
        Add(root.next[table[string[0]]],string[1:])

def Query(root,string):
    if len(string) == 0:
        return root.val
    if root.next[table[string[0]]] == None:
        return 0
    else:
        return Query(root.next[table[string[0]]],string[1:])

n = int(input().strip())
for _ in range(n):
    op,string = list(input().strip().split())
    if op == 'I':
        Add(root,string)
    elif op == 'Q':
        print(Query(root,string))