作者：w703710691d

Codeforces 847J Students Initiation 二分答案 最大流

Codeforce 847J Students Initiation

题意

给一个包含$n$($n \leq 5000$)个点的无向图，边的条数$m \leq 5000$，没有重边自环。现在给每条边一个方向，问每个点的出度的最大值，最小为多少。输出这个最小值，并输出方案。

思路&建图

  1. 看到最大值最小，最小值最大，首先想到炸天哥猜想：二分！！
  2. 二分这个最大值$mid$，检验这个猜测值是否满足要求
  3. 从源点相这$n$个点引一条边，容量为$mid$。
  4. 对于第$i$条边来说，其编号为$n+i$，从其两个断点分别引一条边到这个点，容量为$1$。再从这个点到汇点连一条边，容量为$1$。
  5. 跑最大流，如果最大流和边的数目相同，即这个猜测值可行。此时，对于每一条边对应的点来说，这条边的方向就应该是从[流量来的那个点]到[没有流量流过来的那个点]。

代码

C++
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
const int maxm = 1e6;
struct EDGE
{
    int to, next, flow;
    EDGE(int to = 0, int next = 0, int flow = 0) : to(to), next(next), flow(flow) {}
} edge[maxm];
int head[maxn], edgecnt, maxNodeNum;
void init()
{
    memset(head, -1, sizeof(head));
    edgecnt = 0;
    maxNodeNum = 0;
}
void AddEdge(int s, int t, int c)
{
    edge[edgecnt] = EDGE(t, head[s], c);
    head[s] = edgecnt++;
    edge[edgecnt] = EDGE(s, head[t], 0);
    head[t] = edgecnt++;
    maxNodeNum = max(maxNodeNum, max(s, t));
}
int layer[maxn];
int p[maxn];
bool GetLayer(int st, int en)
{
    memset(layer, 0, sizeof(int) * (maxNodeNum + 1));
    layer[st] = 1;
    queue<int>q;
    q.push(st);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = head[u]; ~i; i = edge[i].next)
        {
            if(edge[i].flow == 0)
                continue;
            int v = edge[i].to;
            if(layer[v])
                continue;
            layer[v] = layer[u] + 1;
            q.push(v);
        }
    }
    return layer[en];
}
int dfsFlow(int u, int en, int f)
{
    int ret = 0;
    if(u == en)
        return f;
    if(layer[u] >= layer[en])
        return 0;
    for(; ~p[u]; p[u] = edge[p[u]].next)
    {
        if(edge[p[u]].flow == 0)
            continue;
        int v = edge[p[u]].to;
        if(layer[v] != layer[u] + 1)
            continue;
        int temp = dfsFlow(v, en, min(f, edge[p[u]].flow));
        ret += temp;
        f -= temp;
        edge[p[u]].flow -= temp;
        edge[p[u] ^ 1].flow += temp;
        if(f == 0)
            break;
    }
    return ret;
}
int dinic(int st, int en)
{
    int ans = 0;
    while(GetLayer(st, en))
    {
        memcpy(p, head, sizeof(int) * (maxNodeNum + 1));
        ans += dfsFlow(st, en, INT_MAX);
    }
    return ans;
}
pair<int, int> E[maxn];
int n, m;
bool check(int mid)
{
    init();
    for(int i = 1; i <= n; i++)
        AddEdge(0, i, mid);
    for(int i = 1; i <= m; i++)
    {
        AddEdge(E[i].first, n + i, 1);
        AddEdge(E[i].second, n + i, 1);
    }
    int en = n + m + 1;
    for(int i = n + 1; i < en; i++)
        AddEdge(i, en, 1);
    int ret = dinic(0, en);
    return ret == m;
}
int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
        scanf("%d %d", &E[i].first, &E[i].second);
    int L = 0, R = m;
    while(L < R)
    {
        int mid = L + R >> 1;
        if(check(mid))
            R = mid;
        else
            L = mid + 1;
    }
    check(L);
    printf("%d\n", L);
    for(int i = 1; i <= n; i++)
    {
        for(int j = head[i]; ~j; j = edge[j].next)
        {
            if(j & 1)
                continue;
            if(edge[j].flow)
                continue;
            int eid = edge[j].to - n;
            int v;
            if(E[eid].first == i)
                v = E[eid].second;
            else
                v = E[eid].first;
            printf("%d %d\n", i, v);
        }
    }
    return 0;
}

 

 

HDU 6214 Smallest Minimum Cut 最小割的割边的数目最少

Smallest Minimum Cut

题意

给一个有向的网络图，每条边有一定的容量$w_i$，现在以$1$点为源点，$n$点为汇点。求一组最小割的割边，使边的数目最少，输出最少数目。

建图&思路

直接按照原网络建图，只是边的容量改变为$10000 * w_i +1$，其中边的条数$m<10000$。这样跑最大流（最小割）后，假设最大流为$flow$，那么$flow / 10000$就是原始网络的最大流（最小割），$flow \mod 10000$就是最小割的最少边的条数。

代码

C++
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 300;
const int maxm = 4000;
struct EDGE
{
    int to, next, flow;
    EDGE(int to = 0, int next = 0, int flow = 0): to(to), next(next), flow(flow) {}
} edge[maxm];
int head[maxn], edgecnt, maxNodeNum;
void init()
{
    memset(head, -1, sizeof(head));
    edgecnt = 0;
    maxNodeNum = 0;
}
void AddEdge(int s, int t, int c)
{
    edge[edgecnt] = EDGE(t, head[s], c);
    head[s] = edgecnt++;
    edge[edgecnt] = EDGE(s, head[t], 0);
    head[t] = edgecnt++;
    maxNodeNum = max(maxNodeNum, max(s, t));
}
int layer[maxn];
int p[maxn];
bool GetLayer(int st, int en)
{
    memset(layer, 0, sizeof(int) * (maxNodeNum + 1));
    layer[st] = 1;
    queue<int>q;
    q.push(st);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = head[u]; ~i; i = edge[i].next)
        {
            if(edge[i].flow == 0)
                continue;
            int v = edge[i].to;
            if(layer[v])
                continue;
            layer[v] = layer[u] + 1;
            q.push(v);
        }
    }
    return layer[en];
}
int dfsFlow(int u, int en, int f)
{
    int ret = 0;
    if(u == en)
        return f;
    if(layer[u] >= layer[en])
        return 0;
    for(; ~p[u]; p[u] = edge[p[u]].next)
    {
        if(edge[p[u]].flow == 0)
            continue;
        int v = edge[p[u]].to;
        if(layer[v] != layer[u] + 1)
            continue;
        int temp = dfsFlow(v, en, min(f, edge[p[u]].flow));
        ret += temp;
        f -= temp;
        edge[p[u]].flow -= temp;
        edge[p[u] ^ 1].flow += temp;
        if(f == 0)
            break;
    }
    return ret;
}
int dinic(int st, int en)
{
    int ans = 0;
    while(GetLayer(st, en))
    {
        memcpy(p, head, sizeof(int) * (maxNodeNum + 1));
        ans += dfsFlow(st, en, INT_MAX);
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        init();
        int n, m;
        scanf("%d %d", &n, &m);
        int s, t;
        scanf("%d %d", &s, &t);
        while(m--)
        {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            AddEdge(u, v, w * 10000 + 1);
        }
        int ret = dinic(s, t) % 10000;
        printf("%d\n", ret);
    }
    return 0;
}

 

