“科大讯飞杯”第18届上海大学程序设计联赛春季赛暨高校网络友谊赛

Contents

Contest Info
Solutions

Contest Info

Solved	A	B	C	D	E	F	G	H	I	J	K	L
12/12	O	O	O	O	O	O	Ø	O	Ø	Ø	O	O

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

Solutions

A. 组队比赛

Solved By Hsueh-. 0:04(+)

签到。

B. 每日一报

Solved By Hsueh-. 0:20(+2)

签到。

C. 最长非公共子序列

Solved By Hsueh-. 0:07(+)

签到。

D. 最大字符集

Solved By Hsueh-. 0:41(+)

思路：

特判 $1$ 和 $2$ ，然后对于 $n > 2$ 的，如下构造：

例如 $n = 5$ ：

Code

#include <bits/stdc++.h>

using namespace std;

int n;

int main() {
    scanf("%d", &n);
    if (n == 1) {
        printf("%d\n", 1);
        printf("%d\n", 1);
    } else if (n == 2) {
        printf("%d\n", 2);
        puts("0");
        puts("11");
    } else {
        printf("%d\n", n - 1);
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                if (j == 1 || j == i)
                    printf("0");
                else
                    printf("1");
            }
            puts("");
        }
    }
    return 0;
}

E. 美味的序列

Solved By ltslts. 0:16(+)

思路：

下降的美味度是固定的。

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        ans += x;
    }
    ans -= 1ll * n * (n - 1) / 2;
    printf("%lld\n", ans);
    return 0;
}

F. 日期小助手

Solved By Dup4. 0:37(+)

思路：

找出当年和下年的母亲节、父亲节，取合法的，最小的。

Code

#include <bits/stdc++.h>
using namespace std;

struct node {
    int y, m, d;
    node(int y = 0, int m = 0, int d = 0) : y(y), m(m), d(d) {}
    bool operator<(const node &other) const {
        if (y != other.y)
            return y < other.y;
        if (m != other.m)
            return m < other.m;
        return d < other.d;
    }
    bool operator==(const node &other) const {
        return y == other.y && m == other.m && d == other.d;
    }
};

int getweek(int y, int m, int d) {
    int ans;
    if (m == 1 || m == 2)
        m += 12, y--;
    if ((y < 1752) || (y == 1752 && m < 9) || (y == 1752 && m == 9 && d < 3)) {
        ans = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 + 5) % 7;
    } else {
        ans = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7;
    }
    ans = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7;
    return ans + 1;
}

int main() {
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        int y, m, d;
        scanf("%d%d%d", &y, &m, &d);
        node A = node(y, m, d);
        vector<node> vec[2];
        for (int i = y; i <= y + 1; ++i) {
            for (int j = 1, cnt = 0; j <= 31; ++j) {
                if (getweek(i, 5, j) == 7) {
                    ++cnt;
                    if (cnt == 2) {
                        vec[0].emplace_back(i, 5, j);
                        break;
                    }
                }
            }
            for (int j = 1, cnt = 0; j <= 30; ++j) {
                if (getweek(i, 6, j) == 7) {
                    ++cnt;
                    if (cnt == 3) {
                        vec[1].emplace_back(i, 6, j);
                        break;
                    }
                }
            }
        }
        node B = node();
        ;
        int flag = -1;
        for (auto &it : vec[0]) {
            if (!(A == it) && A < it) {
                if (flag == -1) {
                    flag = 0;
                    B = it;
                } else if (it < B) {
                    flag = 0;
                    B = it;
                }
            }
        }
        for (auto &it : vec[1]) {
            if (!(A == it) && A < it) {
                if (flag == -1) {
                    flag = 1;
                    B = it;
                } else if (it < B) {
                    flag = 1;
                    B = it;
                }
            }
        }
        if (!flag)
            printf("Mother's Day: May ");
        else
            printf("Father's Day: June ");
        string s = "th";
        if (B.d == 1 || B.d == 21 || B.d == 31)
            s = "st";
        if (B.d == 2 || B.d == 22 || B.d == 32)
            s = "nd";
        if (B.d == 3 || B.d == 23 || B.d == 33)
            s = "rd";
        cout << B.d << s << ", " << B.y << "\n";
    }
    return 0;
}

G. 血压游戏

UpSolved By Dup4.

思路：

