1. 相反数

有个非零且各不相同的整数。

请你编一个程序求出它们中有多少对相反数( 和为一对相反数)。

输入格式
第一行包含一个正整数。

第二行为个用单个空格隔开的非零整数，每个数的绝对值不超过，保证这些整数各不相同。

输出格式
只输出一个整数，即这个数中包含多少对相反数。

数据范围

思路:数组哈希

对于每个数,我们只关心它的绝对值,如果一个数的绝对值出现了两次,说明它和它的相反数都出现了,我们就可以把结果+1
遍历哈希表,统计出现两次的数的个数,就是相反数对的个数

时间复杂度:O(n)

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1005;
int s[N];

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        s[abs(x)]++;
    }

    int res = 0;
    for(auto x:s)
        if(x == 2)
            res++;

    cout << res << endl;

    return 0;
}

2. 窗口

在某图形操作系统中，有个窗口，每个窗口都是一个两边与坐标轴分别平行的矩形区域。

窗口的边界上的点也属于该窗口。

窗口之间有层次的区别，在多于一个窗口重叠的区域里，只会显示位于顶层的窗口里的内容。

当你点击屏幕上一个点的时候，你就选择了处于被点击位置的最顶层窗口，并且这个窗口就会被移到所有窗口的最顶层，而剩余的窗口的层次顺序不变。

如果你点击的位置不属于任何窗口，则系统会忽略你这次点击。

现在我们希望你写一个程序模拟点击窗口的过程。

输入格式
输入的第一行有两个正整数，即和。

接下来行按照从最下层到最顶层的顺序给出个窗口的位置。

每行包含四个非负整数，表示该窗口的一对顶点坐标分别为和。保证。

接下来行每行包含两个非负整数，表示一次鼠标点击的坐标。

题目中涉及到的所有点和矩形的顶点的坐标分别不超过和。

输出格式
输出包括行，每一行表示一次鼠标点击的结果。

如果该次鼠标点击选择了一个窗口，则输出这个窗口的编号(窗口按照输入中的顺序从编号到 )。

如果没有，则输出 IGNORED。

数据范围

思路:模拟

时间复杂度:O(n*m)
空间复杂度:O(n)

用一个结构体数组存储窗口信息和 id,每次点击时从顶层窗口开始往下找,如果找到一个包含点击位置的窗口就输出它的 id,并把它移到最顶层,如果没有找到就输出 IGNORED

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 15;

typedef struct {
    int x1, x2, y1, y2;
    int id;
} Windows;

int main() {
    Windows w[N];
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        w[i] = {x1, x2, y1, y2, i};
    }

    while(m--){
        int x, y;
        cin >> x >> y;
        int res = -1;
        for (int j = n; j >= 1; --j) {
            if (x >= w[j].x1 && x <= w[j].x2 && y >= w[j].y1 && y <= w[j].y2) {
                res = w[j].id;
                auto t = w[j];
                for (int k = j; k < n; ++k)
                    w[k] = w[k + 1];
                w[n] = t;
                break;
            }
        }

        if (res== -1)
            puts("IGNORED");
        else {
            cout << res << endl;
        }
    }

    return 0;
}

3. 命令行选项

请你写一个命令行分析程序，用以分析给定的命令行里包含哪些选项。

每个命令行由若干个字符串组成，它们之间恰好由一个空格分隔。

这些字符串中的第一个为该命令行工具的名字，由小写字母组成，你的程序不用对它进行处理。

在工具名字之后可能会包含若干选项，然后可能会包含一些不是选项的参数。

选项有两类:带参数的选项和不带参数的选项。

一个合法的无参数选项的形式是一个减号后面跟单个小写字母,如 -a 或 -b。

而带参数选项则由两个由空格分隔的字符串构成，前者的格式要求与无参数选项相同，后者则是该选项的参数，是由小写字母，数字和减号组成的非空字符串。

该命令行工具的作者提供给你一个格式字符串以指定他的命令行工具需要接受哪些选项。

这个字符串由若干小写字母和冒号组成，其中的每个小写字母表示一个该程序接受的选项。

如果该小写字母后面紧跟了一个冒号，它就表示一个带参数的选项，否则则为不带参数的选项。

例如，ab:m: 表示该程序接受三种选项，即 -a(不带参数)，-b(带参数)，以及 -m(带参数)。

命令行工具的作者准备了若干条命令行用以测试你的程序。

对于每个命令行，你的工具应当一直向后分析。

当你的工具遇到某个字符串既不是合法的选项，又不是某个合法选项的参数时，分析就停止。

命令行剩余的未分析部分不构成该命令的选项，因此你的程序应当忽略它们。

输入格式

输入的第一行是一个格式字符串，它至少包含一个字符，且长度不超过。

