NOIP2009普及组题解

多项式输出

给一个存了多项式系数的数组，按一定规则输出多项式。

题解

模拟。

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, a[N];
int main() {
  cin >> n;
  for (int i = n; i >= 0; i--) cin >> a[i];
  for (int i = n; i >= 0; i--) {
    if (a[i] == 0) {
      continue;
    }
    if (a[i] > 0) {
      if(i != n) {
        putchar('+');
      }
    } else {
      a[i] = -a[i];
      putchar('-');
    }
    if (i > 1) {
      if (a[i] != 1) {
        cout << a[i];
      }
      cout << "x^" << i;
    } else if (i == 1) {
      if (a[i] != 1) {
        cout << a[i];
      }
      cout << "x";
    } else {
      cout << a[i];
    }
  }
}

分数线划定

有n个选手，选出分数排行前150%*m的选手，分数相同顺延。

题解

模拟。

#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int n, m;
struct P {
  int k, s;
  friend int operator<(P a, P b) {
    return a.s > b.s || a.s == b.s && a.k < b.k;
  }
}a[N];
int main() {
  cin >> n >> m;
  m += m / 2;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].k >> a[i].s;
  }
  sort(a + 1, a + n + 1);
  for (int i = m; i <= n; i++) {
    if (a[i].s != a[m].s) {
      break;
    } else {
      m = i;
    }
  }
  cout << a[m].s << ' ' << m << endl;
  for (int i = 1; i <= m; i++) {
    cout << a[i].k << ' ' << a[i].s << endl;
  }
}

细胞分裂

求最小的$x$使得存在${m_1}^{m_2}|S^{x}$，如果不存在输出-1。

题解

先将${m_1}$质因数分解${m_1}=\prod{p_i^{n_i}}$，于是${m_1}^{m_2}=\prod{p_i^{n_im_2}}$。如果有解，那么$S$必然包含$m_1$分解之后所有的质因数$p_i$。假设$S$对于每个$p_i$可以分解$q_i$个，如果${m_1}^{m_2}|S^{x}$，那么$p_i^{q_ix}|p_i^{n_im_2}$，得到不等式$q_i{x}\geq{n_im_2}$成立，于是$x\geq \lceil\frac {n_im_2} {q_i}\rceil$，对于S得到$x=\min \lceil\frac {n_im_2} {q_i}\rceil$

#include <bits/stdc++.h>
using namespace std;
const int N = 45000;
vector<int> p;
int n, m1, m2, h[N];
vector<pair<int,int>> decomposite(int x) {
  vector<pair<int,int>> res;
  for (int i = 0; i < p.size(); i++) {
    if (x % p[i] != 0) {
      continue;
    }
    int cnt = 0;
    while (x % p[i] == 0) {
      x /= p[i];
      cnt += 1;
    }
    res.push_back(make_pair(p[i], cnt));
  }
  if (x != 1) {
    res.push_back(make_pair(x, 1));
  }
  return res;
}
int main() {
  cin >> n >> m1 >> m2;
  for (int i = 2; i < N; i++) {
    if (h[i]) continue;
    p.push_back(i);
    for (int j = i + i; j < N; j += i) h[j] = 1;
  }
  vector<pair<int,int>> m = decomposite(m1), s;
  for (int i = 0; i < m.size(); i++) {
    m[i].second *= m2;
  }
  int ans = 1e9;
  for (int i = 1; i <= n; i++) {
    int x; cin >> x;
    s = decomposite(x);
    int mx = 0;
    for (int i = 0, j = 0; i < m.size(); i++) {
      while (j < s.size() && m[i].first != s[j].first) j++;
      if (j == s.size()) {
        mx = 1e9;
        break;
      }
      mx = max(mx, (m[i].second + s[j].second - 1) / s[j].second);
    }
    ans = min(ans, mx);
  }
  if (ans > 1e8) {
    puts("-1");
  } else {
    cout << ans << endl;
  }
}

道路游戏