考虑只有同一深度的点才会打架，那么可以直接做一个基于深度的 dp，听群里说按深度分类，对每个虚树 dfs 也可。

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pIL = pair<int, ll>;
#define fi first
#define se second
#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...);
}
const int N = 2e5 + 10;
int n, rt, use[N], a[N];
vector<vector<int>> G;

int fa[N], md[N], hson[N], deep[N];

void pre(int u) {
    hson[u] = 0;
    for (auto &v : G[u]) {
        if (v == fa[u])
            continue;
        fa[v] = u;
        deep[v] = deep[u] + 1;
        pre(v);
        if (!hson[u] || md[v] > md[hson[u]])
            hson[u] = v;
    }
    md[u] = md[hson[u]] + 1;
}

pIL tmp[N << 2], *f[N], *id = tmp;

void dfs(int u) {
    if (hson[u]) {
        int v = hson[u];
        f[v] = f[u] + 1;
        dfs(v);
    }
    for (auto &v : G[u]) {
        if (v == fa[u] || v == hson[u])
            continue;
        f[v] = id;
        id += md[v] * 2;
        dfs(v);
    }
    f[u][0] = pIL(deep[u], a[u]);
    for (auto &v : G[u]) {
        if (v == fa[u] || v == hson[u])
            continue;
        for (int i = 1; i <= md[v]; ++i)
            if (f[u][i].se || f[v][i - 1].se) {
                if (f[u][i].se == 0)
                    f[u][i].fi = deep[v];
                if (f[u][i].fi > deep[v]) {
                    int need = f[u][i].fi - deep[v];
                    f[u][i].se = max(1ll, f[u][i].se - need);
                    f[u][i].fi = deep[u] + 1;
                }
                if (f[v][i - 1].se == 0)
                    f[v][i - 1].fi = deep[v];
                if (f[v][i - 1].fi > deep[v]) {
                    int need = f[v][i - 1].fi - deep[v];
                    f[v][i - 1].se = max(1ll, f[v][i - 1].se - need);
                    f[v][i - 1].fi = deep[v];
                }
                f[u][i].se += f[v][i - 1].se;
                if (use[i] == 0 && f[u][i].se > 1) {
                    --f[u][i].se;
                    use[i] = 1;
                }
                f[u][i].fi = deep[u];
            }
    }
    for (auto &v : G[u]) {
        if (v == fa[u] || v == hson[u])
            continue;
        for (int i = 0; i <= md[v]; ++i) {
            use[i] = 0;
        }
    }
}

int main() {
    scanf("%d%d", &n, &rt);
    memset(use, 0, sizeof use);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        if (a[i] > 1)
            --a[i];
    }
    G.clear();
    G.resize(n + 1);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    fa[rt] = rt;
    deep[rt] = 1;
    pre(rt);
    f[rt] = id;
    id += md[rt] * 2;
    dfs(rt);
    ll res = 0;
    for (int i = 0; i <= md[rt]; ++i)
        if (f[rt][i].se > 0) {
            // dbg(i, f[rt][i].se);
            if (f[rt][i].fi > 1) {
                int need = f[rt][i].fi - 1;
                f[rt][i].se = max(1ll, f[rt][i].se - need);
            }
            res += f[rt][i].se;
        }
    printf("%lld\n", res);
    return 0;
}

H. 纸牌游戏

Solved By Hsueh- & ltslts. 4:56(+7)

思路：

贪心取前 $k$ 个，然后如果不合法，考虑修改几位，显然最多修改两位，因此进行分类：
从小到大暴力判断每一位修改为 $9-0$ 的结果。
修改两位同样是从小到大暴力修改每一位，考虑到当前是修改两位，所以只可能是选两个数字改为 $\% \; 3$ 后减少一或者 $\% \; 3$ 后增加一，暴力判断即可。
最后排序一下判断三种情况大小
注意特判前导零

1
733110 3

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)

void err() {
    cout << endl;
}

template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' ';
    err(args...);
}

int n, k, sum, sum2;
char s[N];
int cnt[20], cnt2[20];
vector<int> vec, vec1, vec2, vec3;

bool cmp(vector<int> V1, vector<int> V2) {
    for (int i = 0; i < k; ++i) {
        if (V1 > V2)
            return true;
        if (V1 < V2)
            return false;
    }
    return true;
}

