Theme NexT works best with JavaScript enabled

2019 牛客暑期多校训练营第二场题解

本文包括 2019 牛客暑期多校训练营第二场的题面与题解。

A - Eddy Walker

题目描述

Eddy likes to walk around. Especially, he likes to walk in a loop called “Infinite loop”. But, actually, it’s just a loop with finite length(Anyway, the name doesn’t matter). Eddy can walk in a fixed length. He finds that it takes him N steps to walk through the loop a cycle. Then, he puts $ N $ marks on the “Infinite loop” labeled with $ 0, 1, \ldots, N-1 $ , where $ i $ and $ i+1 $ are a step away each other, so as $ 0 $ and $ N-1 $ . After that, Eddy stands on the mark labeled $ 0 $ and start walking around. For each step, Eddy will independently uniformly randomly choose to move forward or backward. If currently Eddy is on the mark labeled $ i $ , he will on the mark labeled $ i+1 $ if move forward or $ i-1 $ if move backward. If Eddy is on the mark labeled $ N-1 $ and moves forward, he will stand on the mark labeled $ 0 $ . If Eddy is on the mark labeled $ 0 $ and moves backward, he will stand on the mark labeled $ N-1 $ .

Although, Eddy likes to walk around. He will get bored after he reaches each mark at least once. After that, Eddy will pick up all the marks, go back to work and stop walking around.

You, somehow, notice the weird convention Eddy is doing. And, you record $ T $ scenarios that Eddy walks around. For i-th scenario, you record two numbers $ N_i $ , $ M_i $ , where $ N_i $ tells that in the i-th ​scenario, Eddy can walk through the loop a cycle in exactly $ N_i $ steps ( Yes! Eddy can walk in different fixed length for different day.). While $ M_i $ tells that you found that in the i-th scenario, after Eddy stands on the mark labeled $ M_i $ ​, he reached all the marks.

However, when you review your records, you are not sure whether the data is correct or even possible. Thus, you want to know the probability that those scenarios will happen. Precisely, you are going to compute the probability that first $ i $ scenarios will happen sequentially for each $ i $ .

Precisely, you are going to compute the probability that first $ i $ scenarios will happen sequentially for each $ i $ .

输入描述

The first line of input contains an integers $ T $ .

Following $ T $ lines each contains two space-separated integers $ N_i $ ​ and $ M_i $ ​.

$ 1 \leq T \leq 1021 $

$ 0 \leq M_i < N_i \leq 10^9 $

输出描述

Output $ T $ lines each contains an integer representing the probability that first i scenarios will happen sequentially.
you should output the number module $ 10^9+7(1000000007) $ .
Suppose the probability is $ \dfrac{P}{Q} $ ​, the desired output will be $ P \times Q^{-1}\mod 10^9+7 $

示例1

输入

1
2
3
4
3
1 0
2 1
3 0

输出

1
2
3
1
1
0

题解

题意

圆上有 $ n $ 个点,标号从 $ 0 $ 到 $ n−1 $ 。初始一个人在点 $ 0 $ ,每次会等概率向左或向右移动一步。如果某一时刻所有点均被访问过则停止移动,问最终停留在 $ m $ 点的概率。多次询问,每次输出上一次的结果与这一次的概率的乘积。

解法

若 $ m \neq 0 $ 且 $ n \neq 1 $ ,则 $ f(n,m)=\dfrac{1}{n−1} $

证明如下:

  • 若设答案 $ f(n,m) $ ,可以发现这个函数有如下性质:

    • 函数是关于零点对称的,即 $ f(n,m)=f(n,n−m) $
    • 若 $ m \neq 0,1,n−1 $ ,则 $ f(n,m)=\dfrac{f(n,m−1)+f(n,m+1)}{2} $
  • 接着考虑 $ n $ 的奇偶性

    • 若 $ n $ 为奇数,则设 $ a=\lfloor \dfrac{n}{2} \rfloor ,b=\lceil \dfrac{n}{2} \rceil,c=b+1 $ 。可以发现由如上两条性质,有 $ f(n,a)=f(n,b) $ ,且 $ f(n,b)=\dfrac{f(n,a)+f(n,c)}{2} $ ,因此可以得出 $ f(n,a)=f(n,b)=f(n,c) $ 。以此类推则可以得出所有 $ f(n,m) $ 相等,所以函数取值为 $ \dfrac{1}{n−1} $
    • 若 $ n $ 为偶数,则设 $ a= \dfrac{n}{2}-1 ,b= \dfrac{n}{2} ,c=\dfrac{n}{2} +1 $ ,可以得出 $ f(n,a)=f(n,c) $ ,且 $ f(n,b)=\dfrac{f(n,a)+f(n,c)}{2} $ ,同样可以推出 $ f(n,a)=f(n,b)=f(n,c) $ ,同理可证 $ f(n,m)=\dfrac{1}{n−1}(m \neq 0) $
  • 注意对 $ n=1 $ 的特判

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
ll Qpow(ll x, ll n) {
ll t = 1;
while (n) {
if (n & 1) t = t * x % mod;
x = x * x % mod;
n >>= 1;
}
return t;
}
int main() {
ll t, n, m, ans = 1;
scanf("%lld", &t);
while (t--) {
scanf("%lld%lld", &n, &m);
if (m)
ans = ans * Qpow(n - 1, mod - 2) % mod;
else if (n != 1)
ans = 0;
printf("%lld\n", ans);
}
return 0;
}