计蒜客 Our Journey of Dalian Ends 费用流找最短路

Our Journey of Dalian Ends

题意

给一个无向图，有边权，每个点用地名字符串表示。现在要从大连出发到达西安，并且必须经过上海，且给个点只能经过一次，问最短路径。

建图&思路

  1. 可以认为是找两条路径，起点都是上海，分别到达西安和大连，且经过的点不能重复，求路径和的最小长度。
  2. 将每个点拆点，拆分为入点和出点，入点向出点连一条边，容量为$1$，费用为$0$，代表这个点只能经过一次。
  3. 对于原图上的点，从一个城市的出点连一条边，到另一个城市所代表的点的入点。容量为$1$，费用为这条边的边权。反过来也需要连一条边，代表双向可行。
  4. 从源点向上海的出点连一条边，容量为$2$，费用为$0$，代表需要找到两条路径。
  5. 从西安和大连的出点，分别引一条边到汇点，容量为$1$，费用为$0$，代表只能是以这两个点为终点。
  6. 跑费用流，如果流量为2，那么费用就是两条路径的最短长度。
  7. 当然，如果输入数据中没有这三个城市，直接不行啊！

代码

C++
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<bits/stdc++.h>
const int maxn = 100005;
#define inf 0x3FFFFFFF
using namespace std;
struct node
{
int st;
int en;
int flow, cost;
int next;
} E[1001000];
int num;
int p[maxn];
void init()
{
memset(p, -1, sizeof p);
num = 0;
}
void add(int st, int en, int flow, int cost)
{
E[num].st = st;
E[num].en = en;
E[num].flow = flow;
E[num].cost = cost;
E[num].next = p[st];
p[st] = num++;
E[num].st = en;
E[num].en = st;
E[num].flow = 0;
E[num].cost = -cost;
E[num].next = p[en];
p[en] = num++;
}
int n;
 
int pre[maxn];
int dis[maxn];
bool fg[maxn];
 
 
bool spfa(int st, int en)
{
for (int i = 0; i <= en; i++)
fg[i] = 0, dis[i] = inf, pre[i] = -1;
queue<int>q;
q.push(st);
fg[st] = 1;
dis[st] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
fg[u] = 0;
for (int i = p[u]; i + 1; i = E[i].next)
{
int v = E[i].en;
if (E[i].flow && dis[v] > dis[u] + E[i].cost)
{
dis[v] = dis[u] + E[i].cost;
pre[v] = i;
if (!fg[v])
{
fg[v] = 1;
q.push(v);
}
}
}
}
if (dis[en] < inf)
return 1;
return 0;
}
pair<int, int> solve(int st, int en)
{
int ans = 0;
int f = 0;
while (spfa(st, en))
{
int d = inf;
for (int i = pre[en]; i + 1; i = pre[E[i].st])
d = min(d, E[i].flow);
for (int i = pre[en]; i + 1; i = pre[E[i].st])
{
E[i].flow -= d;
E[i ^ 1].flow += d;
ans += d * E[i].cost;
}
f += d;
}
return make_pair(ans, f);
}
char from[maxn], to[maxn];
vector<pair<int, int> > vec[maxn];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
for (int i = 0; i < maxn; i++)
vec[i].clear();
int cnt = 0;
init();
        unordered_map<string, int> mp;
int m;
scanf("%d",&m);
while (m--)
{
int len;
scanf("%s %s %d", from, to, &len);
if (mp[from] == 0)
mp[from] = ++cnt;
if (mp[to] == 0)
mp[to] = ++cnt;
int u = mp[from];
int v = mp[to];
vec[u].emplace_back(v, len);
vec[v].emplace_back(u, len);
}
if(!mp.count("Dalian") || !mp.count("Shanghai") || !mp.count("Xian"))
        {
            puts("-1");
            continue;
        }
for (int u = 1; u <= cnt; u++)
{
    if(u != mp["Shanghai"])
                add(u, cnt + u, 1, 0);
for (auto &p : vec[u])
{
int v = p.first;
int len = p.second;
add(cnt + u, v, 1, len);
}
}
add(0, mp["Shanghai"] + cnt, 2, 0);
add(mp["Dalian"] + cnt, cnt + cnt + 1, 1, 0);
add(mp["Xian"] + cnt, cnt + cnt + 1, 1, 0);
pair<int, int> ret = solve(0, cnt + cnt + 1);
if (ret.second != 2)
{
puts("-1");
}
else
{
printf("%d\n", ret.first);
}
}
return 0;
}

 

 

Codeforces 546E Soldier and Traveling 最大流找可行方案

Codeforces 546E

题意

一个国家有$n$个城市，由$m$条双向边连接。现在，每个城市有$a_i$个士兵。现在每个士兵可以沿着一条边，走到相邻的城市，并且只能走一次，或者不走，留在原来的城市。问能否达到每个城市分别有$b_i$的士兵。切每条道路有一个上限，通过的士兵的个数不能超过这个上限。

  • 如果可以，输出"YES"。并输出方案，用矩阵$A_{ij}$表示从$i$城市走到$j$城市的士兵的个数。
  • 如果不可以，输出"NO"。

建图&思路

  1. 左边$n$个点，从源点往分别这$n$个点引一条边，容量为$a_i$。
  2. 右边$n$个点，从这个$n$个点分别往汇点引一条边，容量为$b_i$。
  3. 对于每一个城市$i$来说，从左边的第$i$个点向右边的第$i$个点引一条边，容量为$INF$，表示允许驻留。
  4. 对于每一条路来说，它的两个断点分别为$st,en$，那么需要从左边的第$st$个点引一条边到右边的第$en$个点，容量为这条路的上限。同时，从左边的第$en$个点引一条边到右边的第$st$个点，容量为这条路的上限。表示这两个城市之间的士兵可以相互移动，数量的上限不超过路的上限。
  5. 跑最大流，得到最大流量为$flow$，如果$flow$和士兵的总数相同，那么就有可行方案。否则没有。
  6. 对于每一个左边的点，枚举每一条向右边连的边，那么从这个点对应的城市到所连的点的城市所移动的士兵的个数，就是这条边所流过的流量，即这条边反向边的残余流量。

