Namomo Spring Camp 2022 Div1 每日一题记录 (Week 2)

发表于 更新于 分类于 ， 本文字数： 3.3k 阅读时长 ≈ 12 分钟

Namomo Spring Camp 2022 Div1 每日一题记录 (2022.03.05-2022.03.11)

摘桃子

题目链接

1 s, 1024 MB

桃园里面有 \(n\) 个人在摘桃子。现在 \(n\) 个人排成一排，从左到右每个人拥有的桃子数是 \(a_i\). 桃园里有一个免费获得桃子的规则，如果连续 \(x\) 个人的桃子总数除以 \(k\) 的余数正好是 \(x\), 那么这 \(x\) 个人就可以免费获得桃子，并且每天只有一次免费获得桃子的机会。请聪明的你算出一共有多少种不同的方案可以使今天有人免费获得桃子

输入格式

第一行两个数字 \(n\), \(k\)

接下来一行 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)

输出格式

一个数，表示答案

样例输入

1
2
8 4
4 2 4 2 4 2 4 2

样例输出

1
7

NOTE

七个不同方案分别是: \(a_1, a_2\), \(a_2, a_3\), \(a_3, a_4\), \(a_4, a_5\), \(a_5, a_6\), \(a_6, a_7\), \(a_7, a_8\). 注：只要子串有一个边界不同即为不同的方案

数据规模

所有数据保证 \(1\leq n\leq 2 × 10^5, 1 \leq k \leq 10^9, 1 \leq a_i \leq 10^9\)

解题思路

这个区间和有个处理的套路：所有数都减 1, 处理之后要求就变成了 区间和模 \(k\) 为 \(0\)

然后就是经典板子题了

复杂度

\(O(n\log n)\) (使用 map)

代码参考

Show code

Daimayuan_466view raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
const uint32_t N = 2e5 + 5;
map<i64, int> mp;
i64 a[N], s[N];
int main() {
  int n, k;
  cin >> n >> k;
  _for(i, 1, n) cin >> a[i];
  _for(i, 1, n) s[i] = ((s[i - 1] + a[i] - 1) % k + k) % k;
  i64 ans = 0, l = 0;
  mp[0] = 1;
  _for(i, 1, n) {
    if (l <= i - k) {
      if (mp[s[l]] > 0) --mp[s[l]];
      ++l;
    }
    ans += mp[s[i]]++;
  }
  cout << ans;
  return 0;
}

路径计数 2 (CF559C)

题目链接

1 s, 512 MB

有一个 \(n * n\) 的网格，有些格子是可以通行的，还有 \(m\) 个格子是障碍

一开始你在左上角的位置，你可以每一步往下或者往右走，问有多少种走到右下角的方案

由于答案很大，输出对 \(10^9+7\) 取模的结果

输入格式

第一行两个数字 \(n\), \(m\)

接下来 \(m\) 行，每行 \(2\) 个整数 \(x_i , y_i\), 代表第 \(i\) 个障碍的坐标

输出格式

一个数，表示答案

样例输入

1
2
2 1
2 1

样例输出

1
1

数据规模

所有数据保证 \(1\leq n\leq 10^6,1 \leq m \leq 3000,1 \leq x_i,y_i \leq n\)

解题思路

显然是容斥

令

  • 第 \(i\) 个障碍物的坐标为 \((x_i,y_i)\)
  • \(f_i\) 为从 \((1,1)\) 走到第 \(i\) 个障碍物合法方案

显然

\[ f_i=\binom{x_i+y_i-2}{x_i-1}-\sum_{x_i\geq x_j; y_i\geq y_j}\binom{x_i+y_i-x_j-y_j}{x_i-x_j}f_j \]

复杂度

\(O(m^2)\)

代码参考

Show code

CodeForces_559Cview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using pii = pair<int, int>;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
#define _rfor(i, r, l, vals...)                                      \
  for (make_signed_t<decltype(r - l)> i = (r), i##end = (l), ##vals; \
       i >= i##end;                                                  \
       --i)
