分类：二分

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;
}

 

 

HDU6040 Hints of sd0061 分治排序

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

Hints of sd0061

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

sd0061, the legend of Beihang University ACM-ICPC Team, retired last year leaving a group of noobs. Noobs have no idea how to deal with $m$ coming contests. sd0061 has left a set of hints for them.
There are $n$ noobs in the team, the $i$-th of which has a rating $a_i$. sd0061 prepares one hint for each contest. The hint for the $j$-th contest is a number $b_j$, which means that the noob with the $(b_j + 1)$-th lowest rating is ordained by sd0061 for the $j$-th contest.
The coach asks constroy to make a list of contestants. constroy looks into these hints and finds out: $b_i + b_j \leq b_k$ is satisfied if $b_i \neq b_j,$ $b_i < b_k$ and $b_j < b_k$.
Now, you are in charge of making the list for constroy.

Input

There are multiple test cases (about $10$).
For each test case:
The first line contains five integers $n, m, A, B, C$. $(1 \leq n \leq 10^7, 1 \leq m \leq 100)$
The second line contains $m$ integers, the $i$-th of which is the number $b_i$ of the $i$-th hint. $(0 \leq b_i < n)$
The $n$ noobs' ratings are obtained by calling following function $n$ times, the $i$-th result of which is $a_i$.

C++
1
2
3
4
5
6
7
8
9
10
11
12
unsigned x = A, y = B, z = C;
unsigned rng61() {
  unsigned t;
  x ^= x &lt;&lt; 16;
  x ^= x &gt;&gt; 5;
  x ^= x &lt;&lt; 1;
  t = x;
  x = y;
  y = z;
  z = t ^ x ^ y;
  return z;
}

Output

For each test case, output "Case #$x$: $y_1$ $y_2$ $\cdots$ $y_m$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y_i$ $(1 \leq i \leq m)$ denotes the rating of noob for the $i$-th contest of corresponding case.

Sample Input

C++
1
2
3
4
3 3 1 1 1
0 1 2
2 2 2 2 2
1 1

Sample Output

C++
1
2
Case #1: 1 1 202755
Case #2: 405510 405510

Source

2017 Multi-University Training Contest - Team 1

题意

给一个随机程序，生成一个长度为n的数组$a_i$，再给m次寻问$b_i$，询问数组$a_i$排序后，排名为$b_i+1$的数是多少。

思路

将询问的$b_i$数组排序，对$a_i$数组进行分治，类似于快排，选取参考点，交换数据后，在$b_i$数组中二分查找mid的范围，那么此时$b_i=mid$的询问都做出来了，此时$a_i$$b_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
#include<bits/stdc++.h>
using namespace std;
pair<unsigned, unsigned > p[105];
unsigned b[105];
unsigned x, y, z;
unsigned w703710691d()
{
    unsigned t;
    x ^= x << 16;
    x ^= x >> 5;
    x ^= x << 1;
    t = x;
    x = y;
    y = z;
    z = t ^ x ^ y;
    return z;
}
const unsigned maxn = 1e7 + 5;
unsigned  a[maxn];
void w703710691d(unsigned l, unsigned r, unsigned L, unsigned R)
{
    if(L > R)
        return;
    if(l > r)
        return;
    if(l == r)
    {
        for(unsigned i = L; i <= R; i++)
            p[i].first = a[l];
        return;
    }
    unsigned i = l, j = r, x = a[(i + j) / 2], y;
    do
    {
        while(a[i] < x)
            i++;
        while(a[j] > x)
            j--;
        if(i <= j)
        {
            y = a[i];
            a[i] = a[j];
            a[j] = y;
            i++;
            j--;
        }
    }
    while(i <= j);
    unsigned pos = upper_bound(b + L, b + R + 1, j) - b;
    w703710691d(l, j, L, pos - 1);
    if(j + 2 == i)
    {
        unsigned mid = j + 1;
        unsigned pos2 = upper_bound(b + L, b + R + 1, mid) - b;
        for(unsigned x = pos; x < pos2; x++)
            p[x].first = a[mid];
        pos = pos2;
    }
    w703710691d(i, r, pos, R);
}
int main()
{
    unsigned n, m;
    unsigned ks = 0;
    while(~scanf("%u %u %u %u %u", &n, &m, &x, &y, &z))
    {
        for(unsigned i = 1; i <= m; i++)
        {
            scanf("%u", &p[i].first);
            p[i].first++;
            p[i].second = i;
        }
        sort(p + 1, p + 1 + m);
        for(unsigned i = 1; i <= m; i++)
        {
            b[i] = p[i].first;
        }
        for(unsigned i = 1; i <= n; i++)
            a[i] = w703710691d();
        w703710691d(1, n, 1, m);
        unsigned ans[105];
        for(unsigned i = 1; i <= m; i++)
            ans[p[i].second] = p[i].first;
        printf("Case #%u:", ++ks);
        for(unsigned i = 1; i <= m; i++)
            printf(" %u", ans[i]);
        printf("\n");
    }
    return 0;
}

 

 

