2020 牛客国庆集训派对 Day2

Contents

Contest Info

Solved	A	B	C	D	E	F	G	H	I	J
10/10	O	O	O	O	O	O	O	O	Ø	O

O 在比赛中通过
Ø 赛后通过
! 尝试了但是失败了
- 没有尝试

Solutions

Problem A. AKU NEGARAKU

Solved By Dup4. 00:20(+1)

题意

给出 $n$ 个数，并且是 $[1, n]$ 的一个排列，并且是升序的。

这 $n$ 个数形成一个环，第一次第 $m$ 个数先出来，然后往下轮 $m$ 个位置的数出来，然后往下轮 $m$ 个位置的数出来。

问最后出来的那个数是多少？

思路

暴力模拟就没了。

Code

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
int n, m;

void run() {
    if (n == 0 && m == 0)
        return;
    vector<int> vec;
    for (int i = 1; i <= n; ++i) vec.push_back(i);
    int st = m - 1;
    while (SZ(vec) > 1) {
        //		pt(*(vec.begin() + st));
        st = (st + SZ(vec)) % SZ(vec);
        vec.erase(vec.begin() + st);
        st = (st - 1 + SZ(vec)) % SZ(vec);
        st = (st + m) % SZ(vec);
    }
    pt(vec.back());
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    while (cin >> n >> m) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem B. CHEAP DELIVERIES

Solved By Dup4. 03:11(+2)

题意

有 $n$ 个点 $m$ 条边的无向图，有 $k$ 躺运输需求，起点为 $f_i$ ，终点为 $d_i$ ，结束一趟需求后才能开启下一趟需求。

问解决所有需要最少需要多少时间？

思路

先对每个需求的起点和终点作为起点跑最短路。

然后状态压缩 DP 即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 2e4 + 10;
constexpr int INF = 0x3f3f3f3f;
constexpr ll INFLL = 0x3f3f3f3f3f3f3f3f;
int n, m, k, id[N], fid[N];
pII a[N];
vector<vector<pII>> G;
ll f[1 << 19][19];

struct Dijkstra {
    struct node {
        int u;
        ll w;
        node(int u = 0, ll w = 0) : u(u), w(w) {}
        bool operator<(const node &other) const {
            return w > other.w;
        }
    };
    ll dis[N];
    bool used[N];
    void gao(int s) {
        for (int i = 1; i <= n; ++i) {
            dis[i] = INFLL;
            used[i] = 0;
        }
        priority_queue<node> pq;
        dis[s] = 0;
        pq.push(node(s, dis[s]));
        while (!pq.empty()) {
            int u = pq.top().u;
            pq.pop();
            if (used[u])
                continue;
            used[u] = 1;
            for (auto &it : G[u]) {
                int v = it.fi, w = it.se;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    pq.push(node(v, dis[v]));
                }
            }
        }
    }
} dij[50];

