Picnic Cows

题目描述

It’s summer vocation now. After tedious milking, cows are tired and wish to take a holiday. So Farmer Carolina considers having a picnic beside the river. But there is a problem, not all the cows consider it’s a good idea! Some cows like to swim in West Lake, some prefer to have a dinner in Shangri-la, and others want to do something different. But in order to manage expediently, Carolina coerces all cows to have a picnic!
Farmer Carolina takes her $N$ cows to the destination, but she finds every cow’s degree of interest in this activity is so different that they all loss their interests. So she has to group them to different teams to make sure that every cow can go to a satisfied team. Considering about the security, she demands that there must be no less than $T$ cows in every team. As every cow has its own interest degree of this picnic, we measure this interest degree’s unit as “Moo~“. Cows in the same team should reduce their Moo~ to the one who has the lowest Moo~ in this team – It’s not a democratical action! So Carolina wishes to minimize the TOTAL reduced Moo~s and groups $N$ cows into several teams.
For example, Carolina has $7$ cows to picnic and their Moo~ are ‘$8 \; 5 \; 6 \; 2 \; 1 \; 7 \; 6$’ and at least $3$ cows in every team. So the best solution is that cow No. $2, 4, 5$ in a team (reduce $((2-1)+(5-1))$ Moo~) and cow No. $1, 3, 6, 7$ in a team (reduce $((7-6)+(8-6))$ Moo~), the answer is $8$.

题意概述

有$N$头牛,每头牛有一个快乐值。要将牛分成若干组,使得每组至少有$T$头牛。分在一组中的牛的快乐值都会变成那组中最小的快乐值。求分组前后总快乐值之差的最小值。
数据范围:$1 \lt T \le N \le 4 \times 10^5$。

算法分析

将牛的快乐值$a_i$从小到大排序。根据贪心策略,一定存在最优分组方案是将排序后的牛分成若干连续段。
令$f_i$表示排序后前$i$头牛分组前后总快乐值之差的最小值,$s_i=\sum_{j=1}^i a_j$,$b_i=a_{i+1}$。可以得到转移方程
$$f_i=\min(f_j+(s_i-s_j)-(i-j)b_j \mid i-j \ge T)$$
假设$k \lt j \lt i$,且决策$j$比决策$k$更优,那么
$$
\begin{align}
f_j+(s_i-s_j)-(i-j)b_j &\le f_k+(s_i-s_k)-(i-k)b_k \\
(f_j-s_j+j \cdot b_j)-(f_k-s_k+k \cdot b_k) &\le i(b_j-b_k)
\end{align}
$$
$i$单调递增,因此可以斜率优化。但要注意两点:当$i-j \lt T$时$f_j$不能转移到$f_i$;当$i \lt T$时$f_i$没有意义。

代码

/*
 * You attempt things that you do not even plan because of your extreme
 * stupidity.
 */

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

#define int long long

static int const N = 400005;
int a[N], f[N], s[N], b[N], que[N];

int dety(int i, int j) {
  return f[j] - s[j] + b[j] * j - (f[i] - s[i] + b[i] * i);
}

int detx(int i, int j) { return b[j] - b[i]; }

signed main() {
  for (int n, k; ~scanf("%lld%lld", &n, &k);) {
    for (int i = 1; i <= n; ++i)
      scanf("%lld", &a[i]);
    std::sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i)
      s[i] = s[i - 1] + a[i], b[i - 1] = a[i];
    int qb = 0, qe = 1;
    que[0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (; qb + 1 < qe &&
             dety(que[qb], que[qb + 1]) <= i * detx(que[qb], que[qb + 1]);
           ++qb)
        ;
      f[i] = f[que[qb]] + s[i] - s[que[qb]] - b[que[qb]] * (i - que[qb]);
      if (i - k + 1 >= k) {
        for (;
             qb + 1 < qe &&
             dety(que[qe - 2], que[qe - 1]) * detx(que[qe - 1], i - k + 1) >=
                 dety(que[qe - 1], i - k + 1) * detx(que[qe - 2], que[qe - 1]);
             --qe)
          ;
        que[qe++] = i - k + 1;
      }
    }
    printf("%lld\n", f[n]);
  }
  return 0;
}

