Hide

题意概述

有一棵$N$个节点的树,每个节点都是黑色或白色。有$Q$次操作,动态修改点的颜色,询问最远黑点对之间的距离。
数据范围:$1 \le N \le 10^5, \; 1 \le Q \le 5 \times 10^5$。

算法分析

考虑点分治,构造一棵重心树。为了方便,下面所有距离均表示在原树上的距离,堆均为大根堆。
设节点$i$在重心树上的父亲为$p_i$。对于每个节点$u$维护两个堆,第一个堆用来维护重心树上$u$子树中的所有黑点到$p_u$的距离,第二个堆用来维护重心树上$u$各个子树中距离$u$最远的黑点到$u$的距离。那么第二个堆可以借助第一个堆来维护。
接着需要一个全局的堆,用来维护所有节点第二个堆的前两个元素之和(经过该点的路径)以及所有黑点第二个堆的第一个元素(以该点为端点的路径)。
修改时,沿着重心树往上依次处理经过的节点,先在全局的堆中删除,再在第二个堆中删除,在第一个堆中修改后,维护第二个堆和全局的堆。

代码

/*
 * Computer programmers do it byte by byte.
 */

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

template <typename T> void read(T &n) {
  char c;
  for (; (c = getchar()) < '0' || c > '9';)
    ;
  for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0')
    ;
}

typedef int const ic;

static ic N = 100005;

class heap {
private:
  std::priority_queue<int> que, buf;

void clear() {
    for (; !que.empty() && !buf.empty() && que.top() == buf.top();
         que.pop(), buf.pop())
      ;
  }

public:
  void push(ic &n) {
    if (n)
      que.push(n);
  }

void erase(ic &n) {
    if (n)
      buf.push(n);
  }

void pop() {
    clear();
    if (!que.empty())
      que.pop();
  }

int top() {
    clear();
    return que.empty() ? 0 : que.top();
  }

int top2() {
    clear();
    if (que.empty())
      return 0;
    int tmp = que.top(), ret = tmp;
    que.pop(), clear();
    if (que.empty()) {
      que.push(tmp);
      return 0;
    }
    ret += que.top(), que.push(tmp);
    return ret;
  }
} global;

namespace tree {
int n, nume, h[N], col[N];
int tim, fi[N], dep[N], lca[N << 1][20];
int power[N << 1];
int root, up[N], size[N], mx[N], vis[N];
heap toup[N], me[N];
struct Edge {
  int v, nxt;
} e[N << 1];

void add_edge(ic &u, ic &v) {
  e[++nume] = (Edge){v, h[u]}, h[u] = nume;
  e[++nume] = (Edge){u, h[v]}, h[v] = nume;
}

void dfs(ic &t, ic &fa) {
  lca[++tim][0] = t, fi[t] = tim, dep[t] = dep[fa] + 1;
  for (int i = h[t]; i; i = e[i].nxt)
    if (e[i].v != fa)
      dfs(e[i].v, t), lca[++tim][0] = t;
}

void init() {
  for (int i = 2; i <= tim; i <<= 1)
    ++power[i];
  for (int i = 1; i <= tim; ++i)
    power[i] += power[i - 1];
  for (int i = 1; i < 20; ++i)
    for (int j = 1; j <= tim; ++j) {
      ic k = std::min(tim, j + (1 << i - 1));
      lca[j][i] = dep[lca[j][i - 1]] < dep[lca[k][i - 1]] ? lca[j][i - 1]
                                                          : lca[k][i - 1];
    }
}

int get_lca(ic &u, ic &v) {
  ic l = std::min(fi[u], fi[v]), r = std::max(fi[u], fi[v]);
  ic len = power[r - l + 1], k = r - (1 << len) + 1;
  return dep[lca[l][len]] < dep[lca[k][len]] ? lca[l][len] : lca[k][len];
}

int get_dist(ic &u, ic &v) {
  ic lca = get_lca(u, v);
  return dep[u] + dep[v] - 2 * dep[lca];
}

int get_size(ic &t, ic &fa) {
  int ret = 1;
  for (int i = h[t]; i; i = e[i].nxt)
    if (!vis[e[i].v] && e[i].v != fa)
      ret += get_size(e[i].v, t);
  return ret;
}

void get_root(ic &t, ic &fa, ic &tot) {
  size[t] = 1, mx[t] = 0;
  for (int i = h[t]; i; i = e[i].nxt)
    if (!vis[e[i].v] && e[i].v != fa)
      get_root(e[i].v, t, tot), size[t] += size[e[i].v],
          mx[t] = std::max(mx[t], size[e[i].v]);
  (mx[t] = std::max(mx[t], tot - size[t])) < mx[root] && (root = t);
}

void init_heap(ic &t, ic &fa, ic &dep, heap &hp) {
  hp.push(dep);
  for (int i = h[t]; i; i = e[i].nxt)
    if (!vis[e[i].v] && e[i].v != fa)
      init_heap(e[i].v, t, dep + 1, hp);
}

void build(int t) {
  vis[t] = true;
  for (int i = h[t]; i; i = e[i].nxt)
    if (!vis[e[i].v])
      root = 0,
      get_root(e[i].v, 0,
               size[e[i].v] < size[t] ? size[e[i].v] : get_size(e[i].v, t)),
      up[root] = t, init_heap(e[i].v, t, 1, toup[root]),
      me[t].push(toup[root].top()), build(root);
  global.push(me[t].top()), global.push(me[t].top2());
}

void modify(int t) {
  ic p = t;
  if (col[t])
    global.erase(me[t].top());
  else
    global.push(me[t].top());
  for (; up[t]; t = up[t]) {
    if (col[up[t]])
      global.erase(me[up[t]].top());
    global.erase(me[up[t]].top2());
    me[up[t]].erase(toup[t].top());
    if (col[p])
      toup[t].erase(get_dist(p, up[t]));
    else
      toup[t].push(get_dist(p, up[t]));
    me[up[t]].push(toup[t].top());
    if (col[up[t]])
      global.push(me[up[t]].top());
    global.push(me[up[t]].top2());
  }
  col[p] = !col[p];
}
} // namespace tree