void print(vector<int> V) {
    sort(V.begin(), V.end());
    reverse(V.begin(), V.end());
    if (V[0] == 0 && V.size() > 1) {
        puts("-1");
        return;
    }
    for (auto it : V) {
        printf("%d", it);
    }
    puts("");
}

bool ok1(vector<int>& vec) {
    for (int i = k - 1; i >= 0; --i) {
        int it = vec[i];
        for (int j = 9; j >= 0; --j) {
            if (!cnt[j])
                continue;
            if ((sum - it + j) % 3 == 0) {
                vec[i] = j;
                return true;
            }
        }
    }
    return false;
}

bool ok2(vector<int>& vec) {
    for (int i = k - 1; i >= 0; --i) {
        int it = vec[i];
        bool F = false;
        for (int j = 9; j >= 0; --j) {
            if (!cnt[j])
                continue;
            int a = (it % 3 + 2) % 3;
            if (j % 3 == a) {
                vec[i] = j;
                sum = sum - it + j;
                cnt[j]--;
                cnt[it]++;
                F = true;
                break;
            }
        }
        if (F)
            break;
    }
    for (int i = k - 1; i >= 0; --i) {
        int it = vec[i];
        bool F = false;
        for (int j = 9; j >= 0; --j) {
            if (!cnt[j])
                continue;
            int a = (it % 3 + 2) % 3;
            if (j % 3 == a) {
                vec[i] = j;
                sum = sum - it + j;
                cnt[j]--;
                cnt[it]++;
                F = true;
                break;
            }
        }
        if (F)
            break;
    }

    return sum % 3 == 0;
}

bool ok3(vector<int>& vec) {
    for (int i = k - 1; i >= 0; --i) {
        int it = vec[i];
        bool F = false;
        for (int j = 9; j >= 0; --j) {
            if (!cnt2[j])
                continue;
            int a = (it % 3 + 1) % 3;
            if (j % 3 == a) {
                vec[i] = j;
                sum2 = sum2 - it + j;
                cnt2[j]--;
                cnt2[it]++;
                F = true;
                break;
            }
        }
        if (F)
            break;
    }
    for (int i = k - 1; i >= 0; --i) {
        int it = vec[i];
        bool F = false;
        for (int j = 9; j >= 0; --j) {
            if (!cnt2[j])
                continue;
            int a = (it % 3 + 1) % 3;
            if (j % 3 == a) {
                vec[i] = j;
                sum2 = sum2 - it + j;
                cnt2[j]--;
                cnt2[it]++;
                F = true;
                break;
            }
        }
        if (F)
            break;
    }

    return sum2 % 3 == 0;
}

int main() {
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        memset(cnt, 0, sizeof cnt);
        memset(cnt2, 0, sizeof cnt2);
        sum = 0;
        sum2 = 0;
        vec.clear();
        scanf("%s %d", s + 1, &k);
        n = strlen(s + 1);
        for (int i = 1; i <= n; ++i) {
            cnt[s[i] - '0']++;
            cnt2[s[i] - '0']++;
        }
        int need = k;
        for (int i = 9; i >= 0; --i) {
            while (need > 0 && cnt[i]) {
                vec.push_back(i);
                need--;
                cnt[i]--;
                cnt2[i]--;
                sum += i;
                sum2 += i;
            }
        }
        // print(vec);
        if (sum % 3 == 0) {
            print(vec);
            continue;
        }
        vec1 = vec;
        vec2 = vec;
        vec3 = vec;
        bool F1 = ok1(vec1);
        bool F2 = ok2(vec2);
        bool F3 = ok3(vec3);
        sort(vec1.begin(), vec1.end());
        reverse(vec1.begin(), vec1.end());

        sort(vec2.begin(), vec2.end());
        reverse(vec2.begin(), vec2.end());

        sort(vec3.begin(), vec3.end());
        reverse(vec3.begin(), vec3.end());

        if (F1 && (!F2 || vec1 >= vec2) && (!F3 || vec1 >= vec3)) {
            print(vec1);
        } else if (F2 && (!F1 || vec2 >= vec1) && (!F3 || vec2 >= vec3)) {
            print(vec2);
        } else if (F3 && (!F1 || vec3 >= vec1) && (!F2 || vec3 >= vec2)) {
            print(vec3);
        } else {
            puts("-1");
        }
    }
    return 0;
}

I. 古老的打字机

UpSolved By Dup4.

思路：