void run() {
    rd(n, m, k);
    G.clear();
    G.resize(n + 1);
    for (int i = 1, u, v, w; i <= m; ++i) {
        rd(u, v, w);
        G[u].push_back(pII(v, w));
        G[v].push_back(pII(u, w));
    }
    memset(id, 0, sizeof id);
    for (int i = 0; i < k; ++i) {
        rd(a[i].fi, a[i].se);
        if (!id[a[i].fi])
            id[a[i].fi] = ++*id, fid[*id] = a[i].fi;
        if (!id[a[i].se])
            id[a[i].se] = ++*id, fid[*id] = a[i].se;
    }
    for (int i = 1; i <= *id; ++i) dij[i].gao(fid[i]);
    memset(f, 0x3f, sizeof f);
    for (int i = 0; i < k; ++i) {
        f[1 << i][i] = dij[id[a[i].fi]].dis[a[i].se];
    }
    for (int i = 1; i < 1 << k; ++i) {
        for (int j = 0; j < k; ++j)
            if ((i >> j) & 1 && f[i][j] < INF) {
                for (int o = 0; o < k; ++o)
                    if (!((i >> o) & 1)) {
                        chmin(f[i | (1 << o)][o],
                                f[i][j] + dij[id[a[o].fi]].dis[a[o].se] + dij[id[a[j].se]].dis[a[o].fi]);
                    }
            }
    }
    ll res = INFLL;
    for (int i = 0; i < k; ++i) chmin(res, f[(1 << k) - 1][i]);
    if (res >= INFLL)
        res = -1;
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem C. ELI'S CURIOUS MIND

Solved By Dup4. 01:23(+)

题意

给出一个 $n$ ，问有多少个满足条件的子集？

怎样算满足条件？

集合中的任意两个数不相邻。
集合中不能再添加任意一个 $[1, n]$ 内的数，并且该集合仍然满足第一个条件。

思路

考虑 $f[i]$ 表示最大的那个数是 $i$ 并且满足第一个条件的集合数量。
那么对于 $n$ ，它的答案就是 $f[n] + f[n - 1]$ 。
考虑 $f[i]$ 如何递推？
- 首先它可以在 $f[i - 2]$ 的基础上加上 $i$ ，仍然满足第一个条件。
- 其次它可以在 $f[i - 3]$ 的基础上加上 $i$ ，仍然满足第一个条件。

Code

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e2 + 10;
int n;
ll f[N];

void run() {
    if (n <= 2)
        return pt(0);
    f[3] = 1;
    f[4] = 2;
    f[5] = 2;
    f[6] = 3;
    for (int i = 7; i <= n; ++i) {
        f[i] = f[i - 2] + f[i - 3];
    }
    pt(f[n] + f[n - 1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    while (cin >> n && n) {
        cout << "Case #" << _T << ": ";
        ++_T;
        run();
    }
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem D. EXPLORACE

Solved By Dup4. 00:55(+)

题意

题意没读懂，感觉就是求最小生成树。

思路

求了最小生成树就过了，但是数据范围很迷惑。

Code

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
int n, m;

struct Edge {
    int u, v, w;
    Edge() {}
    Edge(int u, int v, int w) : u(u), v(v), w(w) {}
    bool operator<(const Edge &other) const {
        return w < other.w;
    }
} e[N];

int fa[N];
int find(int x) {
    return fa[x] == 0 ? x : fa[x] = find(fa[x]);
}
void Kruskal() {
    int res = 0;
    memset(fa, 0, sizeof fa);
    int tot = m;
    sort(e + 1, e + 1 + tot);
    for (int i = 1; i <= tot; ++i) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        int fu = find(u), fv = find(v);
        if (fu == fv)
            continue;
        res += w;
        fa[fu] = fv;
    }
    pt(res, "meters");
}

void run() {
    rd(n, m);
    for (int i = 1; i <= m; ++i) {
        rd(e[i].u, e[i].v, e[i].w);
    }
    Kruskal();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = nextInt();
    //	while (_T--) run();
    for (int kase = 1; kase <= _T; ++kase) {
        cout << "Case #" << kase << ": ";
        run();
    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem E. MATRIX MULTIPLICATION CALCULATOR

Solved By Dup4. 00:27(+)

题意

给出两个矩阵，如果能够相乘，就按格式输出相乘结果，否则输出 undefined。

思路

签到。

Code

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
int m, n, p, q;

struct node {
    ll a[30][30];
    node() {}
} A, B, res;

void run() {
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            rd(A.a[i][j]);
        }
    }
    for (int i = 1; i <= p; ++i) {
        for (int j = 1; j <= q; ++j) {
            rd(B.a[i][j]);
        }
    }
    if (n != p) {
        cout << "undefined\n";
    } else {
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= q; ++j) {
                res.a[i][j] = 0;
                for (int k = 1; k <= n; ++k) {
                    res.a[i][j] += A.a[i][k] * B.a[k][j];
                }
            }
        }
        for (int i = 1; i <= m; ++i) {
            cout << "|";
            for (int j = 1; j <= q; ++j) {
                cout << " " << res.a[i][j];
            }
            cout << " |\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    while (cin >> m >> n >> p >> q) {
        if (m == 0 && n == 0 && p == 0 && q == 0)
            break;
        cout << "Case #" << _T << ":\n";
        ++_T;
        run();
    }
    return 0;
}

Problem F. SUM OF SUB RECTANGLE AREAS

Solved By Dup4 & lts. 02:06(+)

题意

给出 $n$ ，求下面代码输出的结果。

sum = 0
for r1 = 0 to N-1
for c1 = 0 to N-1
for r2 = r1+1 to N
for c2 = r2+1 to N
sum = sum + (r2-r1)*(c2-c1)
print(sum)

思路

队友发现样例中的答案都是平方数，然后打了个表找了找规律。作二级差分后，发现平方根存在如下规律：

1 4 10 20 35 56 84 120 165
3 6 10 15 21 28 36 45
3 4 5 6 7 8 9

这个东西直接用矩阵快速幂递推就可以了。

但是队友发现这个平方的答案在杨辉三角中都出现了：

那么这是不是意味着，满足某种规律的组合数能够用矩阵快速幂快速求出来。

Code

def mul(a, b):
	res = [
		[0, 0, 0, 0],
		[0, 0, 0, 0],
		[0, 0, 0, 0],
		[0, 0, 0, 0]
	]
	for i in range(0, 4):
		for j in range(0, 4):
#			res[i][j] = 0
			for k in range(0, 4):
				res[i][j] += a[i][k] * b[k][j]
#print(res[i][j])
	return res


def gao(base, res, n):
	while n > 0:
		if (n & 1) == 1:
			res = mul(res, base)
		base = mul(base, base)
		n >>= 1
	return res


T = int(input())

for i in range(T):
	n = int(input())
	base = [
		[1, 0, 0, 0],
		[1, 1, 0, 0],
		[0, 1, 1, 0],
		[0, 0, 1, 1]
	]
	res = [
		[1, 3, 3, 1],
		[0, 0, 0, 0],
		[0, 0, 0, 0],
		[0, 0, 0, 0]
	]
#	res = mul(res, base)
#	res = mul(res, base)
#	for i in range (4):
#		print(res[0][i], end=" ")
#print("")
#	res = mul(res, base);
	res = gao(base, res, n - 1)
	print(res[0][0] ** 2)

Problem G. WAK SANI SATAY

Solved By groggy_. 03:05(+)

题意

给出三种类型原材料每份的售价、加工费以及每公斤原材料成本。给出配料的售价和成本。求一周内的净利润。

思路

按题意计算即可。

Code

#include <iostream>

typedef long long ll;
using namespace std;

double solve(ll chicken, ll beef, ll lamb, ll nasi) {
    double net_profit = 0;
    net_profit += chicken * 0.8;
    net_profit += beef * 1;
    net_profit += lamb * 1.2;
    net_profit += nasi * 0.8;

    double gross_profit = 0;
    gross_profit += 15.5 * chicken;
    gross_profit += 32 * beef;
    gross_profit += 40 * lamb;
    gross_profit /= 85;
    gross_profit += 0.2 * nasi;

    return net_profit - gross_profit;
}

int main() {
    int n;
    int Case = 0;
    while (cin >> n) {
        if (!n)
            break;
        ll chicken = 0, beef = 0, lamb = 0, nasi = 0;
        ll a, b, c, d;
        double result = 0;
        while (n--) {
            cin >> a >> b >> c >> d;
            chicken += a;
            beef += b;
            lamb += c;
            nasi += d;

            result += solve(a, b, c, d);
        }
        printf("Case #%d: RM%.2lf\n", ++Case, result);
    }
}

Problem H. STROOP EFFECT

Solved By groggy_. 04:23(+1)

题意

给出一串字符串要求判断是否为 Stroop 字符串由多个两位数组成，两位数的十位和个位相同代表一致，否则代表不一致。

思路

由两位数形成图中表格符合要求为： 1、表格中一致和不一致数量相同 2、表格每行一致和不一致数量相同 3、表格每列一致和不一致数量相同 4、字符串中数字的十位和个位数不能出现连续 3 个及以上相同按要求判定

Code

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

int num[5][5];

bool jug() {
    int sum = 0;
    int sum1 = 0;
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            sum += num[i][j];
            if (i == j)
                sum1 += num[i][j];
        }
    }

    if (sum1 != sum - sum1)
        return 1;

    for (int i = 1; i <= 4; i++) {
        int total = 0;
        for (int j = 1; j <= 4; j++) {
            if (i == j)
                continue;
            total += num[i][j];
        }
        if (total != num[i][i])
            return 1;
    }

    for (int j = 1; j <= 4; j++) {
        int total = 0;
        for (int i = 1; i <= 4; i++) {
            if (i == j)
                continue;
            total += num[i][j];
        }
        if (total != num[j][j])
            return 1;
    }

    return 0;
}