CodeForces 756B Travel Card 二分 DP

http://codeforces.com/problemset/problem/756/B

B. Travel Card

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A new innovative ticketing systems for public transport is introduced in Bytesburg. Now there is a single travel card for all transport. To make a trip a passenger scan his card and then he is charged according to the fare.

The fare is constructed in the following manner. There are three types of tickets:

  1. a ticket for one trip costs 20 byteland rubles,
  2. a ticket for 90 minutes costs 50 byteland rubles,
  3. a ticket for one day (1440 minutes) costs 120 byteland rubles.

Note that a ticket for x minutes activated at time t can be used for trips started in time range from t to t + x - 1, inclusive. Assume that all trips take exactly one minute.

To simplify the choice for the passenger, the system automatically chooses the optimal tickets. After each trip starts, the system analyses all the previous trips and the current trip and chooses a set of tickets for these trips with a minimum total cost. Let the minimum total cost of tickets to cover all trips from the first to the current is a, and the total sum charged before is b. Then the system charges the passenger the sum a - b.

You have to write a program that, for given trips made by a passenger, calculates the sum the passenger is charged after each trip.

Input

The first line of input contains integer number n (1 ≤ n ≤ 105) — the number of trips made by passenger.

Each of the following n lines contains the time of trip ti (0 ≤ ti ≤ 109), measured in minutes from the time of starting the system. All ti are different, given in ascending order, i. e. ti + 1 > ti holds for all 1 ≤ i < n.

Output

Output n integers. For each trip, print the sum the passenger is charged after it.

Examples

input

C++
1
2
3
4
3
10
20
30

output

C++
1
2
3
20
20
10

input

C++
1
2
3
4
5
6
7
8
9
10
11
10
13
45
46
60
103
115
126
150
256
516

output

C++
1
2
3
4
5
6
7
8
9
10
20
20
10
0
20
0
0
20
20
10

Note

In the first example, the system works as follows: for the first and second trips it is cheaper to pay for two one-trip tickets, so each time 20 rubles is charged, after the third trip the system understands that it would be cheaper to buy a ticket for 90 minutes. This ticket costs 50 rubles, and the passenger had already paid 40 rubles, so it is necessary to charge 10 rubles only.

题意

有一个乘车的收费系统，出售单次票20元，90分钟票50元，1440分钟票120元。当有人来购票的时候，系统会统计前面已经买票的人，然后让总价格最少的方式，要求现在的人补足差价即可。问每个人需要补多少钱。

样例1的解释，3个人，分别在第10分钟、20分钟、30分钟来乘车。第一个人系统买了单次票，第二个人也是单次票，第三个人，由于前两个人已经一共付了40元，且第一个人和第三个人没有超过90分钟，所有系统选择了90分钟票，所以补了10元。

思路

用dp[i]来表示前i个人最少需要花多少钱。很明显，dp是单调递增的。每次算dp[i]的时候，将买单次票、90分钟票，120分钟票的三种情况分别算出后取最小值即可。对于算90分钟和120分钟的，进行二分查找，找到第一个tp>ti-90(或者120)的人，补差价即可。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int t[maxn];
int sum[maxn];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &t[i]);
        sum[i] = sum[i - 1] + 20;
        int p = upper_bound(t, t + i, t[i] - 90) - t;
        int tot = sum[i - 1] - sum[p - 1];
        int charge = 50 - tot;
        sum[i] = min(sum[i], sum[i - 1] + charge);
        p = upper_bound(t, t + i, t[i] - 1440) - t;
        tot = sum[i - 1] - sum[p - 1];
        charge = 120 - tot;
        sum[i] = min(sum[i], sum[i - 1] + charge);
        printf("%d\n", sum[i] - sum[i - 1]);
    }
    return 0;
}

 