const uint32_t OFFSET = 5;
const uint32_t N = 2e5 + OFFSET, M = 2e3 + OFFSET;
const i64 MOD = 1e9 + 7;
template <typename Tp = i64>
constexpr Tp qpow(Tp a, Tp b = MOD - 2, const Tp &mod = MOD) {
  Tp res(1);
  for (; b; b >>= 1, (a *= a) %= mod)
    if (b & 1) (res *= a) %= mod;
  return res;
}
i64 frac[N * 2], ffrac[N], inv[N];
auto __ = []() {
  ffrac[0] = frac[0] = inv[0] = frac[1] = inv[1] = 1;
  _for(i, 2, 2 * N - 1) frac[i] = frac[i - 1] * i % MOD;
  _for(i, 1, N - 1) ffrac[i] = ffrac[i - 1] * frac[i] % MOD;
  i64 _ = qpow(ffrac[N - 1]);
  _rfor(i, N - 1, 2) {
    inv[i] = _ * ffrac[i - 1] % MOD;
    _ = _ * frac[i] % MOD;
  }
  return 0;
}();
auto m_choose_n(int m, int n) -> i64 {
  return m < n ? 0 : frac[m] * inv[n] % MOD * inv[m - n] % MOD;
}
pii obstruct[M];
i64 f[N];
void solve() {
  int h, w, m;
  cin >> h >> w >> m;
  _for(i, 1, m) cin >> obstruct[i].first >> obstruct[i].second;
  obstruct[m + 1] = {h, w};
  sort(obstruct + 1, obstruct + m + 1);
  _for(i, 1, m + 1) {
    auto &obsi = obstruct[i];
    f[i] = m_choose_n(obsi.first + obsi.second - 2, obsi.first - 1);
    if (!f[i]) continue;
    _for(j, 1, i - 1) {
      auto &obsj = obstruct[j];
      if (obsj.first > obsi.first || obsj.second > obsi.second) continue;
      (((f[i] -= f[j] *
                 m_choose_n(obsi.first - obsj.first + obsi.second - obsj.second,
                            obsi.first - obsj.first) %
                 MOD) %= MOD) += MOD) %= MOD;
    }
  }
  cout << f[m + 1];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

函数求和

题目链接

1 s, 1024 MB

给定 \(n\) 个整数 \(a_1, a_2, \dots, a_n\) 和正整数 \(k\) 满足 \((0 \leq a_i \leq 2^k - 1)\)

定义函数 \(f(x)\) 为满足 \(a_i \& x \neq a_i\) 的最小的 \(i\), 当满足条件的 \(i\) 不存在时 \(f(x)=0\)

求 \(\sum_{i = 0}^{2^k - 1}f(i)\). 由于答案可能很大，输出答案取模 \(998244353\) 后的值

输入格式

第一行两个数字 \(n\), \(k\)

接下来一行 \(n\) 个整数 \(a_1, a_2, \dots, a_n\), 表示这 \(n\) 个数

输出格式

一行一个整数，表示答案

样例输入 1

1
2
2 1
0 1

样例输出 1

1
2

样例输入 2

1
2
2 2
2 1

样例输出 2

1
4

样例输入 3

1
2
5 10
389 144 883 761 556

样例输出 3

1
1118

样例解释

对于样例 1, \(f(0) = 2\), \(f(1) = 0\), 答案 \(= 2\)

数据规模

所有数据保证 \(1\leq n \leq 100, 1 \leq k \leq 60\)

解题思路

今天的题好水

乘法原理拼一下就完事了

复杂度

\(O(nk)\)

代码参考

Show code

Daimayuan_468view raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
const uint32_t N = 101;
const uint32_t MOD = 998244353;
i64 a[N];
int a_cnt;
int main() {
  int n, k;
  cin >> n >> k;
  _for(i, 1ll, n) cin >> a[i];
  __int128_t ans = 0;
  i64 _1 = 0, _1pre = 0;
  _for(i, 1, n) {
    _1pre = _1;
    _1pre ^= _1 |= a[i];
    ans += (1ll << (k - __builtin_popcountll(_1))) *
           ((1ll << __builtin_popcountll(_1pre)) - 1) * i;
  }
  cout << (i64)(ans % MOD);
}

XOR Inverse (CF1416C)

题目链接

2 s, 512 MB

题目描述

给你一个有 \(n\) 个非负整数组成的数组 \(a\), 你需要选择一个非负整数 \(x\), 对数组 \(a\) 的每一个 \(a_i\) 与 \(x\) 进行异或后形成新的数组 \(b\), 要求 \(b\) 数组的逆序对个数最小，如果有多个 \(x\) 满足条件，输出最小的 \(x\)

一个逆序对指 \(b\) 数组内对于整数 \(i,j\) 满足条件 \(1\leq i < j \leq n\) 且 \(b_i > b_j\)

输入格式

第一行一个正整数 \(n\)

接下来一行 \(n\) 个非负整数 \(a_1,a_2,\dots,a_n\)

输出格式

两个数: \(b\) 数组的最小逆序对数和此时 \(x\) 的最小值

样例输入 #1

1
2
4
0 1 3 2

样例输出 #1

1
1 0

样例输入 #2

1
2
9
10 7 9 10 7 5 5 3 5

样例输出 #2

1
4 14

样例输入 #3

1
2
3
8 10 3

样例输出 #3

1
0 8

数据范围

\(1\leq n\leq 3\cdot 10^5\), \(0\leq a_i\leq 10^9\)

解题思路

01-trie

将数按顺序插入 01-trie 中，并在插入的结点处记录插入的数的下标，由于 01-trie 中同一层的右儿子代表的数严格大于左儿子的，所以可以根据这个来计算逆序对

复杂度

\(O(n\log n)\)

代码参考

Show code

CodeForces_1416Cview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
#define _rfor(i, r, l, vals...)                                      \
  for (make_signed_t<decltype(r - l)> i = (r), i##end = (l), ##vals; \
       i >= i##end;                                                  \
       --i)
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const int OFFSET = 5;
const int K = 29, N = (3e5 + OFFSET) * (K + 1);
template <int N>
struct Trie {
  struct trie_t {
    pair<int, int> next;
    vector<int> idxs;
  } data[N];
  int cnt_data = 1;
  void insert(int x, int idx, int now = 1, int dep = K) {
    if (dep < 0) return;
    int &next_p =
      ((x >> dep) & 1) ? data[now].next.second : data[now].next.first;
    if (!next_p) next_p = ++cnt_data;
    data[next_p].idxs.push_back(idx);
    insert(x, idx, next_p, dep - 1);
  }
};
Trie<N> tr;
pair<i64, i64> cnt_inversion[K + OFFSET];
void dfs(int now = 1, int dep = K) {
  int lch = tr.data[now].next.first, rch = tr.data[now].next.second;
  if (!lch && !rch) return;
  if (lch) dfs(lch, dep - 1);
  if (rch) dfs(rch, dep - 1);
  i64 now_inv = 0;
  int _ = 0;
  for (int i : tr.data[lch].idxs) {
    while (_ < tr.data[rch].idxs.size() && i > tr.data[rch].idxs[_]) ++_;
    now_inv += _;
  }
  cnt_inversion[dep].first += now_inv;
  cnt_inversion[dep].second +=
    (i64)tr.data[lch].idxs.size() * (i64)tr.data[rch].idxs.size() - now_inv;
}
auto solve() -> void {
  int n;
  cin >> n;
  _for(i, 1, n, x) {
    cin >> x;
    tr.insert(x, i);
  }
  dfs();
  i64 ans = 0, ans_inv = 0;
  _rfor(i, K, 0) {
    ans_inv += min(cnt_inversion[i].first, cnt_inversion[i].second);
    if (cnt_inversion[i].second < cnt_inversion[i].first) ans |= (1 << i);
  }
  cout << ans_inv << " " << ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

Closest Equals (CF522D)

题目链接

2 s, 512 MB

给定一个下标从 \(1\) ~ \(n\) 的序列 \(a\), 然后进行 \(m\) 次询问

每次询问给出一对 \([l, r]\), 找到区间中数值相等的且距离最相近的两个数 \(a_i\) 和 \(a_j\), 求它们的距离

换言之找到一组数 \((a_i, a_j)\) 满足

  • \(a_i = a_j\);
  • \(l \leq i, j \leq r\) \((i \neq j)\);

求 \(|i - j|\) 的最小值，如果区间中不存在相等的两个数，则输出 \(-1\)

输入格式

第一行输入两个整数 \(1 \leq n, m \leq 5 \times 10^5\)

第二行输入 \(n\) 个整数 \(1 \leq a_i \leq 10^9\)

接下来 \(m\) 行，每行输入两个整数 \(1 \leq l \leq r \leq n\)

输出格式

输出 \(m\) 行，每行包含一个整数作为询问的答案

输入样例 1

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

输出样例 1

1
2
3
1
-1
2

输入样例 2

1
2
3
4
5
6
7
6 5
1 2 1 3 2 3
4 6
1 3
2 5
2 4
1 6

输出样例 2

1
2
3
4
5
2
2
3
-1
2

解题思路

RMQ + 二分

首先我们求出全部两端点值相同的线段 \((l,r)\), 然后删去冗余的线段 (若 \(l_1\leq l_2\) 且 \(r_1\geq r_2\), 那么 \((l_1,r_1)\) 对答案不会产生贡献，直接删去即可)

然后就是查询区间最短线段长度

std::lower_bound 和 std::upper_bound 对 comp 签名要求不一致，但作用要求一致 (即 若第一参数先序于第二个则返回 ​true)

  • std::lower_bound<ForwardIter, T> 要求的是 bool comp(const ForwardIter& t1, const T& t2)
  • std::upper_bound<ForwardIter, T> 要求的是 bool comp(const T& t1, const ForwardIter& t2)

详情参见 1 2

  1. https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/lower_bound&oldid=139001↩︎

  2. https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/upper_bound&oldid=139224↩︎

复杂度

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

代码参考

Show code

CodeForces_522Dview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
const uint32_t OFFSET = 5;
const uint32_t N = 5e5 + OFFSET, M = 5e5 + OFFSET, K = 21;
map<int, int> idx;
int pos[N];
struct Seq {
  int l, r;
} s[N];
int cnt_s;
template <size_t N, typename data_t, typename init_func, typename query_func>
class RMQ_ST {
protected:
  init_func ifunc;
  query_func qfunc;
  data_t f[(size_t)log2(N) + 1][N];
  size_t log_table[N];

public:
  RMQ_ST() {}
  void clear() { memset(f, 0, sizeof(f)); }
  void init(size_t n) {
    for (size_t i = 1; i <= n; ++i) f[0][i] = ifunc(i);
    for (size_t i = 1; i <= std::log2(n); ++i)
      for (size_t j = 1; j + (1 << i) - 1 <= n; ++j)
        f[i][j] = qfunc(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
  }
  data_t query(size_t l, size_t r) const {
    size_t _ = std::log2(r - l + 1);
    return qfunc(f[_][l], f[_][r - (1 << _) + 1]);
  }
};
struct ifunc {
  int operator()(const size_t n) const { return s[n].r - s[n].l; }
};
struct qfunc {
  int operator()(const int l, const int r) const { return std::min(l, r); }
};
RMQ_ST<N, int, ifunc, qfunc> st;
auto solve() -> void {
  int n, m;
  cin >> n >> m;
  _for(i, 1, n, x, pre) {
    cin >> x;
    if ((pre = idx[x]) && (pre > s[cnt_s].l)) s[++cnt_s] = {pre, i};
    idx[x] = i;
  }
  st.init(cnt_s);
  _for(i, 1, m, x, y, l, r) {
    cin >> x >> y;
    l = lower_bound(s + 1,
                    s + cnt_s + 1,
                    x,
                    [](const Seq &it, int v) -> bool { return it.l < v; }) -
        s;
    r = upper_bound(s + 1,
                    s + cnt_s + 1,
                    y,
                    [](int v, const Seq &it) -> bool { return it.r > v; }) -
        s - 1;
    cout << (l <= r ? st.query(l, r) : -1) << '\n';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

CCPC Harbin 2021 G, Damaged Bicycle (CodeForces Gym 103447G)

题目链接

3 s, 1024 MB

Ring Ring Ring ... The bell rang at half past six in the morning. After turning off the alarm, George went on to sleep again. When he woke up again, it was seven fifty and there were ten minutes left for class!

George immediately got up from bed, dressed, packed his backpack, brushed his teeth and washed his face. Then, he immediately rushed out of the dormitory and embarked on the road to the teaching building. On the way, he turned on his mobile phone to locate and saw several yellow shared bicycles nearby. Therefore, he headed to a bicycle and took out his mobile phone to scan the QR code on the bicycle. Unfortunately, the bicycle wasn't unlocked, and a line of words "this bicycle is damaged and can't be unlocked" was displayed on the screen

Without riding a bicycle, he was late. What a bad day!

Indeed, some bicycles in the school are damaged, but their location will still be displayed on the app. George always rides faster than he walks, but considering that some bicycles are damaged, if George tries one by one, it may take a long time! In this regard, he has made some modeling, and hopes you can help him find the best strategy

The campus can be modeled as a graph of \(n\) vertices and \(m\) bidirected edges, where the \(i\)-th edge is \(w_i\) meters long. George's dormitory is located at vertex \(1\) and Guanghua Tower (the teaching building) is at vertex \(n\), so George has to go from vertex \(1\) to vertex \(n\) to take classes. His walking speed is \(t\) meters per second and his riding speed is \(r\) meters per second. According to the bicycle sharing app, there are \(k\) parked bicycles in the campus. The \(i\)-th bicycle is located at vertex \(a_i\), and of probability \(\frac{p_i}{100}\) to be damaged according to George's experience. However, only when George arrives at vertex \(a_i\) and scans the QR code, can he determine whether the \(i\)-th bicycle is damaged or not. As soon as a bicycle is confirmed to be undamaged, George will get on it immediately and will not get off until he reaches vertex \(n\)

Now George wants to save time to get to the classroom. So you, George's roommate, should help him find an optimal strategy to minimize the mathematical expectation of the time cost on the way, and then output this value. Or you can let him continue sleeping if vertex \(n\) is not reachable

In this problem, you should only consider the time of walking and cycling, and you can assume that the other actions(scanning QR code, getting on, getting off, \(\cdots\)) cost no time

简单中文翻译：校园可以被看成 \(n\) 个点，\(m\) 条无向边的图，其中第 \(i\) 条边的长度是 \(w_i\). 你的宿舍在 \(1\) 号点，教学楼在 \(n\) 号点，你想从宿舍去教学楼。你的走路速度是每秒 \(t\), 骑车速度是每秒 \(r\). 根据共享单车 app, 校园内一共有 \(k\) 个停车点。第 \(i\) 个停车点在 \(a_i\) 点，但是有 \(\frac{p_i}{100}\) 的概率，车可能是坏的。但是你只有到达 \(a_i\) 点，然后扫描二维码之后才能知道第 \(i\) 辆车是不是好的。如果车是好的，那就可以骑到终点

问你最优策略下，你最小的到达终点的期望时间是多少。如果到达不了 \(n\) 号点，输出 - 1

Input

The first line contains two integers \(t,r\,(1\le t\le r\le 10^4)\) — the speed of walking and the speed of riding, respectively

The second line contains two integers \(n,m\,(1\le n,m\le 10^5)\) — the number of vertices and the number of bidirected edges in the given graph

Following \(m\) lines each contains three integers \(u_i,v_i,w_i\,(1\le u_i,v_i \le n, u_i \neq v_i, 1 \le w_i\le 10^4)\), denoting that vertices \(u,v\) are connected by a \(w_i\)-meter-long bidirected edge

The next line contains a single integer \(k\,(0\le k\le 18)\), denoting the number of bicycles in campus

Following \(k\) lines each contains two integers \(a_i,p_i\,(1\le a_i \le n, 0\le p_i \le 100)\), denoting the locations of the bicycles and the percentages of damage probabilities respectively

It is guaranteed that no two bicycles are in the same vertex

Output

If George cannot reach vertex \(n\), output one line containing one integer -1, or output one line containing one real number, denoting the minimum expectation of the time cost on the way

As long as the relative or absolute error between your answer and the standard answer is within $10^{-6} $, your answer will be considered correct

Examples

input

1
2
3
4
5
6
7
3 15
4 3
1 2 600
1 3 300
2 4 900
1
3 50

output

1
460.000000

input

1
2
3
4
5
6
7
8
9
3 15
5 4
1 2 600
1 3 300
2 5 900
3 4 3
2
3 50
4 0

output

1
220.600000

input

1
2
3
4
5
6
7
8
9
3 15
5 4
1 2 600
1 3 300
4 5 900
3 2 300
2
3 50
4 0

output

1
-1

Note

For the first test case, one possible strategy is:

  • Go along the route \(1\rightarrow 3\) and try to ride the only bicycle in the campus
  • If the bicycle is damaged, go along the route \(3 \rightarrow 1 \rightarrow 2 \rightarrow 4\) on foot, or go by bicycle

Considering the time cost on the way:

  • If the bicycle is damaged, George should go along the route \(1\rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4\) on foot, whose total length is 2100 meters. So the time cost is \(\frac{2100}{3} = 700\) seconds
  • If the bicycle is undamaged, George should go along the route \(1\rightarrow 3\) on foot, whose total length is 300 meters, and then go along the route \(3 \rightarrow 1 \rightarrow 2 \rightarrow 4\) by bicycle, whose total length is 1800 meters. So the time cost is \(\frac{300}{3} + \frac{1800}{15} = 220\) seconds

As given in the input, the only bicycle has \(\frac{50}{100}\) probability to be damaged. So the expectation time cost is \(\frac{50}{100}\times 700 + (1 - \frac{50}{100})\times 220 = 460\)

解题思路

状压 DP + 最短路

官方题解参见 https://codeforces.com/gym/103447/attachments/download/14826/2021CCPCHarbinSolution.pdf#Outline0.8

DP 不会写，写的记搜

思路和官方题解差不多，略

复杂度

\(O(m+kn\log n+k^22^k)\)

代码参考

Show code

CodeForces_Gym_103447Gview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 1e5 + OFFSET, M = 2e5 + OFFSET, K = 19;
const int INF = 0x3f3f3f3f;
struct Edge {
  int w, to, next;
  Edge(int _w = 0, int _to = 0, int _next = 0): w(_w), to(_to), next(_next) {}
} e[M];
int head[N], cnt_edge;
int in[N], out[N];
void addEdge(int x, int y, int w = 1) {
  e[++cnt_edge] = Edge(w, y, head[x]);
  head[x] = cnt_edge;
  ++in[y];
  ++out[x];
}
int dist[K][N];
void dijkstra(int *dis, int s) {
  priority_queue<pair<int, int>,
                 vector<pair<int, int>>,
                 greater<pair<int, int>>>
    q;
  q.emplace(dis[s] = 0, s);
  while (!q.empty()) {
    auto [dis_now, now] = q.top();
    q.pop();
    if (dis[now] < dis_now) continue;
    for (int i = head[now], to; i; i = e[i].next)
      if (dis[to = e[i].to] > dis[now] + e[i].w)
        q.emplace(dis[to] = dis[now] + e[i].w, to);
  }
}
pair<int, double> bicycles[K];
double expectation[1 << K][K];
int t, r, n, m, k;
double dp(int state, int now) {
  if (expectation[state][now] >= 0) return expectation[state][now];
  double ret = bicycles[now].second * dist[now][n] / t +
               (1 - bicycles[now].second) * dist[now][n] / r;
  _for(i, 0, k - 1) {
    if (i == now) continue;
    if (state & (1 << i)) continue;
    ret = min(ret,
              bicycles[now].second * (dp(state | (1 << i), i) +
                                      1.0 * dist[now][bicycles[i].first] / t) +
                (1 - bicycles[now].second) * dist[now][n] / r);
  }
  return expectation[state][now] = ret;
}
auto solve() -> void {
  cin >> t >> r >> n >> m;
  _for(i, 1, m, u, v, w) {
    cin >> u >> v >> w;
    addEdge(u, v, w);
    addEdge(v, u, w);
  }
  cin >> k;
  _for(i, 0, k - 1, a, p) {
    cin >> a >> p;
    bicycles[i] = {a, p / 100.0};
  }
  bicycles[k] = {1, 1};
  memset(dist, 0x3f, sizeof(dist));
  _for(i, 0, k) dijkstra(dist[i], bicycles[i].first);
  if (dist[k][n] == INF) {
    cout << "-1\n";
    return;
  }
  _for(i, 0, (1 << (k + 1)) - 1)
    _for(j, 0, k) expectation[i][j] = -114514;
  cout << fixed << setprecision(6) << dp(1 << k, k);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

拆方块 (CF573B, 51NOD1550)

题目链接

1 s, 1024 MB

有 \(n\) 堆方块，第 \(i\) 堆方块由 \(h_i\) 个方块堆积而成。具体可以看样例

接下来拆方块。一个方块称为内部方块当且仅当他的上下左右都是方块或者是地面。否则方块就是边界方块。每一次操作都要把边界方块拿掉

问多少次操作之后所有方块会消失

输入格式

第一行有一个整数 n (\(1\leq n\leq 10^5\))

第二行有 n 个整数 \(h_i\)(\(1\leq h_i\leq 10^9\)), 表示第 i 堆方块的数目

输出格式

输出使得所有方块消失的操作次数

样例输入

1
2
6
2 1 4 6 2 2

样例输出

1
3

数据规模

所有数据保证 \(1\leq n \leq 10^5, 1 \leq h_i\leq 10^9\)

解题思路

DP

设 \(f(x)\) 为第 \(x\) 堆方块最少需要多少次才能清空，则

\(f(1)=f(n)=1\)

\[ \begin{align} f(x)&=\min\{f(x-1)+1,f(x+1)-1,h(x)\}\\ &=\min\{\min\{f(x-1)+1,h(x)\},\min\{f(x+1)+1,h(x)\}\} \end{align} \]

复杂度

\(O(n)\)

代码参考

Show code

CodeForces_573Bview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
#define _rfor(i, r, l, vals...)                                      \
  for (make_signed_t<decltype(r - l)> i = (r), i##end = (l), ##vals; \
       i >= i##end;                                                  \
       --i)
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 1e5 + OFFSET, M = 2e5 + OFFSET, K = 21;
int h[N], ans[N];
auto solve() -> void {
  int n;
  cin >> n;
  _for(i, 1, n) cin >> h[i];
  ans[1] = ans[n] = 1;
  _for(i, 2, n - 1) ans[i] = min(ans[i - 1] + 1, h[i]);
  _rfor(i, n - 1, 2) ans[i] = min(ans[i + 1] + 1, ans[i]);
  int final_ans = 0;
  _for(i, 1, n) chkmax(final_ans, ans[i]);
  cout << final_ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}