代码

C++
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
#define INFF 0x3fffffff
#define MM 100010
#define NN 5100
struct node
{
    int st, en, flow;
    int next;
} E[MM];
int num;
int p[NN];
void init()
{
    memset(p, -1, sizeof(p));
    num = 0;
}
void add(int st, int en, int flow)
{
    E[num].st = st;
    E[num].en = en;
    E[num].flow = flow;
    E[num].next = p[st];
    p[st] = num++;
    E[num].st = en;
    E[num].en = st;
    E[num].flow = 0;
    E[num].next = p[en];
    p[en] = num++;
}
int T;
int vdis[NN];//到汇点的距离为i（即是同一层）个数为多少
int dis[NN];//i点到汇点距离
int Find(int u, int st, int en, int f)
{
    //f为起点来的流量
    if (u == en)
        return f;//如果点相同返回起点来的流量
    int left = f; //剩余流量
    int tmp = T; //T是到汇点无限远距离
    for (int i = p[u]; i + 1; i = E[i].next)
    {
        int v = E[i].en;
        int flow = E[i].flow;
        if (flow) //如果剩余容量大于0
        {
            if (dis[v] + 1 == dis[u])
            {
                //u->v  倒着推
                int d = min(left, flow); //这条边能过去的最大流量
                d = Find(v, st, en, d); //当前最大流量传向上一条边
                left -= d; //剩余多少
                E[i].flow -= d; //这条边的剩余容量
                E[i ^ 1].flow += d; //反向边的剩余容量
                if (dis[st] >= T + 1) //如果起点不能到汇点，即是距离大于等于无穷
                    return f - left; //返回流了多少流量
                if (!left) //如果剩余容量为0
                    break;
            }
            if (dis[v] < tmp) //下一条边的到汇点距离
                tmp = dis[v];
        }
    }
    if (left == f)
    {
        vdis[dis[u]]--;
        if (vdis[dis[u]] == 0)
            dis[st] = T + 1; //这一层没有点了
        dis[u] = tmp + 1;
        vdis[dis[u]]++;
    }
    return f - left;
}
int isap(int st, int en, int flow)
{
    memset(vdis, 0, sizeof(vdis));
    memset(dis, 0, sizeof(dis));
    vdis[0] = T + 1;
    int ans = 0;
    while (dis[st] <= T)
    {
        int tmp = Find(st, st, en, flow);
        ans += tmp;
        flow -= tmp;
        if (!flow)
            return ans;
    }
    return ans;
}
int A[205][205];
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    init();
    T = 2 * n + 5;
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        sum += x;
        add(0, i, x);
    }
    int sum2 = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        sum2 += x;
        add(i + n, n + n + 1, x);
        add(i, n + i, INFF);
    }
    if (sum2 != sum)
    {
        puts("NO");
        return 0;
    }
    for (int i = 0; i < m; i++)
    {
        int st, en;
        scanf("%d %d", &st, &en);
        add(st, en + n, INFF);
        add(en, st + n, INFF);
    }
    int t = isap(0, 1 + n + n, INFF);
    if (t != sum) printf("NO\n");
    else
    {
        puts("YES");
        memset(A, 0, sizeof(A));
        for (int i = 1; i <= n; i++)
        {
            for (int j = p[i]; ~j; j = E[j].next)
                A[i][E[j].en - n] = E[j ^ 1].flow;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++) printf("%d ", A[i][j]);
            printf("\n");
        }
    }
    return 0;
}

注释

这个代码是2015年写的isap模板，所以不怎么好看。

Codeforces 863F 费用流求最小花费方案

Codeforces 863F

题意

  • 构造一个长度为$n$的序列$a_i$（$1 \leq n \leq 50, 1 \leq a_i \leq n$），需要满足$q$个条件（$0 \leq q \leq 100$）
  • 对于每一个条件，有一下两种可能
    1 $l_i,r_i,v_i$，对于所有满足$l_i \leq x \leq r_i$的下标$x$，有$a_x \geq v_i$
    2 $l_i,r_i,v_i$，对于所有满足$l_i \leq x \leq r_i$的下标$x$，有$a_x \leq v_i$
  • 构造出该序列的花费$cost = \sum_{i=1}^{n}cnt(i)^2$，其中$cnt(i)$为数$i$在构造的序列中出现的次数，求最小的花费。

建图

  • 先确定每个位置能填的数的范围，如果范围非法，可直输出$-1$并结束
  • 左边$n$个点，分别代表$1~n$这$n$个位置上的数，从源点引一条边，到左边的每一个点，容量为$1$，费用为$0$。
  • 右边也有$n$个点，分别代表填写的数。对于每个点，向汇点引$n$条边，第$j$条边的容量为$1$，费用为$j^2-(j-1)^2$。
  • 对于左边的每个点，向范围内的数对应的右边的数连边，容量为$1$，费用为$0$。
  • 由于费用流会优先使用费用较小的边，所以对于一个单独的数对应的右边的点来说，他向汇点的边的，只会使用前几条，这几条边的费用加起来正好是通过这个点的流量的平方，满足题目要求。
  • 跑费用流，即可解决问题。

代码