Matching Names

题目描述

Teachers of one programming summer school decided to make a surprise for the students by giving them names in the style of the “Hobbit” movie. Each student must get a pseudonym maximally similar to his own name. The pseudonym must be a name of some character of the popular saga and now the teachers are busy matching pseudonyms to student names.
There are $n$ students in a summer school. Teachers chose exactly $n$ pseudonyms for them. Each student must get exactly one pseudonym corresponding to him. Let us determine the relevance of a pseudonym $b$ to a student with name $a$ as the length of the largest common prefix $a$ and $b$. We will represent such value as $LCP(a, b)$. Then we can determine the quality of matching of the pseudonyms to students as a sum of relevances of all pseudonyms to the corresponding students.
Find the matching between students and pseudonyms with the maximum quality.

题意概述

给定$2n$个字符串$s_i$,前$n$个为一组,后$n$个为一组。要求将它们建立匹配(不能匹配同一组的字符串),使得两两匹配的字符串的$LCP$的长度之和最大。求最大值及方案。
数据范围:$1 \le n \le 10^5, \; 1 \le \sum |s_i| \le 8 \times 10^5$。

算法分析

首先对所有串建立Trie树,并记录下每个节点是哪些串的前缀。
考虑贪心——在Trie树上DFS(后序遍历),若在一个节点上有未匹配的不同组的串,则直接将它们匹配。这样做的正确性是显而易见的:若它们在之后匹配或与其他串匹配,则一定没有直接匹配更优。
具体实现时可以用vector启发式合并来维护每个节点上的值。

代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

int min(int a, int b) {
  return a < b ? a : b;
}

static const int N = 800005;
int numn = 1, tot;
char s[N];
struct Trie {
  int child[26];
  std :: vector <int> rec[2];
} node[N];
std :: vector <std :: pair <int, int> > ans;

void insert(char s[], int id, int val) {
  int len = strlen(s), root = 0;
  for (int i = 0; i < len; ++ i) {
    if (! node[root].child[s[i] - 'a']) node[root].child[s[i] - 'a'] = numn ++;
    root = node[root].child[s[i] - 'a'];
  }
  node[root].rec[val].push_back(id);
}

void merge(std :: vector <int> &a, std :: vector <int> &b) {
  if (a.size() < b.size()) swap(a, b);
  a.insert(a.end(), b.begin(), b.end());
}

void dfs(int t, int dep) {
  for (int i = 0; i < 26; ++ i)
    if (node[t].child[i]) {
      dfs(node[t].child[i], dep + 1);
      merge(node[t].rec[0], node[node[t].child[i]].rec[0]);
      merge(node[t].rec[1], node[node[t].child[i]].rec[1]);
    }
  while (! node[t].rec[0].empty() && ! node[t].rec[1].empty()) {
    tot += dep;
    ans.push_back(std :: make_pair(node[t].rec[0][node[t].rec[0].size() - 1], node[t].rec[1][node[t].rec[1].size() - 1]));
    node[t].rec[0].pop_back(), node[t].rec[1].pop_back();
  }
}

int main() {
  int n; scanf("%d", &n);
  for (int i = 0; i < n; ++ i) scanf(" %s", s), insert(s, i + 1, 0);
  for (int i = 0; i < n; ++ i) scanf(" %s", s), insert(s, i + 1, 1);
  dfs(0, 0);
  printf("%d\n", tot);
  for (int i = 0; i < n; ++ i) printf("%d %d\n", ans[i].first, ans[i].second);
  return 0;
}

Games of Chess

题目描述

