Cool Pomelo

Per aspera ad astra. 循此苦旅，以达天际。

发表于 更新于 作者 Pomelorin ， Cool-breeze

欢迎来到 Pomelorin 和 Cool-breeze 的博客！希望我们能相互交流，共同进步～

图标是清爽葡萄柚汽水（确信）。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin

B. 出 Bug 的绘画软件I

题意简述

画布由若干有序图层组成，每层是 \(n\times m\) 的像素网格。像素值 \(0\) 表示透明，\(1\sim nm\) 表示不同颜色。某位置的合成可见值为所有图层中最上层非透明像素的值；若所有图层在该位置都透明，则可见值为 \(0\)。

初始没有图层。可以任意次执行：

  • 免费在最上方新建图层，初始化为全为颜色 \(c\) 的常量层（\(1\le c\le nm\)），或全透明层；
  • 花费 \(a\) 将任意图层中任意单个像素涂成颜色 \(c\)；
  • 花费 \(b\) 将任意图层中任意单个像素变为透明。

给定目标可见矩阵 \(p_{i,j}\)，求使最终合成图像等于目标图像的最小总花费。

数据范围

\(1\le T\le 10^5\)，\(1\le n,m\le 500\)，\(1\le a,b\le 10^6\)，\(0\le p_{i,j}\le nm\)，且所有测试用例的 \(\sum nm\le 10^6\)。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin

模板——补充

数论分块、中缀表达式求值、string、在图中找环。

数论分块

求 \(\sum_{i=1}^n \lfloor n/i\rfloor\)，时间复杂度为 \(O(\sqrt n)\)。

1
2
3
4
5
6
7
8
9
10
11
long long H(int n) {
  long long res = 0;  // 储存结果
  int l = 1, r;       // 块左端点与右端点
  while (l <= n) {
    r = n / (n / l);  // 计算当前块的右端点
    // 累加这一块的贡献到结果中。乘上 1LL 防止溢出
    res += 1LL * (r - l + 1) * (n / l);
    l = r + 1;  // 左端点移到下一块
  }
  return res;
}

中缀表达式求值

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
stack<char> op;
   stack<ll> num;
   ll pri[256] = {};
   pri['+'] = pri['-'] = 1;
   pri['*'] = pri['/'] = 2;
   pri['('] = 3;
   expr = '$' + expr + '$';
   for (char c : expr) {
       if (isdigit(c)) { // 只考虑了单数字
           num.push(c - '0');
           continue;
       }
       while (pri[op.top()] >= pri[c] && num.size() >= 2) {
           ll b = num.top();
           num.pop();
           ll a = num.top();
           num.pop();
           if (op.top() == '+') {
               a += b;
           } else if (op.top() == '-') {
               a -= b;
           } else if (op.top() == '*') {
               a *= b;
           } else if (op.top() == '/') {
               a /= b;
           } else if (op.top() == '$') {
               num.push(a);
               num.push(b);
               op.pop();
               break;
           }
           num.push(a);
           op.pop();
       }
       if (c != ')') {
           if (c == '(') {
               op.push('$');
           } else {
               op.push(c);
           }
       }
   }
   cout << "=" << num.top() << "\n";

string

  • size()/length() 获取字符串长度。
  • find(str,pos) 查找字符串中一个字符/字符串在 pos 及之后第一次出现的位置（pos 默认为 0）。如果没有出现，则返回 string::npos（被定义为 -1）。
  • 上面两个函数返回值类型是 size_t/unsigned long。
  • substr(pos, len) 函数返回从 pos 位置开始截取最多 len 个字符组成的字符串（如果从 pos 开始的后缀长度不足 len 则截取这个后缀）。
  • replace(pos, count, str) 从 pos 位置开始 count 个字符的子串替换为 str 。
  • replace(first, last, str) 以 first 开始（含）、last 结束（不含）的子串替换为 str，其中 first 和 last 均为迭代器。

在图中找环

枚举边，断边找环

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
vector<ll> e[N];

ll out[N][N];
ll oncycle[N], lvl[N], last[N];

ll find(ll st, ll ed) { // 这样找到的是极小环
    queue<ll> q;
    for (ll i = 1; i <= n; i++) {
        last[i] = 0;
    }
    last[st] = st;
    q.push(st);
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (auto v : e[u]) {
            if ((u == st && v == ed) || (u == ed && v == st) || last[v]) {
                continue;
            }
            last[v] = u;
            if (v == ed) {
                return 1;
            }
            q.push(v);
        }
    }
    return 0;
}

void mark(ll u, ll v) {
    ll cur = v;
    while (last[cur] != cur) {
        out[cur][last[cur]] = -1;
        out[last[cur]][cur] = 1;
        oncycle[cur] = 1;
        cur = last[cur];
    }
    out[u][v] = -1;
    out[v][u] = 1;
    oncycle[u] = 1;

    cur = u;
    while (lvl[cur] != cur) { // 这个是把从 (x,y) 到环的路径标记出来
        out[cur][lvl[cur]] = -1;
        out[lvl[cur]][cur] = 1;
        oncycle[cur] = 1;
        cur = lvl[cur];
    }
    oncycle[cur] = 1;
}