假设我们知道敲击 $i$ 次，字符串长度为 $j$ 的字符串个数，那么可以这么统计答案：
对于每个 $s_i$ ，假设串 $t$ 的长度为 $n$ ，那么一共有 $n - |s_i| + 1$ 个起点，再乘上它的价值 $v_i$ ，以及敲击 $m$ 次长度为 $n$ 的字符串个数 $f[m][i]$ ，但是要除去 $26^{|s_i|}$ ，因为这 $|s_i|$ 个位置是确定了的。
那么再考虑如何求 $f[i][j]$ ，直接 dp 即可，有如下转移：

\begin{eqnarray*} f[i][j] = \left\{ \begin{array}{cccc} f[i - 1][0] + f[i - 1][1] && j = 0 \\ f[i - 1][j - 1] * 26 && j = i \\ f[i - 1][j - 1] * 26 + f[i - 1][j + 1] && other \end{array} \right. \end{eqnarray*}

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define SZ(x) (int(x.size()))
const int N = 1e3 + 10, mod = 1e9 + 7;
int n, m, v[N], fac[N], inv[N], bit[N], fbit[N];
ll f[N][N];
char s[N];

ll qpow(ll base, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}

ll C(int n, int m) {
    return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fac[0] = 1;
    for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[N - 1] = qpow(fac[N - 1], mod - 2);
    for (int i = N - 1; i >= 1; --i) inv[i - 1] = 1ll * inv[i] * i % mod;
    bit[0] = 1;
    for (int i = 1; i < N; ++i) bit[i] = 1ll * bit[i - 1] * 26 % mod;
    fbit[0] = 1;
    fbit[1] = qpow(26, mod - 2);
    for (int i = 2; i < N; ++i) fbit[i] = 1ll * fbit[i - 1] * fbit[1] % mod;
    f[0][0] = 1;
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (!j) {
                f[i][j] += f[i - 1][0] + f[i - 1][1];
                f[i][j] %= mod;
            } else if (j < i) {
                f[i][j] += f[i - 1][j - 1] * 26 + f[i - 1][j + 1];
                f[i][j] %= mod;
            } else if (j == i) {
                f[i][j] += f[i - 1][j - 1] * 26 % mod;
                f[i][j] %= mod;
            }
        }
    }
    cin >> n >> m;
    vector<string> vec(n + 1);
    for (int i = 1; i <= n; ++i) cin >> vec[i] >> v[i];
    ll res = 0;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            int len = SZ(vec[j]);
            if (i >= len) {
                res += f[m][i] * (i - len + 1) % mod * v[j] % mod * fbit[len] % mod;
                res %= mod;
            }
        }
    }
    printf("%lld\n", res);
    return 0;
}

J. 能到达吗

UpSolved By Dup4.

思路：

考虑暴力怎么做，每个点往四周合并，一个联通块的贡献是 $\displaystyle {n \choose 2} + n$ 。
那么对于 $n \cdot m$ 的图，按行枚举，每一行连续的空地缩成一个点，这样对于单组数据的复杂度是对的。
但是这里是 $T$ 组数据，所以不能按行枚举，只能枚举有障碍物的行，对于连续的整行都是空地的行也要缩点。

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pII = pair<int, int>;
#define fi first
#define se second
#define SZ(x) (int(x.size()))
#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...);
}
const int N = 2e6 + 10, M = 2e5 + 10;
const int mod = 1e9 + 7, inv2 = (mod + 1) / 2;
int n, m, K;

struct UFS {
    int fa[N];
    ll sze[N];
    int tot;
    void init() {
        tot = 0;
    }
    int newnode(ll _sze) {
        ++tot;
        fa[tot] = 0;
        sze[tot] = _sze;
        return tot;
    }
    int find(int x) {
        return fa[x] == 0 ? x : fa[x] = find(fa[x]);
    }
    bool merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            if (sze[fx] > sze[fy])
                swap(fx, fy);
            fa[fx] = fy;
            sze[fy] += sze[fx];
            return true;
        }
        return false;
    }
} ufs;

inline ll C(ll n) {
    return (1ll * (n % mod) * ((n - 1) % mod) % mod * inv2 % mod + n % mod) % mod;
}

struct E {
    int l, r, id;
    bool cross(const E &other) const {
        if ((l >= other.l && l <= other.r) || (r >= other.l && r <= other.r) || (other.l >= l && other.l <= r) ||
                (other.r >= l && other.r <= r))
            return 1;
        return 0;
    }
};