int main() {
  read(tree::n), tree::mx[0] = tree::n;
  for (int i = 1, u, v; i < tree::n; ++i)
    read(u), read(v), tree::add_edge(u, v);
  tree::dfs(1, 0), tree::init(), tree::get_root(1, 0, tree::n),
      tree::build(tree::root);
  for (int i = 1; i <= tree::n; ++i)
    tree::col[i] = 1;
  int q;
  for (read(q); q--;) {
    char c;
    scanf(" %c", &c);
    if (c == 'G')
      printf("%d\n", global.top());
    else {
      int p;
      read(p), tree::modify(p);
    }
  }
  return 0;
}

DZY Loves Modification

题目描述

As we know, DZY loves playing games. One day DZY decided to play with a $n \times m$ matrix. To be more precise, he decided to modify the matrix with exactly $k$ operations.
Each modification is one of the following:

  • Pick some row of the matrix and decrease each element of the row by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the row before the decreasing.
  • Pick some column of the matrix and decrease each element of the column by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the column before the decreasing.

DZY wants to know: what is the largest total value of pleasure he could get after performing exactly $k$ modifications? Please, help him to calculate this value.

题意概述

给定一个$n \times m$的矩阵,每次可以从这个矩阵中选取一行或一列,将这一行或一列的数字之和加到你的分数上,再将这一行或一列上的每个数字减去$p$。共进行$k$次操作,求分数的最大值。
数据范围:$1 \le n, m \le 1000, \; 1 \le k \le 10^6, \; 1 \le p \le 100$。

算法分析

可以发现交换操作顺序对答案没有影响。因此,可以先计算出只取$i$行可以得到的最大值以及只取$j$列可以得到的最大值,根据贪心策略,可以用优先队列维护一行或一列的数字之和。接着枚举取了$i$行,那么也就取了$(k-i)$列,减去重复部分,取最大值,即可得到答案。

代码

#include <iostream>
#include <queue>
using namespace std;
priority_queue<long long> r, c;
long long n, m, k, p, s, t, ans = -1e18, a[1001][1001], rr[1000001], cc[1000001];
int main()
{
  cin >> n >> m >> k >> p;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) cin >> a[i][j];
  for (int i = 1; i <= n; ++i) {
    long long s = 0;
    for (int j = 1; j <= m; ++j) s += a[i][j];
    r.push(s);
  }
  for (int j = 1; j <= m; ++j) {
    long long s = 0;
    for (int i = 1; i <= n; ++i) s += a[i][j];
    c.push(s);
  }
  for (int i = 1; i <= k; ++i) {
    long long u = r.top(); r.pop();
    rr[i] = rr[i - 1] + u;
    r.push(u - p * m);
    u = c.top(); c.pop();
    cc[i] = cc[i - 1] + u;
    c.push(u - p * n);
  }
  for (int i = 0; i <= k; ++i) ans = max(ans, rr[i] + cc[k - i] - p * i * (k - i));
  cout << ans << endl;
  return 0;
}

Minimal Labels

题目描述

You are given a directed acyclic graph with $n$ vertices and $m$ edges. There are no self-loops or multiple edges between any pair of vertices. Graph can be disconnected.
You should assign labels to all vertices in such a way that:

  • Labels form a valid permutation of length $n$ – an integer sequence such that each integer from $1$ to $n$ appears exactly once in it.
  • If there exists an edge from vertex $v$ to vertex $u$ then $label_v$ should be smaller than $label_u$.
  • Permutation should be lexicographically smallest among all suitable.