$N$ friends gathered in order to play chess, according to the following rules. In the first game, two of the $N$ friends will play. In the second game, the winner of the first game will play against another friend (maybe even the same friend who lost the first game). In the third game, the winner of the second game will play against someone else and so on.. No game will end as a draw (tie). Given the number of games each of the $N$ friends played, find a schedule for the games, so that the above rules are obeyed.

题意概述

有$N$个人玩游戏,第一局任意两个人参加,第一局胜利者和除他以外的一个人参加第二局(可以选择第一局失败者),第二局胜利者和除他以外的一个人参加第三局…不存在平局。给定每个人参加游戏的局数,构造一种可行的游戏方案。
数据范围:$2 \le N \le 100$。

算法分析

显然每个人参加游戏的次数之和为偶数,除以$2$即是游戏局数。考虑安排每一局的胜利者和失败者。设某个人参加游戏的次数为$n$,则先安排他连续胜利$(n-1)$局,接着失败一局,直到安排了所有局的胜利者。在安排失败者的时候,要注意不能和胜利者相同,因此应尽量先安排参加游戏局数较多的人胜利,减少冲突的可能。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
  static const int N = 110;
  int n, sum;
  pair <int, int> a[N];
  vector <pair <int, int> > ans;
  void input() {
    io > n;
    for (int i = 1; i <= n; ++ i) io > a[i].first, a[i].second = i, sum += a[i].first;
  }
  void process() {
    io < sum >> 1 < '\n';
    sort(a + 1, a + n + 1, greater <pair <int, int> >());
    int p = 1;
    for (int i = 0; i < sum >> 1; ++ i) {
      if (a[p].first == 1) ans.push_back(make_pair(a[p + 1].second, a[p].second)), -- a[p].first, -- a[++ p].first;
      else ans.push_back(make_pair(a[p].second, 0)), -- a[p].first;
    }
    for (int i = 0; i < sum >> 1; ++ i)
      if (! ans[i].second)
        for (int j = 1; j <= n; ++ j) if (a[j].first && a[j].second != ans[i].first) { ans[i].second = a[j].second, -- a[j].first; break; }
    for (int i = 0; i < sum >> 1; ++ i) io < ans[i].first < ' ' < ans[i].second < '\n';
  }

