Description

奶牛想证明他们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对N头奶牛进行了面试，确定了每头奶牛的智商和情商。 贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值.

Input

第一行：一个整数N，表示奶牛的数量， 1 ≤ N ≤ 100 第二行到第N + 1行：第i + 1行有两个用空格分开的整数：Si和Fi，分别表示第i头奶牛的智商和情商， -1000 ≤ Si ≤ 1000， -1000 ≤ Fi ≤ 1000

Output

第一行：单个整数，表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览，如 果这样应该输出0

Sample Input

5
-5 7
8 -6
6 -3
2 1
-8 -5

Sample Output

8

Hint

选择 1， 3， 4 号奶牛，此时智商和为-5 + 6 + 2 = 3，情商和为7 - 3 + 1 = 5。加 入 2 号奶牛可使总和提升到10，不过由于情商和变成负的了，所以是不允许的.

题解

每只牛有两种选择：参加会展和不参加会展。我们要求在智商一定的情况下情商的最大值，这其实就是01背包的模板。状态转移方程的推导如下：
第 $i$ 只奶牛不参加会展： $dp[i][j]=dp[i-1][j]$
第 $i$ 只奶牛参加会展： $dp[i][j]=dp[i-1][j-a[i].iq]+a[i].eq$
加上决策，选取上面两种情况的最大值： $dp[i][j]=\max(dp[i-1][j], dp[i-1][j-a[i].iq]+a[i].eq)$

有一些奶牛智商居然是负的，这样导致 $j-a[i].iq$ 比 $j$ 大，可以在动规的时候判断一下，如果这只奶牛很傻，那么正着dp，否则反着dp。

因为 $a[i].iq$ 和 $a[i].eq$ 都有可能是负数，所以会导致数组越界。这时，我们可以把 $dp$ 数组向右移动 $400000$ 位。数组的改变意味着我们状态的定义也会发生改变：
$dp[j]$ 表示在奶牛智商之和为 $j-400000$ 时，情商的最大值。

但是在最后求答案时，不要忘记我们求得其实是 $dp[j]+j-400000$的最大值。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
typedef pair<int,int> PII;
typedef long long LL;
const int INF=0x3f3f3f3f;

int f[1000*400*2+10];
int a[410];
int b[410];
int n;

int main()
{
    cin>>n;
    int base=1000*n;
    int upper=base*2;

    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];

    memset(f,-0x3f,sizeof f);
    f[base]=0;

    for(int i=1;i<=n;i++)
        if(a[i] >= 0)
        {
            for(int j=upper;j>=a[i];j--)
                f[j]=max(f[j],f[j-a[i]]+b[i]);
        }
        else
        {
            for(int j=0;j-a[i]<=upper;j++)
                f[j]=max(f[j],f[j-a[i]]+b[i]);
        }

    int res=-upper;
    for(int i=base;i<=upper;i++)
        if(f[i]>0)
            res=max(res,f[i]+i-base);

    if(res < 0) res=0;
    cout<<res<<endl;
   // system("pause");
}

题目描述

y总的这道题解的的太巧妙了，看了好长时间脑壳疼，虽然能做出来，但思路依然不通畅，我等凡人还是理解力差了点Q.Q
现在给出我的解法，希望能帮到在这里感到困惑的同学

思考过程：
首先preorder的第一个节点和postorder的最后一个节点一定是根节点root。preorder的第二个节点preorder[2]要么是左子树根节点，要么是右子树根节点（当左子树不存在）；postorder的倒数第二个节点postorder[-2]要么是右子树根节点，要么是左子树根节点（当右子树不存在）。

1. 如果preorder[2]!=postorder[-2]，那就说明preorder[2]和postorder[-2]所代表地根节点不是同一棵树，因此存在左子树和右子树，从而preorder[2]是左子树根节点，postorder[-2]是右子树根节点。
2. 如果preorder[2]==postorder[-2]，那么就说明只存在一边的子树，那么这个时候你思考一下，其实是只有左子树也可以，只有右子树也可以。所以，存在不同的树的根源就在于这里。

