【LGR-266-Div.2】洛谷 2 月月赛 I &「CROI」Round 3 简要题解

这个 Div2 怎么这么简单，1.25h 就 AK 了。

比赛链接：【LGR-266-Div.2】洛谷 2 月月赛 I &「CROI」Round 3 – 洛谷 | 计算机科学教育新生态

A – 浣熊的快车道

浣熊岭高速公路上有

n

n

n 条车道，一辆车经过第

i

i

i 条车道，需要支付

a

i

a_i

ai​ 的通行费。

有

m

m

m 辆车想要上高速，你需要给每辆车分配合适的车道。每辆车只能选择一条车道且中途不能变道。另外，为了保证道路畅通，分配完成后，第

i

i

i 辆车所在车道的车数不能超过

b

i

b_i

bi​。

求所有车辆的最小通行费总和，如果无解请输出

−

1

-1

−1。

1

≤

n

,

m

≤

10

5

,

1

≤

a

i

,

b

i

≤

10

9

1\\le n,m\\le 10^5,1\\le a_i,b_i\\le 10^9

1≤n,m≤105,1≤ai​,bi​≤109。

我们肯定希望费用小的车道塞入尽可能多的车。

那么我们可以将

b

i

b_i

bi​ 从大到小排序，

a

j

a_j

aj​ 从小到大排序，每次二分出一个前缀

1

∼

i

1 \\sim i

1∼i，使得将

b

1

∼

b

i

b_1 \\sim b_i

b1​∼bi​ 塞入这个车道

j

j

j 是合法的，然后计算贡献，并把

b

1

∼

b

i

b_1 \\sim b_i

b1​∼bi​ 给删掉。

时间复杂度

O

(

n

log

⁡

n

+

(

n

+

m

)

log

⁡

m

)

O(n \\log n + (n + m) \\log m)

O(nlogn+(n+m)logm)。

#include <bits/stdc++.h>
using namespace std;

const int N = 100000;

int n, m;
long long a[N + 10], b[N + 10];

int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 1; i <= m; ++i) cin >> b[i];
sort(b + 1, b + m + 1, greater<long long>());
for (int i = 1; i <= m; ++i) b[i] = i – b[i];
long long now = 0LL, ans = 0LL;
for (int i = 1; i <= n && now < m; ++i) {
long long p = upper_bound(b + now + 1, b + m + 1, now) – b – 1;
if (p > now) {
ans += a[i] * (p – now); now = p;
}
}
if (now < m) cout << –1;
else cout << ans;
return 0;
}

B – 浣熊的蒲公英

浣熊把蒲公英的密码翻译成了表达式。

这个表达式中有

n

n

n 个正整数和

n

−

1

n-1

n−1 个运算符，运算符仅包括 +、-、*，不包含括号。运算规则与一般数学表达式相同。

请首先帮助浣熊求出未修改时表达式的运算结果（对

10

9

+

7

10^9+7

109+7 取模）。

由于风的作用，蒲公英的密码会悄然改变。因此有

q

q

q 次对表达式中符号的修改，对于每

i

i

i 次修改，你会得到一个整数

k

(

1

≤

k

<

n

)

k\\ (1\\leq k < n)

k (1≤k<n) 和一个字符

c

c

c（

c

c

c 为 + 或 – 或 *）：

• 若从左往右第

  k

  k

  k 个符号为 * 且

  c

  c

  c 不为 *，则将该符号修改为

  c

  c

  c，并输出修改后的表达式结果（对

  10

  9

  +

  7

  10^9+7

  109+7 取模）；

• 否则不进行操作与输出。

请注意，修改之间不独立（即每次修改操作后，在后面的运算时保留这次修改后的符号）。

2

≤

n

≤

10

5

2\\leq n \\leq 10^5

2≤n≤105，

∀

i

∈

[

1

,

n

]

,

1

≤

a

i

≤

10

9

{\\forall}i\\in[1,n],1\\leq a_i \\leq 10^9

∀i∈[1,n],1≤ai​≤109。