public:
  void solve() { input(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}

Best Edge Weight

题目描述

You are given a connected weighted graph with $n$ vertices and $m$ edges. The graph doesn’t contain loops nor multiple edges. Consider some edge with id $i$. Let’s determine for this edge the maximum integer weight we can give to it so that it is contained in all minimum spanning trees of the graph if we don’t change the other weights.
You are to determine this maximum weight described above for each edge. You should calculate the answer for each edge independently, it means there can’t be two edges with changed weights at the same time.

题意概述

给定一张$n$个点$m$条边的连通无向图,边权均为正数。对于每一条边,询问它的边权至多是多少,使得在其他边权不变的条件下,它在这张图的所有最小生成树中。
数据范围:$2 \le n \le 2 \times 10^5, \; n-1 \le m \le 2 \times 10^5$。

算法分析

题目要求一条边在所有最小生成树中。我们无法求出所有最小生成树,因此先求出其中一棵。这样,图中的边就被分成了两种:一种在这棵最小生成树中,另一种不在这棵最小生成树中。
对于不在这棵最小生成树中的边$(u, v)$,设它的权值为$w$。显然,它和最小生成树上从$u$到$v$的路径构成了一个环。设这条路径上边权的最大值$w_{max}$。如果$w \ge w_{max}$,那么$(u, v)$可能在这张图的一棵最小生成树中,但一定不是所有。因此,可以将$w$设成$w_{max}-1$,因为根据贪心策略,将路径上权值为$w_{max}$的边替换成$(u, v)$,会得到一棵更小的生成树。这种情况很好解决,只要在最小生成树上进行倍增就可以了。
对于在这棵最小生成树中的边$(u, v)$,设它的权值为$w$。假设我们找到了一条不经过这棵最小生成树上的边从$u$到$v$的路径,设这条路径上边权的最小值为$w_{min}$。类似于不在最小生成树的边,如果$w \ge w_{min}$,那么这条边一定不在所有最小生成树中。将它的权值设为$w_{min}-1$,即可满足要求。由于直接求$w_{min}$较为困难,因此可以按边权从小到大枚举不在这棵最小生成树中的边,并用它来更新最小生成树上的一条路径。因为是从小到大枚举,所以最小生成树上的每条边只需要被更新一次,可以用并查集维护。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct line {
  long long u, v, c, id; bool mst;
  bool operator < (const line &a) const { return c < a.c; }
} l[200001];
struct edge {
  long long v, c, id, nxt;
} e[400001];
long long n, m, nume, h[200001], fa[200001], ans[200001];
long long depth[200001], up[200001][20], ma[200001][20], uid[200001];
long long get_fa(long long t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); }
void add_edge(long long u, long long v, long long c, long long id) {
  e[++nume].v = v, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[u], h[u] = nume;
  e[++nume].v = u, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[v], h[v] = nume;
}
void dfs(long long t, long long fa) {
  for (int i = h[t]; i; i = e[i].nxt)
    if (e[i].v != fa) {
      depth[e[i].v] = depth[t] + 1, up[e[i].v][0] = t;
      ma[e[i].v][0] = e[i].c, uid[e[i].v] = e[i].id, dfs(e[i].v, t);
    }
}
long long get_max(long long u, long long v) {
  long long ret = 0;
  if (depth[u] < depth[v]) u ^= v ^= u ^= v;
  for (int i = 19; i >= 0; --i)
    if (depth[u] - depth[v] >= (1 << i))
      ret = max(ret, ma[u][i]), u = up[u][i];
  if (u == v) return ret;
  for (int i = 19; i >= 0; --i)
    if (up[u][i] != up[v][i])
      ret = max(ret, max(ma[u][i], ma[v][i])), u = up[u][i], v = up[v][i];
  return max(ret, max(ma[u][0], ma[v][0]));
}
void update(long long u, long long v, long long val) {
  if (depth[u] < depth[v]) u ^= v ^= u ^= v;
  long long p = u, q = v;
  for (int i = 19; i >= 0; --i)
    if (depth[p] - depth[q] >= (1 << i)) p = up[p][i];
  if (p != q) {
    for (int i = 19; i >= 0; --i)
      if (up[p][i] != up[q][i]) p = up[p][i], q = up[q][i];
    p = up[p][0];
  }
  u = get_fa(u), v = get_fa(v);
  while (depth[u] > depth[p])
    ans[uid[u]] = val - 1, q = get_fa(up[u][0]), fa[u] = q, u = get_fa(u);
  while (depth[v] > depth[p])
    ans[uid[v]] = val - 1, q = get_fa(up[v][0]), fa[v] = q, v = get_fa(v);
}
int main()
{
  cin >> n >> m, memset(ans, -1, sizeof ans);
  if (n == m + 1) {
    for (int i = 1; i <= m; cout << -1 << ' ', ++i); cout << endl; return 0;
  }
  for (int i = 1; i <= n; fa[i] = i, ++i);
  for (int i = 1; i <= m; cin >> l[i].u >> l[i].v >> l[i].c, l[i].id = i, ++i);
  sort(l + 1, l + m + 1);
  for (int i = 1; i <= m; ++i) {
    long long u = get_fa(l[i].u), v = get_fa(l[i].v);
    if (u != v) add_edge(l[i].u, l[i].v, l[i].c, l[i].id), fa[u] = v, l[i].mst = true;
  }
  depth[1] = 1, dfs(1, 0);
  for (int i = 1; i < 20; ++i)
    for (int j = 1; j <= n; ++j) {
      up[j][i] = up[up[j][i - 1]][i - 1];
      ma[j][i] = max(ma[j][i - 1], ma[up[j][i - 1]][i - 1]);
    }
  for (int i = 1; i <= n; fa[i] = i, ++i);
  for (int i = 1; i <= m; ++i)
    if (!l[i].mst) {
      ans[l[i].id] = get_max(l[i].u, l[i].v) - 1;
      update(l[i].u, l[i].v, l[i].c);
    }
  for (int i = 1; i <= m; cout << ans[i] << ' ', ++i);
  cout << endl;
  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;
}