vector<vector<int>> vec(M);
vector<vector<E>> seg(M);

vector<int> has;

void gao() {
    if (K == 0) {
        ll res = C(1ll * n * m);
        printf("%lld\n", res);
        return;
    }
    ufs.init();
    sort(has.begin(), has.end());
    has.erase(unique(has.begin(), has.end()), has.end());
    for (int i = 0; i < SZ(has); ++i) {
        int p = has[i];
        int pre = 0;
        sort(vec[p].begin(), vec[p].end());
        for (auto &it : vec[p]) {
            if (it - 1 > pre) {
                E tmp = {pre + 1, it - 1, ufs.newnode(it - 1 - pre)};
                //		dbg(tmp.l, tmp.r, tmp.id, ufs.sze[tmp.id]);
                seg[p].push_back(tmp);
            }
            pre = it;
        }
        if (pre < m) {
            E tmp = {pre + 1, m, ufs.newnode(m - pre)};
            seg[p].push_back(tmp);
        }
        //	for (auto &it : seg[p]) {
        //		dbg(it.l, it.r);
        //	}
        if (i == 0) {
            if (p > 1) {
                int node = ufs.newnode(1ll * (p - 1) * m);
                for (auto &it : seg[p]) {
                    ufs.merge(node, it.id);
                }
            }
        } else {
            int preP = has[i - 1];
            if (preP + 1 < p) {
                int node = ufs.newnode(1ll * (p - preP - 1) * m);
                for (auto &it : seg[p]) {
                    ufs.merge(node, it.id);
                }
                for (auto &it : seg[preP]) {
                    ufs.merge(node, it.id);
                }
            } else {
                int pos = 0;
                for (auto &it : seg[p]) {
                    while (pos < SZ(seg[preP])) {
                        E it2 = seg[preP][pos];
                        if (it.cross(it2)) {
                            ufs.merge(it.id, it2.id);
                        }
                        if (it2.r <= it.r)
                            ++pos;
                        else
                            break;
                    }
                }
            }
        }
        if (i == SZ(has) - 1) {
            if (p < n) {
                int node = ufs.newnode(1ll * (n - p) * m);
                //	dbg(ufs.sze[node]);
                for (auto &it : seg[p]) {
                    ufs.merge(node, it.id);
                    //		dbg(it.l, it.r, it.id, ufs.sze[node]);
                }
            }
        }
    }
    for (auto &it : has) {
        vec[it].clear();
        seg[it].clear();
    }
    ll res = 0;
    for (int i = 1; i <= ufs.tot; ++i) {
        if (ufs.fa[i] == 0) {
            // dbg(i, ufs.sze[i]);
            res += C(ufs.sze[i]);
            res %= mod;
        }
    }
    printf("%lld\n", res);
}

int main() {
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d%d%d", &n, &m, &K);
        has.clear();
        for (int i = 1, x, y; i <= K; ++i) {
            scanf("%d%d", &x, &y);
            has.push_back(x);
            vec[x].push_back(y);
        }
        gao();
    }
    return 0;
}

K. 迷宫

Solved By Dup4. 3:36(+3)

思路：

从起点和终点分别 bfs 到每个点的最短路，然后枚举一个点，相当于找矩形框内的最小值。
注意到矩形框大小一致，考虑从上往下枚举，每次多一行，用 $m$ 个单调队列维护每一列 $2d$ 个元素的最小值，然后从左往右枚举的时候，再来一个单调队列。
赛时比较蠢，无脑了一个线段树，但实际上出题人可以直接卡到 $O(nm)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
using pII = pair<int, int>;
#define SZ(x) (int(x.size()))
#define fi first
#define se second
#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...);
}
const int N = 2e3 + 10, INF = 1e9;
int n, m, d, sx, sy, ex, ey, a[N];
pII b[N];
char G[N][N];

int Move[][2] = {1, 0, -1, 0, 0, 1, 0, -1};

