NOI online 题解

普及组

T1文具采购

Description

给定整数 $n$ ,求出 $a,b,c$ 满足以下性质

1. $7a+4b+3c = n$
2. $MAX\ (min (a,b,c))$
3. $MAX(a+b+c)$

   Solution

   针对性质 $2$，我们令 $k =MAX\ (min (a,b,c))$,那么易得 $k$ 在 $\frac{n}{7+4+3}$ 附近

然后，由数论知识可知，对于质数 $p,q$ ，用 $X=ap+bq(a,b\ge 0)$,不能组成的最大的 $X=(p-1)*(q-1)-1$

对于本题，发现不能组成的数字为 $1 , 2 ,5.（3，4来组数）$

然后我们很容易想到当$x = 15$ 时候，虽然 $x\equiv 1\pmod {14}$,但他其实有解，不难想到这个边间为 $19$（因为当剩下的数字$\ge20$ 时候，条件 2 不符合了。）

预处理一下就行了。

Code

// She is Pretty pretty!
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

const int N = 1e6 + 100;
// 7a+4b+3c=n
// max (min(a,b,c))
// a+b+c MAX
int dp[20][3];
void pre() {
    memset(dp, 0xff, sizeof dp);
    for (int i = 0; i <= 19; i++) {
        for (int a = 0; 7 * a <= i; a++) {
            for (int b = 0; 7 * a + 4 * b <= i; b++) {
                if ((i - 7 * a - 4 * b) % 3 == 0) {
                    int c = (i - 7 * a - 4 * b) / 3;
                    if (dp[i][0] == -1) {
                        dp[i][0] = a, dp[i][1] = b, dp[i][2] = c;
                    }
                }
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    pre();
    cin >> n;
    if (n == 1 || n == 2 || n == 5) {
        return cout << "-1", 0;
    }
    for (int i = n / 14; i >= n / 14 - 1; i--) {
        int left = n - 14 * i;
        if (dp[left][0] != -1) {
            cout << i + dp[left][0] << ' ' << i + dp[left][1] << ' '
                 << i + dp[left][2];
            exit(0);
        }
    }
    return 0;
}

Description

Solution

Code

魔法

Description

中文题面略略略

挂两个similar的题
Codeforces Round #319 (Div. 1)-D. Flights for Regular Customers
poj3613 牛站

Solution

法一：倍增 $Floyd$
法二：广义矩阵快速幂优化 $dp$
本文采用法二我是不会说我没做过倍增Floyd的

不妨令$dp{k,i,j}$ 表示从 $i$ 到 $j$ ，使用魔法次数不超过 $k$ 次的所有方案钟的最短路。
容易得到转移方程为: $$dp{k,i,j} = min(dp{k-1,i,t}+dp{1,t,j})$$
由广义矩阵乘法具有结合率(不知道这样描述对不对。)
但在离散中是有这样一个结论的：

对于一个邻接矩阵 $G$ ，那么 $G^k$ 表示的就是恰好经过 $k$ 次后的状态。

这为矩阵快速幂优化提供理论基础。

考虑子问题，
当 $k=0$ 时，$floyd$ 解决即可。
当 $k=1$ 时， 即用一次魔法，枚举每一条边 $(u,v,w)$, $dp{1,i,j}=dp{0,i,u}-w+dp_{0,v,j}$  时间复杂度 $O(n^2m)$

总时间复杂度为 $O(n^3logK+n^2m)$

Code

写矩阵一定要注意初始化的问题！！！！
矩阵不规范，debug两行泪
注意，后来的a矩阵就是用了一次魔法的矩阵

// She is Pretty pretty!
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

const int N = 1e6 + 100;
const int MAXN = 110;
const int MAXM = 2505;
int n, m, k, u, v, w, dis[MAXN][MAXN];
std::tuple<int, int, int> e[MAXM];
struct Matrix {
    int a[MAXN][MAXN];
    Matrix() {}
    Matrix(int tmp[MAXN][MAXN]) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) a[i][j] = tmp[i][j];
    }
    Matrix operator*(Matrix const &b) {
        int tmp[MAXN][MAXN];
        memset(tmp, 0x3f, sizeof tmp);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= n; k++) {
                    tmp[i][j] = min(tmp[i][j], a[i][k] + b.a[k][j]);
                }
            }
        }
        return Matrix(tmp);
    }
    friend Matrix operator^(Matrix base, int n) {
        Matrix res = base;
        n--;
        for (; n; n >>= 1, base = base * base) {
            if (n & 1) {
                res = res * base;
            }
        }
        return res;
    }
    /*Matrix Qpow(ll p)  //矩阵快速幂,求a^p
    {
        --p;
        Matrix res = *this, cur = *this;
        while (p) {
            if (p & 1) res = res * cur;
            cur = cur * cur;
            p >>= 1;
        }
        return res;
    }*/
} a;
void floyd(int n) {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
}
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    memset(dis, 0x3f, sizeof dis);
    for (int i = 1; i <= n; i++) dis[i][i] = 0;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        e[i] = {u, v, w};
        dis[u][v] = min(dis[u][v], w);
    }
    floyd(n);
    a = Matrix(dis);
    if (k == 0) {
        return cout << dis[1][n], 0;
    }
    for (int i = 1; i <= m; i++) {
        auto [u, v, w] = e[i];
        for (int s = 1; s <= n; s++) {
            for (int t = 1; t <= n; t++) {
                a.a[s][t] = min(a.a[s][t], dis[s][u] + dis[v][t] - w);
            }
        }
    }
    Matrix ans = Matrix((a ^ k).a);
    cout << ans.a[1][n];
    // cout << a.Qpow(k).a[1][n];
    return 0;
}

提高组

Description

Solution

Code

Description

Solution

Code

Description

Solution

Code