ABC208

B

题意：有1!, 2!, ..., 10!面值的硬币每个100个，问需要凑成P的最少的硬币数

方法：贪心

#include
#include
#include
#include

using namespace std;

int fac[11];

int main(){
    fac[0] = 1;
    for(int i = 1; i <= 10; i ++) fac[i] = fac[i - 1] * i;
    
    int p;
    cin >> p;
    
    int res = 0;
    for(int i = 10; i >= 1; i --){
        if(p == 0) break;
        int cnt = min(p / fac[i], 100);
        res += cnt;
        p -= cnt * fac[i];
    }
    
    cout << res;
}

C

题意：输入N个人，每个人有一个id，现在有K个糖，如果K比N大，给每个人一个，如果在某一次操作后K小于N，那么给id排名在1~K的所有人一个糖，问第i个人有多少糖（i = 1, 2, ... N）

方法：每个人的基本糖数为k / n, 为每一个人保存序号和id，然后根据id升序排序，然后给前k个人多分一个糖，最后按照序号升序排序，输出答案

#include
#include

using namespace std;

#define int long long

const int N = 2e5 + 10;

struct node{
    int id, pos, val;
}a[N];

int n, k;

int cmp1(const node &n1, const node &n2){
    return n1.id < n2.id;
}

int cmp2(const node &n1, const node &n2){
    return n1.pos < n2.pos;
}

signed main(){
    cin >> n >> k;
    for(int i = 0; i < n; i ++){
        int id;
        cin >> id;
        a[i] = {id, i};
    }
    
    sort(a, a + n, cmp1);
    int p = k % n, q = k / n;
    for(int i = 0; i < n; i ++) a[i].val = q + (i < p);
    sort(a, a + n, cmp2);
    for(int i = 0; i < n; i ++) cout << a[i].val << endl;
}

D

题意：给你一个有向图，问

其中f(i, j, k)是从i到j只经过结点1~k的最短路径

状态转移：根据i到j的只经过结点1~k的最短路径是否经过k来划分状态，不经过k的最短路为\(f(i, j, k-1)\), 经过k的最短路为\(f(i, k, k - 1) + f(k, j, k - 1)\)

所以\(f(i, j, k) = min(f(i, j, k - 1), f(k, j, k - 1))\)

初始条件：\(f(i, i, 0) = 0, i = 1,...,n\)和\(f(a, b, 0) = c\)其中a可以直接到b且权值为c，其他情况\(f(i, j, *) = \inf\)（注意inf要足够大），另外空间可以用滚动数组优化...(开三维数组本地re)

#include
#include
#include
#include

using namespace std;

#define int long long

const int N = 410, INF = 0x3f3f3f3f3f3f3f3f;

int n, m;
int f[N][N][2];

// f[s][t][k] = min(f[s][t][k - 1], f[s][k][k - 1] + f[k][t][k - 1])

// f[s][k][k] f[k][t][k]

// f[s][k][k] = min(f[s][k][k - 1], f[s][k][k - 1] + f[k][k][k - 1])
// f[k][t][k] = min(f[k][t][k - 1], f[k][k][k - 1] + f[k][t][k - 1])


signed main(){
    memset(f, 0x3f, sizeof f);
    
    cin >> n >> m;
    for(int i = 0; i < m; i ++){
        int a, b, c;
        cin >> a >> b >> c;
        f[a][b][0] = c;
    }
    
    for(int i = 1; i <= n; i ++)
        f[i][i][0] = 0;
    
    int res = 0, cur = 1, pre = 0;
    for(int k = 1; k <= n; k ++){
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++){
                f[i][j][cur] = min(f[i][j][pre], f[i][k][pre] + f[k][j][pre]);
                if(f[i][j][cur] < INF)
                    res += f[i][j][cur];
            }
        cur ^= 1, pre ^= 1;
    }
            
    cout << res;
}