图像旋转 (100)

旋转是图像处理的基本操作,在这个问题中,你需要将一个图像逆时针旋转 90 度。

计算机中的图像表示可以用一个矩阵来表示,为了旋转一个图像,只需要将对应的矩阵旋转即可。

输入格式

输入的第一行包含两个整数 n,m,分别表示图像矩阵的行数和列数。

接下来 n 行每行包含 m 个整数,表示输入的图像。

输出格式

输出 m 行,每行包含 n 个整数,表示原始矩阵逆时针旋转 90 度后的矩阵。

数据范围

1≤n,m≤1,000,矩阵中的数都是不超过 1000 的非负整数。

输入样例:

2 3
1 5 3
3 2 4

输出样例:

3 4
5 2
1 3

题目分析

找规律

代码实现

#include <iostream>
using namespace std;
const int N = 1010;

int n, m, g[N][N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            cin >> g[i][j];
    for(int i = m - 1; i >= 0; --i) {
        for(int j = 0; j < n; ++j)  cout << g[j][i] << ' ';
        cout << '\n';
    }
    return 0;
} 

数字排序 (100)

给定 n 个整数,请统计出每个整数出现的次数,按出现次数从多到少的顺序输出。

输入格式

输入的第一行包含一个整数 n,表示给定整数的个数。

第二行包含 n 个整数,相邻的整数之间用一个空格分隔,表示所给定的整数。

输出格式

输出多行,每行包含两个整数,分别表示一个给定的整数和它出现的次数。

按出现次数递减的顺序输出。如果两个整数出现的次数一样多,则先输出值较小的,然后输出值较大的。

数据范围

1≤n≤1000,给出的数都是不超过 1000 的非负整数。

输入样例:

12
5 2 3 3 1 3 4 2 5 2 3 5

输出样例:

3 4
2 3
5 3
1 1
4 1

题目分析

Sort Hash

代码实现

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

int n, t;
unordered_map <int,int> mp;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> t;
        ++mp[t];
    }
    int idx = 0;
    PII a[N];
    for(auto i : mp) {
        a[idx].x = i.x;
        a[idx++].y = i.y;
    }
    sort(a, a + idx, [](const PII& a, const PII& b) {
        if(a.y == b.y) return a.x < b.x;
        return a.y > b.y;
    });
    for(int i = 0; i < idx; ++i) cout << a[i].x << ' ' << a[i].y << '\n';
    return 0;
} 

节日 (100)

有一类节日的日期并不是固定的,而是以“a 月的第 b 个星期 c”的形式定下来的,比如说母亲节就定为每年的五月的第二个星期日。

现在,给你 a, b, c 和 y1, y2,希望你输出从公元 y1 年到公元 y2 年间的每年的 a 月的第 b 个星期 c 的日期。

提示:关于闰年的规则:年份是 400 的整数倍时是闰年,否则年份是 4 的倍数并且不是 100 的倍数时是闰年,其他年份都不是闰年。例如 1900 年就不是闰年,而 2000 年是闰年。为了方便你推算,已知 1850 年 1 月 1 日是星期二。

输入格式

输入包含恰好一行,有五个整数 a, b, c, y1, y2。

其中 c=1,2,……,6,7 分别表示星期一、二、……、六、日。

输出格式

对于 y1 和 y2 之间的每一个年份,包括 y1 和 y2,按照年份从小到大的顺序输出一行。

如果该年的 a 月第 b 个星期 c 确实存在,则以 yyyy/mm/dd 的格式输出,即输出四位数的年份,两位数的月份,两位数的日期,中间用斜杠 / 分隔,位数不足时前补零。

如果该年的 a 月第 b 个星期 c 并不存在,则输出 none。

数据范围 1≤a≤12,1≤b≤5,1≤c≤7,1850≤y1, y2≤2050

输入样例:

5 2 7 2014 2015

输出样例:

2014/05/11
2015/05/10

题目分析

模拟

代码实现

#include <iostream>
using namespace std;