B - Eddy Walker 2

题目描述

As you may already know, Eddy likes to walk around. Especially, he likes to walk in a number line called “Infinite line”. Actually, it’s exactly a line with infinite length!

Eddy is at number $ 0 $ and starts to walk around. Since Eddy is a little drunk(just finished his work, make sense), he will not walk in a fixed length. Instead, he will independently uniformly randomly walk in an integer length between $ 1 $ and $ K $ . That is, he will walk for $ 1 $ unit of length in a probability of $ \dfrac{1}{K} $ ​, $ 2 $ units in $ \dfrac{1}{K} $ , $ \cdots $ , $ K $ units in $ \dfrac{1}{K} $ . If he currently stands on number $ i $ and walk for $ j $ unit of length, he will end up on number $ i+j $ .

Since Eddy is drunk, he will walk around infinitely. You, somehow, notice this weird thing and start wondering whether will Eddy ever step on the number $ N $ . However, you don’t want to wait for such stupid thing. You would like to compute the probability that Eddy would ever step on number $ N $ .

输入描述

The first line of input contains an integers T.

Following T lines each contains two space-separated integers $ K_i $ and $ N_i $ .

If $ N_i = -1 $ , $ N_i $ ​ is a number approaching infinity.

  • $ 1 \leq T \leq 10 $
  • $ 1 \leq K_i \leq 1021 $
  • $ \textbf{-1} \leq N_i \leq 10^{18} $

输出描述

For each $ i $ , output one line containing a number representing the probability.

you should output the number module $ 10^9+7(1000000007) $

Suppose the probability is $ \dfrac{P}{Q} $ , the desired output will be $ P \times Q^{-1} \mod 10^9+7 $

示例1

输入

1
2
3
4
3
1 0
2 1
3 -1

输出

1
2
3
1
500000004
500000004

题解

题意

T组数据,每次给定一对 $ n $ 和 $ k $ 。现在你从 $ 0 $ 号点出发, 每次有 $ \dfrac{1}{k} $ 的概率前进 $ 1 $ 步, $ \dfrac{1}{k} $ 的概率前进 $ 2 $ 步, $ \dfrac{1}{k} $ 的概率前进 $ 3 $ 步 $ \dots $ $ \dfrac{1}{k} $ 的概率前进 $ k $ 步 , 询问你经过 $ n $ 号点的期望。特别的,如果 $ n $ 为 $ -1 $ ,则表示询问 $ n $ 无限大时经过它的概率。

解法

  • n为有限远处时

    • 令 $ P_{i} $ 表示从经过 $ i $ 点的概率。那么 $ \displaystyle P_{i}=\sum_{j=max(i-k,1)}^{i-1} P_{j} \times \dfrac{1}{k} $
    • 表示从前 $ k $ 步转移过来,转移概率为 $ \dfrac{1}{k} $
    • 然后我们发现这个公式是个线性递推式,于是套用BM算法
    • 注意至少要推入 $ 2 \times k $ 项
  • n为无限远处时

    • 假设到达某一个无穷远处的期望为 $ E $
    • 那么有 $ \displaystyle E = \sum_{i=1}^{k} i \times \dfrac{1}{k} = \dfrac{1+k}{2} $
    • 所以此时 $ P_{n} $ 为 $ \dfrac{2}{1+k} $

代码

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define per(i, a, n) for (ll i = n - 1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define SZ(x) ((ll)(x).size())
typedef long long ll;
typedef vector<ll> VI;
typedef pair<ll, ll> PII;
const ll mod = 1000000007;
ll powmod(ll a, ll b) {
ll res = 1;
a %= mod;
assert(b >= 0);
for (; b; b >>= 1) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
}
return res;
}
// head