Skills

题目描述

Lesha plays the recently published new version of the legendary game hacknet. In this version character skill mechanism was introduced. Now, each player character has exactly $n$ skills. Each skill is represented by a non-negative integer $a_i$ — the current skill level. All skills have the same maximum level $A$.
Along with the skills, global ranking of all players was added. Players are ranked according to the so-called Force. The Force of a player is the sum of the following values:

  • The number of skills that a character has perfected (i.e., such that $a_i=A$), multiplied by coefficient $c_f$.
  • The minimum skill level among all skills ($\min(a_i)$), multiplied by coefficient $c_m$.

Now Lesha has m hacknetian currency units, which he is willing to spend. Each currency unit can increase the current level of any skill by $1$ (if it’s not equal to $A$ yet). Help him spend his money in order to achieve the maximum possible value of the Force.

题意概述

给定$n$个技能,第$i$个技能的等级为$a_i$。所有技能的最高等级为$A$。你有$m$个技能点,每个技能点可以让某个技能升$1$级。给定两个数$c_f, c_m$,定义所有技能的价值总和为$c_f$乘满级技能的个数加$c_m$乘所有技能的最低等级。求价值总和的最大值。
数据范围:$1 \le n \le 10^5, \; 1 \le A \le 10^9, \; 0 \le c_f, c_m \le 1000, \; 0 \le m \le 10^{15}$。

算法分析

将技能按等级从小到大排序。记录两个指针$p, q$,$p$指针之后的技能都已满级,$q$指针之前的技能的等级极差不大于$1$。先计算出$p$的最小值,接着依次枚举$p$,同时根据贪心策略,前$q$个技能的等级越平均越好。这样就可以计算出答案。

代码

#include <iostream>
#include <algorithm>
using namespace std;
struct skill {
  long long a, id;
} s[100002];
bool cmp1(skill a, skill b) { return a.a < b.a; }
bool cmp2(skill a, skill b) { return a.id < b.id; }
long long n, A, cf, cm, m, ans, pnt, cnt, rec[3], pre[100002], suf[100002];
int main()
{
  cin >> n >> A >> cf >> cm >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> s[i].a; s[i].id = i;
  }
  sort(s + 1, s + n + 1, cmp1);
  for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + s[i].a;
  for (int i = n; i; --i) suf[i] = suf[i + 1] + s[i].a;
  cnt = 0, pnt = n, rec[0] = n + 1;
  while (pnt > 0 && (n - pnt + 1) * A - suf[pnt] <= m) --pnt;
  for (++pnt; pnt <= n + 1; ++pnt) {
    long long rem = m - (n - pnt + 1) * A + suf[pnt];
    while (cnt < pnt && s[cnt].a * cnt - pre[cnt] <= rem) ++cnt; --cnt;
    if (cnt) (rem -= s[cnt].a * cnt - pre[cnt]) /= cnt; else rem = 1e18;
    if (ans < (n - pnt + 1) * cf + min((s[cnt].a + rem), A) * cm) {
      ans = (n - pnt + 1) * cf + min((s[cnt].a + rem), A) * cm;
      rec[0] = pnt, rec[1] = cnt, rec[2] = min((s[cnt].a + rem), A);
    }
  }
  for (int i = 1; i <= rec[1]; ++i) s[i].a = rec[2];
  for (int i = rec[0]; i <= n; ++i) s[i].a = A;
  sort(s + 1, s + n + 1, cmp2);
  cout << ans << endl;
  for (int i = 1; i <= n; ++i) cout << s[i].a << ' ';
  cout << endl;
  return 0;
}

