链接: link.

Atomic Energy

题意：

有 n n n个原子，每个原子都会爆炸产生能量，原子含有的中子数为 k ( k < = n ) k(k<=n) k(k<=n)则他会转换为 a k a_k ak​焦耳的能量，如果原子含有的中子数 k > n k>n k>n，那么它会先分裂成两个含有 i 和 j i和j i和j个中子的原子，然后这两个再接着而分裂或者爆炸，因为不知道原子是如何分裂的，现在无法精确的知道每个原子在爆炸过程中释放的能量，先给定 a 1 , a 2 . . . . a n a_1,a_2....a_n a1​,a2​....an​,现在有 q q q次查询，现在问爆炸过程中它所释放的最小能量

思路：

由于要查询的原子的中子数太大了，不能直接 d p dp dp，如果查询的范围不大，可以直接套 01 01 01背包的模板，把中子数当成体积，能量当成价值， d p ( i ) dp(i) dp(i)就是体积为 i i i的最小价值， d p ( i ) = m i n ( d p ( i ) , d p ( i − j ) + a ( j ) ) dp(i)=min(dp(i),dp(i-j)+a(j)) dp(i)=min(dp(i),dp(i−j)+a(j))

这个方程可以求出 1 e 6 1e6 1e6之内的最小能量值，但是查询值最大是 1 e 9 1e9 1e9，所以可以贪心，由于中子数 n u m num num很大，所以可以让原子分裂成性价比 a ( i ) i \frac{a(i)}{i} ia(i)​最佳的，就是单位中子数，放出能量最少的原子，所以就是先让原子分裂到我们能 d p dp dp的范围内，然后再求答案即可

具体操作就是 c n t = k − u p V （ 向 上 取 整 ） cnt=\frac{k-up}{V}（向上取整） cnt=Vk−up​（向上取整）就是求当前中子数分裂到最大界限需要多少个最佳原子，然后答案就是 c n t ∗ a V + d p ( k − c n t ∗ V ) cnt*a_V+dp(k-cnt*V) cnt∗aV​+dp(k−cnt∗V)

如果询问的中子数不大，那么就直接输出 d p ( k ) dp(k) dp(k)即可

上面这种方法适用于部分数据范围大，需要优化的动态规划

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 111;
#define int long long
const int inf = 0x3f3f3f3f;
int dp[N];
int a[M];
int n, T;
signed main() {
    memset(dp, 0x3f, sizeof(dp));
    cin >> n >> T;

    int pos = -1;
    double best = 1e9 + 1.0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        dp[i] = a[i];
        double x = 1.0 * a[i] / i;
        if (x < best) {
            pos = i;
            best = x;
        }
    }
    int up = n * n;
    for (int i = n + 1; i <= up; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i] = min(dp[i], dp[i - j] + a[j]);
        }
    }
    int k;
    while (T--) {
        cin >> k;
        if (k <= up) {
            cout << dp[k] << endl;
        } else {
            int cnt = k - up;
            int d = (cnt + pos - 1) / pos;
            int res = d * a[pos];
            k -= d * pos;
            res += dp[k];
            cout << res << endl;
        }
    }
    return 0;
}

Flight Collision

题意：

在一维坐标上，给定 n n n个车的位置和速度，如果某一个位置发生车祸，那么两个车会从坐标轴上消失，保证不会在一个点上三辆或更多以上的车发生相撞，现在问你，最终会有多少辆车安全地留在坐标轴上

思路：

可以发现，发生车祸地两辆车一定是一开始相邻的，也就是中间没有其他的车(可能原来有，但早就消失了)，所以只要模拟看哪辆车先发生车祸，然后去掉，在把前后的车关联起来就行，就是一个模拟的过程

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define int long long
#define ld long double
typedef pair<int, int> PII;
struct node {
    ld t;
    int x, y;
    bool operator<(node p) const { return p.t < t; }
};