C++
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
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200 + 5;
const int maxm = 1e5 + 5;
struct EDGE
{
    int to, next, flow, cost;
    EDGE() {}
    EDGE(int to, int next, int flow, int cost) : to(to), next(next), flow(flow), cost(cost) {}
} edge[maxm];
int head[maxn], edgecnt, maxNodeNum;
void init()
{
    memset(head, -1, sizeof(head));
    edgecnt = 0;
    maxNodeNum = 0;
}
void AddEdge(int st, int en, int flow, int cost)
{
    edge[edgecnt] = EDGE(en, head[st], flow, cost);
    head[st] = edgecnt++;
    edge[edgecnt] = EDGE(st, head[en], 0, -cost);
    head[en] = edgecnt++;
    maxNodeNum = max(maxNodeNum, max(st, en));
}
int pre[maxn], dis[maxn];
bool SPFA(int st, int en)
{
    static bool vis[maxn];
    memset(dis, 0x7F, sizeof(int) * (maxNodeNum + 1));
    dis[st] = 0;
    queue<int> q;
    q.push(st);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = head[u]; ~i; i = edge[i].next)
        {
            int v = edge[i].to;
            if(edge[i].flow && dis[v] > dis[u] + edge[i].cost)
            {
                if(!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
            }
        }
    }
    return dis[en] != 0x7F7F7F7F;
}
pair<int, int> solve(int st, int en, int maxFlow = INT_MAX)
{
    int cost = 0, flow = 0;
    while(SPFA(st, en))
    {
        int d = maxFlow - flow;
        for(int u = en; u != st; u = edge[pre[u] ^ 1].to)
            d = min(d, edge[pre[u]].flow);
        flow += d;
        for(int u = en; u != st; u = edge[pre[u] ^ 1].to)
        {
            edge[pre[u]].flow -= d;
            edge[pre[u] ^ 1].flow += d;
            cost += edge[pre[u]].cost * d;
        }
        if(flow == maxFlow)
            break;
    }
    return make_pair(cost, flow);
}
bool area[55][55];
int main()
{
    init();
    int n, q;
    scanf("%d %d", &n, &q);
    for(int i = 1; i <= n; i++)
    {
        AddEdge(0, i, 1, 0);
        for(int j = 1; j <= n; j++)
            AddEdge(n + i, n + n + 1, 1, j * j - (j - 1) * (j - 1));
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            area[i][j] = 1;
    while(q--)
    {
        int op, l, r, v;
        scanf("%d %d %d %d", &op, &l, &r, &v);
        if(op == 1)
            for(int j = l; j <= r; j++)
                for(int k = 1; k < v; k++)
                    area[j][k] = 0;
        else
            for(int j = l; j <= r; j++)
                for(int k = v + 1; k <= n; k++)
                    area[j][k] = 0;
    }
    for(int i = 1; i <= n; i++)
    {
        bool ok = 0;
        for(int j = 1; j <= n; j++)
            if(area[i][j])
            {
                AddEdge(i, n + j, 1, 0);
                ok = 1;
            }
        if(!ok)
        {
            puts("-1");
            return 0;
        }
    }
    int ans = solve(0, n + n + 1).first;
    printf("%d\n", ans);
    return 0;
}

 

CodeForces 818G 费用流 优化建图

CodeForces 818G

题意

给定一个长度为$n$的序列$a_i$，$4 \leq n \leq 3000,1 \leq a_i \leq 10^5$，从中选出$4$个不想交的子序列，满足每个子序列中相邻的两个项，要么是差的绝对值为$1$，要么他们模$7$的结果相同。问这四个序列的总长度最长为多少。

思路

  • 对于每个项来说，将其看成一个点，将其拆点为为$i$和$i+n$，从$i$向$i+n$引一条边，容量为$1$，费用为$-1$，表示该点项只能被选一次，且选了之后收益$+1$。这一对点的流量方向，一定为从$i$进，并且从$i+n$出。
  • 对于每个项来说，都有可能作为子序列的起点或者终点。所以，从源点引一条边到$i$点，容量为$1$，费用为$0$；再从$i+n$点引一条边到汇点，容量为$1$，费用为$0$。
  • 对于每一个可能相邻的项$a_i,a_j$且$i \lt j$来说，需要建一条边从$i+n$到$j$，容量为$1$，费用为$-1$。但是这样建边之后，会发现边很多，根本跑不过。其实会发现，对于每一类相邻来说，只需要往后找到四个是同类的并建边就好了。
  • 从源点压入$4$点流量，跑费用流即可，答案为最小费用的相反数。

代码

C++
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 6e3 + 5;
const int maxm = 5e5 + 5;
struct EDGE
{
    int to, next, flow, cost;
    EDGE() {}
    EDGE(int to, int next, int flow, int cost) : to(to), next(next), flow(flow), cost(cost) {}
} edge[maxm];
int head[maxn], edgecnt, maxNodeNum;
void init()
{
    memset(head, -1, sizeof(head));
    edgecnt = 0;
    maxNodeNum = 0;
}
void AddEdge(int st, int en, int flow, int cost)
{
    edge[edgecnt] = EDGE(en, head[st], flow, cost);
    head[st] = edgecnt++;
    edge[edgecnt] = EDGE(st, head[en], 0, -cost);
    head[en] = edgecnt++;
    maxNodeNum = max(maxNodeNum, max(st, en));
}
int pre[maxn], dis[maxn];
bool SPFA(int st, int en)
{
    static bool vis[maxn];
    memset(dis, 0x7F, sizeof(int) * (maxNodeNum + 1));
    dis[st] = 0;
    queue<int> q;
    q.push(st);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = head[u]; ~i; i = edge[i].next)
        {
            int v = edge[i].to;
            if(edge[i].flow && dis[v] > dis[u] + edge[i].cost)
            {
                if(!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
            }
        }
    }
    return dis[en] != 0x7F7F7F7F;
}
pair<int, int> solve(int st, int en, int maxFlow = INT_MAX)
{
    int cost = 0, flow = 0;
    while(SPFA(st, en))
    {
        int d = maxFlow - flow;
        for(int u = en; u != st; u = edge[pre[u] ^ 1].to)
            d = min(d, edge[pre[u]].flow);
        flow += d;
        for(int u = en; u != st; u = edge[pre[u] ^ 1].to)
        {
            edge[pre[u]].flow -= d;
            edge[pre[u] ^ 1].flow += d;
            cost += edge[pre[u]].cost * d;
        }
        if(flow == maxFlow)
            break;
    }
    return make_pair(cost, flow);
}
vector<int> lastPos[maxm];
vector<int> lastModPos[7];
int a[maxn];
int main()
{
    init();
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = n; i >= 1; i--)
    {
        AddEdge(0, i, 1, 0);
        AddEdge(i + n, n + n + 1, 1, 0);
        AddEdge(i, i + n, 1, -1);
        for(int j = 0; j < min(4, (int)lastPos[a[i] + 1].size()); j++)
        {
            int sz = lastPos[a[i] + 1].size();
            AddEdge(i + n, lastPos[a[i] + 1][sz - j - 1], 1, 0);
        }
        for(int j = 0; j < min(4, (int)lastPos[a[i] - 1].size()); j++)
        {
            int sz = lastPos[a[i] - 1].size();
            AddEdge(i + n, lastPos[a[i] - 1][sz - j - 1], 1, 0);
        }
        for(int j = 0; j < min(4, (int)lastModPos[a[i] % 7].size()); j++)
        {
            int sz = lastModPos[a[i] % 7].size();
            AddEdge(i + n, lastModPos[a[i] % 7][sz - j - 1], 1, 0);
        }
        lastPos[a[i]].push_back(i);
        lastModPos[a[i] % 7].push_back(i);
    }
    int ret = -solve(0, n + n + 1, 4).first;
    printf("%d\n", ret);
    return 0;
}

2014-2015 ACM-ICPC Southwestern Europe Regional Contest (SWERC 14)

https://odzkskevi.qnssl.com/727b6827e404fd453ff4858e2619c49c?v=1504751451

A - GREAT+SWERC=PORTO

全排列枚举。先将字母按照出现的顺序，重新编码为以$0$为开始值的数字，方便后续使用。然后构造一个排列数组$p$，长度为$10$，初始值$p[i] = i$。然后枚举$p$的全排列，$p[i]$的意义就是将数字（实质上是被重新编码后的字母）$i$以值$p[i]$来代替。假设有$cnt$个不同的字母，全排列我们枚举的却是$10$个数，每次只取前$cnt$个进行代替，那么最终的答案会重复计算$(10-cnt)!$次。进行暴力枚举并统计答案后，除以$(10-cnt)!$即可。