ll _, n, k;
namespace linear_seq {
const ll N = 10010;
ll res[N], base[N], _c[N], _md[N];

vector<ll> Md;
void mul(ll *a, ll *b, ll k) {
rep(i, 0, k + k) _c[i] = 0;
rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] =
(_c[i + j] + a[i] * b[j]) % mod;
for (ll i = k + k - 1; i >= k; i--)
if (_c[i])
rep(j, 0, SZ(Md)) _c[i - k + Md[j]] =
(_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;
rep(i, 0, k) a[i] = _c[i];
}
ll solve(ll n, VI a, VI b) {
ll ans = 0, pnt = 0;
ll k = SZ(a);
assert(SZ(a) == SZ(b));
rep(i, 0, k) _md[k - 1 - i] = -a[i];
_md[k] = 1;
Md.clear();
rep(i, 0, k) if (_md[i] != 0) Md.push_back(i);
rep(i, 0, k) res[i] = base[i] = 0;
res[0] = 1;
while ((1ll << pnt) <= n) pnt++;
for (ll p = pnt; p >= 0; p--) {
mul(res, res, k);
if ((n >> p) & 1) {
for (ll i = k - 1; i >= 0; i--) res[i + 1] = res[i];
res[0] = 0;
rep(j, 0, SZ(Md)) res[Md[j]] =
(res[Md[j]] - res[k] * _md[Md[j]]) % mod;
}
}
rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod;
if (ans < 0) ans += mod;
return ans;
}
VI BM(VI s) {
VI C(1, 1), B(1, 1);
ll L = 0, m = 1, b = 1;
rep(n, 0, SZ(s)) {
ll d = 0;
rep(i, 0, L + 1) d = (d + (ll)C[i] * s[n - i]) % mod;
if (d == 0)
++m;
else if (2 * L <= n) {
VI T = C;
ll c = mod - d * powmod(b, mod - 2) % mod;
while (SZ(C) < SZ(B) + m) C.pb(0);
rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
L = n + 1 - L;
B = T;
b = d;
m = 1;
} else {
ll c = mod - d * powmod(b, mod - 2) % mod;
while (SZ(C) < SZ(B) + m) C.pb(0);
rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
++m;
}
}
return C;
}
ll gao(VI a, ll n) {
VI c = BM(a);
c.erase(c.begin());
rep(i, 0, SZ(c)) c[i] = (mod - c[i]) % mod;
return solve(n, c, VI(a.begin(), a.begin() + SZ(c)));
}
}; // namespace linear_seq
ll P[3000], s[3000], T, k_;
inline ll inv(ll b) { return powmod(b, mod - 2); }
int main() {
scanf("%lld", &T);
while (T--) {
scanf("%lld%lld", &k, &n);
if (n == -1)
printf("%lld\n", 2 * inv(k + 1) % mod);
else {
vector<ll> v;
memset(P, 0, sizeof(P));
memset(s, 0, sizeof(s));
P[0] = s[0] = 1;
v.push_back(1);
k_ = inv(k);
for (ll i = 1; i <= k; i++) {
P[i] = s[i - 1] * k_ % mod;
s[i] = (s[i - 1] + P[i]) % mod;
v.push_back(P[i]);
}
for (ll i = k + 1; i <= 2 * k + 1; i++) {
P[i] = (s[i - 1] - s[i - 1 - k]) * k_ % mod;
s[i] = (s[i - 1] + P[i]) % mod;
v.push_back(P[i]);
}
printf("%lld\n", linear_seq::gao(v, n));
}
}
return 0;
}

C - Go on Strike!

题目描述

There are $ N $ cities in Eddy’s neverland. There are some flights to connect some pair of cities. Except flight, there’s no any other way to shuttle between cities.

However, in some cases, flight attendants may go on strike to fight for their rights. Therefore, some flight may be shut down for a period of time. On the other hand, some flight may come out to compete the market.

In Eddy’s neverland, each flight must propose its expected cost to be granted the license to fly. Then, Eddy will choose some flights and grant them the licenses. In order to keep the neverland great, Eddy will choose a minimum total cost flights to grant the license such that each city is possible to connect to each other city by the granted flights.

Since the new coming flight and flight shut down events come everyday, Eddy is not able to find out the best combination of flights with minimum total cost. Please help Eddy to keep his neverland great. Reporting the chosen combination would be too large to check. You only need to tell Eddy what is the most flights needed to connect two cities is under the chosen flights(Not the total cost!).

输入描述

The first line of input contains two space-separated integers $ N $ and $ Q $ , where $ N $ is the number of cities and $ Q $ is the number of events.