那么我们就可以递归地去判断，只要存在一次preorder[2] == postorder[-2]，就说明有多个解，这个时候我们只构造左子树（或右子树）就行了。


所以其实我们可以看出一个规律：只有满二叉树才能通过前序遍历和后序遍历唯一确定

算法思路：
先通过前序遍历和后序遍历的序列来构造二叉树，如果存在在不同的选择，默认选择构造左子树。最后进行中序遍历

样例

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

const int N = 40;
int l[N],r[N];  //l[i],r[i]代表i号节点的左右儿子
int post[N], pre[N]; //后续遍历和前序遍历的序列
bool is_only = true;  //全局变量，是否为唯一二叉树的标志
int in[N], cnt = 0;

//根据pre[l1,r1], post[l2,r2]创建二叉树节点，并分配左右儿子指针
int build(int l1, int r1, int l2, int r2)
{
    int root = pre[l1];

    if(l1 == r1) return root;
    //根据pre[l1+1] 和 post[r2-1]来判断答案是否为1
    if(pre[l1+1] == post[r2-1]) //说明答案不唯一，我们直接认为右儿子不存在即可
        l[root] = build(l1+1, r1, l2, r2-1), is_only = false;
    else  //不相同，那么说明 pre[l1+1]为左儿子的根节点， post[r2-1]为右儿子根节点
    {
        int lpre, rpost; //lpre代表前序序列中左子树的右边界，rpost代表后序序列中右子树的左边界
        for(lpre = l1+1;lpre<=r1;lpre++) if(pre[lpre] == post[r2-1]) break;
        for(rpost = r2-1;rpost>=l2;rpost--) if(post[rpost] == pre[l1+1]) break;
        lpre--, rpost++;
        l[root] = build(l1+1, lpre, l2, rpost-1);
        r[root] = build(lpre+1, r1, rpost, r2-1);
    }

    return root;
}

//中序遍历
void inorder(int root)
{
    if(l[root] != -1) inorder(l[root]);
    in[cnt++] = root;
    if(r[root] != -1) inorder(r[root]);
}

int main()
{
    //用-1来来代表儿子节点为空
    memset(l,-1,sizeof(l));
    memset(r,-1,sizeof(r));
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> pre[i];
    for(int i=0;i<n;i++)
        cin >> post[i];

    //根据前序遍历和后序遍历创建二叉树
    int root = build(0,n-1,0,n-1);

    if(is_only) puts("Yes");
    else puts("No");
    inorder(root);

    cout << in[0];
    for(int i=1;i<n;i++)
        cout << " " <<in[i];
}

代码：

int a[100000];
class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {

        for(int i=0;i<target.size();i++){
            a[target[i]]++;
        }
        for(int i=0;i<arr.size();i++){
            a[arr[i]]--;
        }
        for(int i=1;i<=1001;i++){
            if(a[i]!=0) return false;
        }
        return true;
    }
};

题目：https://leetcode-cn.com/problems/make-two-arrays-equal-by-reversing-sub-arrays/submissions/

#1到n中与n互质的个数
#欧拉公式 = n(1-1/p1)(1-1/p2)...(1-1/pk)
#容质原理
#1 从1~n中去掉p1,p2,...pk的所有倍数
#2 加上pi*pj的倍数
#3 减去pi*pj*pk的倍数
#...
#等于欧拉函数展开


if __name__ == '__main__':

    n = int(input())

    for i in range(n):
        x = int(input())
        res = x

        #分解质因数
        i = 2
        while i <= x//i:
            if x % i == 0:
                res = res // i * (i - 1)
                while  x % i == 0: x //= i
            i+=1

        if  x > 1 : res = res // x * (x - 1) 

        print(res)

求y总讲的建图的视频，谢谢各位了。