C++
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
#include<bits/stdc++.h>
using namespace std;
char str[12][12];
int length[12];
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        for(int i = 1; i <= n; i++)
            scanf("%s", str[i]);
        int mp[127];
        memset(mp, -1, sizeof(mp));
        int cnt = 0;
        for(int i = 1; i <= n; i++)
        {
            length[i] = strlen(str[i]);
            for(int j = 0; j < length[i]; j++)
            {
                if(mp[str[i][j]] != -1)
                    continue;
                mp[str[i][j]] = cnt++;
            }
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j < length[i]; j++)
                str[i][j] = mp[str[i][j]];
        }//对字母进行重新编码
        int p[12];
        for(int i = 0; i < 10; i++)
            p[i] = i;//排列数组
        int ans = 0;
        do
        {
            bool ok = 1;
            for(int i = 1; i <= n; i++)
            {
                if(p[str[i][0]] == 0)//不能将第一位替换为0
                {
                    ok = 0;
                    break;
                }
            }
            if(!ok)
                continue;
            int val[12];
            memset(val, 0, sizeof(val));
            for(int i = 1; i <= n; i++)
            {
                for(int j = 0; j < length[i]; j++)
                    val[i] = val[i] * 10 + p[str[i][j]];//计算替换后，每个单词的值
            }
            int sum = 0;
            for(int i = 1; i < n; i++)
                sum += val[i];
            if(sum == val[n])
                ans++;
        }
        while(next_permutation(p, p + 10));//枚举下一个排列
        int t = 1;
        for(int i = 10 - cnt; i >= 2; i--)
            t *= i;//(10-cnt)的阶乘
        printf("%d\n", ans / t);
    }
    return 0;
}

B - Flowery Trails

从起点和终点进行两次最短路。开一个$dis[2][i]$数组，分别表示从$0$点到$i$点的最短路、从$n-1$点到$i$点的最短路。要判断一条边是否在最短路上，可以枚举每一条$单向边$，假设这条边的两个端点分别为$u$和$v$，如果满足$dis[0][u] + len + dis[1][v] = dis[0][n-1]$，那么从$u->v$方向的这条边就在最短路上，应该纳入统计。这个题可能会卡SPFA，所以使用了堆优化的DIJ

C++
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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 10005;
const int maxm = 250000 * 2;
struct EDGE
{
    int to, next, len;
    EDGE() {}
    EDGE(int to, int next, int len) : to(to), next(next), len(len) {}
} edge[maxm];
int head[maxn], edgecnt;
int dis[2][maxn];
int n;
struct node
{
    int u, dis;
    node(int u, int dis): u(u), dis(dis) {}
    bool operator < (const node &b) const
    {
        return dis > b.dis;
    }
};
void init()
{
    memset(head, -1, sizeof(head));
    edgecnt = 0;
}
void add(int s, int t, int l)
{
    edge[edgecnt] = EDGE(t, head[s], l);
    head[s] = edgecnt++;
}
void spfa(int st, int dis[])
{
    memset(dis, 0x7F, sizeof(int) *n);
    dis[st] = 0;
    priority_queue<node> q;
    static bool f[maxn];
    memset(f, 0, n);
    q.emplace(st, 0);
    while(!q.empty())
    {
        int u = q.top().u;
        q.pop();
        if(f[u])
            continue;
        f[u] = 1;
        for(int i = head[u]; ~i; i = edge[i].next)
        {
            int v = edge[i].to;
            if(dis[v] > dis[u] + edge[i].len)
            {
                dis[v] = dis[u] + edge[i].len;
                q.emplace(v, dis[v]);
            }
        }
    }
}
int main()
{
    int m;
    while(~scanf("%d %d", &n, &m))
    {
        init();
        for(int i = 1; i <= m; i++)
        {
            int s, t, l;
            scanf("%d %d %d", &s, &t, &l);
            add(s, t, l);
            add(t, s, l);
        }
        spfa(0, dis[0]);
        spfa(n - 1, dis[1]);
        int len = dis[0][n - 1];
        int ans = 0;
        for(int u = 0; u < n; u++)
        {
            for(int i = head[u]; ~i; i = edge[i].next)
            {
                int v = edge[i].to;
                if(v == u)
                    continue;
                if(dis[0][u] + edge[i].len + dis[1][v] == len)
                    ans += edge[i].len;
            }
        }
        printf("%d\n", 2 * ans);
    }
    return 0;
}

C - Golf Bot

使用FFT进行计数。使用$cnt$数组记录每个值是否出现。将$cnt$数组和自己进行卷积后（假设为$A$数组），$A[i]$的意义就是任意选两个存在的数进行求和后，和值为$i$的方案数。再将$A$数组加回到$cnt$数组。$cnt[i]$是否为$0$，就代表是否有方案至多选两个数，至少选一个数的和为i。

