发表于 | 分类于

没啥讲的，纯模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void gauss()
{
    int n;
    cin>>n;
    vector<vector<double>> a(n,vector<double>(n+1));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=n;j++)//多出一维增广矩阵
        {
            cin>>a[i][j];
        }
	}
    for(int i=0;i<n;i++)
    {
        int mx=i;
        for(int j=i+1;j<n;j++)//找出第i列中最大元素
        {
            if(fabs(a[j][i])>fabs(a[mx][i]))
            {
                mx=j;
            }
		}
        swap(a[mx],a[j]);//将最大元素所在行换到第i行
        if(fabs(a[i][i])<1e-9)//该列元素都为0的情况
        {
            cout<<"No ans!"
        }
        for(int j=0;j<n;j++)
        {
            if(j!=i)
            {
                double tmp=a[j][i]/a[i][i];
                for(int k=i;k<=n;k++)
                {
                    a[j][k]-=a[i][k]*tmp;
                }
            }
        }
    }
}

莫名奇妙上面一个写挂了。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
void gauss()
{
    ll n;
    cin >> n;
    vector<vector<double>> a(n + 1, vector<double>(n + 1));
    vector<vector<double>> b(n + 1, vector<double>(n + 1));
    for (ll i = 0; i <= n; i++)
    {
        for (ll j = 0; j < n; j++)
        {
            cin >> b[i][j]; //第i个点的第j维
        }
    }
    for (ll i = 0; i <n; i++)
    {
        a[i][n] = 0;
        for (ll j = 0; j < n; j++)
        {
            a[i][j] = -2 * (b[i][j] - b[(i + 1) % (n + 1)][j]);
            a[i][n] += b[(i + 1) % (n + 1)][j] * b[(i + 1) % (n + 1)][j];
            a[i][n] -= b[i][j] * b[i][j];
        }
    }
    for (ll i = 0; i < n;i++)
    {
        for (ll j = i; j < n;j++)
        {
            if(fabs(a[j][i])>1e-8)
            {
                swap(a[i], a[j]);//使a[i][i]>1e-8
            }
        }
        for (ll j = 0; j < n;j++)
        {
            if(i==j)
            {
                continue;
            }
            double rate = a[j][i] / a[i][i];
            for (ll k = i; k <= n;k++)
            {
                a[j][k] -= a[i][k] * rate;
            }
        }
    }
    for (ll i = 0; i < n;i++)
    {
        cout<<a[i][n]/a[i][i]<<" ";
    }
    cout << "\n";
}

题面:https://www.acwing.com/problem/content/209/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
void gauss()
{
    vector<vector<ll>> a(m + 1, vector<ll>(n + 2, 0));
    // vector<ll> c(n + 1);
    ll ans = 0;
    ll num = 0;
    string str1, str2;
    for (ll i = 1; i <= m; i++)
    {
        cin >> k;
        cin >> str1 >> str2;
        a[i][n + 1] = (mp[str2] - mp[str1] + 8) % 7;
        for (ll j = 1; j <= k; j++)
        {
            cin >> num;
            a[i][num] = (a[i][num] + 1) % 7;
        }
    }
    /*for (ll i = 1; i <= m; i++)
    {
        for (ll j = 1; j <= n + 1; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }*/
    // sort(a.begin() + 1, a.begin() + n + 1,cmp);
    ll row = 1, col = 1;
    //vector<ll> pos;
    for (row = 1, col = 1;row<=m&&col<=n; row++,col++)
    {
        for (ll j = row; j <= m; j++)
        {
            if (a[row][col] == 0 && a[j][col] != 0)
            {
                swap(a[row], a[j]);
                break;
            }
        }
        if (a[row][col] == 0)
        {
            row--;
            ans = 1;//出现自由元
            continue;
        }
        //pos.push_back(col);
        for (ll j = 1; j <= m; j++)
        {
            if (row == j || a[j][col] == 0)
            {
                continue;
            }
            // double rate = a[j][i] / a[i][i];
            ll rate1 = a[j][col] / gcd(a[j][col], a[row][col]);
            ll rate2 = a[row][col] / gcd(a[j][col], a[row][col]);
            for (ll k = 1; k <= n + 1; k++)
            {
                a[j][k] = (a[j][k] * rate2 - a[row][k] * rate1)%7;
            }
            
        }
    }
    for (ll i = 1; i <= m; i++)
    {
        ll flag = 0;
        for (ll j = 1; j <= n; j++)
        {
            if(a[i][j]!=0)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0 && a[i][n + 1]%7!= 0)
        {
            ans = 2;
        }
    }
    if(ans==0&&n>m)
    {
        ans = 1;
    }
    /*for (ll i = 1; i <= m; i++)
    {
        for (ll j = 1; j <= n + 1; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }*/
    if (ans == 2)
    {
        cout << "Inconsistent data.\n";
    }
    else if (ans == 1)
    {
        cout << "Multiple solutions.\n";
    }
    else
    {
        for (ll i = 1; i <= n; i++)
        {
            ll ret = (quick(a[i][i]%7, 5) * a[i][n + 1] % 7 + 7) % 7;
            //ret = (ret + 7) % 7 + 3;
            if(ret<3)
            {
                ret = ret + 7;
            }
            cout << ret << " ";
        }
        cout << "\n";
    }
    // cout << num << " " << ans << "\n";
}