1

≤

q

≤

10

5

1\\leq q\\leq 10^5

1≤q≤105，在每次询问中，

1

≤

k

<

n

1\\leq k < n

1≤k<n，

c

c

c 为 +、- 或 *。

设所有正整数为

a

i

a_i

ai​，

a

i

−

1

a_{i – 1}

ai−1​ 与

a

i

a_i

ai​ 之间的符号位

o

p

t

i

opt_i

opti​，定义一个极长连乘段为不能扩展的

[

l

,

r

]

[l, r]

[l,r] 使得

∀

i

∈

[

l

,

r

)

,

o

p

t

i

=

∗

\\forall i \\in [l, r), opt_i = *

∀i∈[l,r),opti​=∗。

那么设当前的答案为

a

n

s

ans

ans，每次修改，我们找到

o

p

t

k

opt_k

optk​ 所在的极长连乘段

[

l

,

r

]

[l, r]

[l,r]，并将

a

n

s

ans

ans 减去

[

l

,

r

]

[l, r]

[l,r] 的贡献，然后加上

[

l

,

k

]

[l, k]

[l,k] 和

[

k

+

1

,

r

]

[k + 1, r]

[k+1,r] 的贡献。

一个连乘段的贡献可以通过前缀积得出，时间复杂度 $O(|S| + (n + q) \\log n) $。

#include <bits/stdc++.h>
using namespace std;

const int N = 100000;
const long long mod = 1000000007LL;

long long q_pow(long long u, long long v) {
long long res = 1LL;
while (v) {
if (v & 1LL) res = res * u % mod;
u = u * u % mod, v >>= 1;
}
return res;
}

long long Inv(long long u) {
return q_pow(u, mod – 2LL);
}

int n, q; string s;
vector<long long> val, opt;
long long pre[N + 10], invpre[N + 10];
set<int> bond;

long long get(int l, int r) {
if (l > r) return 1LL;
return pre[r] * invpre[l – 1] % mod;
}

int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> s >> q;
val.push_back(0LL), opt.push_back(1LL);
long long sum = 0LL;
for (int i = 0; i < s.size(); ++i) {
if ('0' <= s[i] && s[i] <= '9') sum = (sum * 10LL + (long long)s[i] – (long long)'0') % mod;
else {
val.push_back(sum); sum = 0LL;
if (s[i] == '+') opt.push_back(1LL);
else if (s[i] == '-') opt.push_back(–1LL);
else opt.push_back(0LL);
}
}
val.push_back(sum);
n = val.size() – 1, pre[0] = invpre[0] = 1LL;
for (int i = 1; i <= n; ++i) {
pre[i] = pre[i – 1] * val[i] % mod; invpre[i] = Inv(pre[i]);
}
for (int i = 1; i < n; ++i) if (opt[i] != 0LL) bond.insert(i);
long long ans = 0LL; int lst = 1;
for (int i = 1; i < n; ++i) {
if (opt[i] == 0LL) continue;
ans = (ans + opt[lst – 1] * get(lst, i) + mod) % mod; lst = i + 1;
}
ans = (ans + opt[lst – 1] * get(lst, n) + mod) % mod;
cout << ans << '\\n';
while (q—) {
int k; char c; cin >> k >> c;
if (c == '*' || opt[k] != 0LL) continue;
set<int>::iterator it = bond.lower_bound(k);
int r = it == bond.end() ? n : *it, l = it == bond.begin() ? 1 : (*prev(it) + 1);
ans = (ans – opt[l – 1] * get(l, r) + mod) % mod;
ans = (ans + opt[l – 1] * get(l, k) + mod) % mod;
ans = (ans + (c == '+' ? 1LL : –1LL) * get(k + 1, r) + mod) % mod;
bond.insert(k), opt[k] = c == '+' ? 1LL : –1LL;
cout << ans << '\\n';
}
return 0;
}

C – 浣熊的长木桥

一个木桥的长度为

n

n

n，桥面可以看作一个

2

2

2 行

n

n