struct BFS {
    int dis[N][N];
    pII pre[N][N];
    bool ok(int x, int y) {
        if (x < 1 || x > n || y < 1 || y > m || G[x][y] == 'X')
            return 0;
        return 1;
    }
    void gao(int sx, int sy) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                dis[i][j] = INF;
                pre[i][j] = pII(-1, -1);
            }
        }
        dis[sx][sy] = 0;
        queue<pII> que;
        que.push(pII(sx, sy));
        while (!que.empty()) {
            int x = que.front().fi, y = que.front().se;
            que.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = x + Move[i][0];
                int ny = y + Move[i][1];
                if (ok(nx, ny) && dis[nx][ny] > dis[x][y] + 1) {
                    dis[nx][ny] = dis[x][y] + 1;
                    pre[nx][ny] = pII(x, y);
                    que.push(pII(nx, ny));
                }
            }
        }
    }
} f, g;

struct DEQUE {
    int que[N], head, tail;
    void init() {
        head = 1, tail = 0;
    }
} q[N];

struct SEG {
    struct node {
        int Min;
        pII pos;
        node() {
            Min = INF;
            pos = pII(-1, -1);
        }
        node operator+(const node& other) const {
            node res = node();
            if (Min < other.Min) {
                res.Min = Min;
                res.pos = pos;
            } else {
                res.Min = other.Min;
                res.pos = other.pos;
            }
            return res;
        }
    } t[N << 2], res;
    void build(int id, int l, int r) {
        t[id] = node();
        if (l == r) {
            t[id].Min = a[l];
            t[id].pos = b[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        t[id] = t[id << 1] + t[id << 1 | 1];
    }
    //  void update(int id, int l, int r, int pos, int v) {
    //      if (l == r) {
    //          t[id].Min = v;
    //          return;
    //      }
    //      int mid = (l + r) >> 1;
    //      if (pos <= mid) update(id << 1, l, mid, ql, qr, v);
    //      else update(id << 1 | 1, mid + 1, r, ql, qr, v);
    //      t[id] = t[id << 1] + t[id << 1 | 1];
    //  }
    void query(int id, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr) {
            res = res + t[id];
            return;
        }
        int mid = (l + r) >> 1;
        if (ql <= mid)
            query(id << 1, l, mid, ql, qr);
        if (qr > mid)
            query(id << 1 | 1, mid + 1, r, ql, qr);
    }
} seg;

int main() {
    scanf("%d%d%d", &n, &m, &d);
    for (int i = 1; i <= n; ++i) scanf("%s", G[i] + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (G[i][j] == 'S') {
                sx = i, sy = j;
            } else if (G[i][j] == 'T') {
                ex = i, ey = j;
            }
        }
    }
    //  dbg(sx, sy, ex, ey);
    f.gao(sx, sy);
    g.gao(ex, ey);
    //  for (int i = 1; i <= n; ++i) {
    //      for (int j = 1; j <= m; ++j) {
    //          dbg(i, j, f.dis[i][j]);
    //      }
    //  }

    //  for (int i = 1; i <= n; ++i) {
    //      for (int j = 1; j <= m; ++j) {
    //          dbg(i, j, g.dis[i][j]);
    //      }
    //  }
    for (int i = 1; i <= m; ++i) q[i].init();
    int up = 1, down = 0;
    pII A = pII(ex, ey), B = pII(-1, -1);
    int dis = f.dis[ex][ey];
    for (int i = 1; i <= n; ++i) {
        up = max(1, i - d);
        int _down = min(n, i + d);
        while (down < _down) {
            ++down;
            for (int j = 1; j <= m; ++j) {
                while (q[j].head <= q[j].tail && g.dis[q[j].que[q[j].tail]][j] >= g.dis[down][j]) --q[j].tail;
                q[j].que[++q[j].tail] = down;
            }
        }
        for (int j = 1; j <= m; ++j) {
            while (q[j].head <= q[j].tail && q[j].que[q[j].head] < up) ++q[j].head;
            a[j] = g.dis[q[j].que[q[j].head]][j];
            b[j] = pII(q[j].que[q[j].head], j);
        }
        seg.build(1, 1, m);
        for (int j = 1; j <= m; ++j)
            if (G[i][j] != 'X') {
                int l = max(1, j - d);
                int r = min(m, j + d);
                seg.res = SEG::node();
                seg.query(1, 1, m, l, r);
                pII _A = pII(i, j);
                pII _B = seg.res.pos;
                int _dis = f.dis[i][j] + seg.res.Min + 1;
                if (_dis <= dis) {
                    //  dbg(i, j, f.dis[i][j], g.dis[_B.fi][_B.se], _B.fi, _B.se);
                    dis = _dis;
                    A = _A;
                    B = _B;
                }
            }
    }
    if (dis >= INF)
        puts("-1");
    else {
        printf("%d\n", dis);
        vector<pII> vecA, vecB;
        while (A != pII(-1, -1)) {
            vecA.push_back(A);
            A = f.pre[A.fi][A.se];
        }
        while (B != pII(-1, -1)) {
            vecB.push_back(B);
            B = g.pre[B.fi][B.se];
        }
        reverse(vecA.begin(), vecA.end());
        for (int i = 0; i < SZ(vecA); ++i) {
            printf("%d %d\n", vecA[i].fi - 1, vecA[i].se - 1);
        }
        for (int i = 0; i < SZ(vecB); ++i) {
            printf("%d %d\n", vecB[i].fi - 1, vecB[i].se - 1);
        }
    }
    return 0;
}

