目录

• 写在前面
• A
• B
• C
• D
• E
• F
• G
• 总结

写在前面

比赛地址：https://codeforces.com/contest/1433。

草 div3 的难度有点亲民了/jk

A

Link。

没啥意思。

模拟即可。

//知识点：模拟
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#define LL long long
const int kN = 1e4 + 10;
//=============================================================
int t, x, ans[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) {
    w = (w << 3) + (w << 1) + (ch ^ '0');
  }
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
//=============================================================
int main() {
  for (int i = 1, last = 0; i <= 9; ++ i) {
    int now = i;
    for (int j = 1; now <= 10000; ++ j) {
      ans[now] = ans[last] + j;
      last = now;
      now = 10 * now + i;
    }
  }
  
  t = read();
  while (t --) {
    x = read();
    printf("%d\n", ans[x]);
  }
  return 0;
}

B

Link。

\(t\) 组数据，每次给定一长度为 \(n\) 的 01 序列，每次操作可以选择一段连续的 1 使其左移/右移 1位，不能移出边界。
求使所有 1 连续的最小操作数。
\(1\le t\le 200\)，\(1\le n\le 50\)。
1S，256MB。

显然答案即两个距离最远的 1 的距离，减去中间的 1 的数量。
移动时选择距离最远的 1 其中的一个，每次选择一段以它为端点的最长的 1，不断向另一个移动。

注意特判不需要移动。

//知识点：思维
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#define LL long long
const int kN = 50 + 10;
//=============================================================
int t, n, fir, las, cnt[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) {
    w = (w << 3) + (w << 1) + (ch ^ '0');
  }
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
//=============================================================
int main() {
  t = read();
  while (t --) {
    n = read();
    for (int i = 1; i <= n; ++ i) {
      cnt[i] = cnt[i - 1] + read();
      if (!cnt[i - 1] && cnt[i] == 1) fir = i;
      if (cnt[i] > cnt[i - 1]) las = i;
    }
    if (las <= fir + 1) {
      printf("0\n");
    } else {
      printf("%d\n", las - fir - 1 - (cnt[las - 1] - cnt[fir]));  
    }
    
  }
  return 0;
}

C

Link。

\(t\) 组数据，每次有 \(n\) 条鱼排成一个序列，第 \(i\) 条鱼的体积为 \(a_i\)。
每条鱼可以吃掉与自己相邻，且体积小于它的鱼，被吃掉的鱼将消失，吃鱼的鱼体积将会 \(+1\)。
求是否存在一条鱼，以任意方案吃鱼后，能够吃掉所有的鱼。若存在则输出其中一条的编号。
\(1\le t\le 2\times 10^4\)，\(2\le \sum n\le 3\times 10^5\)，\(1\le a_i\le 10^9\)。
2S，256MB，有 SPJ。

显然当 \(a\) 均相等时不存在。

否则显然应让体积最大的鱼开始吃，若存在一条鱼的体积最大，且与它相邻的鱼中有一条的体积比它小，它必将加冕为王。输出它的编号即可。
排个序就做完了。

//知识点：思维
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#define LL long long
const int kN = 3e5 + 10;
const int kInf = 1e9 + 2077;
//=============================================================
struct Data {
  int pos, val;
} a[kN];
int t, n, ori[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) {
    w = (w << 3) + (w << 1) + (ch ^ '0');
  }
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
bool CMP(Data fir_, Data sec_) {
  if (fir_.val != sec_.val)return fir_.val > sec_.val;
  return fir_.pos < sec_.pos;
}
//=============================================================
int main() {
  t = read();
  while (t --) {
    n = read();
    ori[0] = ori[n + 1] = kInf;
    for (int i = 1; i <= n; ++ i) {
      ori[i] = read();
      a[i] = (Data) {i, ori[i]};
    }
    std::sort(a + 1, a + n + 1, CMP);
    
    if (a[1].val == a[n].val) {
      printf("%d\n", -1);
      continue ;
    }
    for (int i = 1; i <= n; ++ i) {
      if (ori[a[i].pos - 1] < a[i].val || ori[a[i].pos + 1] < a[i].val) {
        printf("%d\n", a[i].pos);
        break;
      }
    }
  }
  return 0;
}

D

Link。

给定 \(n\) 个节点，第 \(i\) 个节点的颜色为 \(a_i\)。
判断能否构造一棵树，使得颜色相同的点不直接连边，若可以则输出一种方案。
\(1\le t\le 500\)，\(2\le \sum n\le 5000\)，\(1\le a_i\le 10^9\)。
1S，256MB，有 SPJ。