Office Keys

题目描述

There are $n$ people and $k$ keys on a straight line. Every person wants to get to the office which is located on the line as well. To do that, he needs to reach some point with a key, take the key and then go to the office. Once a key is taken by somebody, it couldn’t be taken by anybody else.
You are to determine the minimum time needed for all $n$ people to get to the office with keys. Assume that people move a unit distance per $1$ second. If two people reach a key at the same time, only one of them can take the key. A person can pass through a point with a key without taking it.

题意概述

在一条数轴上有$n$个人和$k$把钥匙。每个人一秒可以移动一个单位长度。已知办公室的位置在$p$,求所有人都拿到一把钥匙并到达办公室的最少时间。
数据范围:$1 \le n \le 1000, \; 1 \le k \le 2000, \; 1 \le p \le 10^9$。

算法分析1

考虑贪心策略,一定有一组最优解中所有人选的钥匙在排序后是连续的。否则,可以将钥匙向靠近门的方向移动使它们连续,这不会使答案变劣。因此可以直接暴力枚举。

代码1

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int n, k, p, ans = 2e9, a[1001], b[2001];
int get_dist(int x, int y) { return abs(a[x] - b[y]) + abs(b[y] - p); }
int main()
{
  cin >> n >> k >> p;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= k; ++i) cin >> b[i];
  sort(a + 1, a + n + 1), sort(b + 1, b + k + 1);
  for (int i = 1; i <= k - n + 1; ++i) {
    int ma = 0;
    for (int j = i; j <= i + n - 1; ++j) ma = max(ma, get_dist(j - i + 1, j));
    ans = min(ans, ma);
  }
  cout << ans << endl;
  return 0;
}

算法分析2

令$f_{i, j}$表示前$i$个人拿前$j$把钥匙的最少时间,DP解决问题。

代码2

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n, k, p, a[1001], b[2001], f[1001][2001];
int get_dist(int x, int y) { return abs(a[x] - b[y]) + abs(b[y] - p); }
int main()
{
  cin >> n >> k >> p; memset(f, 0x7f, sizeof(f));
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= k; ++i) cin >> b[i];
  sort(a + 1, a + n + 1), sort(b + 1, b + k + 1);
  for (int i = 0; i <= k; ++i) f[0][i] = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = i; j <= k; ++j)
      f[i][j] = min(f[i][j - 1], max(f[i - 1][j - 1], get_dist(i, j)));
  cout << f[n][k] << endl;
  return 0;
}

High Load

题目描述

Arkady needs your help again! This time he decided to build his own high-speed Internet exchange point. It should consist of $n$ nodes connected with minimum possible number of wires into one network (a wire directly connects two nodes). Exactly $k$ of the nodes should be exit-nodes, that means that each of them should be connected to exactly one other node of the network, while all other nodes should be connected to at least two nodes in order to increase the system stability.
Arkady wants to make the system as fast as possible, so he wants to minimize the maximum distance between two exit-nodes. The distance between two nodes is the number of wires a package needs to go through between those two nodes.
Help Arkady to find such a way to build the network that the distance between the two most distant exit-nodes is as small as possible.

题意概述

构造一棵有$n$个节点的树,使得这棵树恰有$k$个叶子节点,且直径最小。
数据范围:$3 \le n \le 2 \times 10^5, \; 2 \le k \le n-1$。

算法分析

首先确定一个根节点,从它引出$k$个叶子节点。接着从这$k$个叶子节点一层一层往外扩展,每次扩展一个节点,直到树中的节点数为$n$。此时树的直径就是深度最大的两个节点的深度和。证明如下:

假设根节点连出的某棵子树中有两个以上的叶子节点,我们可以找出它们的LCA,并将LCA和它到根节点路径上的所有点“分裂”成两个节点。由于这个操作使得树中的节点数增加,因此需要删去一些叶子节点。这样并不会使树的直径增加。

由此得证。

代码

