这里有两道作业题没做，F 题比较简单，G 题是洛谷黑题

A. 智力测试

传统题 1000ms 512MiB

题目背景

现在很多题目都是想让大家去做题，只有这道题想让大家进行评价，这都不能算机考了，简直就是互评。

题目描述

小 C 来到了一家“正规”的医疗机构进行智商测试，而你是其中的工作人员之一。

机构会通过检查小 C 的大脑来测出他的智商，小 C 的大脑可以看成由 \(n\) 个神经元和 \(m\) 条单向传递关系构成的信号传递网络，其中第 \(i\) 条单向传递关系会将信号从第 \(u_i\) 个神经元传到第 \(v_i\) 个神经元（\(u_i\) 可能等于 \(v_i\)），且传递长度为 \(l_i\)，频率为 \(s_i\)。

如果信号从某个神经元开始通过该网络能传递回自己，那么形成的传递路径称为“脑回路”。在这里，“脑回路”会使小 C 大脑变迟钝，从而使智商降低。

定义该“脑回路”的迟钝度为该路径中经过的所有传递关系的 \(s_i\) 之和与 \(l_i\) 之和的比值，如果一条传递关系被经过了多次，那么其也会被重复计算多次。

在机构那里，小 C 的智商会被认为是所有可能的“脑回路”迟钝度的最小值。特别地，如果小 C 的大脑不存在“脑回路”，则认为小 C 的智商为 \(+\infty\)。

机构会在智商测试后得到小 C 的智商 \(IQ\)，并对其进行智力评价，评价细则如下：

如果 \(IQ \geq 140\)，则智力评价为 A+。
如果 \(120 \leq IQ < 140\)，则智力评价为 A。
如果 \(110 \leq IQ < 120\)，则智力评价为 B。
如果 \(90 \leq IQ < 110\)，则智力评价为 C。
如果 \(70 \leq IQ < 90\)，则智力评价为 D。
如果 \(IQ < 70\)，则智力评价为 E。

但就在今天，一股神秘的东方力量让机构的所有工作人员的智商全部 \(< 70\)，只有你的智商还 \(\geq 140\)，有能力对小 C 进行智商测试，所以由你来负责给小 C 进行智力评价。

Ps：你只需要给出智力评价，无需给出小 C 的 \(IQ\) 具体值。

输入格式

本题有多组数据，第一行一个整数 \(T\)。

接下来 \(T\) 组数据，每组数据第一行两个整数 \(n, m\)。

接下来 \(m\) 行，其中第 \(i\) 行共四个整数 \(u_i, v_i, l_i, s_i\)。

输出格式

输出共 \(T\) 行，每行代表对应数据下你给出的智力评价。

由于本评价不是数据结构 Pre 的打分，所以如果你打出了 A+ 或 E，无需给出理由。

输入输出样例 #1

输入 #1

输出 #1

A+
E
D
E
C
A
B
A+

说明/提示

【样例解释】

对于第 \(1\) 组数据，虽然小 C 大脑中的 \(s_i\) 巨大低，\(l_i\) 巨大长，但由于小 C 的大脑不存在“脑回路”，此时你只能恭喜！小 C 的智商经过测试 \(\geq 140\)，智力评价为 A+！

对于第 \(2\) 组数据，虽然小 C 的大脑中有一条 \(s_i\) 巨大高，\(l_i\) 巨大短的单向传递关系，但由于其它关系不给力，所以小 C 的智商只差一点点就能到 \(70\) 了（具体为 \(69\frac{2}{3}\)），智力评价为 E。

对于第 \(4\) 组数据，仅由一条从 \(1\) 号神经元到它本身的“脑回路”使得小 C 的智商为 \(69 < 70\)，所以智力评价为 E。

对于第 \(5\) 组数据，从 \(2\) 号神经元到 \(3\) 号神经元再回到 \(2\) 号神经元的“脑回路”使得小 C 的智商为 \(109.5\)，所以智力评价为 C。