只求方案，可以随便 YY 一个类似 Prim 的算法出来。
从 1 节点开始 bfs，每次往未加入树的、颜色不同的点连边，记录方案并将该点加入队列。
连边数 \( 说明无解。
时间复杂度 \(O(n^2)\) 级别。

//知识点：图论
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
const int kN = 5e3 + 10;
//=============================================================
int n, a[kN];
std::vector  ansu, ansv;
bool vis[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) {
    w = (w << 3) + (w << 1) + (ch ^ '0');
  }
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
bool Bfs() {
  std::queue  q;
  q.push(1);
  vis[1] = true;
  int tot = 0;
  while (! q.empty()) {
    int u = q.front();
    q.pop();
    for (int v = 1; v <= n; ++ v) {
      if (a[u] == a[v]) continue ;
      if (vis[v]) continue ;
      ++ tot;
      vis[v] = true;
      ansu.push_back(u);
      ansv.push_back(v);
      q.push(v);
    }
  }
  return tot >= n - 1;
}
//=============================================================
int main() {
  int t = read();
  while (t --) {
    n = read();
    for (int i = 1; i <= n; ++ i) {
      a[i] = read();
      vis[i] = false; 
    }
    ansu.clear(), ansv.clear();
    if (Bfs()) {
      printf("YES\n");
      for (int i = 0; i < n - 1; ++ i) {
        printf("%d %d\n", ansu[i], ansv[i]);
      }
    } else {
      printf("NO\n");
    }
  }
  return 0;
}

E

Link。

给定参数 \(n\)，将 \(1\sim n\) 分为两个大小为 \(\frac{n}{2}\) 的圆排列，求方案数。
认为两种方案相同当且仅当 两圆排列分别相同。
\(2\le n\le 20\)，保证 \(n\) 是偶数。
1S，256MB。

先考虑两个圆排列内有的元素集合，显然有 \(\frac{\binom{n}{\frac{n}{2}}}{2}\) 种方案，除 \(2\) 是因为圆排列无序。
再考虑 \(\frac{n}{2}\) 个元素构成的一个圆排列的种类数，考虑插空，显然种类数为 \(\left(\frac{n}{2} - 1\right)!\)。
则答案即为：

\[\frac{\binom{n}{\frac{n}{2}}\cdot \left[\left(\frac{n}{2} - 1\right)!\right]^2}{2} \]

\(O(n)\) 预处理下阶乘即可。

//知识点：组合数学
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#define LL long long
const int kN = 100 + 10;
//=============================================================
LL fac[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) {
    w = (w << 3) + (w << 1) + (ch ^ '0');
  }
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
//=============================================================
int main() {
  fac[0] = 1;
  LL n = read();
  for (int i = 1; i <= n; ++ i) {
    fac[i] = 1ll * fac[i - 1] * i; 
  }
  LL ans = ((fac[n] / fac[n / 2]) / fac[n / 2]) / 2ll;
  ans = ans * fac[n / 2 - 1] * fac[n / 2 - 1];
  printf("%lld\n", ans);
  return 0;
}

F

Link。

给定一 \(n\times m\) 的数字矩阵 \(a\)，参数 \(k\)。
要求在矩阵中选择一些数，使得每行选择的数量不超过 \(\frac{m}{2}\)，且数的总和是 \(k\) 的倍数。
最大化选择的数的和。
\(1\le n,m,k, a_{i,j}\le 70\)。
1S，256MB。

这数据范围显然是给 \(O(n^4)\) 草的，考虑暴力 DP。
设 \(f_{i,j,cnt,r}\) 表示第 \(i\) 行，考虑到第 \(j\) 个数，选择了 \(cnt\) 个数，选择的数之和 \(\bmod k = r\) 时，选择的数之和的最大值。

初始化 \(f_{i,j,0,0} = 0\)，其他 \(f = -\infin\)。
转移时暴力转移即可，有：

\[f_{i,j,cnt,r} = \max{\{f_{i,j-1,cnt,r},\ f_{i,j-1,cnt-1,(r-a_{i,j})\bmod k} + a_{i,j}\}} \]

再设 \(g_{i,j}\) 表示在前 \(i\) 行选出了一些数，选择的数之和 \(\bmod k = j\) 时，选择的数之和的最大值。

初始化 \(g_{0,0} = 0\)，其他 \(g = -\infin\)。
转移时枚举第 \(i\) 行选数的情况，暴力转移，有：

\[g_{i,j} = \max{\{g_{i-1, (j-f_{i,m,cnt, r})\bmod k} + f_{i,m,cnt, r}\}} \]

发现 \(f\) 的第一维并没有什么用，实现时删除即可。
最后的答案即为 \(g_{n,0}\)。

总时间复杂度 \(O(n^4)\)。

//知识点：DP
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#define LL long long
const int kN = 70 + 10;
const int kInf = 1e9 + 2077;
//=============================================================
int n, m, k, a[kN][kN];
int f[kN][kN][kN], g[kN][kN];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) {
    w = (w << 3) + (w << 1) + (ch ^ '0');
  }
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
//=============================================================
int main() {
  n = read(), m = read(), k = read();
  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= m; ++ j) {
      a[i][j] = read();
    }
  }
  
  memset(g, 128, sizeof (g));
  g[0][0] = 0;
  for (int i = 1; i <= n; ++ i) {
    memset(f, 128, sizeof (f));
    for (int j = 0; j <= m; ++ j) {
      f[j][0][0] = 0;
    }
    
    for (int j = 1; j <= m; ++ j) {
      for (int cnt = 1; cnt <= m / 2; ++ cnt) {
        for (int r = 0; r < k; ++ r) {
          f[j][cnt][r] = f[j - 1][cnt][r];
          int val = f[j - 1][cnt - 1][(r - a[i][j] % k + k) % k];
          if (val < 0) continue ;
          Chkmax(f[j][cnt][r], val + a[i][j]);
        }
      }
    }
    
    for (int r = 0; r < k; ++ r) {
      for (int cnt = 0; cnt <= m / 2; ++ cnt) {
        for (int rr = 0; rr < k; ++ rr) {
          int val = f[m][cnt][rr];
          if (val < 0) continue ;
          Chkmax(g[i][r], g[i - 1][(r - val % k + k) % k] + val);
        }
      }
    }
  }
  printf("%d\n", g[n][0]);
  return 0;
}