#include <cstdio>
#include <queue>
using namespace std;
struct edge {
  int v, nxt;
} e[400001];
int n, m, nume, h[200001], depth[200001];
queue<int> que;
void add_edge(int u, int v) {
  e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
}
int main()
{
  scanf("%d%d", &n, &m);;
  for (int i = 1; i <= m; ++i) {
    add_edge(1, i + 1), depth[i + 1] = 1;
    que.push(i + 1);
  }
  for (int i = m + 2; i <= n; ++i) {
    int u = que.front(); que.pop();
    add_edge(u, i), depth[i] = depth[u] + 1;
    que.push(i);
  }
  printf("%d\n", depth[n] + depth[n - 1]);
  for (int i = 1; i <= n; ++i) {
    for (int j = h[i]; j; j = e[j].nxt) {
      printf("%d %d\n", i, e[j].v);
    }
  }
  return 0;
}

Calculator

题目描述

Chef has a calculator which has two screens and two buttons. Initially, each screen shows the number zero. Pressing the first button increments the number on the first screen by $1$, and each click of the first button consumes $1$ unit of energy.
Pressing the second button increases the number on the second screen by the number which is currently appearing on the first screen. Each click of the second button consumes $B$ units of energy.
Initially the calculator has $N$ units of energy.
Now chef wonders what the maximum possible number is, that he gets on the second screen of the calculator, with the limited energy.

题意概述

有两个按钮和两个初始为$0$的数字,按下第一个按钮可以消耗$1$单位能量使第一个数字加$1$,按下第二个按钮可以消耗$B$单位能量使第二个数字加上第一个数字。总共有$N$单位能量,问第二个数字最大能达到多少。
数据范围:$1 \le N, B \le 10^9$。

算法分析

根据贪心策略,按第一个按钮的操作一定在按第二个按钮的操作之前(否则交换一下顺序一定能得到更优解)。设按下第一个按钮$x$次,则第二个数字$y={N-x \over B}x$,对称轴为$x={N \over 2}$。令$a={N-x \over B}$,当$x={N \over 2}$时$a={N \over 2B}$。由于$a$是整数(否则会造成能量浪费),因此只需计算$a=\left\lfloor {N \over 2B} \right\rfloor$和$a=\left\lceil {N \over 2B} \right\rceil$时$y$的值,取较大者即可。

代码

#include <iostream>
#include <cmath>
using namespace std;
long long T, n, b, p, q, x, ans;
long double k;
int main()
{
  cin >> T;
  while (T--) {
    cin >> n >> b;
    ans = 0;
    k = 1.0 * n / 2 / b;
    p = floor(k), q = ceil(k);
    x = n - b * p;
    if (x > 0 && x < n) ans = max(ans, p * x);
    x = n - b * q;
    if (x > 0 && x < n) ans = max(ans, q * x);
    cout << ans << endl;
  }
  return 0;
}

Till I Collapse

题目描述

Rick and Morty want to find MR. PBH and they can’t do it alone. So they need of Mr. Meeseeks. They Have generated $n$ Mr. Meeseeks, standing in a line numbered from $1$ to $n$. Each of them has his own color. $i$-th Mr. Meeseeks’ color is $a_i$.
Rick and Morty are gathering their army and they want to divide Mr. Meeseeks into some squads. They don’t want their squads to be too colorful, so each squad should have Mr. Meeseeks of at most $k$ different colors. Also each squad should be a continuous subarray of Mr. Meeseeks in the line. Meaning that for each $1 \le i \le e \le j \le n$, if Mr. Meeseeks number $i$ and Mr. Meeseeks number $j$ are in the same squad then Mr. Meeseeks number $e$ should be in that same squad.
Also, each squad needs its own presidio, and building a presidio needs money, so they want the total number of squads to be minimized.
Rick and Morty haven’t finalized the exact value of $k$, so in order to choose it, for each $k$ between $1$ and $n$ (inclusive) need to know the minimum number of presidios needed.