Following $ Q $ lines each contains four space-separated integers $ q_i, u_i, v_i, c_i $ . If $ q_i = 1 $ , there is a new flight coming out between city $ u_i $ and city $ v_i $ with cost $ c_i $ . If $ q_i = 0 $ , the flight attendants of the flight connecting city $ u_i $ and $ v_i $ with cost $ c_i $ has gone on strike and the flight is shut down.

  • $ 1 \leq N \leq 10^4 $
  • $ 1 \leq Q \leq 2 \times 10^4 $
  • $ 0 \leq q_i \leq 1 $
  • $ 1 \leq u_i \neq v_i \leq N $
  • $ 0 \leq c_i \leq 10^9 $

It’s guaranteed that if $ q_i = 0 $ , the required flight exists.

输出描述

Output $ Q $ lines each contains an integer representing the most flights needed to connect two cities in the chosen combination. If there exists two cities which can not be connected through the current flights, output $ \texttt{“-1”} $ .

It’s guaranteed that the chosen combination will be unique.

示例1

输入

1
2
3
4
5
6
7
3 6
1 1 2 1
1 1 3 2
1 2 3 4
1 1 2 8
0 1 2 1
0 2 3 4

输出

1
2
3
4
5
6
-1
2
2
2
2
2

示例2

输入

1
2
3
4
5
4 4
1 1 2 1
1 1 3 2
1 1 4 8
1 2 3 4

输出

1
2
3
4
-1
-1
2
2

说明

First two flights are not enough to make each pair of cities connected.First three flights are enough to make each pair of cities connected. The most flights needed to connect some pair of cities results from connecting city $ 2 $ and city $ 3 $ which needs two flights to connect(so as city $ 2 $ and city $ 4 $ , city $ 3 $ and city $ 4 $ ).The forth flights won’t be included in the chosen combination. The scenario remains the same.

D - Kth Minimum Clique

题目描述

Given a vertex-weighted graph with N vertices, find out the K-th minimum weighted clique.

A subset of vertices of an undirected graph is called clique if and only if every two distinct vertices in the subset are adjacent. The weight of a clique is the summation of the weight of vertices in it.

输入描述

The first line of input contains two space-separated integers $ N $ , $ K $ .

The second line of input contains $ N $ space-separated integers $ w_i $ representing the weight of each vertex.

Following $ N $ lines each contains $ N $ characters $ e_{ij} $ . There’s an edge between vertex $ i $ and vertex $ j $ if and only if $ e_{ij} =\texttt{“1”} $ .

  • $ 1 \leq N \leq 100 $
  • $ 1 \leq K \leq 10^6 $
  • $ 0 \leq w_i \leq 10^9 $
  • $ e_{ij} \in \texttt{“01”} $
  • $ e_{ii} = \texttt{“0”} $
  • $ e_{ij} = e_{ji} $

输出描述

Output one line containing an integer representing the answer. If there’s less than $ K $ cliques, output $ \texttt{“-1”} $ .

示例1

输入

1
2
3
4
2 3
1 2
01
10

输出

1
2

说明

1
An empty set is considered as a clique.

题解

题意

给定一张图,求它权值第 $ k $ 小的完全子图。

解法

完全图的边是已经确定的,那么只需枚举点集即可枚举全部完全子图。

而枚举点集时间复杂度高达 $ \mathcal{O}(2^n) $ ,所以考虑找到一种能够保证权值递增的顺序来遍历这些点集。

考虑初始状态为空集,每次以当前最小状态为基础,拓展出其他可能的点集状态,也就是加一个点构成新状态。

为了防止重复枚举,假定当前最小状态中的点的下标最大为 $ x $ ,那么选择的新的点下标必须大于 $ x $ 。

这样使用优先队列维护这些状态,可以达到 $ \mathcal{O}(k\log_k) $ 的时间复杂度。

同时为了满足完全图的性质,每次加点的时候要验证该点是否与其他点有边,本文采用__int128位掩码判断来优化时间复杂度,当然也可以用bitset

代码

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
#include <bits/stdc++.h>
using namespace std;
#define N 101
#define ll long long
#define Piii pair<ll, pair<int, __int128>>
#define MPiii(a, b, c) make_pair((a), make_pair((b), (c)))
int w[N], n, k;
__int128 v[N], s[N];
priority_queue<Piii, vector<Piii>, greater<Piii>> que;
int main() {
s[0] = 1;
for (int i = 1; i < N; i++) s[i] = s[i - 1] * 2;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
for (int i = 1; i <= n; i++) {
getchar();
for (int j = 1; j <= n; j++) {
char c = getchar();
v[i] = v[i] * 2 + c - '0';
}
}
int num = 0;
que.push(MPiii(0, 0, 0));
while (!que.empty()) {
Piii t = que.top();
que.pop();
if (++num == k) {
printf("%lld\n", t.first);
return 0;
}
for (int i = t.second.first + 1; i <= n; i++)
if ((v[i] & t.second.second) == t.second.second)
que.push(MPiii(t.first + w[i], t.second.first = i,
t.second.second + s[n - i]));
}
printf("-1\n");
return 0;
}