【数据范围】

对于全部测试点：

\(1 \leq T \leq 3000, n \geq 1, m \geq 0, \sum n \leq 3000, \sum m \leq 6000\)，

\(1 \leq u_i, v_i \leq n\)，

\(1 \leq l_i \leq 10^3\)，

\(0 \leq s_i \leq 10^5\)。

思路与题解

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
using ll = long long;

struct Edge {
    int u, v;
    ll l, s;
};

vector<Edge> edges;
vector<vector<int>> g;
vector<int> indeg;
vector<int> cand;

bool SOLVE(int n, ll X) {
    vector<int> used(n + 1, 0);
    for (int x : cand) used[x] = 1;

    vector<ll> dist(n + 1, 0);
    int m = (int)edges.size();

    for (int i = 0; i < n; ++i) {
        bool updated = false;
        for (int j = 0; j < m; ++j) {
            const Edge &e = edges[j];
            if (!used[e.u] || !used[e.v]) continue;
            ll w = e.s - X * e.l;
            if (dist[e.v] > dist[e.u] + w) {
                dist[e.v] = dist[e.u] + w;
                updated = true;
            }
        }
        if (!updated) break;
    }
    for (int j = 0; j < m; ++j) {
        const Edge &e = edges[j];
        if (!used[e.u] || !used[e.v]) continue;
        ll w = e.s - X * e.l;
        if (dist[e.v] > dist[e.u] + w) {
            return true;
        }
    }
    return false;
}

void solve() {
    int n, m;
    cin >> n >> m;
    edges.resize(m);
    g.assign(n + 1, {});
    indeg.assign(n + 1, 0);
    cand.clear();

    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].l >> edges[i].s;
        int u = edges[i].u, v = edges[i].v;
        g[u].push_back(v);
        ++indeg[v];
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (indeg[i] == 0) q.push(i);

    vector<int> inTopo(n + 1, 0);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inTopo[u] = 1;
        for (int v : g[u]) {
            if (--indeg[v] == 0) q.push(v);
        }
    }
    for (int i = 1; i <= n; ++i)
        if (!inTopo[i]) cand.push_back(i);

    if (cand.empty()) {
        cout << "A+\n";
        return;
    }

    if (SOLVE(n, 70)) cout << "E\n";
    else if (SOLVE(n, 90)) cout << "D\n";
    else if (SOLVE(n, 110)) cout << "C\n";
    else if (SOLVE(n, 120)) cout << "B\n";
    else if (SOLVE(n, 140)) cout << "A\n";
    else cout << "A+\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

B. 最短合法路径

题目描述

给定一个 \(n\) 个点的有向图
任意不同的两点 \(i, j\)，存在一条从 \(i\) 到 \(j\) 的有向边
\(w_{i,j}\) 为边 \((i \to j)\) 的边权
边权可以为负，且不保证图中没有负环
定义一条路径的长度为这条路径上的边权和
对于 \(\forall i, j \in [1, n]\)，求出从 \(i\) 到 \(j\) 的最短合法路径长度
一条从 \(i\) 到 \(j\) 的路径是合法路径，当且仅当其恰好经过 \(m\) 条边
在不违反 (7) 的情况下，路径中的中间结点皆不受限制
以 Floyd 之名宣布，以上各条皆为不变的规则
大家一起愉快地求最短路吧

输入格式

第一行两个整数 \(n, m\)，表示点数和合法路径的边数。
接下来 \(n\) 行，每行 \(n\) 个整数，其中第 \(i\) 行第 \(i\) 个整数为 \(0\)，第 \(i\) 行第 \(j(i \neq j)\) 个整数为 \(w_{i,j}\)。

输出格式

输出 \(n\) 行，每行 \(n\) 个整数，其中第 \(i\) 行第 \(j\) 个整数表示从 \(i\) 到 \(j\) 的最短合法路径长度。

样例输入1

样例输出1

1
2
3

-4 -2 0
2 -4 -2
-4 -2 0

