Skip to content

第 17 届浙江省程序设计竞赛

Contents

Contest Info

Practice Link

Solved A B C D E F G H I J K L
7/12 O O O - O - O ! O - O -
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • - 没有尝试

Reply

Dup4:

  • 杭电真强。
  • 太菜了啊，赛时连区间第 k 大都不知道怎么求了啊。
  • Hash 还是 Trie, 傻傻分不清了啊。
  • 好像除了第一年打省赛把卡着的那一题过了，之后两年都没过啊？

Hsueh-：

  • 老了该退役了，比赛的时候并查集都写的一愣一愣的。
  • 几何永远出不来，愿天堂没有计算几何。

Solutions

Problem A. AD 2020

Solved By Dup4 & Hsueh-. 01:10(+)

题意：

  • 如果一个日期字符串中包含 202 这个子串，那么称它为 Disaster Reduction。
  • 给出一个起始日期和一个终止日期，问这之间的日期有多少个 Disaster Reduction ？

思路：

预处理一下，处理一个边边角角。

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

const int N = 1e5 + 10;
int f[N];
int y[2], m[2], d[2];
int Mon[2][13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeap(int y) {
    if (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) {
        return true;
    }
    return false;
}

int allD(int y) {
    if (isLeap(y))
        return 366;
    else
        return 365;
}

int getAll(int y) {
    if (y / 10 == 202)
        return allD(y);
    if (y % 1000 == 202)
        return allD(y);
    int res = 1;
    if (y % 10 == 2) {
        if (isLeap(y))
            res += 1;
        res += 28;
    } else {
        res += 1;
    }
    return res;
}

int calc(int y, int m, int d) {
    if (y / 10 == 202 || y % 1000 == 202) {
        int res = 0;
        int ok = isLeap(y);
        for (int i = 1; i < m; ++i) {
            res += Mon[ok][i];
        }
        res += d;
        return res;
    }
    int res = 0;
    if (y % 10 == 2) {
        if (m == 2)
            res += d;
        else if (m > 2)
            res += int(isLeap(y)) + 28;
    } else {
        if (m == 2 && d >= 2)
            res += 1;
        else if (m > 2)
            res += 1;
    }
    if (m == 12 && d >= 2)
        res += 1;
    return res;
}

int valid(int y, int m, int d) {
    if (y / 10 == 202 || y % 1000 == 202) {
        return 1;
    }
    if (m == 12 && d == 2)
        return 1;
    if (y % 10 == 2) {
        if (m == 2)
            return 1;
    } else {
        if (m == 2 && d == 2)
            return 1;
    }
    return 0;
}

int main() {
    for (int i = 2000; i <= 9999; ++i) {
        f[i] = f[i - 1] + getAll(i);
    }
    //	cout << f[9999] << endl;
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        for (int i = 0; i < 2; ++i) {
            scanf("%d %d %d", y + i, m + i, d + i);
        }
        int l = y[0], r = y[1];
        int res = 0;
        if (l < r) {
            res += f[r - 1] - f[l];
        }
        if (l == r) {
            res += calc(y[1], m[1], d[1]) - calc(y[0], m[0], d[0]) + valid(y[0], m[0], d[0]);
        } else {
            res += calc(y[0], 12, 31) - calc(y[0], m[0], d[0]) + valid(y[0], m[0], d[0]);
            res += calc(y[1], m[1], d[1]);
        }
        printf("%d\n", res);
    }
    return 0;
}

Problem B. Bin Packing Problem

Solved By all. 00:57(+)

题意：

  • 给出 n 个石头，和无限个容量为 C 的箱子，每个石头的容量为 a_i。
  • 现在要将石头都放进箱子中，现在有两种做法：

对于第 i 个石头：

  • 按顺序遍历，遇到能放的就放。
  • 找一个最小的并且能放下的箱子，将当前的石头放下。

求出两种做法分别求出所需的箱子数量。

思路：

  • 线段树维护箱子容量的最大值，优先走左儿子。
  • 用一个 set 维护即可。
Code 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n, C;
int a[N];