E - MAZE

题目描述

Given a maze with $ N $ rows and $ M $ columns, where $ b_{ij} $ represents the cell on the i-row, j-th column. If $ b_{i, j} = \texttt{“1”} $ , it’s a wall and can’t not be passed. If you are on the cell $ b_{i, j} $ , you can go to $ b_{i+1, j} $ , $ b_{i, j-1} $ , or $ b_{i,j+1} $ as long as it’s not a wall.

Sometime, a cell may be changed into wall, or vise versa. You need to find out the number of way to pass through the maze starting at some given cell and finishing at some given cell.

If the starting cell or finishing cell is a wall, there’s clearly no way to pass through the maze.

Note that you can’t go back to the cell you just from.

输入描述

The first line of input contains three space-separated integers $ N $ , $ M $ , $ Q $ .

Following $ N $ lines each contains M characters $ b_{ij} $ ​ representing the maze .

Following $ Q $ lines each contains three space-separated integers $ q_i, a_i, b_i $ .

If $ q_i = 1 $ , the state of cell $ b_{a_i, b_i} $ is changed.

If $ q_i = 2 $ , you need to find out the number of way to start at cell $ b_{1, a_i} $ ​​ and finish at cell $ b_{N, b_i} $ ​​.

  • $ 1 \leq N, Q \leq 50000 $
  • $ 1 \leq M \leq 10 $
  • $ b_{ij} \in \texttt{“01”} $
  • $ 1 \leq q_i \leq 2 $
  • If $ q_i = 1 $ , $ 1 \leq a_i \leq N $ and $ 1 \leq b_i \leq M $ .
  • If $ q_i = 2 $ , $ 1 \leq a_i, b_i \leq M $ .

输出描述

For each $ q_i = 2 $ , Output one line containing an integer representing the answer module $ 10^9+7(1000000007) $ .

示例1

输入

1
2
3
4
5
6
2 2 3
00
00
2 1 2
1 1 2
2 1 2

输出

1
2
2
1

题解

题意

给定一个 $ n \times m $ 的 $ 01 $ 矩阵,你可以从第一行的某一个点出发,每次可以向左、下和右三个方向移动到为 $ 0 $ 的格点,但是不得重复经过相同的格点。现有 $ m $ 次操作与查询,每次操作给定两个数 $ a $ 和 $ b $ ,表示将格点 $ (a,b) $ 的值反转;每次查询给定两个数 $ a $ 和 $ b $ ,询问你从 $ (1,a) $ 出发,到达 $ (n,b) $ 的方案数量。

解法

令 $ f_{i,j} $ 表示到达格点 $ (i,j) $ 的方案数,令第 $ i $ 行包含 $ (i,j) $ 的最大全 $ 1 $ 区间为 $ [l,r] $ 。

那么有 $ \displaystyle f_{i,j} = \sum_{k=l}^{r} f_{i-1,k} $ ,也就是从上一行转移到这一行。

仔细观察发现这个状态递推式是按行不断更新的,把每一行的 $ f $ 看作一个向量,那么行与行之间的关系可以用一个矩阵来表示,令 $ A_{i} $ 表示第 $ i $ 层向量向下一层拓展的时的矩阵,那么 $ \displaystyle f_{i} = (\prod_{j=1}^{i-1} A_{j}) \times f_{1} $