C++
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
115
116
117
#include<bits/stdc++.h>
using namespace std;
const int FFT_MAXN = 1 << 19;
const double pi = acos(-1.0);
struct Complex
{
    double R, I;
    inline Complex(double real = 0.0, double image = 0.0)
    {
        R = real, I = image;
    }
    inline Complex operator + (Complex const &b) const
    {
        return Complex(R + b.R, I + b.I);
    }
    inline Complex operator - (Complex const &b) const
    {
        return Complex(R - b.R, I - b.I);
    }
    inline Complex operator * (Complex const &b) const
    {
        return Complex(R * b.R - I * b.I, I * b.R + R * b.I);
    }
} Wn[FFT_MAXN + 1];
int bitrev[FFT_MAXN];
inline int getLength(int n, int m)
{
    n = n + m - 1;
    int i = 1;
    for(; i < n; i <<= 1);
    return i;
}
void Change(Complex a[], int n)
{
    int d = 0;
    while((1 << d)*n != FFT_MAXN)
        d++;
    for(int i = 0; i < n; i++)
        if(i < (bitrev[i] >> d))
            swap(a[i], a[bitrev[i] >> d]);
}
void FFT(Complex P[], int n, int op)
{
    Change(P, n);
    for(int len = 2; len <= n; len <<= 1)
    {
        int m = len >> 1;
        int del = FFT_MAXN / len * op;
        for(int i = 0; i < n; i += len)
        {
            Complex *p = P + i, *q = P + i + m, *w = op == 1 ? Wn : Wn + FFT_MAXN;
            for(int j = 0; j < m; j++, p++, q++, w += del)
            {
                Complex ne = *q * *w;
                *q = *p - ne;
                *p = *p + ne;
            }
        }
    }
    if(op == -1)
        for(int i = 0; i < n; i++)
        {
            P[i].R /= n;
            P[i].I /= n;
        }
}
void FFTInit()
{
    int L = 0;
    while((1 << L) != FFT_MAXN)
        L++;
    bitrev[0] = 0;
    for(int i = 1; i < FFT_MAXN; i++)
        bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (L - 1));
    for(int i = 0; i <= FFT_MAXN; i++)
        Wn[i] = Complex(cos(2 * pi / FFT_MAXN * i), sin(2 * pi / FFT_MAXN * i));
}
Complex A[FFT_MAXN], B[FFT_MAXN];
long long cnt[FFT_MAXN];
int main()
{
    FFTInit();
    int n;
    while(~scanf("%d", &n))
    {
        memset(cnt, 0, sizeof(cnt));
        for(int i = 1; i <= n; i++)
        {
            int x;
            scanf("%d", &x);
            cnt[x]++;
        }
        for(int i = 0; i < FFT_MAXN; i++)
            A[i] = Complex(cnt[i], 0);
        FFT(A, FFT_MAXN, 1);
        for(int i = 0; i < FFT_MAXN; i++)
            A[i] = A[i] * A[i];
        FFT(A, FFT_MAXN, -1);
        for(int i = 0; i < FFT_MAXN; i++)
        {
            int t = A[i].R + 0.5;
            cnt[i] += t;
        }
        int m;
        scanf("%d", &m);
        int ans = 0;
        while(m--)
        {
            int x;
            scanf("%d", &x);
            if(cnt[x])
                ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

D - Book Club

最大流求是否有合法方案

给出一些给书的关系，问是否有方案，使得每个人可以交出一本书，并且获得一本书，不能自己和自己玩。

将一个人$i$看作两个点，编号$A_i$和$B_i$。从源点引边到每一个$A_i$点，容量为1，表示$i$这个人要交出一本书。从每一个$B_i$引一条边到汇点，容量为1，表示$i$这个人要获得一本书。如果有一个关系，$i$的书可以给$j$，那么连一条边从$A_i$到$B_j$。最后跑最大流，如果流量为n，就满足要求。

C++
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
const int maxm = 2e5;
struct EDGE
{
    int to, next, flow;
    EDGE(int to = 0, int next = 0, int flow = 0): to(to), next(next), flow(flow) {}
} edge[maxm];
int head[maxn], edgecnt;
void init()
{
    memset(head, -1, sizeof(head));
    edgecnt = 0;
}
void AddEdge(int s, int t, int c)
{
    edge[edgecnt] = EDGE(t, head[s], c);
    head[s] = edgecnt++;
    edge[edgecnt] = EDGE(s, head[t], 0);
    head[t] = edgecnt++;
}
int layer[maxn];
int p[maxn];
bool GetLayer(int st, int en)
{
    memset(layer, 0, sizeof(int) * (en + 1));
    layer[st] = 1;
    queue<int>q;
    q.push(st);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].next)
        {
            if (edge[i].flow == 0) continue;
            int v = edge[i].to;
            if (layer[v]) continue;
            layer[v] = layer[u] + 1;
            q.push(v);
        }
    }
    return layer[en];
}
int dfsFlow(int u, int en, int f)
{
    int ret = 0;
    if (u == en) return f;
    if (layer[u] >= layer[en]) return 0;
    for (; ~p[u]; p[u] = edge[p[u]].next)
    {
        if (edge[p[u]].flow == 0) continue;
        int v = edge[p[u]].to;
        if (layer[v] != layer[u] + 1) continue;
        int temp = dfsFlow(v, en, min(f, edge[p[u]].flow));
        ret += temp;
        f -= temp;
        edge[p[u]].flow -= temp;
        edge[p[u] ^ 1].flow += temp;
        if (f == 0) break;
    }
    return ret;
}
int dinic(int st, int en)
{
    int ans = 0;
    while (GetLayer(st, en))
    {
        memcpy(p, head, sizeof(int) * (en + 1));
        ans += dfsFlow(st, en, INT_MAX);
    }
    return ans;
}
int main()
{
    init();
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        AddEdge(0, i, 1);
        AddEdge(n + i, n + n + 1, 1);
    }
    while (m--)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        u++;
        v++;
        AddEdge(u, n + v, 1);
    }
    int flow = dinic(0, n + n + 1);
    if (flow != n)
        puts("NO");
    else puts("YES");
    return 0;
}

G - Playing With Geometry

离散化，坐标旋转。

给定两个图，以转角坐标的方式逆时针给出，问两个图的轮廓是否相似。允许进行压缩或者旋转。

直接将两个图的横纵坐标进行离散化（压缩）。枚举将第一图进行旋转，和第二个图进行匹配，匹配的时候，需要找到两张图最左下角的点，让后从这个点开始，逆时针匹配。如果每个坐标都是相同的，那么就是OK的。

C++
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 505;
int n;
void Compress(pair<int, int> p[maxn])
{
    int x[maxn], y[maxn];
    for (int i = 0; i < n; i++)
    {
        x[i] = p[i].first;
        y[i] = p[i].second;
    }
    sort(x, x + n);
    sort(y, y + n);
    int cntx = unique(x, x + n) - x - 1;
    int cnty = unique(y, y + n) - y - 1;
    for (int i = 0; i < n; i++)
    {
        p[i].first = lower_bound(x, x + cntx, p[i].first) - x;
        p[i].second = lower_bound(y, y + cnty, p[i].second) - y;
    }
}
void Rotate(pair<int, int> p[maxn])
{
    int ym = 0;
    for (int i = 0; i < n; i++) ym = max(ym, p[i].second);
    for (int i = 0; i < n; i++)
        p[i] = make_pair(ym - p[i].second, p[i].first);
}
bool Compare(pair<int, int> p[2][maxn])
{
    int p1 = min_element(p[0], p[0] + n) - p[0];
    int p2 = min_element(p[1], p[1] + n) - p[1];
    for (int i = 0; i < n; i++)
        if (p[0][(p1 + i) % n] != p[1][(p2 + i) % n]) return false;
    return true;
}
bool check(pair<int, int> p[2][maxn])
{
    for (int i = 0; i < 4; i++)
    {
        if (Compare(p)) return true;
        Rotate(p[0]);
    }
    return false;
}
int main()
{
    pair<int, int> p[2][maxn];
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &p[0][i].first, &p[0][i].second);
    int m;
    scanf("%d", &m);
    if (n != m)
    {
        puts("no");
        return 0;
    }
    for (int i = 0; i < n; i++)
        scanf("%d %d", &p[1][i].first, &p[1][i].second);
    Compress(p[0]);
    Compress(p[1]);
    if (check(p))
        puts("yes");
    else
        puts("no");
    return 0;
}