L. 动物森友会

Solved By Hsueh-. 3:11(+)

思路：

考虑二分时间，那么我们就知道了每个日子有几天，建立网络流去判断，其中左边为任务，向右边的星期几流需要的需求

Code

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)

void err() {
    cout << endl;
}

template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' ';
    err(args...);
}

const ll INF = 0x3f3f3f3f3f3f3f3f;

template <class Type>
struct Dinic {
    static const int M = 1e6 + 10;
    static const int N = 1e5 + 10;
    struct Edge {
        int to, nxt;
        Type flow;
        Edge() {}
        Edge(int to, int nxt, Type flow) : to(to), nxt(nxt), flow(flow) {}
    } edge[M];
    int S, T;
    int head[N], tot;
    int dep[N];
    void init() {
        memset(head, -1, sizeof head);
        tot = 0;
    }
    void set(int S, int T) {
        this->S = S;
        this->T = T;
    }
    void addedge(int u, int v, ll w, ll rw = 0) {
        // dbg(u, v, w);
        edge[tot] = Edge(v, head[u], w);
        head[u] = tot++;
        edge[tot] = Edge(u, head[v], rw);
        head[v] = tot++;
    }
    bool BFS() {
        memset(dep, -1, sizeof dep);
        queue<int> q;
        q.push(S);
        dep[S] = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = head[u]; ~i; i = edge[i].nxt) {
                if (edge[i].flow && dep[edge[i].to] == -1) {
                    dep[edge[i].to] = dep[u] + 1;
                    q.push(edge[i].to);
                }
            }
        }
        return dep[T] >= 0;
    }
    Type DFS(int u, Type f) {
        if (u == T || f == 0)
            return f;
        Type w, used = 0;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
                w = DFS(edge[i].to, min(f - used, edge[i].flow));
                edge[i].flow -= w;
                edge[i ^ 1].flow += w;
                used += w;
                if (used == f)
                    return f;
            }
        }
        if (!used)
            dep[u] = -1;
        return used;
    }
    Type solve() {
        Type ans = 0;
        while (BFS()) {
            ans += DFS(S, INF);
        }
        return ans;
    }
};
Dinic<ll> dinic;

const int N = 1e3 + 10;

int n, e;
ll sum;
ll cnt[20];
ll c[N];
int a[N][10];

bool ok(int x) {
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= 7; ++i) {
        cnt[i] = x / 7;
        if (x % 7 >= i)
            cnt[i]++;
    }
    dinic.init();
    int S = 0, T = n + 10;
    dinic.set(S, T);
    for (int i = 1; i <= n; ++i) {
        dinic.addedge(S, i, c[i]);
        for (int j = 1; j <= a[i][0]; ++j) {
            dinic.addedge(i, n + a[i][j], c[i]);
        }
    }
    for (int i = 1; i <= 7; ++i) {
        dinic.addedge(n + i, T, cnt[i] * e);
    }
    ll res = dinic.solve();
    // dbg(res, sum);
    return res >= sum;
}

int main() {
    scanf("%d %d", &n, &e);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld %d", c + i, &a[i][0]);
        for (int j = 1; j <= a[i][0]; ++j) {
            scanf("%d", &a[i][j]);
        }
        sum += c[i];
    }
    ll l = 0, r = 1e9, res = -1;
    // ok(5);
    while (r - l >= 0) {
        ll mid = (l + r) >> 1;
        if (ok(mid)) {
            r = mid - 1;
            res = mid;
        } else {
            l = mid + 1;
        }
    }
    printf("%lld\n", res);
    return 0;
}

Last update: March 27, 2022
Created: March 27, 2022