int main() {
    int n;
    cin >> n;
    for (int Case = 1; Case <= n; Case++) {
        memset(num, 0, sizeof num);
        int flag = 0;
        int a;
        vector<int> v1, v2;
        while (cin >> a) {
            int t1 = a / 10;
            int t2 = a % 10;
            if (t1 == 0 && t2 == 0)
                break;
            num[t1][t2]++;
            v1.push_back(t1);
            v2.push_back(t2);
        }

        for (int i = 0; i < v1.size(); i++) {
            if (i >= 2 && v1[i] == v1[i - 1] && v1[i] == v1[i - 2])
                flag = 1;
        }

        for (int i = 0; i < v2.size(); i++) {
            if (i >= 2 && v2[i] == v2[i - 1] && v2[i] == v2[i - 2])
                flag = 1;
        }

        if (jug())
            flag = 1;

        if (flag)
            printf("Case #%d: Not Stroop\n", Case);
        else
            printf("Case #%d: Stroop\n", Case);
    }
}

Problem I. SUPER BALL

Upsolved By Dup4.

题意

有 $n$ 个工厂， $m$ 种球，给出任意两个工厂之间的运输时间，给出每个工厂对于每种球生产和回收分别所需的花费，如果是 $-1$ 表示该工厂不能生产或回收该球。