Find such sequence of labels to satisfy all the conditions.

题意概述

给定一张$n$个点$m$条边的有向无环图。现要将图中所有点标号。如果点$u$有一条连向点$v$的边,那么点$u$的标号要比点$v$小。求一组字典序最小的标号方案。
数据范围:$2 \le n \le 10^5, \; 1 \le m \le 10^5$。

算法分析

这是一张拓扑图,只需进行一次拓扑排序即可得到一组方案。但由于题目要求字典序最小,因此需要逆向拓扑,并用优先队列维护id最大的节点。证明如下:

对于节点$1$,它的标号等于它在逆向拓扑树上的子树大小,这显然属于字典序最小的方案。对于节点$2$,它的标号等于节点$1$子树并上节点$2$子树的大小,这也属于字典序最小的方案。以此类推,每个节点的标号都属于字典序最小的方案。

由此得证。

代码

#include <iostream>
#include <queue>
using namespace std;
struct edge { int v, nxt; } e[100001];
int n, m, nume, cnt, h[200001], in[200001], id[200001];
priority_queue<int> que;
void add_edge(int u, int v) {
  e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
}
int main()
{
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v; cin >> u >> v;
    add_edge(v, u), ++in[u];
  }
  for (int i = 1; i <= n; ++i) if (!in[i]) que.push(i);
  while (!que.empty()) {
    int u = que.top(); que.pop(), id[u] = cnt++;
    for (int i = h[u]; i; i = e[i].nxt) {
      --in[e[i].v]; if (!in[e[i].v]) que.push(e[i].v);
    }
  }
  for (int i = 1; i <= n; ++i) cout << n - id[i] << ' ';
  cout << endl;
  return 0;
}

The Lazy Programmer

题目描述

A new web-design studio, called SMART (Simply Masters of ART), employs two people. The first one is a web-designer and an executive director at the same time. The second one is a programmer. The director is so a nimble guy that the studio has already got $N$ contracts for web site development. Each contract has a deadline $d_i$.
It is known that the programmer is lazy. Usually he does not work as fast as he could. Therefore, under normal conditions the programmer needs $b_i$ of time to perform the contract number $i$. Fortunately, the guy is very greedy for money. If the director pays him $x_i$ dollars extra, he needs only $(b_i-a_ix_i)$ of time to do his job. But this extra payment does not influent other contract. It means that each contract should be paid separately to be done faster. The programmer is so greedy that he can do his job almost instantly if the extra payment is $(b_i/a_i)$ dollars for the contract number $i$.
The director has a difficult problem to solve. He needs to organize programmer’s job and, may be, assign extra payments for some of the contracts so that all contracts are performed in time. Obviously he wishes to minimize the sum of extra payments. Help the director!

题意概述

有$N$个合同,第$i$个合同需要在时刻$d_i$前完成。程序员完成第$i$个合同所需的时间为$b_i$,若给他$x_i$元钱则他完成这个合同所需的时间会减少$a_ix_i$(但不会小于$0$)。求在按时完成所有合同的前提下所需的最少钱数。
数据范围:$1 \le N \le 10^5, \; 1 \le a_i, b_i \le 10^4, \; 1 \le d_i \le 10^9$。

算法分析

首先完成合同的顺序是确定的,即先将所有合同按$d_i$从小到大排序。
接下来我们依次处理合同。如果发现第$i$个合同无法按时完成,那么就从之前已经完成的合同中找一个$a_j$最大的,给这个任务付钱(当然,要保证$b_j$不小于$0$)。
建一个大根堆,维护已经完成合同的$a_i$,同时维护当前耗时$t$。当处理第$i$个合同时发现$t \gt d_i$,就给堆顶合同付钱直到$t \le d_i$;若堆顶合同的$b_j=0$,则将它从堆中移出。
时间复杂度为$O(N\log N)$。

代码

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int n, t;
double ans;
struct contract {
    int a, b, d;
    bool operator < (const contract &t) const {
        return a < t.a;
    }
} c[100001];
bool cmp(contract a, contract b) {
    return a.d < b.d;
}
priority_queue<contract> q;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &c[i].a, &c[i].b, &c[i].d);
    }
    sort(c + 1, c + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        q.push(c[i]);
        t += c[i].b;
        if (t > c[i].d) {
            int delta = t - c[i].d;
            while (delta) {
                contract tmp = q.top();
                q.pop();
                if (tmp.b < delta) {
                    delta -= tmp.b;
                    ans += tmp.b * 1.0 / tmp.a;
                } else {
                    tmp.b -= delta;
                    ans += delta * 1.0 / tmp.a;
                    delta = 0;
                    q.push(tmp);
                }
            }
            t = c[i].d;
        }
    }
    printf("%.2lf\n", ans);
    return 0;
}