struct SEG {
    int t[N << 2];
    void build(int id, int l, int r) {
        t[id] = 0;
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
    void update(int id, int l, int r, int pos, int v) {
        if (l == r) {
            t[id] += v;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            update(id << 1, l, mid, pos, v);
        else
            update(id << 1 | 1, mid + 1, r, pos, v);
        t[id] = max(t[id << 1], t[id << 1 | 1]);
    }
    int query(int id, int l, int r, int v) {
        if (l == r)
            return l;
        int mid = (l + r) >> 1;
        if (t[id << 1] >= v)
            return query(id << 1, l, mid, v);
        return query(id << 1 | 1, mid + 1, r, v);
    }
} seg;

int gao() {
    int m = 0;
    seg.build(1, 1, n);
    seg.update(1, 1, n, m + 1, C);
    m += 1;
    for (int i = 1; i <= n; ++i) {
        if (seg.t[1] < a[i]) {
            seg.update(1, 1, n, m + 1, C);
            m += 1;
        }
        int pos = seg.query(1, 1, n, a[i]);
        seg.update(1, 1, n, pos, -a[i]);
    }
    return m;
}

int gao1() {
    multiset<int> se;
    for (int i = 1; i <= n; ++i) {
        auto pos = se.lower_bound(a[i]);
        if (pos == se.end()) {
            se.insert(C);
            pos = se.lower_bound(a[i]);
        }
        int now = *pos - a[i];
        se.erase(pos);
        se.insert(now);
        //		cout << now << endl;
    }
    //	cout << "----\n";
    //	for (auto &it : se)
    //		cout << it << endl;
    return int(se.size());
}

int main() {
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d%d", &n, &C);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
        }
        int A = gao();
        int B = gao1();
        printf("%d %d\n", A, B);
    }
    return 0;
}

Problem C. Crossword Validation

Solved By Dup4 & Hsueh-. 02:57(+1)

题意：

  • 给出一个 n \cdot n 的字符矩阵，横着竖着以 # 分割开若干个字符串，再给出 m 个字典，并且字典中每个字符串都有价值 v_i。字典中每个字符串都两两不同。
  • 现在要将以 # 分割开的每个字符串找到字典中对应字符串的价值累加起来。
  • 如果出现一个字符串未出现在字典中，那么输出 -1。

思路：

  • 直接建立一个 Trie 即可，刚开始写了个 Hash，被卡了。
  • 而且 Trie 复杂度非常正确，又不会有冲突。
  • 听说自然溢出过了？
Code 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 4e6 + 10;
const int M = 1e3 + 10;
const int ALP = 26;
#define fi first
#define se second
int n, m;
char s[N];
char t[M][M];

struct Trie {
    struct node {
        int nx[ALP];
        int v;
        int cnt;
        void init() {
            memset(nx, -1, sizeof nx);
            v = 0;
            cnt = 0;
        }
    } t[N];
    int root, tot;
    int newnode() {
        ++tot;
        t[tot].init();
        return tot;
    }
    void init() {
        tot = 0;
        root = newnode();
    }
    void insert(char *s, int v) {
        int len = strlen(s);
        int now = root;
        for (int i = 0; i < len; ++i) {
            if (t[now].nx[s[i] - 'a'] == -1) {
                t[now].nx[s[i] - 'a'] = newnode();
            }
            now = t[now].nx[s[i] - 'a'];
        }
        t[now].v += v;
        t[now].cnt++;
    }
    int query(char *s) {
        int len = strlen(s);
        int now = root;
        for (int i = 0; i < len; ++i) {
            int ch = s[i] - 'a';
            if (t[now].nx[ch] == -1)
                return -1;
            now = t[now].nx[ch];
        }
        if (t[now].cnt == 0)
            return -1;
        return t[now].v;
    }
} trie;

ll gao() {
    ll res = 0;
    for (int i = 1; i <= n; ++i) {
        int len = 0;
        for (int j = 1; j <= n; ++j) {
            if (t[i][j] == '#') {
                s[len] = 0;
                if (len) {
                    int now = trie.query(s);
                    if (now == -1)
                        return -1ll;
                    res += now;
                }
                len = 0;
            } else {
                s[len] = t[i][j];
                len++;
            }
        }
        if (len) {
            s[len] = 0;
            int now = trie.query(s);
            if (now == -1)
                return -1ll;
            res += now;
        }
    }
    for (int i = 1; i <= n; ++i) {
        int len = 0;
        for (int j = 1; j <= n; ++j) {
            if (t[j][i] == '#') {
                s[len] = 0;
                if (len) {
                    int now = trie.query(s);
                    if (now == -1)
                        return -1ll;
                    res += now;
                }
                len = 0;
            } else {
                s[len] = t[j][i];
                len++;
            }
        }
        if (len) {
            s[len] = 0;
            int now = trie.query(s);
            if (now == -1)
                return -1ll;
            res += now;
        }
    }
    return res;
}