现在有一个工艺品，需要制造 $q$ 个球，并且需要按顺序单线程制造，制造完了还需要回收。

但是制造最后一个球和回收最后一个球的时候所在的工厂不需要相同，并且这中间也不需要转移费用。

问生产和回收过程最少需要多少费用。

思路

两个流程基本一致，只是顺序不一样，那么做两遍 DP 即可。考虑 $f_{i, j}$ 表示目前生产/回收到第 $i$ 个球，当前处于的工厂为 $j$ 时的最小费用。

Code

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 5e2 + 10;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
ll D[N][N], R[N][N], G[N], g[N][N], f[N][N], h[N][N];

void run() {
    rd(n, m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            rd(g[i][j]);
        }
        for (int j = 1; j <= m; ++j) {
            rd(R[i][j]);
        }
        for (int j = 1; j <= m; ++j) {
            rd(D[i][j]);
        }
    }
    rd(*G);
    for (int i = 1; i <= *G; ++i) rd(G[i]);
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    //	reverse(G + 1, G + 1 + *G);
    memset(h, 0x3f, sizeof h);
    memset(h[0], 0, sizeof h[0]);
    memset(f, 0x3f, sizeof f);
    memset(f[0], 0, sizeof f[0]);
    for (int i = 0; i < *G; ++i) {
        int x = G[i + 1];
        for (int j = 1; j <= n; ++j)
            if (f[i][j] < INF) {
                for (int k = 1; k <= n; ++k) {
                    if (R[k][x] != -1) {
                        if (!i) {
                            f[1][k] = R[k][x];
                            continue;
                        }
                        chmin(f[i + 1][k], f[i][j] + R[k][x] + g[j][k]);
                    }
                }
            }
    }
    reverse(G + 1, G + 1 + *G);
    for (int i = 0; i < *G; ++i) {
        int x = G[i + 1];
        for (int j = 1; j <= n; ++j)
            if (h[i][j] < INF) {
                for (int k = 1; k <= n; ++k) {
                    if (D[k][x] != -1) {
                        if (!i) {
                            h[1][k] = D[k][x];
                            continue;
                        }
                        chmin(h[i + 1][k], h[i][j] + D[k][x] + g[j][k]);
                    }
                }
            }
    }
    ll res = INF;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            chmin(res, f[*G][i] + h[*G][j]);
            //	+ g[i][j]);
        }
    }
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem J. VIRUS OUTBREAK

Solved By Dup4. 00:36(+)

题意

求出几个数，让找规律。

思路

斐波那契。

Code

a = [0] * 500
a[1] = 1
a[2] = 1

for i in range(3, 500):
	a[i] = a[i - 1] + a[i - 2]

while True:
	n = int(input())
	if n == -1:
		break
	print("Hour: %d: %d cow(s) affected" % (n, a[n]))

Last update: March 24, 2022
Created: March 23, 2022