G

给定一 \(n\) 个点 \(m\) 条边的无向图，边有边权。并给定 \(k\) 组点对。
可使任意一条边权置零，最小化 \(k\) 组点对最短路径的长度之和。
\(2\le n,m\le 10^3\)，\(n-1\le m\le \frac{n(n-1)}{2}\)，\(1\le k\le 10^3\)，\(1\le\) 边权 \(\le 10^3\)。
1S，256MB。

\(n,m\) 都很小，又全是正权，先 \(O(n(n+m)\log (n+m))\) 地把两两之间的最短路 \(dis\) 跑出来。

考虑置零边 \(d(u,v)\) 对点对 \((x,y)\) 的影响。
若置零后 \(x\rightarrow y\) 的最短路经过 \(d(x,y)\)，考虑把最短路拆成三部分，显然最短路长度为 \(\min{(dis_{x,u} + dis_{y,v},\ dis_{x,v} +dis_{y,u})}\)。
若置零后 \(x\rightarrow y\) 的最短路不经过 \(d(x,y)\)，则 \(x\rightarrow y\) 的最短路长度仍为 \(dis_{x,y}\)。
两种情况取最小值即为置零边 \(d(x,y)\) 后 \(x\rightarrow y\) 的最短路。

暴力枚举置零边，再枚举点对检查即可。
总复杂度 \(O(n(n+m)\log (n+m) + mk)\)。

//知识点：最短路 
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define pr std::pair
#define mp std::make_pair
const int kN = 1e3 + 10;
const int kInf = 1e9 + 2077;
//=============================================================
int n, m, k, ans, dis[kN][kN];
int e_num, head[kN], v[kN * kN], w[kN * kN], ne[kN * kN];
int qu[kN], qv[kN];
bool vis[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) {
    w = (w << 3) + (w << 1) + (ch ^ '0');
  }
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
void AddEdge(int u_, int v_, int w_) {
  v[++ e_num] = v_;
  w[e_num] = w_;
  ne[e_num] = head[u_];
  head[u_] = e_num;
}
void Dijkstra(int s_) {
  std::priority_queue  > q;
  memset(dis[s_], 63, sizeof (dis[s_]));
  memset(vis, 0, sizeof (vis));
  dis[s_][s_] = 0;
  q.push(mp(0, s_));
  while (! q.empty()) {
    int u_ = q.top().second;
    q.pop();
    if (vis[u_]) continue ;
    vis[u_] = true;
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i], w_ = w[i];
      if (dis[s_][v_] > dis[s_][u_] + w_) {
        dis[s_][v_] = dis[s_][u_] + w_;
        q.push(mp(-dis[s_][v_], v_));
      }
    }
  }
}
//=============================================================
int main() {
  n = read(), m = read(), k = read();
  for (int i = 1; i <= m; ++ i) {
    int u_ = read(), v_ = read(), w_ = read();
    AddEdge(u_, v_, w_), AddEdge(v_, u_, w_);
  }
  for (int i = 1; i <= n; ++ i) Dijkstra(i);
  for (int i = 1; i <= k; ++ i) {
    qu[i] = read(), qv[i] = read();
    ans += dis[qu[i]][qv[i]];
  }
  for (int u_ = 1; u_ <= n; ++ u_) {
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i], sum = 0;
      for (int j = 1; j <= k; ++ j) {
        int val = std::min(dis[qu[j]][u_] + dis[qv[j]][v_], 
                           dis[qu[j]][v_] + dis[qv[j]][u_]);
        sum += std::min(dis[qu[j]][qv[j]], val);
      }
      Chkmin(ans, sum);
    }
  }
  printf("%d\n", ans);
  return 0;
}

总结

确实没啥意思，以后不打 div3 了= =