现在 $ f_{1} $ 已知,那么想要维护这个乘法关系,可以套用线段树维护 $ A $ 的前缀乘积。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 50001
#define inf 0x3f3f3f3f
#define mod 1000000007
int n, m, q;
int mp[N][12];
struct Matrix {
ll s[12][12];
void clear() { memset(s, 0, sizeof(s)); }
};
Matrix Mat_mul(Matrix a, Matrix b, int len) {
Matrix c;
c.clear();
for (int i = 1; i <= len; i++)
for (int j = 1; j <= len; j++)
for (int k = 1; k <= len; k++)
c.s[i][j] = (c.s[i][j] + a.s[i][k] * b.s[k][j]) % mod;
return c;
}
Matrix mul[N << 2], a[N];
void pushup(int rt) { mul[rt] = Mat_mul(mul[rt << 1], mul[rt << 1 | 1], m); }
void build(int l, int r, int rt) {
if (l == r) {
for (int i = 1; i <= m; i++)
for (int j = 1; j <= m; j++) mul[rt].s[i][j] = a[l].s[i][j];
return;
}
int m = (l + r) >> 1;
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
pushup(rt);
}
void update(int pos, int l, int r, Matrix aa, int rt) {
if (l == r) {
for (int i = 1; i <= m; i++)
for (int j = 1; j <= m; j++) mul[rt].s[i][j] = aa.s[i][j];
return;
}
int m = (l + r) >> 1;
if (pos <= m)
update(pos, l, m, aa, rt << 1);
else
update(pos, m + 1, r, aa, rt << 1 | 1);
pushup(rt);
}
char c[12];
int main() {
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++) {
scanf("%s", c + 1);
for (int j = 1; j <= m; j++) mp[i][j] = c[j] - '0';
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
for (int k = j, add = 1; k >= 1; k--) {
if (mp[i][k]) add = 0;
a[i].s[k][j] = add;
}
for (int k = j, add = 1; k <= m; k++) {
if (mp[i][k]) add = 0;
a[i].s[k][j] = add;
}
}
build(1, n, 1);
while (q--) {
int kind, x, y;
scanf("%d%d%d", &kind, &x, &y);
if (kind == 1) {
mp[x][y] = !mp[x][y];
for (int j = 1; j <= m; j++) {
for (int k = j, add = 1; k >= 1; k--) {
if (mp[x][k]) add = 0;
a[x].s[k][j] = add;
}
for (int k = j, add = 1; k <= m; k++) {
if (mp[x][k]) add = 0;
a[x].s[k][j] = add;
}
}
update(x, 1, n, a[x], 1);
} else {
Matrix ans;
ans.clear();
ans.s[1][x] = 1;
ans = Mat_mul(ans, mul[1], m);
printf("%lld\n", ans.s[1][y]);
}
}
return 0;
}

F - Partition problem

题目描述

Given $ 2N $ people, you need to assign each of them into either red team or white team such that each team consists of exactly $ N $ people and the total competitive value is maximized.

Total competitive value is the summation of competitive value of each pair of people in different team.

The equivalent equation is $ \displaystyle\sum_{i=1}^{2N} \sum_{j=i+1}^{2N} $ ( $ v_{ij} $ if $ i $ -th person is not in the same team as j-th person else $ 0 $ )

输入描述

The first line of input contains an integers $ N $ .

Following $ 2N $ lines each contains $ 2N $ space-separated integers $ v_{ij} $ is the j-th value of the i-th line which indicates the competitive value of person i and person j.

  • $ 1 \leq N \leq 14 $
  • $ 0 \leq v_{ij} \leq 10^{9} $
  • $ v_{ij} = v_{ji} $

输出描述

Output one line containing an integer representing the maximum possible total competitive value.

示例1

输入

1
2
3
1
0 3
3 0

输出

1
3

题解

题意

给定2n个人,将其分为人数相同的两组。任意两个人 $ i $ 和 $ j $ 若不在同一组都会产生 $ val_{i,j} $ 的价值。现已知 $ val $ 表,询问你最大价值和为多少。

解法

n不超过14,因此可以暴力枚举分组情况,对于每一种情况,计算当前情况的价值。

时间复杂度 $ \mathcal{O}( \tbinom{n}{2n-1} \times n) $ ,最坏情况下大约 $ 3e8 $ ,刚好卡过 $ 4s $ 时限。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[30][30], n, m;
int d1[16], d2[16];
int num1, num2;
ll Sum1, Sum2, Sum, ans;
void search(int x) {
if (x > m) {
ans = max(ans, Sum - Sum1 - Sum2);
return;
}
if (num1 < n) {
d1[++num1] = x;
ll sum = 0;
for (int i = 1; i < num1; i++) sum += a[d1[i]][x];
Sum1 += sum;
search(x + 1);
Sum1 -= sum;
num1--;
}
if (num2 < n) {
d2[++num2] = x;
ll sum = 0;
for (int i = 1; i < num2; i++) sum += a[d2[i]][x];
Sum2 += sum;
search(x + 1);
Sum2 -= sum;
num2--;
}
}
int main() {
scanf("%d", &n);
m = 2 * n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
if (i > j) Sum += a[i][j];
}
d1[1] = 1;
num1 = 1;
search(2);
printf("%lld\n", ans);
return 0;
}

G - Polygons

题目描述

Lines make polygons. Given $ N $ lines, please tell how many closed polygons are formed by these $ N $ straight lines and what is the largest and smallest area of them? Moreover, could you tell $ q_i $ -th largest area?

输入描述

The first line of input contains an integers $ N $ indicating the number of lines.

Following $ N $ lines each contains four space-separated integers $ x_1, y_1, x_2, y_2 $ ​ indicating two points on the i-th line.

The next line contains an integer $ M $ indicating the number of questions.

Following $ M $ lines each contains an integer $ q_i $ ​.

  • $ 3 \leq N \leq 1000 $
  • $ 1 \leq M \leq 10000 $
  • $ |x_i|, |y_i| \leq 1000 $
  • $ 1 \leq q_i \leq 10^9 $

