两道洛谷上的题。

Table of Contents

  1. Luogu P2425
    1. Description
    2. Solution
  2. Luogu P1875
    1. Description
    2. Solution

Luogu P2425

Description

小红帽喜欢回文数，但生活中的数常常不是回文数。

现在她手上有$t$个数，现在她知道这$t$个数分别在$x$进制下是回文数$(x \ge 2)$，请你对于每个数求出最小的$x$.

Solution

首先, 对于一个数$n$, $n+1$ 一定是一个回文数, 因为她在该进制下只有一位.

对于小于$\sqrt{n}$的进制, 我们可以暴力枚举.

对于大于$\sqrt{n}$的进制, 我们知道她一定只有两位, 分别是$n \div x$和$n\,mod\,x$ , 如果她是回文的, $n$就可以表示成$p \times x + p$的形式, 也就是$p(x + 1) = n$, 所以我们可以找一个最大的$p$, 使得$p \le \sqrt{n}$且$p |n$. 这样的枚举也是$O(\sqrt{n})$的, 找到一个以后, 答案就是$n \div p - 1$了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

typedef long long ll;

const ll inf = 10000000000;

ll a, arr[1005], len;

bool chk(ll d) {
  bool sol = true; 
  ll tmp = a;
  len = 0;
  while (tmp) {
    arr[len++] = tmp % d;
    tmp /= d;
  }
  int mid = len / 2;
  for (int i = 0; i <= mid; ++i) {
    int j = len - i - 1;
    if (arr[i] != arr[j]) {
      sol = false; break;
    }
  }
  return sol;
}

int main() {
  int T; scanf("%d", &T);
  while (T--) {
    scanf("%lld", &a);
    if (a == 1 || a == 3) {
      puts("2");
      continue;
    } else if (a == 2) {
      puts("3");
      continue;
    }
    ll pos = inf;
    ll lim = sqrt(a) + 1;
    for (int i = 2; i <= lim; ++i) {
      if (chk(i)) {
        pos = i; break;
      }
    }
    if (pos < inf) {
      printf("%lld\n", pos);
      continue;
    }
    for (ll i = a / lim - 1; i; --i) {
      if (a == a / i * i) {
        pos = a / i - 1;
        break;
      }
    }
    if (pos < inf) printf("%lld\n", pos);
    else printf("%lld\n", a + 1);
  }
  return 0;
}

Luogu P1875

Description

给定一些合成关系, 和直接购买的费用, 求得到一个东西的最小代价和方案数.

Solution

听说树形DP能过, 不过没什么意义. 因为题目并没有保证没有环出现.

我们用最短路的过程来消去DP的后效性.

考虑Dijkstra的过程, 当一个点从堆里被拿出来的时候, 就可以确定她是最小值了. 那么我们的更新就建立再已经求出的最小值上, 并且只用最小值向下更新, 至于计数就是套路了, 都知道怎么做.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int maxn = 1005;

struct node
{
  int d, id;
  node(int d_ = 0, int i_ = 0):d(d_), id(i_) {}
  bool operator < (const node &rhs) const {
    return d > rhs.d;
  }
};
int n, tow[maxn][maxn], cost[maxn];
int f[maxn], tag[maxn], ans[maxn];
priority_queue<node> q;

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    scanf("%d", &cost[i]), q.push(node(cost[i], i)), ans[i] = 1;
  int x, y, z;
  memset(tow, -1, sizeof tow);
  while (scanf("%d%d%d", &x, &y, &z) != EOF) {
    tow[x][y] = z;
    tow[y][x] = z;
  }
  while (!q.empty()) {
    node u = q.top(); q.pop();
    if (tag[u.id]) continue;
    //printf("%d\n", u.id);
    tag[u.id] = 1;
    for (int i = 0; i < n; ++i) {
      if (tag[i] && ~tow[u.id][i]) {
        //printf("%d %d %d\n", u.id, i, tow[u.id][i]);
        if (cost[u.id] + cost[i] < cost[tow[u.id][i]])
          cost[tow[u.id][i]] = cost[u.id] + cost[i], 
          ans[tow[u.id][i]] = ans[u.id] * ans[i],
          q.push(node(cost[tow[u.id][i]], tow[u.id][i]));//,printf("+%d\n", tow[u.id][i]);
        else if (cost[u.id] + cost[i] == cost[tow[u.id][i]])
          ans[tow[u.id][i]] += ans[u.id] * ans[i],
          q.push(node(cost[tow[u.id][i]], tow[u.id][i]));//,printf("s%d\n", ans[tow[u.id][i]]);
      }
    }
  }
  printf("%d %d\n", cost[0], ans[0]);
  return 0;
}