样例输入2

5 10
0 3 -5 -3 2
5 0 -2 -8 -4
7 2 0 0 0
6 7 -6 0 9
3 2 9 8 0

样例输出2

-30 -33 -41 -39 -35
-35 -36 -44 -44 -40
-29 -34 -36 -36 -36
-30 -34 -42 -36 -36
-29 -34 -36 -36 -36

数据范围

对于 100% 的数据，\(3 \leq n \leq 200, 2 \leq m \leq 10^9, |w_{i,j}| \leq 10^9\)。

思路与题解

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;
const ll INF = (ll)4e18;

using Matrix = vector<vector<ll>>;

Matrix mul(const Matrix &A, const Matrix &B) {
    int n = (int)A.size();
    Matrix C(n, vector<ll>(n, INF));
    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < n; ++k) {
            if (A[i][k] == INF) continue;
            ll aik = A[i][k];
            for (int j = 0; j < n; ++j) {
                if (B[k][j] == INF) continue;
                ll val = aik + B[k][j];
                if (val < C[i][j]) C[i][j] = val;
            }
        }
    }
    return C;
}

Matrix mpow(Matrix base, long long e) {
    int n = (int)base.size();
    Matrix res(n, vector<ll>(n, INF));
    for (int i = 0; i < n; ++i) res[i][i] = 0;
    while (e > 0) {
        if (e & 1) res = mul(res, base);
        base = mul(base, base);
        e >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long m;
    cin >> n >> m;

    Matrix A(n, vector<ll>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> A[i][j];

    for (int i = 0; i < n; ++i) A[i][i] = INF;

    Matrix ans = mpow(A, m);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (j) cout << ' ';
            cout << ans[i][j];
        }
        cout << '\n';
    }
    return 0;
}

C.SA. 选课

传统题 1000ms 256MB

题目背景

3202年，FDUCS的同学们已经卷上天啦！现在一共有 \(n\) 门课要修，而学校为了让同学们不再为选课瞎操心，每门课的学分都变成相同的了。

现在一门课的练点上限已经不再是 \(4.0\)，因为这已经完全满足不了同学们卷成绩了。具体来说，现在每门课的练点最高为 \(m\)，且一个同学的练点必须是 \(1, 2, 3, \cdots, m\) 这些整数中的一个。

此外，学校为了防止同学们乱选课，给出了 \(k\) 条选课限制，每个限制表示为 \(u, v(1 \leq u, v \leq n)\)，意思是必须先修完课程 \(u\) 才能修课程 \(v\)。

而且现在每个学期只能够修一门课，因此不能够同时上好几门课，必须等到一门课修完了才能修下一门课。也不允许在某个学期不修课程，这太摆烂了。

现在，小聂同学已经根据超大模型预测出了自己每门课的练点，第 \(i(1 \leq i \leq n)\) 门课的练点将会是 \(p_i\)，且不同课程的练点两两不同 (\(i < j \leq n, p_i \neq p_j\))。

请你帮小聂同学规划一个最优的选课顺序，使得他满足学校的 \(k\) 条选课限制，并且每个学期出成绩后，他的 GPA（平均练点，即所有已修课程的练点均值）要尽可能高，这样才能有可能卷赢其他同学。

输入格式

第一行，3个整数 \(n, m, k\)，分别表示课程总数，每门课的练点上限，学校的选课限制数量。

第二行，\(n\) 个整数 \(p_1, p_2, \cdots, p_n\)，其中 \(p_i(1 \leq i \leq n)\) 表示小聂同学修完课程 \(i\) 后这门课的练点。保证小聂同学不同课程的练点互不相同。

接下来 \(k\) 行，每行两个整数 \(u, v(1 \leq u, v \leq n)\) 表示必须先修完课程 \(u\) 之后才能修课程 \(v\)。

数据保证一定存在至少一个合法顺序可以修完所有课程。

输出格式