void bfs() { // 这里是优先找离 (x,y) 最近的环
    queue<ll> q;
    for (ll i = 1; i <= n; i++) {
        lvl[i] = 0;
    }
    lvl[x] = x;
    lvl[y] = y;
    q.push(x);
    q.push(y);
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (auto v : e[u]) {
            if (!lvl[v]) {
                lvl[v] = u;
                if (find(u, v)) {
                    mark(u, v);
                    return;
                }
                q.push(v);
            }
        }
    }
}

Floyd 找最小环

只能找出最小环。

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
// 图的点数为 n
int val[MAXN + 1][MAXN + 1];  // 原图的邻接矩阵
int cnt, path[MAXN + 5];      // 记录最小环的路径和长度

void get_path(int u, int v) {  // 获得 u 到 v 之间的路径
  if (pos[u][v] == 0) return;

  int k = pos[u][v];
  get_path(u, k);
  path[++cnt] = k;
  get_path(k, v);
}

void Floyd(const int &n) {
  static int dis[MAXN + 1][MAXN + 1];  // 最短路矩阵
  static int pos[MAXN + 1][MAXN + 1];
  memcpy(dis, val, sizeof(val));
  memset(pos, 0, sizeof(pos));
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i < k; ++i)
      for (int j = 1; j < i; ++j)
        if (ans >
            (long long)val[i][k] + val[k][j] + dis[i][j]) {  // 发现了更短的环
          // 由于这里保证了 j<i<k，所以三个点不同，不会出现零环．
          ans = val[i][k] + val[k][j] + dis[i][j], cnt = 0;
          path[++cnt] = i, path[++cnt] = k,
          path[++cnt] = j;  // 依次加入 i,k,j 三点
          get_path(j, i);   // 加入 j 到 i 的路径
        }

    for (int i = 1; i <= n; ++i)  // 正常 Floyd 更新最短路
      for (int j = 1; j <= n; ++j) {
        if (dis[i][j] > dis[i][k] + dis[k][j]) {
          dis[i][j] = dis[i][k] + dis[k][j];
          pos[i][j] = k;  // 当前路径可以由 k 更新得到
        }
      }
  }
}

多源最短路找环

把包含

发表于 更新于 分类于 ， 作者 Pomelorin

模板——树上算法

LCA，树的一些性质，点分治，树上莫队，DFS 序与欧拉序，树上启发式合并，Kruskal 重构树，树链剖分。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin

模板——数据结构2

线段树，树状数组，动态开点线段树，线段树合并，主席树，树套树，平衡树。

阅读全文 »

发表于 分类于 ， 作者 Pomelorin

B. 梦中星河

给定非负整数 \(x\)，求三个非负整数 \(a,b,c\) 满足 \(a\times b+c=x\)，并使得 \(\max(a,b,c)−\min(a,b,c)\) 尽可能小。输出该最小值。要求约 \(O(\sqrt x)\)。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin

G. 炒股高手

已知 \(n\) 个交易日中股票的股价（所有价格均以自然对数的形式给出）。可以购买非整数份的股票。共有 \(m\) 个时间区间，本金均为 \(e^k\)。求每个时间区间进行买入卖出后得到的总资产。\(n\le 10^5,m\le 10^5\)。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin ， Cool-breeze

D. 与或博弈

博弈规则如下：

  • gsh 和 AI 轮流操作，gsh 先手。
  • 他们操作两个非负整数 \(a\) 和 \(b\)，gsh 的目标是将其变为目标非负整数 \(x\) 和 \(y\)，而 AI 需要阻止 gsh 达成目标。
  • gsh 在自己的回合可以执行以下两种操作之一：
    1. \(a := a \mathbin{\&} v\)（按位与某个非负整数 \(v\)）。
    2. \(b := b \mathbin{|} v\)（按位或某个非负整数 \(v\)）。
  • AI 在自己的回合可以执行以下两种操作之一：
    1. \(a := a \mathbin{|} v\)（按位或某个非负整数 \(v\)）。
    2. \(b := b \mathbin{\&} v\)（按位与某个非负整数 \(v\)）。
  • 允许选择的 \(v\) 满足 \(0 \leq v \lt 2^{60}\)。
  • 双方都足够聪明，并且都会采取最优策略以赢得游戏。
  • 若在 \(10^{100}\) 回合内，存在某一时刻 \(a = x\) 且 \(b = y\)，则 gsh 获胜；否则，AI 获胜。

请你判断 gsh 是否必胜，若必胜，输出 Yes，否则输出 No。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin ， Cool-breeze

F. Inversion Pairs

只含有 01? 三种字符的字符串，可以把 ? 变成 0 或 1，求逆序对最多为多少。

逆序对 贪心 填法一定是左边都填 1，右边都填 0，枚举这个分界点即可。

预处理前缀 1 个数与后缀 0 个数，先假设都填 0，之后从左向右开始填 1。贡献变化为加后面 0 的个数减前面 1 的个数。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin ， Cool-breeze

CSP38 T4 月票发行

CSP38 T4 月票发行

题意：长度为 \(n\)（\(10^9\)）的字符串有 \(m\)（\(10^6\)）个固定为 #，其余能填任意小写字母。问至少有一个 ccf 和一个 cspark 子串，且至少有一个 ccf 出现在 cspark 前的字符串数量。

阅读全文 »
0%