有n段马路组成一条环形马路，m个单位时间，每个单位时间每段马路上都会出现不同数量的金币，第i段马路出售花费$cost[i]$金币的机器人，机器人从第i段马路开始，每走过一段马路花费一个单位时间，同时收集该段马路在当前时间的金币，最多可以走p段马路。每个单位时间有且只有一个机器人存在，问在扣除机器人的费用之后最多可以收集多少金币。

题解

DP，用$f[i]$表示到第$i$个时间最多能得到的金币数，转移方程为 $$f[i] = \max_{max(0, i-p)<=j<i,1<=k<=n}(f[j]+sum[k][j+1][i]-cost[k])$$ 其中$sum[k][j+1][i]$表示从j+1时间到i时间以第k段公路为起点获得的金币总数。
直接暴力计算$sum$，时间复杂度$O(nmp^2)$

优化1

考虑用前缀和计算$sum[k][j+1][i]$。
$a[i][j]$表示第i段公路，第j单位时间出现的金币。
$s[i][j]$表示以第i段公路为起点，从第一个单位时间到第j个单位时间能获得的金币。
$$s[i][j]=s[i][j-1]+a[(i+j-1)\%n][j]$$ 用$t$表示第k段公路往前数j个的公路编号，那么$s[t][i]-s[t][j]$表示从$t$开始$j$个单位时间之后能获取的金币数，而从$t$开始$j$个单位时间之后恰好是$k$，即$s[t][i]-s[t][j]$为从j+1时间到i时间以第k段公路为起点共获得的金币。
转移方程可以写为 $$f[i] = \max_{\substack{max(0, i-p)<=j<i \\ 0<=k<n}}(f[j]+s[t][i]-s[t][j]-cost[k])$$ 其中$t=((k-j)\%n+n)\%n$
通过前缀和优化得到$O(nmp)$的算法。

优化2

观察$f[i] = \max(f[j]+s[t][i]-s[t][j]-cost[k])$，考虑去掉t。
从$k$往后数$j$段公路，方程改写为 $$f[i] = \max_{\substack{max(0, i-p)<=j<i \\ 0<=k<n}}(f[j]+s[k][i]-s[k][j]-cost[(k+j)\%n])$$ 将$k$移到外层 $$f[i] = \max_{0<=k<n}{(s[k][i]+\max_{max(0, i-p)<=j<i}(f[j]-s[k][j]-cost[(k+j)\%n]))}$$ 可以发现$f[j]-s[k][j]-cost[(k+j)\%n]$是一个跟$i$无关的表达式。
令$$g[k][j]=f[j]-s[k][j]-cost[(k+j)\%n]$$ 得到 $$f[i] = \max_{0<=k<n}{(s[k][i]+\max_{max(0, i-p)<=j<i}g[k][j])}$$ 现在要求$\displaystyle\max_{max(0, i-p)<=j<i}g[k][j]$，这是一个经典的RMQ问题，可以用ST表等方法优化，
最后的时间复杂度为$O(nm\log{m})$。

优化3

令$j_1<j_2<i$，假设$g[k][j1] <= g[k][j2]$ ，那么$g[k][j1]$永远不会决策到，于是对于每个$g[k]$维护一个单调递减的队列。时间复杂度$O(nm)$。

参考代码

$O(nmp)$的算法就a了，并没有写更多的优化。

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, p;
int a[N][N], f[N], s[N][N], b[N];
int main() {
  cin >> n >> m >> p;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      scanf("%d", &a[i][j]);
    }
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &b[i]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      s[i][j] = s[i][j-1] + a[(i+j-2)%n+1][j];
    }
  }
  memset(f, 0xc0, sizeof(f));
  f[0] = 0;
  for (int i = 1; i <= m; i++) {
    for (int j = max(1, i - p + 1); j <= i; j++) {
      for (int k = 1; k <= n; k++) {
        // (j, k) -> (1, ?)
        int t = ((k-(j-1))%n+n)%n;
        if (t == 0) t = n;
        f[i] = max(f[i], f[j - 1] + s[t][i] - s[t][j - 1] - b[k]);
      }
    }
  }
  cout << f[m] << endl;
}