门禁系统 (100)

涛涛最近要负责图书馆的管理工作,需要记录下每天读者的到访情况。

每位读者有一个唯一编号,每条记录用读者的编号来表示。

给出读者的来访记录,请问每一条记录中的读者是第几次出现。

输入格式: 输入的第一行包含一个整数 n,表示涛涛的记录条数。

第二行包含 n 个整数,依次表示涛涛的记录中每位读者的编号。

输出格式: 输出一行,包含 n 个整数,由空格分隔,依次表示每条记录中的读者编号是第几次出现。

数据范围: 1≤n≤1000 ,读者的编号为不超过 n 的正整数。

输入样例:

5
1 2 1 1 3

输出样例:

1 1 2 3 1

题目分析

hash

代码实现

#include <iostream>
using namespace std;
const int N = 1e3 + 10;

int n, mp[N], v;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> v;
        cout << ++mp[v] << ' ';
    }
    return 0;
} 

Z字形扫描 (100)

在图像编码的算法中,需要将一个给定的方形矩阵进行 Z 字形扫描(Zigzag Scan)。

给定一个 n×n 的矩阵,Z 字形扫描的过程如下图所示:

zig.png

对于下面的 4×4 的矩阵,

1 5 3 9 3 7 5 6 9 4 6 4 7 3 1 3

对其进行 Z 字形扫描后得到长度为 16 的序列:1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3。

请实现一个 Z 字形扫描的程序,给定一个 n×n 的矩阵,输出对这个矩阵进行 Z 字形扫描的结果。

输入格式: 输入的第一行包含一个整数 n,表示矩阵的大小。

输入的第二行到第 n+1 行每行包含 n 个正整数,由空格分隔,表示给定的矩阵。

输出格式: 输出一行,包含 n×n 个整数,由空格分隔,表示输入的矩阵经过 Z 字形扫描后的结果。

数据范围: 1≤n≤500 ,矩阵元素为不超过 1000 的正整数。

输入样例:

4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

输出样例:

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

题目分析

找规律 BFS

代码实现

#include <iostream>
#include <queue>
#define x first 
#define y second 
using namespace std;
using PII = pair <int,int>;
const int N = 510;

int g[N][N], n;
bool st[N][N];
PII dir[4] = {{1,0},{0,1}};
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cin >> g[i][j];
    bool f = 0;
    queue <PII> que[2];
    que[f].push({0,0});
    st[0][0] = 1;
    cout << g[0][0] << ' ';
    while(que[f].size() || que[!f].size()) {
        int ans[N], idx = 0;
        while(que[f].size()) {
            auto t = que[f].front(); que[f].pop();
            for(int k = 0; k < 2; ++k) {
                int I = t.x + dir[k].x, J = t.y + dir[k].y;
                if(I >= 0 && I < n && J >= 0 && J < n && !st[I][J]) {
                    st[I][J] = 1;
                    ans[idx++] = g[I][J];
                    que[!f].push({I,J});
                }
            }
        }
        f = !f;
        if(!f) for(int i = 0; i < idx; ++i) cout << ans[i] << ' ';
        else while(--idx >= 0) cout << ans[idx] << ' ';
    }
    return 0;
} 

集合竞价 (100)

某股票交易所请你编写一个程序,根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。

该程序的输入由很多行构成,每一行为一条记录,记录可能有以下几种:

  • buy p s 表示一个购买股票的买单,每手出价为 p,购买股数为 s。
  • sell p s 表示一个出售股票的卖单,每手出价为 p,出售股数为 s。
  • cancel i 表示撤销第 i 行的记录。被撤销的记录一定是前两种。

如果开盘价为 p0,则系统可以将所有出价至少为 p0 的买单和所有出价至多为 p0 的卖单进行匹配。

因此,此时的开盘成交量为出价至少为 p0 的买单的总股数和所有出价至多为 p0 的卖单的总股数之间的较小值。

你的程序需要确定一个开盘价,使得开盘成交量尽可能地大。