输出一行，\(n\) 个整数用空格隔开，从左到右表示按先后顺序选课。你需要保证该顺序选课后，每个学期的 GPA 都尽可能高。（这意味着，如果在第 \(i\) 个学期小聂同学有多门课可以选择，他总是会贪心选择能收获练点最高的课程）。

样例 #1

样例输入 #1

样例输出 #1

5 2 1 4 3

数据范围与提示

\(1 \leq n \leq 2000, 1 \leq k \leq 4000, 1 \leq m \leq 10^6\)。

数据不保证同一条限制不会重复出现，即在 \(k\) 条选课限制中存在重复出现的可能。

思路与题解

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    vector<int> p(n + 1);
    for (int i = 1; i <= n; ++i) cin >> p[i];

    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 0; i < k; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        ++indeg[v];
    }

    priority_queue<pair<int, int>> pq; 
    for (int i = 1; i <= n; ++i) 
        if (indeg[i] == 0) pq.push({p[i], i});
    

    vector<int> order;
    order.reserve(n);
    while (!pq.empty()) {
        auto [pi, u] = pq.top();
        pq.pop();
        order.push_back(u);
        for (int v : g[u]) {
            if (--indeg[v] == 0) pq.push({p[v], v});
        }
    }

    for (int i = 0; i < n; ++i) {
        if (i) cout << ' ';
        cout << order[i];
    }

    return 0;
}

D. 美丽值对抗大赛

Description

嘉然听了很多 Y 讲的关于军训的故事，她发现她对美丽值非常感兴趣！

她决定在她的 \(n\) 名粉丝中举办 \(m\) 次美丽值对抗大赛！

她每次选择两名粉丝进行比赛，美丽值大的粉丝将会获胜（假设没有两名粉丝美丽值相同），她会把这些比赛记录下来。

请问当她赛到第几场时，所有粉丝的美丽值的大小关系就已经确定。如果 \(m\) 次比赛之后仍未确定，输出 -1。

Format

Input

第一行两个整数 \(n\) 和 \(m\) 表示粉丝的数量和比赛的次数。

接下来 \(m\) 行每行两个整数 \(x\) 和 \(y\) 表示 \(x\) 在比赛中赢过了 \(y\)。

Output

一行输出确定所有大小关系的最小比赛场数，或输出 -1。

Samples

输入样例

输出样例

Limitation

\(1 \leq n, m \leq 10^5\)

思路与题解

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

bool solve(int n, const vector<int> &U, const vector<int> &V, int t) {
    vector<int> head(n + 1, -1);
    vector<int> indeg(n + 1, 0);
    vector<int> to(t), nxt(t);

    for (int i = 0; i < t; ++i) {
        int u = U[i], v = V[i];
        to[i] = v;
        nxt[i] = head[u];
        head[u] = i;
        ++indeg[v];
    }

    deque<int> q;
    for (int i = 1; i <= n; ++i) if (indeg[i] == 0) q.push_back(i);

    int cnt = 0;
    while (!q.empty()) {
        if ((int)q.size() != 1) return false;
        int u = q.front();
        q.pop_front();
        ++cnt;
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (--indeg[v] == 0) q.push_back(v);
        }
    }
    return cnt == n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> U(m), V(m);
    for (int i = 0; i < m; ++i) cin >> U[i] >> V[i];

    if (!solve(n, U, V, m)) {
        cout << -1 << '\n';
        return 0;
    }

    int lo = 1, hi = m, ans = m;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (solve(n, U, V, mid)) {
            ans = mid;
            hi = mid - 1;
         } else lo = mid + 1;
        
    }

    cout << ans;
    return 0;
}

E. 猫猫喂养

传统题 1000ms 256MB

Background

复旦的校园里有很多很多猫猫，而猫猫们无法从环境中直接获取足够多的食物，因此很多猫猫都需要有人定期对她们进行投喂。

Description

这天你在校园里遇到了 \(n\) 只猫猫，每只猫猫都有一个饥饿值 \(a_i\)，值越大代表她越饥饿。