格式字符串只包含小写字母和冒号，保证每个小写字母至多出现一次，不会有两个相邻的冒号，也不会以冒号开头。

输入的第二行是一个正整数，表示你需要处理的命令行的个数。

接下来有行，每行是一个待处理的命令行，它包括不超过个字符。该命令行一定是若干个由单个空格分隔的字符串构成，每个字符串里只包含小写字母，数字和减号。

输出格式

输出有行。其中第行以 Case i: 开始，然后应当有恰好一个空格，然后应当按照字母升序输出该命令行中用到的所有选项的名称，对于带参数的选项，在输出它的名称之后还要输出它的参数。

如果一个选项在命令行中出现了多次，只输出一次。

如果一个带参数的选项在命令行中出现了多次，只输出最后一次出现时所带的参数。

数据范围

,
对于每组数据，所有命令行工具的名字一定相同，且由小写字母构成。

思路:模拟

时间复杂度:o(n)
空间复杂度:O(n)

构建两个 bool 数组,o1记录不带参数的选项,o2记录带参数的选项,一个字符串数组 ans 用来记录选项的参数,如果是无参数选项则记录为 *,如果是带参数选项则记录为参数值,最后题目要求的字典序升序输出

#include <iostream>
#include <cstring>
#include <algorithm>
#include <sstream>

using namespace std;

const int N = 30;
bool o1[N],o2[N]; // 用来判断是无参数选项还是有参数选项
string ans[N]; // 用来保存有参数选项的参数


int main(){
    //读取选项并判断选项类型
    string str;cin >> str;
    for(int i = 0;i<str.size();++i){
        if(i+1<str.size() && str[i+1] == ':'){
            o2[str[i] - 'a'] = true;
            ++i;
        }else{
            o1[str[i] - 'a'] = true;
        }
    }

    int n;cin >> n;
    getchar(); // 过滤 n 后面的回车
    for(int c = 1;c<=n;++c){
        printf("Case %d:",c);
        getline(cin,str);
        stringstream scin(str);
        vector<string> ops;
        while(scin >> str)ops.push_back(str);
        for(int i = 0;i<26;++i)ans[i].clear(); //注意每次都需要将 ans 清空

        // 存储有参数选项的参数,第一个ops是 ls 可以直接跳过
        for(int i=1;i<ops.size();++i){
            if(ops[i][0] != '-' || ops[i][1] < 'a' || ops[i][1] >'z' || ops[i].size()!=2)break;
            int k = ops[i][1] - 'a';
            if(o1[k] ){
                ans[k] = '*';
            }else if(o2[k] && i+1<ops.size()){
                ans[k] = ops[i+1];
                ++i;
            }else
                break;
        }

        // 输出结果
        for(int i = 0;i<26;++i){
            if(ans[i].size()){
                cout << " -" << (char)('a'+i);
                if(o2[i])cout <<" "<< ans[i];
            }
        }
        cout << endl;
    }

    return 0;
}

4. 无线网络

目前在一个很大的平面房间里有个无线路由器，每个无线路由器都固定在某个点上。

任何两个无线路由器只要距离不超过就能互相建立网络连接。

除此以外，另有个可以摆放无线路由器的位置。

你可以在这些位置中选择至多个增设新的路由器。

你的目标是使得第个路由器和第个路由器之间的网络连接经过尽量少的中转路由器。

请问在最优方案下中转路由器的最少个数是多少?

输入格式

第一行包含四个正整数。

接下来行，每行包含两个整数和，表示一个已经放置好的无线路由器在点处。输入数据保证第和第个路由器在仅有这个路由器的情况下已经可以互相连接（经过一系列的中转路由器）。

接下来行，每行包含两个整数和，表示点处可以增设一个路由器。

输入中所有的坐标的绝对值不超过，保证输入中的坐标各不相同。

输出格式

输出只有一个数，即在指定的位置中增设个路由器后，从第个路由器到第个路由器最少经过的中转路由器的个数。

数据范围

输入样例：

输出样例：

思路:图最短路径 + BFS

时间复杂度:O(k*(n+m)^2)
空间复杂度:O(n*m)

目标:从路由器 1 到路由器 2 的且不同特殊点数 <= k的最短路径

等价于:

从路由器 1 到路由器 2 的且特殊点数 <= k的最短路径,因为路径出现了环,肯定不是最短路径

DP问题可以看做特殊的图问题(拓扑图问题)

什么是拓扑图?

拓扑图是指一个有向无环图（DAG），其中的节点表示任务或事件，边表示任务之间的依赖关系。在拓扑图中，如果存在一条从节点 A 到节点 B 的路径，那么 A 必须在 B 之前完成。这种结构常用于表示任务调度、编译顺序等问题。