No three lines intersect in one point

No two lines coincide

There is at least $ 1 $ closed polygon

输出描述

First output a single line containing three numbers, the number of closed polygons, the largest area and the smallest area.

Then, output m lines each contains a number indicating $ q_i $ ​-th largest area.

If $ q_i $ ​ is greater than the number of polygons, output $ \texttt{“Invalid question”} $ (without quotes) instead.

Your answer will be considered correct if its absolute or relative error doesn’t exceed $ 10^{-4} $

示例1

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
6
1 1 0 2
1 3 0 4
1 6 0 7
1 3 0 2
1 -1 0 -2
1 4 0 4
7
1
2
3
4
5
6
7

输出

1
2
3
4
5
6
7
8
6 5.75 0.25
5.75
4.0
3.0
2.25
1.0
0.25
Invalid question

H - Second Large Rectangle

题目描述

Given a $ N \times M $ binary matrix. Please output the size of second large rectangle containing all $ \texttt{“1”} $ .

Containing all $ \texttt{“1”} $ means that the entries of the rectangle are all $ \texttt{“1”} $ .

A rectangle can be defined as four integers $ x_1, y_1, x_2, y_2 $ where $ 1 \leq x_1 \leq x_2 \leq N $ and $ 1 \leq y_1 \leq y_2 \leq M $ . Then, the rectangle is composed of all the cell $ (x, y) $ where $ x_1 \leq x \leq x_2 $ and $ y_1 \leq y \leq y2 $ . If all of the cell in the rectangle is $ \texttt{“1”} $ , this is a valid rectangle.

Please find out the size of the second largest rectangle, two rectangles are different if exists a cell belonged to one of them but not belonged to the other.

输入描述

The first line of input contains two space-separated integers $ N $ and $ M $ .

Following $ N $ lines each contains $ M $ characters $ c_{ij} $ ​.

  • $ 1 \leq N, M \leq 1000 $
  • $ N \times M \geq 2 $
  • $ c_{ij} \in \texttt{“01”} $

输出描述

Output one line containing an integer representing the answer. If there are less than $ 2 $ rectangles containning all $ \texttt{“1”} $ , output $ \texttt{“0”} $ .

示例1

输入

1
2
1 2
01

输出

1
0

示例2

输入

1
2
1 3
101

输出

1
1

题解

题意

给定一个 $ 01 $ 矩阵,询问其中次大全 $ 1 $ 矩阵的面积。

解法

用最大全 $ 1 $ 矩阵的模板改一下即可。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define N 1010
int l[N], r[N], f[N][N], n, m;
char c[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", c + 1);
for (int j = 1; j <= m; j++)
f[i][j] = (c[j] == '1') ? f[i - 1][j] + 1 : 0;
}
int ans1 = 0, ans2 = 0, sign1 = 0, sign2 = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) l[j] = r[j] = j;
f[i][0] = f[i][m + 1] = -1;
for (int j = 1; j <= m; j++)
while (f[i][j] <= f[i][l[j] - 1]) l[j] = l[l[j] - 1];
for (int j = m; j >= 1; j--)
while (f[i][j] <= f[i][r[j] + 1]) r[j] = r[r[j] + 1];
for (int j = 1; j <= m; j++)
if (f[i][j]) {
int t = (r[j] - l[j] + 1) * f[i][j];
if (t > ans1)
ans2 = max(ans1, t - min(r[j] - l[j] + 1, f[i][j])),
ans1 = t, sign1 = r[j], sign2 = i;
else if (t > ans2 && (sign1 != r[j] || sign2 != i))
ans2 = t;
}
}
printf("%d\n", ans2);
return 0;
}

I - Inside A Rectangle

题目描述

Given $ N \times M $ grid, each cell has a value $ a_{ij} $ , you can choose at most two rectangles such that sum of values of the cell belonging to $ \textbf{exactly} $ one rectangle is maximized.

A rectangle can be defined as four integers $ x_1, y_1, x_2, y_2 $ where $ 1 \leq x_1 \leq x_2 \leq N $ and $ 1 \leq y_1 \leq y_2 \leq M $ . Then, the rectangle is composed of all the cell $ (x, y) $ where $ x_1 \leq x \leq x_2 $ and $ y_1 \leq y \leq y2 $ .

After choosing the rectangles, the resulting value will be the sum of values of the cell belonging to $ \textbf{exactly} $ one of them.

输入描述

The first line of input contains two space-separated integers $ N $ and $ M $ .

Following N lines each contains M space-separated integers $ a_{ij} $ ​.

  • $ 1 \leq N, M \leq 50 $
  • $ -10^5 \leq a_{ij} \leq 10^5 $