猫猫们最开始分散在校园的各处。随着时间的推移，猫猫们可能会互相见面，见面后他们会选择组成猫猫小队一起行动，两个猫猫小队见面会让他们一起组成一个新的猫猫小队。

现在你手捧猫粮在校园里随机游走，在这期间你按照时间顺序观测到了一个长度为 \(q\) 的事件序列。每种事件为下面的两种之一：

1 x y：编号为 \(x\) 和编号为 \(y\) 的猫猫相遇了。如果他们本来就属于一个猫猫小队，则无事发生，否则他们各自属于的猫猫小队（或者他自己一只猫猫）合并组成了一个新的猫猫小队。
2 x：你遇到了编号为 \(x\) 的猫猫所在的猫猫小队（或者他自己一只猫猫），你会为这个猫猫小队发放一份猫粮，猫猫小队中饥饿值最高的猫猫将抢到这一份食物（如果有多个饥饿值相同的猫猫，则没有吃过猫粮的猫猫优先享用）。食用猫粮之后猫猫在接下来的时间中，在包括当前事件的每一个事件结束时饥饿值就会除以二并向下取整。特别的，若一只吃过猫粮的猫猫在已食用了一份猫粮之后再一次抢到了猫粮，则猫粮造成的效果不会叠加，猫猫也还是保持一份猫粮造成的效果。

每一次操作完之后你都好奇现在整个校园还有多少猫猫的饥饿值还大于零，请输出这一结果。

Input Format

第一行两个整数 \(n, q\)，猫猫数量和事件数量。

第二行 \(n\) 个整数 \(a_i\)，代表第 \(i\) 只猫猫的初始饥饿值。

接下来 \(q\) 行每行为一个操作，格式与操作内容见题目描述。

Output

输出 \(q\) 行各整数，即每个时刻结束时的饥饿值大于零的猫猫数量。

Samples

输入数据 1

6 4
1 1 4 5 1 4
2 6
2 4
1 2 4
2 2

输出数据 1

解释：

事件 1 结束后，当前饥饿值序列为 \(1\; 1\; 4\; 5\; 1\; 2\)，第六只猫猫食用了猫粮。
事件 2 结束后，当前饥饿值序列为 \(1\; 1\; 2\; 2\; 1\; 1\)，第四只猫猫食用了猫粮。
事件 3 结束后，当前饥饿值序列为 \(1\; 1\; 2\; 1\; 1\; 0\)，第二只和第四只猫猫组成了小队。
事件 4 结束后，当前饥饿值序列为 \(1\; 0\; 2\; 0\; 1\; 0\)，虽然投喂时第二只和第四只猫猫的饥饿值一样，但是第二只猫猫没有食用过猫粮而第四只猫猫食用过，因此第二只猫猫获得了猫粮。

Limitation

\(1 \leq n, q \leq 10^5, 0 < a_i \leq 10^9\)

复旦的猫猫数量确实惊人。

思路与题解

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
using ll = long long;

int bitlen(ll x) {
    int r = 0;
    while (x) { ++r; x >>= 1; }
    return r;
}

class DSUHeap {
public:
    int n = 0;
    vector<int> parent, sz;

    vector<ll> a;  
    vector<int> firstEatTime;  

    struct Node {
        ll val;   
        int never;  
        int id;     
    };

    struct cmp {
        bool operator()(const Node &x, const Node &y) const {
            if (x.val != y.val) return x.val < y.val;
            if (x.never != y.never) return x.never < y.never;
            return x.id > y.id;
        }
    };

    vector<priority_queue<Node, vector<Node>, cmp>> pq; 