int main() {
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            scanf("%s", t[i] + 1);
        }
        trie.init();
        for (int i = 1, v; i <= m; ++i) {
            scanf("%s%d", s, &v);
            trie.insert(s, v);
        }
        printf("%lld\n", gao());
    }
    return 0;
}

Problem D. Dividing the Points

Upsolved By -.

题意：

思路：

Problem E. Easy DP Problem

Solved By all. 02:09(+)

题意：

给出 dp[i][j] 的转移过程：

dp[i][j] = \left\{ \begin{array}{c} 0 & (i = 0)\\ i^2 + dp[i - 1][j] & (i > 0, j = 0) \\ i^2 + \max(dp[i - 1][j], dp[i - 1][j - 1] + b[i]) & (i > 0, j > 0) \end{array} \right.

然后给出 n 个数 b_i，每次询问给出 l_i, r_i, k_i，要求用 b_l, \cdots, b_r 进行转移, 求 dp[m_i][k_i]。

思路：

  • 不考虑 i^2，那么这个 dp 的意义是找出区间内最大的 k 个数的和。
  • 然后对于 i^2，它根本不会影响 dp 过程。
  • 所以用主席树多维护一下数的和即可。
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 int N = 1e5 + 10;
int n, m, q;
int a[N], t[N];
ll f[N];

struct Hash {
    int a[N];
    void init() {
        *a = 0;
    }
    int size() {
        return *a;
    }
    void add(int x) {
        a[++*a] = x;
    }
    void gao() {
        sort(a + 1, a + 1 + *a);
        *a = unique(a + 1, a + 1 + *a) - a - 1;
        //		cout << *a << endl;
    }
    int get(int x) {
        return lower_bound(a + 1, a + 1 + *a, x) - a;
    }
} hs;

struct SEG {
    struct node {
        int ls, rs, sum;
        ll S;
        void init() {
            ls = rs = sum = 0;
            S = 0;
        }
    } t[N * 50];
    int tot;
    ll res;
    void init() {
        tot = 0;
        t[tot].init();
    }
    int newnode() {
        ++tot;
        t[tot].init();
        return tot;
    }
    void build(int &id, int l, int r) {
        if (!id)
            id = newnode();
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        build(t[id].ls, l, mid);
        build(t[id].rs, mid + 1, r);
    }
    void update(int &rt, int l, int r, int pos, int v) {
        int now = newnode();
        t[now] = t[rt];
        t[now].sum += v;
        t[now].S += 1ll * hs.a[pos] * v;
        if (l == r) {
            rt = now;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            update(t[now].ls, l, mid, pos, v);
        else
            update(t[now].rs, mid + 1, r, pos, v);
        rt = now;
    }
    void query(int l_rt, int r_rt, int l, int r, int k) {
        if (l == r) {
            //			dbg(k, hs.a[l], res);
            res += 1ll * k * hs.a[l];
            return;
        }
        int mid = (l + r) >> 1;
        int lsum = t[t[l_rt].rs].sum, rsum = t[t[r_rt].rs].sum;
        if (rsum - lsum >= k) {
            l_rt = t[l_rt].rs;
            r_rt = t[r_rt].rs;
            query(l_rt, r_rt, mid + 1, r, k);
        } else {
            ll lS = t[t[l_rt].rs].S, rS = t[t[r_rt].rs].S;
            res += rS - lS;
            //			dbg(lsum, rsum, lS, rS, res);
            l_rt = t[l_rt].ls;
            r_rt = t[r_rt].ls;
            query(l_rt, r_rt, l, mid, k - (rsum - lsum));
        }
    }
} seg;

int main() {
    f[0] = 0;
    for (int i = 1; i < N; ++i) {
        f[i] = f[i - 1] + 1ll * i * i;
    }
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d", &n);
        hs.init();
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
            hs.add(a[i]);
        }
        hs.gao();
        m = hs.size();
        //		dbg(m);
        //		for (int i = 1; i <= m; ++i) dbg(i, hs.a[i]);
        seg.init();
        t[0] = 0;
        seg.build(t[0], 1, m);
        for (int i = 1; i <= n; ++i) {
            t[i] = t[i - 1];
            //			dbg(i, hs.get(a[i]));
            seg.update(t[i], 1, m, hs.get(a[i]), 1);
        }
        scanf("%d", &q);
        for (int i = 1, l, r, k; i <= q; ++i) {
            scanf("%d%d%d", &l, &r, &k);
            ll res = f[r - l + 1];
            seg.res = 0;
            seg.query(t[l - 1], t[r], 1, m, k);
            res += seg.res;
            printf("%lld\n", res);
        }
    }
    return 0;
}

Problem F. Finding a Sample