set<int> s;
int n;
int pos[N], v[N];
priority_queue<node> q;
void add(int a, int b) {
    if (v[a] <= v[b]) return;
    ld t = (ld)(pos[b] - pos[a]) / (ld)(v[a] - v[b]);
    q.push({t, a, b});
}
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> pos[i] >> v[i];
        s.insert(i);
    }

    for (int i = 1; i < n; i++) {
        add(i, i + 1);
    }

    while (q.size() && s.size()) {
        auto x = q.top().x;
        auto y = q.top().y;
        q.pop();
        if (!s.count(x) || !s.count(y)) {
            continue;
        }
        s.erase(x), s.erase(y);
        if (s.size() == 0) {
            break;
        }
        auto it = s.lower_bound(x);
        if (it == s.end() || it == s.begin()) {
            continue;
        }

        int pre = *(--it);
        int Next = *s.lower_bound(y);
        add(pre, Next);
    }
    cout << s.size() << endl;
    for (auto it : s) {
        cout << it << endl;
    }
    return 0;
}

Island Tour

题意：

现在给定有 n n n个旅游景点，现在有 3 3 3个人，会环绕着把 n n n个景点都参观完，现在给定三个人参观每个景点的时间，和从景点 i i i走到 i + 1 i+1 i+1 ( i = n 时 ， i + 1 = 1 ) (i=n时，i+1=1) (i=n时，i+1=1)的时间（每个人是一样的），现在需要你给这三个人确定一个起点，保证不会有多个人同时位于一个景点的情况，如果不能就impossible，当一个人参观完全部景点时，这个人会离开。

思路：

f ( a , b , i , j ) f(a,b,i,j) f(a,b,i,j)定义为 a a a人起点为 i i i， b b b人起点为 j j j时的方案这两个人是否冲突。
由于 n n n很小，所以可以直接枚举每个人的起点是哪，然后把每个人的起点确定下来后，看当前起点下，每个景点所占据的时间，看是否会与另一个人的时间相冲突，不冲突就是1，冲突是0
最后看 f [ 1 ] [ 2 ] [ i ] [ j ] f[1][2][i][j] f[1][2][i][j] and f [ 1 ] [ 3 ] [ i ] [ k ] f[1][3][i][k] f[1][3][i][k] and f [ 2 ] [ 3 ] [ j ] [ k ] f[2][3][j][k] f[2][3][j][k]

#include <bits/stdc++.h>
using namespace std;
const int N = 555;
typedef pair<int, int> PII;
bool f[5][5][N][N];
int n;
int posT[N];
int dT[5][N];
vector<PII> vis[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &posT[i]);
    }

    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &dT[i][j]);
        }
    }

    for (int a = 1; a <= 3; a++) {
        for (int b = a + 1; b <= 3; b++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == j) {
                        continue;
                    }
                    for (int k = 0; k <= n; k++) {
                        vis[k].clear();
                    }
                    int now1 = i, now2 = j;
                    int time1 = 0, time2 = 0;
                    for (int k = 1; k <= n; k++) {
                        if (now1 > n) now1 = 1;
                        if (now2 > n) now2 = 1;
                        vis[now1].push_back({time1, time1 + dT[a][now1]});
                        vis[now2].push_back({time2, time2 + dT[b][now2]});
                        time1 += dT[a][now1] + posT[now1];
                        time2 += dT[b][now2] + posT[now2];
                        now1++, now2++;
                    }
                    bool flag = 0;
                    for (int k = 1; k <= n; k++) {
                        sort(vis[k].begin(), vis[k].end());
                        if (vis[k][0].second > vis[k][1].first) {
                            flag = 1;
                            break;
                        }
                    }
                    if (flag) {
                        f[a][b][i][j] = 0;
                    } else {
                        f[a][b][i][j] = 1;
                    }
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            for (int k = 1; k <= n; k++) {
                if (i == k || k == j) continue;
                if (f[1][2][i][j] && f[1][3][i][k] && f[2][3][j][k]) {
                    cout << i << " " << j << " " << k << endl;
                    return 0;
                }
            }
        }
    }
    puts("impossible");
    return 0;
}

To be continued
如果你有任何建议或者批评和补充，请留言指出，不胜感激