    DSUHeap(int n_, const vector<ll> &a_) : n(n_) {
        parent.resize(n + 1);
        sz.assign(n + 1, 1);
        a = a_;
        firstEatTime.assign(n + 1, 0);
        pq.resize(n + 1);

        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
            pq[i].push(Node{a[i], 1, i});
        }
    }

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

    ll curVal(int id, int curTime) const {
        int t0 = firstEatTime[id];
        if (t0 == 0) return a[id];
        int shift = curTime - t0; 
        if (shift <= 0) return a[id];
        if (shift >= 63) return 0;
        return a[id] >> shift;
    }

    int neverEat(int id) const {
        return firstEatTime[id] == 0 ? 1 : 0;
    }

    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        parent[y] = x;
        sz[x] += sz[y];
        auto &A = pq[x];
        auto &B = pq[y];
        while (!B.empty()) {
            A.push(B.top());
            B.pop();
        }
    }

    int getBest(int root, int curTime) {
        auto &H = pq[root];
        while (!H.empty()) {
            Node top = H.top();
            ll rv = curVal(top.id, curTime);
            int rn = neverEat(top.id);
            if (rv == top.val && rn == top.never) return top.id;
            H.pop();
            H.push(Node{rv, rn, top.id});
        }
        return -1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    DSUHeap dsu(n, a);

    ll hungryCnt = n;   
    vector<int> deathCnt(q + 2, 0); 

    for (int t = 1; t <= q; ++t) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            cin >> x >> y;
            dsu.unite(x, y);
        } else {
            int x;
            cin >> x;
            int r = dsu.find(x);
            int id = dsu.getBest(r, t);
            if (id != -1 && dsu.firstEatTime[id] == 0) {
                dsu.firstEatTime[id] = t;
                int die = t + bitlen(a[id]) - 1;
                if (die <= q) ++deathCnt[die];
            }
        }

        hungryCnt -= deathCnt[t];
        cout << hungryCnt << '\n';
    }
    return 0;
}

F. 彩砖大师

传统题 2000ms 128MiB

题目背景

彩砖大师是一款经典的计分类桌游，其游戏中具有丰富的博弈论策略。此题受彩砖大师游戏的计分方式启发而产生。

题目描述

地板上从左到右有 \(n\) 个位置需要铺地砖，其中有一些位置已经铺上了地砖，有些位置还没有铺上。我们用一个长度为 \(n\) 的字符串来表示每个位置的状态，用字符 # 表示已经铺上砖的位置，而用字符 . 表示未铺上砖的位置。

接下来，你需要按照某个顺序，依次为所有未铺上砖的位置进行铺砖。每铺上一块砖，都能获取一定的分数，计分规则是这样的：

当在第 \(i\) 个位置铺上一块砖时，假设位置 \(i\) 左边连续已铺上砖的位置有 \(l\) 个，右边连续已铺上砖的位置有 \(r\) 个，那么此时获得 \(l+r+1\) 分。

当所有位置都铺上砖之后，你获得的总分为每次铺砖的得分之和。

例如 \(n=9\) 的时候，假设状态为 .#.##.#.#，这时候我们为第 \(6\) 个位置铺砖，将会得到 \(2+1+1=4\) 分，然后局面变为 .#.####.#；接下来如果为第 \(1\) 个位置铺砖，将会得到 \(0+1+1=2\) 分，并将局面变为 ##.####.#。

现在你需要找到一个铺砖的顺序，使得最终获得的总分最大，请输出能得到的最大总分值。

输入格式

第一行输入一个正整数 \(n\)，表示地板的长度。

接下来输入一个长度为 \(n\) 的字符串，表示地板初始的局面。

输出格式

输出一行，一个整数，表示在最优策略下能获得的最大总分值。

样例 #1

样例输入 #1

1
2

4
....

样例输出 #1

样例 #2

样例输入 #2

1 2	9 .#.##.#..

样例输出 #2

提示

【样例解释】

对于第一个样例，按顺序从左到右铺满即可得分 \(1+2+3+4=10\) 分。

对于第二个样例，按照位置 \(3, 6, 1, 8, 9\) 的顺序铺剩下的 \(5\) 块砖，得分分别为 \(4+6+7+8+9=34\) 分。

【数据范围】

对于 15% 的数据满足 \(n \leq 10\)