在 DP 问题中，我们可以将状态转移关系表示为一个拓扑图，其中节点表示 DP 状态，边表示状态之间的转移关系。通过对这个拓扑图进行遍历，我们可以按照依赖关系计算出最终的 DP 结果。

什么是循环依赖?

循环依赖是指在一个系统中，两个或多个组件相互依赖，形成一个闭环。这种情况会导致系统无法正常运行，因为每个组件都需要另一个组件的输出才能完成自己的功能，但又无法得到所需的输入。

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 210, M = N * N; // n+m 最多 200个节点,最多 M 个边
int n, m, k, r;
// h[N]     // h[i] = 节点i的邻接表头指针（初值-1表示无邻接）
// e[M]     // e[j] = 第j条边指向的目标节点
// ne[M]    // ne[j] = 第j条边之后的下一条边的索引（形成链表）
// idx      // 当前边的编号计数器
int h[N], e[M], ne[M], idx; // 邻接表存储图
PII p[N]; // 存储所有路由器坐标
int dist[N][N]; // dist[x][y]:到路由器x用y个新路由器的最少步数

bool check(PII a, PII b) {
    ll dx = a.x - b.x;
    ll dy = a.y - b.y;
    return dx * dx + dy * dy <= (ll)r * r;
}

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int bfs() { 
    queue<PII> q;
    q.push({1, 0});
    memset(dist, 0x3f, sizeof dist); //按字节赋值实际为 0x3f3f3f3f
    dist[1][0] = 0;

    while (q.size()) {
        auto t = q.front();
        q.pop();

        // 遍历路由器 t.x 的所有邻接节点
        for (int i = h[t.x]; i != -1; i = ne[i]) { // i != -1 等价于 ~i 因为 -1 == ...1111, ~(-1) == ...0000 = 0
            int x = e[i]; //下一个节点
            int y = t.y; //继承当前使用的新路由器数
            if (x > n) // 下一节点是新增路由器
                ++y;
            if (y <= k) {  //不超过 k 个新路由器
                if (dist[x][y] > dist[t.x][t.y] + 1) {
                    dist[x][y] = dist[t.x][t.y] + 1;
                    q.push({x, y});
                }
            }
        }
    }

    int res = 1e8;
    for (int i = 0; i <= k; ++i) {
        res = min(res, dist[2][i]); // 路由器 2 处,用 0~k个新路由器的最少步数
    }
    return res - 1; //因为这里求的中转数,步数 - 1 == 中转数
}

int main() {
    cin >> n >> m >> k >> r;
    memset(h, -1, sizeof h);
    // 存储节点
    for (int i = 1; i <= n; ++i)
        cin >> p[i].x >> p[i].y;
    for (int i = n + 1; i <= n + m; ++i)
        cin >> p[i].x >> p[i].y;

    for (int i = 1; i <= n+m; ++i) {
        for (int j = i + 1; j <= n + m; ++j)
            if (check(p[i], p[j]))
                add(i, j), add(j, i);
    }

    cout << bfs() << endl;
    return 0;
}

5. 任务调度

有个任务需要在一台机器上运行。任务之间没有依赖关系，可以按任意顺序执行。该机器配置为：2个 CPU + 1个 GPU。

任务调度方案

对每个任务，可选择以下四种硬件分配方案之一：

在单个 CPU 上运行
在两个 CPU 上同时运行
在单个 CPU 和 GPU 上同时运行
在两个 CPU 和 GPU 上同时运行

重要约束：任务一旦开始执行，将独占所用硬件资源，不得中断，直到执行结束。

任务参数

第个任务用不同硬件配置运行的耗时分别为：

：单 CPU
：双 CPU
：单 CPU + GPU
：双 CPU + GPU

目标

计算完成所有任务所需的最少时间。

输入格式

第一行：正整数（任务总数）
接下来行：每行四个正整数

输出格式

输出一个整数，表示完成所有任务的最少时间。

数据范围

输入样例

输出样例

样例说明

以下是一种在 7 个时间单位内完成所有任务的调度方案：

时间段	操作	完成时刻
时刻 0～2	任务 1 运行于（单 CPU + GPU），耗时 2	时刻 2
时刻 0～3	任务 3 运行于（单 CPU），耗时 3	时刻 3
时刻 3～7	任务 2 运行于（双 CPU），耗时 4	时刻 7

硬件利用情况：

两个 CPU 在 0～3 时段都被占用（任务 1 占 1 个，任务 3 占 1 个）
GPU 在 0～2 时段被占用（任务 1 占用）
双 CPU 在 3～7 时段被占用（任务 2 占用）

思路: DP + 滚动数组

性质 1:两个 CPU 都在工作的话,后续任务无法执行

本质上只有三个状态

模式 1:用 1 个 cpu -> a
模式 2:用 1 个 cpu 和 1 个gpu -> c
模式 3:用 2 个 cpu 和 1 个gpu 或只用 2 个 cpu -> min(b,d)