HDU 5853 Jong Hyok and String 后缀数组 二分 RMQ

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

Jong Hyok and String

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Jong Hyok loves strings. One day he gives a problem to his friend you. He writes down n strings Pi in front of you, and asks m questions. For i-th question, there is a string Qi. We called strange set(s) = {(i, j) | s occurs in Pi and j is the position of its last character in the current occurence}. And for ith question, you must answer the number of different strings t which satisfies strange set(Qi) = strange set(t) and t is a substring of at least one of the given n strings.

Input

First line contains T, a number of test cases.

For each test cases, there two numbers n, m and then there are n strings Pi and m strings Qj.(i = 1…n, j = 1…m)

1 <= T <= 10
1 <= n <= 100000
1 <= m<= 500000
1 <=|Pi|<=100000
1 <=|Qi|<=100000
∑ni=1|Pi|≤100000
File size is less than 3.5 megabytes.

Output

For each test case, first line contains a line “Case #x:”, x is the number of the case.

For each question, you should print one integer in one line.

Sample Input

1
2 2
aba
ab
a
ab

Sample Output

Case #1:
1
2

Hint

strange set(“a”) ={(1, 1), (1, 3), (2, 1)}.
strange set(“ab”) ={(1, 2), (2, 2)}.
strange set(“b”) ={(1, 2), (2, 2)}.

Author

金策工业综合大学（DPRK）

Source

2016 Multi-University Training Contest 9

题意

给定n个字符串Pi，（1<=n<=105，Pi的总长度小于105）。然后是m次询问，每次询问给出一个字符串Qi，Qi的长度小于105，定义集合set(s)={(i,j)|字符串s出现在Pi中，且最后一个字符的位置为j}。询问有多少个不同的字符串t，使得set(t)和set(Qi)相同。

思路

由于题叙的位置为出现字符串的最后一个字符的位置，可以考虑将所有字符串倒序，那么这个位置就变成的第一次字符的位置。（后面说的串都是反转之后的）。考虑t=Qi的情况，这个t是显然可以的。若让t删除几个末尾的字符，set(t)只会在原有的基础上，增加元素，或者是不增加。若让t在末尾增加几个字符，set(t)也只会在原有的基础上，减少元素，或者不减少。这里增加长度的时候，只考虑在和某个Pi的某个位置匹配的时候，增加后面的字符。那么增加后使set(t)不变的最长长度，删减后，使set(t)不变的最短长度，这两个的差值+1就是答案。