对于 30% 的数据满足 \(n \leq 60\)

对于 50% 的数据满足 \(n \leq 500\)

对于 100% 的数据满足 \(n \leq 5000\)

G. k一串的几何题

传统题 500ms 256MiB

题目描述

kjhhjki 今天遇到了一道几何题，它定义了二维平面上一条直线 \(l\) 关于两个点 \(A,B\) 的圆曲值如下：

[ (l, A, B) = _{X l} |AX - BX| ]

其中 \(|AX|\) 表示点 \(A\) 到点 \(X\) 的距离，\(|BX|\) 表示点 \(B\) 到点 \(X\) 的距离。

现在他有两个固定点 \(A,B\) 的坐标分别为 \((c,0)\) 和 \((-c,0)\)，以及 \(n\) 个两两不同的点。求所有 \(\frac{n(n-1)}{2}\) 条通过这 \(n\) 个点中任意两个点的直线中 \(\mathrm{val}(l, A, B)\) 的最小值。

输入格式

第一行输入两个整数 \(n, c\) \((n \leq 2 \times 10^5，1 \leq c \leq 10^5)\)，表示点的数量和特殊点位置。

接下来 \(n\) 行，每行两个整数 \(x, y\) \((-10^5 \leq x, y \leq 10^5)\)，表示一个点的坐标。

输出格式

输出一个有理数 \(v\)，表示答案。你的答案的相对误差或绝对误差中有一个小于 \(10^{-6}\) 即为正确答案，即满足

[ ^{-6} ]

或

[ |v - v_{}| ^{-6} ]

样例 #1

样例输入 #1

1
2
3

2 5
1 0
2 1

样例输出 #1

1	7.2111025509

样例 #2

样例输入 #2

样例输出 #2

1	0.0000000000

SB. 嘉然今天分什么

传统题 1000ms 256MiB

Description

Y 给嘉然带了一根拉面，他希望嘉然能够喜欢。

但是嘉然根本不喜欢吃拉面，于是嘉然希望将这根拉面切成 \(k\) 段分给她的粉丝们，每段都必须连续。

由于 Y 的拉面水平很差，他拉出来的面的每个单位长度的重量都不一定一样。具体地，这条长度为 \(n\) 的拉面的每个单位长度的重量分别为 \(a_1, a_2, \dots, a_n\)。同时，嘉然只能切出整数长度的拉面。

当然，不能给一个粉丝分太多的拉面，嘉然希望分出的这 \(k\) 段拉面重量的最大值最小。请输出这个最小的最大值。

注意，每段拉面的重量被定义为这段所对应的每个单位长度拉面的重量之和。

Format

Input

第一行两个整数 \(n,k\) 表示拉面长度和粉丝数量。

第二行 \(n\) 个整数表示每单位长度的拉面重量 \(a_1, a_2, \dots, a_n\)。

Output

输出一行表示这 \(k\) 段拉面重量的最大值的最小值。

Samples

输入样例

1 2	5 3 2 3 4 1 3

输出样例

Limitation

\(1 \leq k < n \leq 5 \times 10^5\)，\(1 \leq a_i \leq 10^9\)。

样例解释：切割方式为 2 3 | 5 | 1 3，第一段的重量为 \(2 + 3 = 5\)，第二段的重量为 \(5\)，第三段的重量为 \(1 + 3 = 4\)。

思路与题解

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
using ll = long long;


int main(){
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    ll amax = 0;
    ll suma = 0;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        amax = max(amax, a[i]);
        suma += a[i];
    }
    ll l = amax, r = suma;
    while(l < r){
        ll mid = l +(r-l)/2;
        ll cnt = 1;
        ll cursum = 0;
        for(int i = 0; i < n; ++i){
            if(cursum + a[i] <= mid) cursum += a[i];
            else{
                cnt++;
                cursum = a[i];
            }
        }
        if(cnt <= k){
            r = mid;
        } else{
            l = mid+1;
        }
    }
    cout << l;
    


    return 0;
}