如果有多个符合条件的开盘价,你的程序应当输出最高的那一个。

输入格式: 输入数据有任意多行,每一行是一条记录。

保证输入合法。股数为不超过 10^8 的正整数,出价为精确到恰好小数点后两位的正实数,且不超过 10000.00。

输出格式: 你需要输出一行,包含两个数,以一个空格分隔。

第一个数是开盘价,第二个是此开盘价下的成交量。

开盘价需要精确到小数点后恰好两位。

数据范围: 对于 10 0 < p ≤ 10^4

1 ≤ s ≤ 10^8

数据保证一定存在某个开盘价使得成交量不为 0。

保证输入合法。数据保证 cancel 指令只会取消 buy 和 sell 记录。

输入样例:

buy 9.25 100
buy 8.88 175
sell 9.00 1000
buy 9.00 400
sell 8.92 400
cancel 1
buy 100.00 50

输出样例:

9.00 450

题目分析

模拟 二分查找 离散化 前缀和

代码实现

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
#define x first 
#define y second
using namespace std;
using LL = long long;
using PFI = pair <float,int>;
const int N = 5010;

int idx, s[N];
string type[N];
bool del[N];
float p[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(cin >> type[++idx]) {
        if(type[idx] == "buy") cin >> p[idx] >> s[idx];
        else if (type[idx] == "sell") cin >> p[idx] >> s[idx];
        else {
            cin >> s[idx];
            del[s[idx]] = 1;
            //if(type[s[idx]] == "cancel") del[s[s[idx]]] = 0;
        }
    }
    float resp = 0; 
    LL ress = 0;
    for(int i = 1; i <= idx; ++i) {
        LL by = 0, sl = 0;
        if(!del[i]) {
            for(int j = 1; j <= idx; ++j) {
                if(!del[j]) {
                    if(type[j] == "buy" && p[j] >= p[i])
                        by += s[j];
                    else if (type[j] == "sell" && p[j] <= p[i])
                        sl += s[j];
                }
            }
        }
        if(ress < min(by,sl)) {
            ress = min(by,sl);
            resp = p[i];
        }
        else if (ress == min(by,sl) && p[i] > resp) resp = p[i];
    }
    printf("
    return 0;
} 

最优灌溉 (100)

雷雷承包了很多片麦田,为了灌溉这些麦田,雷雷在第一个麦田挖了一口很深的水井,所有的麦田都从这口井来引水灌溉。

为了灌溉,雷雷需要建立一些水渠,以连接水井和麦田,雷雷也可以利用部分麦田作为“中转站”,利用水渠连接不同的麦田,这样只要一片麦田能被灌溉,则与其连接的麦田也能被灌溉。

现在雷雷知道哪些麦田之间可以建设水渠和建设每个水渠所需要的费用(注意不是所有麦田之间都可以建立水渠)。请问灌溉所有麦田最少需要多少费用来修建水渠。

输入格式: 输入的第一行包含两个正整数 n, m,分别表示麦田的片数和雷雷可以建立的水渠的数量。麦田使用 1,2,3,…… 依次标号。

接下来 m 行,每行包含三个整数 ai, bi, ci,表示第 ai 片麦田与第 bi 片麦田之间可以建立一条水渠,所需要的费用为 ci。

输出格式: 输出一行,包含一个整数,表示灌溉所有麦田所需要的最小费用。

数据范围: 前 2 前 4 前 6 所有评测用例都满足:1≤n≤1000,1≤m≤100,000,0≤ci≤10,000。 保证一定可以灌溉到所有麦田,并且无重边和自环(补充这个条件是为了和官方数据保持一致)。 注意,关于 ci 的取值范围,官网标注的是 ci≥1,但是经过实际测试,官方数据中包含 ci=0 的数据,因此在这里予以修正,并添加相应数据。

输入样例:

4 4
1 2 1
2 3 4
2 4 2
3 4 3

输出样例:

6

样例解释: 建立以下三条水渠:麦田 1 与麦田 2、麦田 2 与麦田 4、麦田 4 与麦田 3。

题目分析

Kruskal

代码实现

#include <iostream>
#include <queue> 
#include <cstring>
#define x first 
#define y second 
using namespace std;
using PII = pair <int,int>;
const int N = 1010;

class UnionFind{
    int p[N];
public:
    UnionFind() {
        for(int i = 0; i < N; ++i) p[i] = i;
    }
    int find(int i) {
        return p[i] == i ? i : p[i] = find(p[i]);
    }
    void merge(int i, int j) {
        p[find(i)] = find(j);
    }
};
int n, m, idx, c;
PII edges[N];
priority_queue <PII, vector <PII>, greater<PII>> heap;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    UnionFind uf;
    cin >> n >> m;
    for(int i = 0; i < m; ++i) {
        cin >> edges[i].x >> edges[i].y >> c;
        heap.push({c,i});
    }
    int res = 0, cnt = 0;
    while(heap.size()) {
        PII t = heap.top(); heap.pop();
        if(uf.find(edges[t.y].x) != uf.find(edges[t.y].y)) {
            uf.merge(edges[t.y].x,edges[t.y].y);
            res += t.x;
            ++cnt;
        }
    }
    if(cnt == n - 1) cout << res;
    else cout << "impossible";
    return 0;
} 