int a, b, c, y1, y2, day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool cy(int y) {
    return (y
}
int year[2100];
void init() {
    int theday = 3;
    int l = 1800, t = 0;
    while(l < 2100) {
        year[l] = theday;
        theday += 1 + cy(l++);
        if(theday > 7) theday = theday
    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> a >> b >> c >> y1 >> y2;
    init();
    int theday = year[y1];
    while(y1 <= y2) {
        int m = 1;
        bool flag = 0;
        while(m <= 12) {
            int cnt = 1, d = 1, lim = day[m] + (m == 2 ? cy(y1) : 0);
            while(d <= lim) {
                if(m == a && cnt == b && theday == c) {
                    cout << y1 << '/'; 
                    if(m < 10) cout << '0';
                    cout << m << '/';
                    if(d < 10) cout << '0'; 
                    cout << d << '\n';
                    flag = 1;
                }
                ++d, ++theday;
                if(theday > 7) theday = 1;
                if(theday == year[y1]) ++cnt;
            }
            ++m;
        }
        if(!flag) cout << "none\n";
        ++y1;
    } 
    return 0;
} 

网络延时 (100)

给定一个公司的网络,由 n 台交换机和 m 台终端电脑组成,交换机与交换机、交换机与电脑之间使用网络连接。

交换机按层级设置,编号为 1 的交换机为根交换机,层级为 1。

其他的交换机都连接到一台比自己上一层的交换机上,其层级为对应交换机的层级加 1。

所有的终端电脑都直接连接到交换机上。

当信息在电脑、交换机之间传递时,每一步只能通过自己传递到自己所连接的另一台电脑或交换机。

请问,电脑与电脑之间传递消息、或者电脑与交换机之间传递消息、或者交换机与交换机之间传递消息最多需要多少步。

输入格式

输入的第一行包含两个整数 n, m,分别表示交换机的台数和终端电脑的台数。

第二行包含 n−1 个整数,分别表示第 2、3、……、n 台交换机所连接的比自己上一层的交换机的编号。第 i 台交换机所连接的上一层的交换机编号一定比自己的编号小。

第三行包含 m 个整数,分别表示第 1、2、……、m 台终端电脑所连接的交换机的编号。

输出格式

输出一个整数,表示消息传递最多需要的步数。

数据范围 前 3 前 5 前 7 所有评测用例都满足:1≤n≤10000,1≤m≤10000

输入样例1:

4 2
1 1 3
2 1

输出样例1:

4

输入样例2:

4 4
1 2 2
3 4 4 4

输出样例2:

4

题目分析

BFS DFS Tree 树的直径

代码实现

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e5;

int n, m, h[N], e[N], ne[N], idx;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 2; i <= n; ++i) {
        int p;
        cin >> p;
        add(i,p), add(p,i);
    }
    for(int i = n + 1; i <= n + m; ++i) {
        int p;
        cin >> p;
        add(i,p), add(p,i);
    }
    bool st[N];
    memset(st, 0, sizeof st);
    queue <int> que;
    que.push(1);
    st[1] = 1;
    int node = 1;
    while(que.size()) {
        int t = que.front(); que.pop();
        for(int i = h[t]; ~i; i = ne[i]) {
            int p = e[i];
            if(!st[p]) {
                st[p] = 1;
                que.push(p);
                node = p;
            }
        }
    }
    int dist[N], ans = 0;
    memset(dist, 0x3f, sizeof dist);
    que.push(node);
    dist[node] = 0;
    while(que.size()) {
        int t = que.front(); que.pop();
        for(int i = h[t]; ~i; i = ne[i]) {
            int p = e[i];
            if(dist[p] > dist[t] + 1) {
                dist[p] = dist[t] + 1;
                ans = max(ans, dist[p]);
                que.push(p);
            }
        }
    }
    cout << ans;
    return 0;
} 

最小花费 (0)

C 国共有 n 个城市,编号 1∼n。

有 n−1 条双向道路,每条道路连接两个城市,任意两个城市之间能互相到达。

小 R 来到 C 国旅行,他共规划了 m 条旅行的路线,第 i 条旅行路线的起点是 si,终点是 ti。

在旅行过程中,小 R 每行走一单位长度的路需要吃一单位的食物。

C 国的食物只能在各个城市中买到,而且不同城市的食物价格可能不同。

然而,小 R 不希望在旅行中为了购买较低价的粮食而绕远路,因此他总会选择最近的路走。

现在,请你计算小 R 规划的每条旅行路线的最小花费是多少。

输入格式

第一行包含 2 个整数 n 和 m。

第二行包含 n 个整数。第 i 个整数 wi 表示城市 i 的食物价格。

接下来 n−1 行,每行包括 3 个整数 u,v,e,表示城市 u 和城市 v 之间有一条长为 e 的双向道路。

接下来 m 行,每行包含 2 个整数 si 和 ti,分别表示一条旅行路线的起点和终点。

输出格式

输出 m 行,分别代表每一条旅行方案的最小花费。

数据范围 前 1 前 3 另有 4 所有评测用例都满足:1≤n,m≤105,1≤wi≤106,1≤e≤10000。

输入样例:

6 4
1 7 3 2 5 6
1 2 4
1 3 5
2 4 1
3 5 2
3 6 1
2 5
4 6
6 4
5 6

输出样例:

35
16
26
13

题目分析

点分治 二分 倍增, 此题难度大。


0 条评论

发表回复

Avatar placeholder

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

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

站点状态:Status