性质 2:模式 3 可以和后面的任务交换执行顺序,放在最后执行

性质 3:只考虑模式 1,2,总用时中,cpu1 用时为 i,cpu2 用时为 j,gpu 用时为 k,则用时时间且一定存在一个顺序使得用时时间等于

可以不考虑顺序

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 50, M = 210, INF = 0x3f3f3f3f;
// c[i][0]: 任务 i 用 1 个 CPU 的耗时 a_i
// c[i][1]: 任务 i 用 1 个 CPU + GPU 的耗时 c_i
// c[i][2]: 任务 i 使用 GPU 时的最优耗时 min(b_i, d_i)
int c[N][3];
// f[cur][i][j][k]: 处理到当前任务时，三类资源累计时间分别为 i,j,k 的最小“额外代价”
// 这里用滚动数组，cur 只有 0/1 两层
int f[2][M][M][M];

int main() {
    int n; // 任务数量
    cin >> n;
    int m = 0, m2 = 0; // m: a_i 总和上界, m2: 奇数下标任务的 a_i 和（用于压缩上界）
    for (int i = 1; i <= n; ++i) {
        int x, y, z, t; // 输入的 a_i, b_i, c_i, d_i
        cin >> x >> y >> z >> t;
        c[i][0] = x, c[i][1] = z, c[i][2] = min(y, t);
        m += x;
        if (i % 2)
            m2 += x;
    }
    m = max(m2, m - m2); // 这里简单得按奇偶性分成两组即可
    memset(f, 0x3f, sizeof f);
    f[0][0][0][0] = 0;

    for (int u = 1; u <= n; ++u) { // 枚举任务编号
        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= m; ++k) {
                    int &v = f[u & 1][i][j][k]; // 当前层状态引用
                    if (k > j)
                        v = INF;
                    else {
                        register int x = c[u][0], y = c[u][1], z = c[u][2], t = (u - 1) & 1;
                        // t: 上一层滚动数组下标
                        // x,y,z: 当前任务在不同资源方案下的耗时参数
                        v = f[t][i][j][k] + z;
                        if (i >= x)
                            v = min(v, f[t][i - x][j][k]);
                        if (j >= x)
                            v = min(v, f[t][i][j - x][k]);
                        if (i >= y && k >= y)
                            v = min(v, f[t][i - y][j][k - y]);
                        if (j >= y && k >= y)
                            v = min(v, f[t][i][j - y][k - y]);
                    }
                }
            }
        }
    }

    int res = INF; // 最终最小完工时间
    for (int i = 0; i <= m; ++i)
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= m; ++k)
                res = min(res, f[n & 1][i][j][k] + max(i, max(j, k)));

    cout << res << endl;

    return 0;
}

TK的小站

第一届CCF计算机软件能力认证题解

1. 相反数

思路:数组哈希

2. 窗口

思路:模拟

3. 命令行选项

输入格式

输出格式

数据范围

思路:模拟

4. 无线网络

输入格式

输出格式

数据范围

输入样例：

输出样例：

思路:图最短路径 + BFS

什么是拓扑图?

什么是循环依赖?

5. 任务调度

任务调度方案

任务参数

目标

输入格式

输出格式

数据范围

输入样例

输出样例

样例说明

思路: DP + 滚动数组

性质 1:两个 CPU 都在工作的话,后续任务无法执行

性质 2:模式 3 可以和后面的任务交换执行顺序,放在最后执行

性质 3:只考虑模式 1,2,总用时中,cpu1 用时为 i,cpu2 用时为 j,gpu 用时为 k,则用时时间且一定存在一个顺序使得用时时间等于

ttkqwe

第一届CCF计算机软件能力认证题解

1. 相反数

思路:数组哈希

2. 窗口

思路:模拟

3. 命令行选项

输入格式

输出格式

数据范围

思路:模拟

4. 无线网络

输入格式

输出格式

数据范围

输入样例：

输出样例：

思路:图最短路径 + BFS

什么是拓扑图?

什么是循环依赖?

5. 任务调度

任务调度方案

任务参数

目标

输入格式

输出格式

数据范围

输入样例

输出样例

样例说明

思路: DP + 滚动数组

性质 1:两个 CPU 都在工作的话,后续任务无法执行

性质 2:模式 3 可以和后面的任务交换执行顺序,放在最后执行

性质 3:只考虑模式 1,2,总用时中,cpu1 用时为 i,cpu2 用时为 j,gpu 用时为 k,则用时时间 且一定存在一个顺序使得用时时间等于

ttkqwe

性质 3:只考虑模式 1,2,总用时中,cpu1 用时为 i,cpu2 用时为 j,gpu 用时为 k,则用时时间且一定存在一个顺序使得用时时间等于