Upsolved By -.

题意：

思路：

Problem G. Gliding

Solved By Hsueh- & ltslts. 03:33(+1)

题意：

  • 给出起点终点，v_f, v_p, v_h，表示不开降落伞下落速度，开降落伞下落速度，水平移动速度。
  • 给出 n+1 个点,每个点都有一个向上速度为 v_i 的水流，在第 i 个水流上的速度为 v_i - v_p。
  • 问起点到终点的最短时间。

思路：

  • 将二维图转化为简单的图，每两个点之间的距离为 \displaystyle \frac{dis}{v_h}。
  • 可以肯定每个速度为 v_i 的点会向速度更大的点移动，那么很显然将 n+1 个点按照速度排序，然后从 f[i] 向 f[j](i \lt j) 转移，每次转移时间为水平移动时间以及需要停留的时间。
  • 简单的二维 dp 方程转移一下即可。

PS: 最短路边太多了，可能会 TLE。

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

const int N = 4e3 + 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...);
}
using db = double;

struct node {
    int x, y, h;

    node() {}

    node(int x, int y, int h) : x(x), y(y), h(h) {}

    void input() {
        scanf("%d %d %d", &x, &y, &h);
    }

    bool operator<(const node& other) {
        return h < other.h;
    }
} a[N];

int n;
int sx, sy, ex, ey;
int vf, vp, vh;
db f[N];

db dis(int i, int j) {
    db res = (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y);
    return sqrt(res);
}

db calc(int i, int j) {
    db t = dis(i, j) / vh;
    db d = t * vp;
    if (a[i].h - vp <= 0)
        return 1e9;
    t += d / (a[i].h - vp);
    return t;
}

int main() {
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
        scanf("%d %d %d", &vf, &vp, &vh);
        scanf("%d", &n);
        ++n;
        for (int i = 1; i <= n; ++i) {
            a[i].input();
        }
        ++n;
        a[n] = node(ex, ey, 100000);
        sort(a + 1, a + 1 + n);
        for (int i = 1; i <= n; ++i) f[i] = 1e9;
        int st = 0;
        for (int i = 1; i <= n; ++i) {
            if (a[i].x == sx && a[i].y == sy)
                st = i;
        }
        f[st] = 0;
        for (int i = st; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                f[j] = min(f[j], f[i] + calc(i, j));
            }
        }
        printf("%.10f\n", f[n]);
    }
    return 0;
}

Problem H. Huge Clouds

Upsolved By -.

题意：

思路：

Problem I. Invoking the Magic

Solved By Hsueh- & ltslts. 00:16(+)

题意：

有 n 对袜子，有一个机器可以将丢进去的 x 堆袜子配对好，问最小的 x。

思路：

  • 签到。
  • 求连通块大小。
Code 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, tot;
int fa[N], sze[N], num[N];
map<int, int> mp;

int get(int x) {
    if (mp.count(x))
        return mp[x];
    mp[x] = ++tot;
    return tot;
}

int find(int x) {
    return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
}

void Union(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) {
        if (sze[x] > sze[y])
            swap(x, y);
        fa[y] = x;
        sze[x] += sze[y];
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            sze[i] = 1, num[i] = 0, fa[i] = i;
        }
        tot = 0;
        mp.clear();
        for (int i = 1, u, v; i <= n; ++i) {
            scanf("%d %d", &u, &v);
            u = get(u), v = get(v);
            Union(u, v);
        }
        for (int i = 1; i <= n; ++i) {
            num[find(i)]++;
        }
        int res = 0;
        for (int i = 1; i <= n; ++i) res = max(res, num[i]);
        printf("%d\n", res);
    }
    return 0;
}

Problem J. Just an Old Problem

Upsolved By -.

题意：

思路：

Problem K. Killing the Brute-forces

Solved By Dup4. 00:14(+)

题意：

签到题。

思路：

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

const int N = 1e5 + 10;
int a[N], b[N];

int main() {
    int _T;
    cin >> _T;
    while (_T--) {
        int m;
        scanf("%d", &m);
        for (int i = 1; i <= m; ++i) {
            scanf("%d", a + i);
        }
        for (int i = 1; i <= m; ++i) {
            scanf("%d", b + i);
        }
        int n = -1;
        for (int i = 1; i <= m; ++i) {
            if (a[i] * 3 < b[i]) {
                n = i;
                break;
            }
        }
        printf("%d\n", n);
    }
    return 0;
}

Problem L. List of Products

Upsolved By -.

题意：

思路：

Last update: March 27, 2022
Created: March 27, 2022
Back to top