n 列的方格纸。

施工队共有五种不同形状的砖块，形状如下图所示。

现在你需要用这五种砖块来建造这座桥，使得桥面上的所有方格都被砖块填充且砖块之间不重叠。

不过，善良的小浣熊已经把方格内

m

m

m 个

1

×

1

1\\times 1

1×1 的位置填上了，这些位置不需要也不允许再被砖块填充。第

i

i

i 个被填上的方格位于第

x

i

x_i

xi​ 行，第

y

i

y_i

yi​ 列。请你计算，使用上述五种砖块填充剩余方格的方案数，模

10

9

+

7

10^9+7

109+7 的结果。

数据保证这

m

m

m 个位置互不相同。

1

≤

n

≤

10

18

1\\leq n\\leq 10^{18}

1≤n≤1018，

0

≤

m

≤

min

⁡

(

2

n

,

2

×

10

4

)

0\\leq m\\leq \\min(2n,2\\times 10^4)

0≤m≤min(2n,2×104)，

1

≤

x

≤

2

,

1

≤

y

≤

n

1\\leq x\\leq 2,1\\leq y\\leq n

1≤x≤2,1≤y≤n。

这种看起来就像矩阵乘法优化 dp，我们先考虑没有已填充砖块的时候是怎么做的。

考虑状压 dp，设

d

p

(

i

,

S

)

dp(i, S)

dp(i,S) 表示考虑了前

i

i

i 列，第

i

i

i 列填的方格的 bitmask 为

S

S

S 的方案数。

转移方程写成矩阵就是：

(

d

p

(

i

,

0

)

d

p

(

i

,

1

)

d

p

(

i

,

2

)

d

p

(

i

,

3

)

)

×

(

1

1

1

2

1

0

0

0

1

0

0

1

1

0

0

0

)

=

(

d

p

(

i

+

1

,

0

)

d

p

(

i

+

1

,

1

)

d

p

(

i

+

1

,

2

)

d

p

(

i

+

1

,

3

)

)

\\begin{pmatrix} dp(i, 0) \\\\ dp(i, 1) \\\\ dp(i, 2) \\\\ dp(i, 3) \\end{pmatrix} \\times \\begin{pmatrix} 1 & 1 & 1 & 2 \\\\ 1 & 0 & 0 & 0 \\\\ 1 & 0 & 0 & 1 \\\\ 1 & 0 & 0 & 0 \\end{pmatrix} = \\begin{pmatrix} dp(i + 1, 0) \\\\ dp(i + 1, 1) \\\\ dp(i + 1, 2) \\\\ dp(i + 1, 3) \\end{pmatrix}

​dp(i,0)dp(i,1)dp(i,2)dp(i,3)​

​×

​1111​1000​1000​2010​

​=

​dp(i+1,0)dp(i+1,1)dp(i+1,2)dp(i+1,3)​

​

那么对于没有已填充方格就直接矩阵快速幂，对于有填充方格就停下来特判（也是套路，具体可以看代码）。

时间复杂度

O

(

V

2

m

log

⁡

n

)

O(V^2 m \\log n)

O(V2mlogn)，其中

V

=

4

V = 4

V=4。

#include <bits/stdc++.h>
using namespace std;

const long long mod = 1000000007LL;

struct Matrix {
long long a[4][4];
Matrix() {memset(a, 0, sizeof(a));}
void init() {for (int i = 0; i < 4; ++i) a[i][i] = 1LL;}
Matrix operator * (Matrix &other) const {
Matrix res;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
for (int k = 0; k < 4; ++k) {
res.a[i][j] = (res.a[i][j] + a[i][k] * other.a[k][j]) % mod;
}
}
}
return res;
}
};

struct Matrix2 {
long long a[4];
Matrix2() {memset(a, 0, sizeof(a));}
};

Matrix2 mul(Matrix2 u, Matrix v) {
Matrix2 res;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
res.a[i] = (res.a[i] + u.a[j] * v.a[j][i]) % mod;
}
}
return res;
}