将所有的Pi串连到一起，用不同的特殊符合隔开，这个用#表示，构成一个串s。注意，每个#的值都是不同的。构建关于s的后缀数组。每次询问一个串Qi的时候。二分查找Qi第一次出现在后缀数组中的位置low和最后一次出现的位置high。当然，如果没有出现Qi串，那么答案一定就是0了。考虑最小长度，可以发现，就是max(height[low]，height[high+1])+1，如果删减到小于这个长度，会使得set(t)的元素数目变多。那么最大长度，则使min(height[low+1……height])，这个用rmq维护即可。但是如果low==high的时候，最小长度还是可以按照上述方法求的，但是最大长度则是这个起始位置到后面离它最近一个#的距离。

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
const int  MAXN = 201000;
using namespace std;
int s[MAXN];
int sa[MAXN], t[MAXN], t2[MAXN], c[MAXN];
void build_sa(int m, int n)
{
int *x = t, *y = t2;
for(int i = 0; i < m; i++) c[i] = 0;
for(int i = 0; i < n; i++) c[x[i] = s[i]]++;
for(int i = 1; i < m; i++) c[i] += c[i - 1];
for(int i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
for(int k = 1; k <= n; k <<= 1)
{
int p = 0;
for(int i = n - k; i < n; i++) y[p++] = i;
for(int i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
for(int i = 0; i < m; i++) c[i] = 0;
for(int i = 0; i < n; i++) c[x[y[i]]]++;
for(int i = 0; i < m; i++) c[i] += c[i - 1];
for(int i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1;
x[sa[0]] = 0;
for(int i = 1; i < n; i++)
x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
if(p >= n) break;
m = p;
}
}
int cmp_suffix(int* pattern, int p, int m)
{
for(int i = 0; i < m; i++)
if(pattern[i] < s[sa[p] + i]) return -1;
else if(pattern[i] > s[sa[p] + i]) return 1;
return 0;
}
int Rank[MAXN], height[MAXN];
void getHeight(int n)
{
int i, j, k = 0;
for(i = 0; i < n; i++) Rank[sa[i]] = i;
for(i = 0; i < n; i++)
{
if(k) k--;
j = sa[Rank[i] - 1];
while(s[i + k] == s[j + k]) k++;
height[Rank[i]] = k;
}
height[0] = 0;
}
int mi[MAXN][18];
void rmq_init(int *a, int n)
{
for(int i = 0; i < n; i++) mi[i][0] = a[i];
for(int j = 1; (1 << j) <= n; j++)
for(int i = 0; i + (1 << j) - 1 < n; i++)
mi[i][j] = min(mi[i][j - 1], mi[i + (1 << j - 1)][j - 1]);
}
int getmin(int l, int r)
{
int k = 0;
while((1 << k + 1) <= r - l + 1) k++;
return min(mi[l][k], mi[r - (1 << k) + 1][k]);
}
int q[MAXN];
void GetArr(int len, int n, int &l, int &r)
{
int L = 0, R = n;
while(L < R)
{
int mid = L + R >> 1;
if(cmp_suffix(q, mid, len) <= 0) R = mid;
else L = mid + 1;
}
l = L;
L = 0, R = n;
while(L < R)
{
int mid = L + R >> 1;
if(cmp_suffix(q, mid, len) < 0) R = mid;
else L = mid + 1;
}
r = L - 1;
}
char str[MAXN];
int LastSpePos[MAXN];
int Query(int n)
{
int len = strlen(str);
for(int i = 0; i < len; i++) q[len - i - 1] = str[i];
q[len] = 0;
int low, high;
GetArr(len, n, low, high);
if(low > high) return 0;
int minlen, maxlen;
minlen = max(height[low], height[high + 1]) + 1;
if(low == high)
maxlen = LastSpePos[sa[low]] - sa[low];
else
maxlen = getmin(low + 1, high);
return maxlen - minlen + 1;
}
struct FastIO
{
static const int S = 1310720;
int wpos;
char wbuf[S];
FastIO() : wpos(0) {}
inline int xchar()
{
static char buf[S];
static int len = 0, pos = 0;
if(pos == len)
pos = 0, len = fread(buf, 1, S, stdin);
if(pos == len) return -1;
return buf[pos ++];
}
inline int xuint()
{
int c = xchar(), x = 0;
while(c <= 32) c = xchar();
for(; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x;
}
inline void xstring(char *s)
{
int c = xchar();
while(c <= 32) c = xchar();
for(; c > 32; c = xchar()) * s++ = c;
*s = 0;
}
inline void wchar(int x)
{
if(wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
wbuf[wpos ++] = x;
}
inline void wint(int x)
{
if(x < 0) wchar('-'), x = -x;
char s[24];
int n = 0;
while(x || !n) s[n ++] = '0' + x % 10, x /= 10;
while(n--) wchar(s[n]);
}
inline void wstring(const char *s)
{
while(*s) wchar(*s++);
}
~FastIO()
{
if(wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
}
} io;
int main()
{
int T = io.xuint(), ks = 0;
while(T--)
{
int n = io.xuint(), m = io.xuint();
int maxn = 0;
for(int i = 1; i <= n; i++)
{
io.xstring(str);
int len = strlen(str);
for(int j = 0; j < len; j++) s[maxn + j] = str[len - j - 1];
s[maxn + len] = 'z' + i;
for(int j = maxn; j < maxn + len; j++) LastSpePos[j] = maxn + len;
maxn += len + 1;
}
s[maxn++] = 0;
s[maxn] = 0;
build_sa('z' + n + 1, maxn);
getHeight(maxn);
rmq_init(height, maxn);
io.wstring("Case #");
io.wint(++ks);
io.wstring(":\n");
while(m--)
{
io.xstring(str);
int ret = Query(maxn);
io.wint(ret);
io.wchar('\n');
}
}
return 0;
}