I - The Safe Secret

循环枚举，区间DP

给一个由数字和运算符号组成的序列，长度为$2*n$运算符号只包含+-*和?,?可以任意替换为+-*。枚举将序列向左进行循环位移，每次位移$2$个单位，可以得到$n$个表达式序列，问这$n$个表达式的值的最小值和最大值的绝对值。

先将原始序列的数字和符号进行分离。再分别复制一份后接到后面。这样就可以进行区间dp了。注意，第i个数字就是$num[i]$了，它后面的符号就是$symbol[i]$。用$mx[i][j]$来表示从第$i$个数字到第$j$个数字组成的子区间的表达式的最大值，$mi[i][j]$表示最小值。初始化$mx[i][i] = mi[i][i] = num[i]$。枚举区间长度，枚举区间起点，再枚举区间内的断点，进行转移即可。要注意断点处为乘号的时候，并不是最小值*最小值就是最小值（考虑两个都是负数的情况），为了偷懒，直接暴力枚举了4种情况进行转移。

最后mx[i][n+i-1]和mi[i][n+i-1]就是第i个序列的表达式的最大值和最小值

C++
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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 405;
LL mx[maxn][maxn];
LL mi[maxn][maxn];
void getMaxMin(const vector<int> &num, const vector<char> &symbol)
{
    memset(mx, 0x80, sizeof(mx));
    memset(mi, 0x7F, sizeof(mi));
    int n = num.size();
    for (int i = 0; i < n; i++)
        mi[i][i] = mx[i][i] = num[i];
    for (int len = 2; len <= n / 2; len++)
    {
        for (int st = 0; st + len <= n; st++)
        {
            int en = st + len - 1;
            for (int mid = st; mid < en; mid++)
            {
                if (symbol[mid] == '+' || symbol[mid] == '?')
                {
                    mi[st][en] = min(mi[st][en], mi[st][mid] + mi[mid + 1][en]);
                    mx[st][en] = max(mx[st][en], mx[st][mid] + mx[mid + 1][en]);
                }
                if (symbol[mid] == '-' || symbol[mid] == '?')
                {
                    mi[st][en] = min(mi[st][en], mi[st][mid] - mx[mid + 1][en]);
                    mx[st][en] = max(mx[st][en], mx[st][mid] - mi[mid + 1][en]);
                }
                if (symbol[mid] == '*' || symbol[mid] == '?')
                {
                    mi[st][en] = min(mi[st][en], mi[st][mid] * mi[mid + 1][en]);
                    mi[st][en] = min(mi[st][en], mi[st][mid] * mx[mid + 1][en]);
                    mi[st][en] = min(mi[st][en], mx[st][mid] * mi[mid + 1][en]);
                    mi[st][en] = min(mi[st][en], mx[st][mid] * mx[mid + 1][en]);
                    mx[st][en] = max(mx[st][en], mx[st][mid] * mx[mid + 1][en]);
                    mx[st][en] = max(mx[st][en], mx[st][mid] * mi[mid + 1][en]);
                    mx[st][en] = max(mx[st][en], mi[st][mid] * mx[mid + 1][en]);
                    mx[st][en] = max(mx[st][en], mi[st][mid] * mi[mid + 1][en]);
                }
            }
        }
    }
}
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        vector<int> num;
        vector<char> symbol;
        for (int i = 0; i < n; i++)
        {
            int x;
            scanf("%d", &x);
            num.push_back(x);
            char s[10];
            scanf("%s", s);
            symbol.push_back(s[0]);
        }
        for (int i = 0; i < n; i++)
        {
            num.push_back(num[i]);
            symbol.push_back(symbol[i]);
        }
        getMaxMin(num, symbol);
        for (int i = 0; i < n; i++)
            printf("%lld%lld", abs(mi[i][i + n - 1]), abs(mx[i][i + n - 1]));
        printf("\n");
    }
    return 0;
}

 

以HDU 2089 不要62 为例的数位DP小结

题意不多说，不知道自己去看http://acm.hdu.edu.cn/showproblem.php?pid=2089

C++
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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
///一般数位DP都是在int范围内问满足要求的数的个数，也有在long long范围内的
///也有的是算贡献的。做之前请先考虑好数据范围
LL dp[44][2]; ///哎，状态的确定，随缘吧！一般肯定是有维表示当前位的。
///根据限制条件，适当地加一些维度。
///如果对长度有特殊要求，或者是不允许前导0的出现等，
///可以酌情考虑添加一维start，表示从这个位置开始填。
///一般直接用dp表示方案数或者贡献
///该dp[pos][i]对于次题的意义为当前要填写第i位，这位是否允许填2
///而且这个dp的值，应该和前面填的东西（除了已经表示的限制之外）无关 -> limit = 0
int dig[44]; ///为了操作方便，一般要将寻问的上届展开，最低位的下标为0
LL dfs(int pos, bool canUseTwo,  bool limit)
///基本上传的参数都是dp的几个维度，外加一个limit，表示前面填写的时候，
///是否都和上界的对应位置相同
{
    if(pos < 0) ///到达边界的时候，返回一个默认值，
///请仔细思考这个默认值是0还是1，还是其他什么东西
        return 1;///一般记数的个数就是1啦~
    if(!limit && dp[pos][canUseTwo] != -1)
///在limit=0的情况，dfs的本质应该是返回参数对应的DP值，
///调用dfs和使用dp数组，是等效的。
        return dp[pos][canUseTwo];
///但是这个DP值可能还没有计算出来(dp值为-1)，所以这个时候应该改进行计算
///而limit=1的时候，求出的数据不具有通用性，所以保存下来毫无意义
    int maxx = limit ? dig[pos] : 9;
    ///根据limit(其实应该叫前面填的数的情况)的值，来推断这位能填的数的范围
    int sum = 0; ///返回值，枚举这一位填什么后，求和
    for(int i = 0; i <= maxx; i++) ///枚举这一位填什么
    {
        if(i == 4) continue; ///题目要求，不能出现4
        if(i == 2 && canUseTwo) ///如果前面填的数，对本位做出了要求，不能填2，就跳过
            continue;
        sum += dfs(pos - 1, i == 6, limit && i == maxx);
        ///填写下一位，根本位填写的内容，来限制下一位能不能填哪些数
        ///(i==6这句，会限制下一位不能填2)
        ///同时也要推断，limit的值，只要一个位置不擦边，以后都不会擦边了。
    }
    if(!limit)
        dp[pos][canUseTwo] = sum;
        ///计算出了dp值，如果这个dp值是通用的，则保存下来
    return sum;
}
LL solve(int n)
{
    int cnt = 0;
    while(n)
    {
        dig[cnt++] = n % 10;
        n /= 10;
    }
    return dfs(cnt - 1, 0, 1);
}
int main()
{
    int n, m;
    memset(dp, -1, sizeof(dp));
    while(scanf("%d%d", &n, &m), n + m)
    {
        int ans = solve(m) - solve(n - 1);
        printf("%d\n", ans);
    }
    return 0;
}

 