题意概述

给定一个长度为$n$的数列,第$i$个数为$a_i$。要求将它们分成若干连续段。对于所有$k \in [1, n]$,问至少分成多少段,使得每一段中数字的种类数不超过$k$。
数据范围:$1 \le a_i \le n \le 10^5$。

算法分析1

有个显然的贪心策略:每一段越长越好。
容易发现答案一定单调不递增。对于$i \le j$,如果$ans_i=ans_j$,那么$ans_i=ans_{i+1}=ans_{i+2}= \cdots =ans_j$。因此我们可以贪心$O(n)$计算出左端点和右端点的$ans$,若它们相等,则将这个区间中的$ans$全都赋成左端点的$ans$;否则,取区间中点,并递归处理左右两个区间。

代码1

#include <cstdio>
#include <cstring>
using namespace std;
int n, last, a[100001], c[100001], ans[100001];
int get(int t) {
  memset(c, 0, sizeof(c));
  int p = 0, q = 1, ret = 0;
  while (q <= n) {
    int cnt = 1; c[a[q]] = 1;
    while (q < n) {
      if (cnt < t || c[a[q + 1]]) {
        cnt += !c[a[++q]], ++c[a[q]];
      } else break;
    }
    while (p < q) --c[a[++p]];
    ++q, ++ret;
  }
  return ret;
}
void solve(int l, int r) {
  if (l > r) return;
  ans[l] = get(l), ans[r] = get(r);
  if (ans[l] == ans[r]) {
    for (int i = l + 1; i < r; ++i) ans[i] = ans[l];
    return;
  }
  int mid = l + r >> 1;
  solve(l + 1, mid), solve(mid + 1, r - 1);
}
int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  solve(1, n);
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}

算法分析2

建可持久化线段树,第$i$个节点上的线段树维护区间$[j, i]$中数字的种类数。当遇到一个前面已经出现过的数字时,就在前面出现的位置上减一,在当前位置上加一。枚举$k$,并依据上述贪心策略,即可得到答案。

代码2

#include <cstdio>
using namespace std;
struct node_type {
  int val, child[2];
} node[4000001];
int n, tot, ans, a[100001], root[100001], pre[100001];
int insert_line(int root, int l, int r, int p, int val) {
  if (l == r) {
    node[++tot].val = node[root].val + val;
    node[tot].child[0] = node[tot].child[1] = 0;
    return tot;
  }
  int mid = l + r >> 1, ch;
  if (p <= mid) {
    ch = insert_line(node[root].child[0], l, mid, p, val);
    node[++tot].child[0] = ch, node[tot].child[1] = node[root].child[1];
  } else {
    ch = insert_line(node[root].child[1], mid + 1, r, p, val);
    node[++tot].child[0] = node[root].child[0], node[tot].child[1] = ch;
  }
  node[tot].val = node[node[tot].child[0]].val + node[node[tot].child[1]].val;
  return tot;
}
int query(int root, int l, int r, int p) {
  if (l == r) if (p >= node[root].val) return l; else return l + 1;
  int mid = l + r >> 1;
  if (p >= node[node[root].child[1]].val) return query(node[root].child[0], l, mid, p - node[node[root].child[1]].val);
  else return query(node[root].child[1], mid + 1, r, p);
}
int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  pre[a[1]] = 1, root[1] = insert_line(0, 1, n, 1, 1);
  for (int i = 2; i <= n; ++i) {
    int rt = root[i - 1];
    if (pre[a[i]]) rt = insert_line(rt, 1, n, pre[a[i]], -1);
    pre[a[i]] = i, root[i] = insert_line(rt, 1, n, i, 1);
  }
  for (int i = 1; i <= n; ++i) {
    if (ans != 1) {
      ans = 0;
      int l = n, r;
      while (l) r = l, l = query(root[r], 1, n, i) - 1, ++ans;
    }
    printf("%d ", ans);
  }
  printf("\n");
  return 0;
}