货物调度 (0)

某公司要处理一个周期性的物流问题。

有 n 个城市,第 i 个城市在每周的第 j(1≤j≤7) 天会生产 aij 吨某种货物,同时需要消耗 bij 吨该种货物。

已知每周的产量等于消耗量(即 aij 之和等于 bij 之和)。

城市之间有 m 条道路,第 k 条道路连接了城市 sk 和 tk。

一条道路上运输 1 吨货物有一个固定的成本 ck。

道路都可以双向使用。

每天运输的货物量没有限制。

城市之间的距离并不远,货物可以从任意一个城市运输到任意另一个城市并且在当天到达。

货物如果在当天没有被消耗掉,就需要存放在仓库里过夜。

第 i 个城市的仓库容量为 vi,存放 1 吨货物过一夜所需的成本是 wi。

请你计算该公司如果每周循环性地按照一个固定的流程调度货物的话,该公司在最优方案下每周需要为货物的运输和存储消耗多少成本。

输入格式: 输入的第一行有两个正整数 n 和 m,即城市的个数和道路的条数。

接下来有 n 行,每行包含 16 个整数,用以描述第 i 个城市的相关数据。其中第 i 行包含的数为 ai1,ai2,ai3,ai4,ai5,ai6,ai7,bi1,bi2,bi3,bi4,bi5,bi6,bi7,vi,wi。

接下来有 m 行,每行包含 3 个整数,用以描述一条道路的相关数据。其中第 k 行包含的数为 sk,tk 和 ck。

输入数据中城市的编号均为 1 到 n 之间。

输入数据的每行的行首行尾均保证没有空格,两个数之间恰好被一个空格隔开。

输出格式: 你只需要输出一个数,即最优方案下每周的支出。

数据范围: 对于 10 数据保证仓库够用。 数据保证无重边和自环。(补充这个条件是为了和官方数据保持一致)

输入样例:

3 3
0 0 0 0 5 0 0 0 0 0 0 0 0 0 2 4
0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 1
0 0 0 0 0 0 0 0 0 3 0 0 0 0 2 5
1 2 1
1 3 5
2 3 1

输出样例:

67

样例解释: 城市 1 每周五生产 5 吨货物,把其中 2 吨运到存储费用低廉的城市 2 存储,把 1 吨运到城市 3 存储,剩下的 2 吨留在城市 1。

在次周一的时候城市 2 会消耗掉存放在那里的 2 吨货物。

为了节约存储成本,将囤放在城市 1 的货物运到城市 2 存放。

周三再将所有货物运到城市 3 以满足该城市的需求。

在此方案下,每周的运输成本为 8,每周的存储成本为 59,因此每周的总支出为 67。

题目分析

最大流 费用流 现在没学,没法做。


0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status