输出描述

Output one line containing an integer representing the answer.

示例1

输入

1
2
3
4
5
6
5 5
10 10 10 10 -1
10 -1 -1 -1 10
10 -1 -1 -1 10
10 -1 -1 -1 10
-1 10 10 10 10

输出

1
140

J - Subarray

题目描述

Given an array A of length $ 10^9 $ containing only $ 1 $ and $ -1 $ . The number of 1 is not more than $ 10^7 $ .
Please count how many pairs of $ (l, r) $ satisfy $ \sum\limits_{i=l}^r A_i > 0 $ and $ 0 \leq l \leq r < 10^9 $ .

输入描述

The first line of input contains an integers $ N $ indicating how many segments of $ A $ is $ 1 $ .
Following $ N $ lines each contains two space-separated integers $ l_i, r_i $ ​ indicating that $ A_j $ ​ is $ 1 $ for $ l_i \leq j \leq r_i $ ​

  • $ 0 < n \leq 10^6 $
  • $ l_i \leq r_i $
  • $ r_i + 1 < l_{i+1} $ for $ 0 \leq i < n - 1 $
  • $ 0 \leq l_0 $
  • $ r_{n-1} < 10^9 $
  • $ \sum (r_i - l_i + 1) \leq 10^7 $

输出描述

Output one line containing an integer representing the answer.

示例1

输入

1
2
1
0 1

输出

1
4

示例2

输入

1
2
1
1 2

输出

1
16

题解

题意

给定一个 $ (1,-1) $ 序列,长度不超过 $ 1e9 $ ,下标从 $ 0 $ 开始。已知有 $ n $ 个区间为 $ 1 $ ,其余为 $ -1 $ ,询问你存在多少区间满足其区间和 $ > 1 $ 。

解法

已知为 $ 1 $ 的点最多 $ 1e7 $ 个,那么可能作为区间端点的点至多有 $ 3e7 $ 个

那么令 $ f_{i} $ 表示第 $ i $ 个区间右端点为答案右端点的最大区间和,令 $ g_{i} $ 表示第 $ i $ 个区间左端点为答案左端点的最大区间和

所以有公式:

  • $ f_{i} = max(0,f_{i-1}-(l_{i}-r_{i-1}-1))+r_{i}-l_{i}+1 $
  • $ g_{i} = max(0,g_{i+1}-(l_{i+1}-r_{i}-1))+r_{i}-l_{i}+1 $

如果 $ f_{i}+g_{i+1} \leq l_{i+1}-r_{i}-1 $ ,那么此时答案的左右端点可以跨越到旁边的区间,把这些区间合并考虑。

此时问题的规模即可缩小到 $ 1e7 $

那么此时只需从右到左枚举左端点,统计右边比当前值大的个数。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define N 30000005
#define M 1000005
int l[M], r[M], f[M], g[M];
int sum[N], b[N], c[N], n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &l[i], &r[i]);
f[1] = r[1] - l[1] + 1;
for (int i = 2; i <= n; i++)
f[i] = max(0, f[i - 1] - (l[i] - r[i - 1] - 1)) + r[i] - l[i] + 1;
g[n] = r[n] - l[n] + 1;
for (int i = n - 1; i >= 1; i--)
g[i] = max(0, g[i + 1] - (l[i + 1] - r[i] - 1)) + r[i] - l[i] + 1;
int i = 1, base = 10000000;
ll ans = 0;
while (i <= n) {
int j = i + 1;
while (j <= n && g[j] + f[j - 1] >= l[j] - r[j - 1] - 1) j++;
j--;
int left = max(0, l[i] - g[i]),
right = min(1000000000 - 1, r[j] + f[j]);
int t = i, mi = INF, mx = 0;
sum[0] = 0;
for (int k = left; k <= right; k++) {
if (k >= l[t] && k <= r[t])
sum[k - left + 1] = sum[k - left] + 1;
else
sum[k - left + 1] = sum[k - left] - 1;
if (k == r[t]) t++;
mi = min(mi, sum[k - left + 1] + base);
mx = max(mx, sum[k - left + 1] + base);
b[sum[k - left + 1] + base]++;
}
for (int k = mx - 1; k >= mi; k--) b[k] += b[k + 1];
ans += b[base + 1];
for (int k = left; k <= right; k++) {
t = sum[k - left + 1] + base;
b[t + 1] -= c[t + 1];
c[t] += c[t + 1] + 1;
c[t + 1] = 0;
ans += b[t + 1];
}
for (int k = mi; k <= mx; k++) b[k] = 0, c[k] = 0;
i = j + 1;
}
printf("%lld", ans);
return 0;
}