A. 坑爹的售票机

题意

用\(1,5,10,25,50,100\)的纸币买\(n\)张单价为\(p\)的船票，且一次性最多买\(k\)张，求钱数恰好时最少需要多少张纸币。

Hard: \(n,k,p\leq 10^9\)

思路

Easy: dp

Hard: dp + 瞎搞

当钱数过大或者张数过多时，（由直觉）其中的大部分都是遵循一定的规律来取的，只有剩余的一小部分需要dp.

Code

Easy

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 10010
using namespace std;
typedef long long LL;
int a[6] = {1,5,10,20,50,100}, dp[maxn], dp2[maxn];
int main() {
    int n, k, p;
    scanf("%d%d%d", &n, &k, &p);
    int lim = k*p;
    F2(i, 1, lim) {
        int minn = INT_MAX;
        F(j, 0, 6) {
            if (i-a[j]<0) break;
            minn = min(minn, dp[i-a[j]]);
        }
        dp[i] = minn+1;
    }
    F2(i, 1, n) {
        int minn = INT_MAX;
        F2(j, 1, k) {
            if (i-j<0) break;
            minn = min(minn, dp2[i-j]+dp[j*p]);
        }
        dp2[i] = minn;
    }
    printf("%d\n", dp2[n]);
    return 0;
}

Hard

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
int a[6] = {1,5,10,20,50,100}, dp[1010];
LL dp2[1010], val[20];
int main() {
    LL n, p; int k;
    scanf("%lld%d%lld", &n, &k, &p);
    F(i, 1, 1000) {
        int minn = INT_MAX;
        F(j, 0, 6) {
            if (i-a[j]<0) break;
            minn = min(minn, dp[i-a[j]]);
        }
        dp[i] = minn+1;
    }
    F2(i, 1, k) {
        LL x = i * p;
        val[i] = x/1000*10 + dp[x%1000];
    }
    LL ans = inf;
    F2(i, 1, 1000) {
        LL minn = inf;
        F2(j, 1, k) {
            if (i-j<0) break;
            minn = min(minn, dp2[i-j]+val[j]);
        }
        dp2[i] = minn;
        ans = min(ans, n/i*dp2[i]+dp2[n%i]);
    }
    printf("%lld\n", ans);
    return 0;
}

B. 无聊的游戏

题意

给定一棵树，两人轮流从树中选取一个度数不为 0 的结点 (度数为 0 则不与任何边相连) 将其与其相连的边删去，谁最终无法删去结点，则谁败。问是否先手必胜？

思路

状压dp.

对删去的点进行状压，记录是必胜态还是必败态，记忆化搜索进行转移。

后继全部是必胜态的状态为必败态，后继中有一个是必败态的状态为必胜态。

Code

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 1100000
using namespace std;
typedef long long LL;
int n, dp[maxn], mp[22][22];
bool vis[maxn];
bool dfs(int state) {
    if (vis[state]) return dp[state];
    vis[state] = true;
    F(i, 0, n) {
        if (!(state&(1<<i))) {
            F(j, 0, n) {
                if (!(state&(1<<j)) && mp[i][j]) {
                    bool ret = dfs(state|(1<<i));
                    if (!ret) return dp[state] = 1;
                }
            }
        }
    }
    return 0;
}
int main() {
    scanf("%d", &n);
    F(i, 1, n) {
        int u, v;
        scanf("%d%d", &u, &v); --u, --v;
        mp[u][v] = mp[v][u] = true;
    }
    if (dfs(0)) puts("First");
    else puts("Second");
    return 0;
}

C. 贪吃的 xjj 和贪心的 oxx

题意

求 \(S=\{a_1,a_2,\ldots,a_n\}\) 这一多重集的一个非空子集 \(S’=\{a_{i_1}, a_{i_2}, \ldots, a_{i_k} \}\)，使得

\[\left(Sum(S’) \le Sum(S-S’) \right) \land \left(\forall t \in S-S’, Sum(S’) \ge Sum(S-S’) – t\right)
\]

记多重集 \(Sum(A)\) 表示多重集 \(A\) 所有元素的和。特别地，\(Sum(\varnothing)=0\)。