该模板适用于整数mod7方程组，且使用了row、col两个变量来分辨无解、多解的情况

题面:https://www.acwing.com/problem/content/description/229/

发表于 | 分类于

即状态转移关系以树形结构为基础的dp

例题1：https://www.luogu.com.cn/problem/UVA1292

以最少的点覆盖整颗树，则dp[i][1]表示覆盖以i为根的树，选择了i节点的最少节点数，dp[i][0]则表示没选择i节点的最少节点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int u,int fa)
{
    dp[u][1]=1;
    dp[u][0]=0;
    for(int i=0;i<g[u].size();i++)
    {
        if(g[u][i]!=fa)
        {
            int v=g[u][i];
            dfs(g[u][i]);
            dp[u][0]+=dp[v][1];//不选u则v必选
            dp[u][1]+=min(dp[v][1],dp[v][0]);//选u时v可选可不选
		}
	}
}

例题2：https://www.luogu.com.cn/problem/P2014

可将每棵子树看作一个容量为N的背包问题，即树形背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int u)
{
    dp[u][0]=0;
    dp[u][1]=val[u];
    for(int i=0;i<g[u].size();i++)
    {
        dfs(g[u][i]);
        int v=g[u][i];
        for(int j=N+1;j>1;j--)//分配给u的总节点数,注意需要从大到小更新
        {
            for(int k=0;k<j;k++)//枚举分配给v的
            {
                dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]);
            }
        }
    }
}

注意通过设0节点将森林变成树，0必选，故背包容量为N+1

时间复杂度为

易知在枚举背包容量时，有许多容量是不需要枚举的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs(int u)
{
    sz[u]=1;
    dp[u][0]=0;
    dp[u][1]=val[u];
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        dfs(v);
        for(ll j=min(N+1,sz[u]+sz[v]);j>1;j--)
        {
            for(ll k=max(0,j-sz[u]);k<=min(j,sz[v]);k++)
            {
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
            }
        }
        sz[u]+=sz[v];
    }
}

优化后时间复杂度转为

大致计算如下：考虑以u为根节点的子树，其子节点为v1、v2….

则合并时t=size[v1]*size[v1]+(size[v1]+size[v2])*size[v2]+…

t=size[u]*size[u]

其子节点合并复杂度为size[v]*size[v]，远小于t，递归下去，复杂度为

感觉还是不太理解orz

参考：

https://ouuan.github.io/post/%E6%A0%91%E4%B8%8A%E8%83%8C%E5%8C%85%E7%9A%84%E4%B8%8A%E4%B8%8B%E7%95%8C%E4%BC%98%E5%8C%96/