long long n; int m;
map<long long, int> mp;
Matrix pre[70];

Matrix2 q_pow(Matrix2 res, long long v) {
int cnt = 0;
while (v) {
if (v & 1LL) res = mul(res, pre[cnt]);
++cnt, v >>= 1;
}
return res;
}

int main() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x; long long y; cin >> x >> y;
mp[y] |= 1 << (x – 1);
}
Matrix tran; Matrix2 base; base.a[0] = 1LL;
tran.a[0][0] = 1, tran.a[0][1] = 1, tran.a[0][2] = 1, tran.a[0][3] = 2;
tran.a[1][0] = 1, tran.a[1][1] = 0, tran.a[1][2] = 0, tran.a[1][3] = 1;
tran.a[2][0] = 1, tran.a[2][1] = 0, tran.a[2][2] = 0, tran.a[2][3] = 1;
tran.a[3][0] = 1, tran.a[3][1] = 0, tran.a[3][2] = 0, tran.a[3][3] = 0;
pre[0] = tran;
for (int i = 1; i <= 65; ++i) pre[i] = pre[i – 1] * pre[i – 1];
long long lst = 1LL;
for (pair<long long, int> tmp : mp) {
long long y = tmp.first; int x = tmp.second;
if (y > lst) base = q_pow(base, y – lst);
Matrix2 nxt;
for (int s = 0; s < 4; ++s) {
if (!base.a[s]) continue;
if ((s & x) == 0) nxt.a[s | x] = (nxt.a[s | x] + base.a[s]) % mod;
}
base = nxt, lst = y;
}
base = q_pow(base, n + 1LL – lst);
cout << base.a[0];
return 0;
}

D – 浣熊的小游戏

有

q

q

q 次询问，每次询问给出

l

,

r

l,r

l,r，求出

[

l

,

r

]

[l,r]

[l,r] 值域范围内选偶数个互不相同的数进行异或可以得到多少种不同的值。规定异或和为

0

0

0 不计入总数。

对于所有的数据，均有

1

≤

l

≤

r

≤

10

18

,

1

≤

q

≤

10

6

1\\le l\\le r\\le 10^{18},1\\le q\\le 10^6

1≤l≤r≤1018,1≤q≤106 。

由于异或的特性，不难发现这等价于集合

S

=

{

l

⊕

(

l

+

1

)

,

⋯
 

,

(

r

−

1

)

⊕

r

}

S = \\{l \\oplus (l + 1), \\cdots, (r – 1) \\oplus r\\}

S={l⊕(l+1),⋯,(r−1)⊕r} 中选任意个数的进行异或得到的值的数量。

而

x

⊕

(

x

+

1

)

x \\oplus (x + 1)

x⊕(x+1) 有很好的性质，即

x

⊕

(

x

+

1

)

=

2

k

−

1

x \\oplus (x + 1) = 2^k – 1

x⊕(x+1)=2k−1，其中

k

k

k 为二进制下

x

+

1

x + 1

x+1 末尾的

0

0

0 的个数。

那么我们就要对于每个

k

k

k，统计

[

l

+

1

,

r

]

[l + 1, r]

[l+1,r] 中是否存在

x

x

x 使得

x

x

x 是

2

k

2^k

2k 的倍数，且不是

2

k

+

1

2^{k + 1}

2k+1 的倍数。这个很 trivial（具体看代码）。

时间复杂度

O

(

q

log

⁡

V

)

O(q \\log V)

O(qlogV)。

#include <bits/stdc++.h>
using namespace std;

int q;

int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> q;
while (q—) {
long long l, r; cin >> l >> r; ++l;
if (l > r) {cout << 0 << '\\n'; continue;}
long long ans = 1LL;
for (int i = 0; i <= 61; ++i) {
long long d = 1LL << i; if (d > r) break;
long long mi = (l + d – 1LL) / d, ma = r / d;
if (mi < ma || (mi == ma && mi & 1)) ans <<= 1;
}
cout << ans – 1LL << '\\n';
}
return 0;
}