HDU 6156 Palindrome Function 数位DP

 问题主要是求$k$进制下小于等于$n$的回文串的个数。

用$dp[base][start][cur]$表示在base进制下，从第start位开始填写，当前填到了第cur位，往后继续填能构成回文的方案数。如果填写的长度超过了一半，就不需要继续DFS了。

C++
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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int dp[37][32][32];
int targe[32], now[32];
int dfs(int base, int start, int cur, bool limit)
{
    if(cur < (start + 1) / 2)
    {
        if(!limit)
            return 1;
        for(int i = cur; i >= 0; i--)
        {
            int should = now[start - i];
            if(should > targe[i])
                return 0;
            if(should < targe[i])
                return 1;
        }
        return 1;
    }
    if(!limit && dp[base][start][cur] != -1)
        return dp[base][start][cur];
    int ret = 0;
    int mx = limit ? targe[cur] : base - 1;
    for(int i = 0; i <= mx; i++)
    {
        now[cur] = i;
        if(i == 0 && start == cur)
            ret += dfs(base, start - 1, cur - 1, 0);
        else
            ret += dfs(base, start, cur - 1, limit && i == mx);
    }
    if(!limit)
        dp[base][start][cur] = ret;
    return ret;
}
int f(int base, int j)
{
    int cnt = 0;
    while(j)
    {
        targe[cnt++] = j % base;
        j /= base;
    }
    return dfs(base, cnt - 1, cnt - 1, 1);
}
int g(int base, int l, int r)
{
    return f(base, r) - f(base, l - 1);
}
int main()
{
    memset(dp, -1, sizeof(dp));
    int T, ks = 0;
    scanf("%d", &T);
    while(T--)
    {
        int L, R, l, r;
        scanf("%d %d %d %d", &L, &R, &l, &r);
        LL ans = 0;
        for(int i = l; i <= r; i++)
        {
            int ret = g(i, L, R);
            ans += (LL)i * ret + R - L + 1 - ret;
        }
        printf("Case #%d: %lld\n", ++ks, ans);
    }
    return 0;
}

 

HDU 6155 Subsequence Count 线段树维护矩阵DP转移

http://acm.hdu.edu.cn/showproblem.php?pid=6155

给一个01序列，有区间反转操作，询问区间内本质不同的子序列的个数 $%10^9+7$

写出dp转移方程，用$dp[i][j]$表从起点到第$i$个点，最后一位是$j$的方案数。

当第$i$位是$0$的时候:

$$dp[i][0] = dp[i-1][0] + dp[i-1][1] + 1$$

$$dp[i][1] = dp[i-1][1] $$

当第$i$位是$1$的时候:

$$dp[i][0] = dp[i-1][0] $$

$$dp[i][1] = dp[i-1][0] + dp[i-1][1] + 1$$

写成矩阵的形式进行转移

如果这一位是$0$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

如果这一位是$1$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

可以用线段树维护任意区间内的转移方程。

考虑反转，会发现把$0$矩阵交换$r_1,r_2$和$c_1,c_2$就能变成$1$矩阵，反之亦然。令$T=\begin{bmatrix} 0 & 1& 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}$，可知$TT=E$

交换行，可以在矩阵前乘以个 $T$，交换列，可以在矩阵后乘以一个$T$。假设$C=AB$ ，那么$TCT = TABT = TATTBT$。意味着，进行区间反转的时候，将维护的转移矩阵进行交换行列就好了，并打上延时标记。

C++
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
const int g[2][3][3] =
{
    {
        {1, 1, 1},
        {0, 1, 0},
        {0, 0, 1},
    },
    {
        {1, 0, 0},
        {1, 1, 1},
        {0, 0, 1},
    }
 
};
struct Mat
{
 
    int a[3][3];
    Mat()
    {
        memset(a, 0, sizeof(a));
    }
    Mat(int x)
    {
        memcpy(a, g[x], sizeof(a));
    }
    void flip()
    {
        for(int i = 0; i < 3; i++)
            swap(a[0][i], a[1][i]);
        for(int i = 0; i < 3; i++)
            swap(a[i][0], a[i][1]);
    }
    Mat operator * (const Mat &b) const
    {
        Mat ret;
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                for(int k = 0; k < 3; k++)
                {
                    ret.a[i][j] += (LL)a[i][k] * b.a[k][j] % mod;
                    if(ret.a[i][j] >= mod)
                        ret.a[i][j] -= mod;
                }
        return ret;
    }
} t[maxn * 4];
bool flip[maxn * 4];
char s[maxn];
void pushdown(int id)
{
    if(flip[id])
    {
        flip[id << 1] ^= 1;
        flip[id << 1 | 1] ^= 1;
        t[id << 1].flip();
        t[id << 1 | 1].flip();
        flip[id] = 0;
    }
}
void build(int id, int L, int R)
{
    flip[id] = 0;
    if(L == R)
        t[id] = Mat(s[L] - 48);
    else
    {
        int mid = L + R >> 1;
        build(id << 1, L, mid);
        build(id << 1 | 1, mid + 1, R);
        t[id] = t[id << 1 | 1] * t[id << 1];
    }
}
Mat query(int id, int L, int R, int l, int r)
{
    if(l <= L && R <= r)
        return t[id];
    else
    {
        int mid = L + R >> 1;
        pushdown(id);
        if(r <= mid)
            return query(id << 1, L, mid, l, r);
        else if(l > mid)
            return query(id << 1 | 1, mid + 1, R, l, r);
        else
            return query(id << 1 | 1, mid + 1, R, l, r) * query(id << 1, L, mid, l, r);
    }
}
void opt(int id, int L, int R, int l, int r)
{
    if(l <= L && R <= r)
    {
        t[id].flip();
        flip[id] ^= 1;
    }
    else
    {
        int mid = L + R >> 1;
        pushdown(id);
        if(l <= mid)
            opt(id << 1, L, mid, l, r);
        if(mid < r)
            opt(id << 1 | 1, mid + 1, R, l, r);
        t[id] = t[id << 1 | 1] * t[id << 1];
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n, q;
        scanf("%d %d", &n, &q);
        scanf("%s", s + 1);
        build(1, 1, n);
        while(q--)
        {
            int type, l, r;
            scanf("%d %d %d", &type, &l, &r);
            if(type == 1)
                opt(1, 1, n, l, r);
            else
            {
                Mat ret = query(1, 1, n, l, r);
                printf("%d\n", (ret.a[0][2] + ret.a[1][2]) % mod);
            }
        }
    }
    return 0;
}