Problem A. 文具订购

枚举最小值。

问题就变成了求解二元方程的解

三个数相互互质,所以可以直接枚举答案。以$4a+3b=k$为例,若要使答案最大,那么$a\in[0,3)$,接下来就是一个模拟

时间复杂度 $O(n)$

#include <bits/stdc++.h>
using namespace std;
template <class T>
void chkmax(T& x, T y) {
  x = x > y ? x : y;
}
template <class T>
void chkmin(T& x, T y) {
  x = x < y ? x : y;
}
template <class T>
void read(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  x *= f;
}
template <class T>
void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}
template <class T>
void writeln(T x) {
  write(x), puts("");
}
int a, b, c, n;
void update(int x, int y, int z) {
  if (min(x, min(y, z)) > min(a, min(b, c)) || (min(x, min(y, z)) > min(a, min(b, c)) && (x + y + z > a + b + c))) {
    a = x, b = y, c = z;
  }
}
int main() {
  a = -1, b = -1, c = -1;
  read(n);
  for (int i = 0; i * 14 <= n; i++) {
    int r = n - i * 14;
    for (int j = 0; j < 3; j++) {
      if ((r - j * 4) % 3 == 0 && j * 4 <= r) {
        update(i + (r - j * 4) / 3, i + j, i);
        break;
      }
    }
    for (int j = 0; j < 3; j++) {
      if ((r - j * 7) % 3 == 0 && j * 7 <= r) {
        update(i + (r - j * 7) / 3, i, i + j);
        break;
      }
    }
    for (int j = 0; j < 4; j++) {
      if ((r - j * 7) % 4 == 0 && j * 7 <= r) {
        update(i, i + (r - j * 7) / 4, i + j);
        break;
      }
    }
  }
  if (a == -1 && b == -1 && c == -1) {
    cout << -1 << '\n';
  } else {
    cout << c << ' ' << b << ' ' << a << '\n';
  }
  return 0;
}

Problem B. 跑步

Solution 1

有序转无序,题目就变成了有多少种本质不同的拆分数的方案数。

考虑朴素$DP$,定义$f[i][j]$为$[1,i]$,和为$j$的方案数。

转移方程为 $f[i][j]=f[i-1][j-i]+f[i][j-i]$

考虑根号分治,定义阈值$lim=\sqrt n$,所有的拆分方法都满足有$< lim$和$\geq lim$的部分。

$\geq lim$的部分考虑$DP$,定义状态为$g[i][j]$表示有$i$个$\geq lim$的数,和为$j$的方案总数。

转移方程为$g[i][j]=g[i-1][j-lim]+g[i][j-i]$

这个转移比较巧妙,第一部分是加入一个新的$lim$,第二部分是当前所有的数$+1$,你会发现所有的方案都是通过这样的操作实现的。

最后在统计所有的方案数即可。

时间复杂度 $O(n\sqrt n)$

#include <bits/stdc++.h>
#define For(i, s, t) for (int i = s; i <= t; i++) 
using namespace std;
template <class T>
void chkmax(T& x, T y) {
  x = x > y ? x : y;
}
template <class T>
void chkmin(T& x, T y) {
  x = x < y ? x : y;
}
template <class T>
void read(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  x *= f;
}
template <class T>
void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}
template <class T>
void writeln(T x) {
  write(x), puts("");
}
const int N = 1e5 + 5;
int f[N], g[350][N];
int n, mod, lim;
int main() {
  read(n), read(mod);
  f[0] = 1;
  lim = sqrt(n);
  For (i, 1, lim - 1) {
    For (j, i, n) {
      f[j] = (f[j] + f[j - i]) % mod;
    }
  }
  g[0][0] = 1;
  For (i, 1, lim + 1) {
    For (j, i * lim, n) {
      g[i][j] = (g[i - 1][j - lim] + g[i][j - i]) % mod;
    }
  }
  int ans = 0;
  For (i, 0, n) {
    int sum = 0;
    For (j, 0, lim + 1) {
      sum = (sum + g[j][n - i]) % mod;
    }
    ans = (ans + (long long)sum * f[i]) % mod; 
  }
  writeln(ans); 
  return 0;
}

Solution 2

五边形数定理,To be continued

Problem C. 魔法

这题其实考察了一个小$\mathrm {trick}$。

这个$\mathrm {trick}$我第一次见到是在做 IOI2020 国家集训队作业的时候看到的,题号是Codeforces 576D

对于一个邻接矩阵$G$,那么$G^k$表示的就是恰好经过$k$后的状态。

举一个比较简单的例子:

$G$是一个简单的$01$邻接矩阵,$G(i,j)$表示的就是在一步内$i\rightarrow j$的方案数,$0$即意味着两者之间没有连边,也意味着$1$步内有$0$种到达的方案,$1$也同理。然后再在这个邻接矩阵做$k$遍矩阵乘法后,得到的$G'$中$(i,j)$就是在恰好走了$k$步,从$i\rightarrow j$的方案数。

这个其实就代替了做动态规划的必要

因为这$k$步,每一步的本质相同,只是对应的状态不同,所以我们考虑重载矩阵乘法的定义,了解过动态 DP 的读者也可以类比动态 DP。

对应到这道题,我们首先计算出一步能够得到的状态,然后用相同的转移来做矩阵快速幂即可。

时间复杂度 $O(n^3Log_2 k)$

#define int long long
const int N = 105;
const int M = 2505;
int n, m, kk;
struct Matrix {
  int a[N][N];
  int* operator[](int i) {
    return a[i];
  }
  Matrix operator*(Matrix oth) {
    Matrix res; 
    memset(res.a, 0x3f, sizeof res.a);
    For (k, 0, n - 1) {
      For (i, 0, n - 1) {
        For (j, 0, n - 1) {
          chkmin(res[i][j], a[i][k] + oth[k][j]);
        }
      }
    } 
    return res;
  }
  friend Matrix operator^(Matrix x, int idx) {
    Matrix res = x; 
    idx--;
    for (; idx; idx >>= 1, x = x * x) {
      if (idx & 1) {
        res = res * x;
      }
    }
    return res;
  }
};
struct Path {
  int u, v, t;
} path[M];
int g[N][N];
signed main() {
  memset(g, 0x3f, sizeof g);
  read(n), read(m), read(kk);
  For (i, 0, m - 1) {
    read(path[i].u), read(path[i].v), read(path[i].t);
    path[i].u--, path[i].v--;
    g[path[i].u][path[i].v] = path[i].t;
  }
  For (i, 0, n - 1) {
    g[i][i] = 0;
  }
  For (k, 0, n - 1) {
    For (i, 0, n - 1) {
      For (j, 0, n - 1) {
        chkmin(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
  Matrix base;
  memset(base.a, 0x3f, sizeof base.a);
  For (i, 0, n - 1) {
    base[i][i] = 0;
  }
  For (i, 0, m - 1) {
    int u = path[i].u, v = path[i].v, t = path[i].t;
    For (j, 0, n - 1) {
      For (k, 0, n - 1) {
        chkmin(base[j][k], g[j][u] - t + g[v][k]);
      }
    } 
  }
  if (kk) {
    writeln((base ^ kk)[0][n - 1]);
  } else {
    writeln(g[0][n - 1]);
  }
  return 0;
}
最后修改:2020 年 04 月 11 日 09 : 10 PM
如果觉得我的文章对你有用,请随意赞赏