相反数 (100)

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

请编写一个程序,计算这些整数中有多少对相反数(a 和 −a 为一对相反数)。

输入格式

  • 第一行包含一个正整数 N。
  • 第二行为 N 个用单个空格隔开的非零整数,每个数的绝对值不超过 1000,保证这些整数各不相同。

输出格式

只输出一个整数,即这 N 个数中包含多少对相反数。

数据范围

1 ≤ N ≤ 500

输入样例:

5
1 2 3 -1 -2

输出样例:

2

代码实现

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

int n, v, po[N], ne[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> v;
        if(v > 0) ++po[v];
        else ++ne[-v];
    }
    int cnt = 0;
    for (int i = 0; i < N; ++i) cnt += min(po[i], ne[i]);
    cout << cnt;
    return 0;
} 

窗口 (100)

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

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

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

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

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

输入格式

输入的第一行有两个正整数,即 N 和 M。

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

每行包含四个非负整数 x1,y1,x2,y2,表示该窗口的一对顶点坐标分别为 (x1,y1) 和 (x2,y2)。保证 x1<x2,y1<y2。

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

输出格式

输出包括 M 行,每一行表示一次鼠标点击的结果。

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

如果没有,则输出 IGNORED。

数据范围

1 ≤ N, M ≤ 10

输入样例:

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

输出样例:

2
1
1
IGNORED

题目分析

模拟

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;

typedef struct {
    int x1, x2, y1, y2, p;
}page;
page pages[N];
int n, m;
bool check(int x, int y, int i) {
    auto& t = pages[i];
    return x >= t.x1 && x <= t.x2 && y >= t.y1 && y <= t.y2;
}
void move(int i) {
    page t = pages[i];
    for (int k = i; k > 1; --k) pages[k] = pages[k - 1];
    pages[1] = t;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> pages[n - i + 1].x1
            >> pages[n - i + 1].y1
            >> pages[n - i + 1].x2
            >> pages[n - i + 1].y2;
        pages[n - i + 1].p = i;
    }
    while(m--) {
        int x, y;
        bool flag = 0;
        cin >> x >> y;
        for (int i = 1; i <= n; ++i) {
            if (check(x,y,i)) {
                flag = 1;
                cout << pages[i].p << '\n';
                move(i);
                break;
            }
        }
        if (!flag) cout << "IGNORED\n";
    }
    return 0;
} 

命令行选项 (100)

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

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

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

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

输出格式

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

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

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

数据范围 1 ≤ N ≤ 20,

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

输入样例:

albw:x
4
ls -a -l -a documents -b
ls
ls -w 10 -x -w 15
ls -a -b -c -d -e -l

输出样例:

Case 1: -a -l
Case 2:
Case 3: -w 15 -x
Case 4: -a -b

题目分析

大模拟

代码实现

#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <vector>
using namespace std;
const int M = 26;

int n, mp[M];
string s;
void solve(int c) {
    getline(cin,s);
    bool v[M];
    memset(v, 0, sizeof v);
    stringstream sstr(s);
    vector <string> vs, w(M, "");
    while(sstr >> s) vs.push_back(s);
    for (int i = 1; i < vs.size(); ++i) {
        if(vs[i].size() != 2 || *vs[i].begin() != '-' || !mp[vs[i][1] - 'a']) break;
        int ch = vs[i][1] - 'a';
        if(mp[ch] == 1) v[ch] = 1;
        else {
            if(i + 1 < vs.size() && *vs[i + 1].begin() != '-') {
                v[ch] = 1;
                w[ch] = vs[++i];
            }
            else break;
        }
    }
    cout << "Case " << c << ':' << ' ';
    for (int i = 0; i < M; ++i) {
        if(v[i]) cout << '-' << (char)(i + 'a') << ' ';
        if(w[i] != "") cout << w[i] << ' ';
    }
    cout << '\n';
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    s += ' ';
    for (int i = 0; i < s.length() - 1; ++i) {
        if(s[i] != ':') {
            int ch = s[i] - 'a';
            mp[ch] = 1;
            if(s[i + 1] == ':') mp[ch] = 2;
        }
    }
    cin >> n;
    cin.ignore();
    for (int i = 1; i <= n; ++i) solve(i);
    return 0;
} 

无线网络 (100)

第一行包含四个正整数 n, m, k, r。

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

接下来 m 行,每行包含两个整数 xi 和 yi,表示 (xi, yi) 点处可以增设一个路由器。

输出格式

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

数据范围 2 ≤ n ≤ 100, 1 ≤ k ≤ m ≤ 100, 1 ≤ r ≤ 10^8

输入样例:

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

输出样例:

2

题目分析

BFS

代码实现

#include <iostream>
#include <queue>
#include <cstring>
#define x first 
#define y second 
using namespace std;
using PII = pair <int,int>;
using LL = long long;
const int N = 220, M = N * N;

int n, m, k, r, dp[N][N], h[N],e[M],ne[M],idx;
PII nodes[N];
bool check(int i, int j) {
    LL x = nodes[i].x - nodes[j].x;
    LL y = nodes[i].y - nodes[j].y;
    return x * x + y * y <= 1ll * r * r;
}
bool isSpecial(int i) {return i > n;}
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs() {
    queue <PII> que;
    dp[1][0] = 0;
    que.push({1,0});
    while(que.size()) {
        PII t = que.front(); que.pop();
        for (int i = h[t.x]; ~i; i = ne[i]) {
            int j = e[i];
            int y = t.y + isSpecial(j);
            if(y > k) continue;
            if(dp[j][y] > dp[t.x][t.y] + 1) {
                dp[j][y] = dp[t.x][t.y] + 1;
                que.push({j,y});
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= k; ++i) 
        ans = min(ans, dp[2][i]);
    return ans - 1;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(h, -1, sizeof h);
    memset(dp, 0x3f, sizeof dp);
    cin >> n >> m >> k >> r;
    for (int i = 1; i <= n; ++i) cin >> nodes[i].x >> nodes[i].y;
    for (int i = n + 1; i <= n + m; ++i) cin >> nodes[i].x >> nodes[i].y;
    for (int i = 1; i <= n + m; ++i)
        for (int j = i + 1; j <= n + m; ++j)
            if(check(i,j)) add(i,j), add(j,i);
    cout << bfs();
    return 0;
} 

任务调度 (0)

输入的第一行只有一个正整数 n,是总共需要执行的任务个数。

接下来的 n 行每行有四个正整数 ai, bi, ci, di,以空格隔开。

输出格式

输出只有一个整数,即完成给定的所有任务所需的最少时间。

数据范围 1 ≤ n ≤ 40, 1 ≤ ai, bi, ci, di ≤ 10

输入样例:

3
4 4 2 2
7 4 7 4
3 3 3 3

输出样例:

7

题目分析

DP, 有空回来填坑。


0 条评论

发表回复

Avatar placeholder

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

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

站点状态:Status