SC. K步能到几个点？

传统题 1000ms 256MiB

题目背景

给出 \(n\) 个结点，以及 \(n \times n\) 的 01 矩阵 \(W_{n \times n}\)，其中 \(W_{i,j}=1\) 则表示存在从 \(i\) 走向 \(j\) 的边；而 \(W_{i,j}=0\) 则表示不存在从 \(i\) 走向 \(j\) 的边。特别的，如果 \(W_{i,i}=1,(1 \leq i \leq n)\) 则表示存在从 \(i\) 走到 \(i\) 自己的自环。

现在，有 \(m\) 次询问，其中第 \(i\) 次询问会给出两个值 \(x_i, k_i\)，询问的内容是，如果从 \(x_i\) 结点出发，走恰好 \(k_i\) 步（每步经过一条可以走的边），请问最后停下来时所在的结点有多少种不同的可能？

输入格式

第一行，\(2\) 个整数 \(n, m\)，分别表示结点数量和询问数量。

接下来 \(n\) 行，每行 \(n\) 个整数（\(0\) 或 \(1\)），用空格隔开，表示矩阵 \(W_{n \times n}\)。其中第 \(i\) 行第 \(j\) 列的整数表示 \(W_{i,j}\)。

接下来 \(m\) 行，每行两个整数 \(x_i, k_i\) 表示一次询问。

输出格式

输出 \(m\) 行，回答每组询问的答案。

样例 #1

样例输入 #1

样例输出 #1

1
2
3

2
2
3

数据范围与提示

\(1 \leq n \leq 70, 1 \leq m \leq 5000, 1 \leq x_i, k_i \leq n\)

思路与题解

#include <iostream>
#include <vector>

using namespace std;
using Matrix =  vector<vector<int>>;

Matrix mul(Matrix& A, Matrix& B){
    int n = A.size();
    Matrix C(n, vector<int> (n, 0));
    for(int i = 0; i < n; ++i){
        for(int k = 0; k < n; ++k){
            if(A[i][k] == 0) continue;
            int aik = A[i][k];
            for(int j = 0; j < n; ++j){
                if(B[k][j] == 0) continue;
                int res = aik & B[k][j];
                if(res == 1) C[i][j] = 1;
            }
        }
    }
    return C;
}


int main(){
    int n, m;
    cin >> n >> m;
    Matrix A(n, vector<int>(n));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j) cin >> A[i][j];
    }

    vector<pair<int, int>> q(m);
    int maxk = 0;

    for(int i = 0; i < m; ++i){
        cin >> q[i].first >> q[i].second;
        maxk = max(maxk, q[i].second);
    }

    vector<Matrix> G(maxk+1);
    G[0] = A;
    for(int i = 1; i <= maxk; ++i){
        G[i] = mul(A, G[i-1]);
    }

    for(int i = 0; i < m; ++i){
        int cx = q[i].first, ck = q[i].second;
        cx--;
        int res = 0;
        for(int j = 0; j < n; ++j){
            if(G[ck-1][cx][j] == 1) res++;  
        }
        cout << res << "\n";
    }
    return 0;
}

(´-ω-｀)

数据结构作业题解12

A. 智力测试

题目背景

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

【样例解释】

【数据范围】

思路与题解

B. 最短合法路径

题目描述

输入格式

输出格式

样例输入1

样例输出1

样例输入2

样例输出2

数据范围

思路与题解

C.SA. 选课

题目背景

输入格式

输出格式

样例 #1

数据范围与提示

思路与题解

D. 美丽值对抗大赛

Description

Format

Input

Output

Samples

输入样例

输出样例

Limitation

思路与题解

E. 猫猫喂养

Background

Description

Input Format

Output

Samples

输入数据 1

输出数据 1

Limitation

思路与题解

F. 彩砖大师

题目背景

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

G. k一串的几何题

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

SB. 嘉然今天分什么

Description

Format

Input

Output

Samples

输入样例