T1[不一样的逆序数]

题目描述

小团最近对逆序数（将一个数字逐位逆序，例如1234的逆序数位4321）特别感兴趣，但是又觉得普通的逆序数问题有点太乏味了。
于是他想出了一个新的定义：如果一个数的4倍恰好是它的逆序数，那么称这两个数是新定义下的逆序对。
接下来给定一正整数$n$，问：不超过n的正整数中有多少对新定义下的逆序对？

输入描述

单组输入。
输入一个正整数$n$，$n < 1e^7$。

输出描述

第一行输出在不超过$n$的前提下有多少对逆序数，接下来每一行输出一对逆序数，以空格分隔。如果有多组逆序数，按照第一个数升序输出。
如果没有一对逆序数则直接输出0即可。

示例1

样例输入

10000

样例输出

1
2178 8712

提示

在本题目的情景中我们认为：1234的逆序数为4321，1100的逆序数为11

限制

时间：1000MS
内存：65536KB

算法

(枚举) $O(k \times n)$

1. 按照题目要求枚举一遍就行了
2. 逆序数也不能超过$n$

时间复杂度

只会遍历$n$次，每次会求长度为$O(k)$的数的逆序数，时间复杂度为$O(k \times n)$

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

typedef pair<int, int> PII;

int n, ret;
vector<PII> out;

int get(int u) {
    int ret = 0;
    while (u) ret = ret * 10 + u % 10, u /= 10;
    return ret;
}

int main() {

    cin >> n;

    for (int i = 1; i <= n; i ++ ) {
        int t = get(i);
        if (t <= n && t == i * 4) {
            out.push_back({i, t});
            ret ++ ;
        }
    }

    cout << ret << endl;
    for (auto x: out) cout << x.first << ' ' << x.second << endl;

    return 0;
}

T2[小团的旅行线路]

题目描述

小团是一个旅游爱好者，快要过春节了，他想统计一下，在过去的一年中他进行过几次旅行，于是他打开了美团$App$的订单记录，记录显示了他的购买车票的记录。记录是按时间顺序给出的，已知一次旅行的线路一定是一个闭环，即起点和终点是同一个地点。因此当每找到一段闭合的行程，即认为完成了一次旅行。数据保证不会出现不在闭环路径中的数据。
请你在小团的购票记录中统计出他全年共进行了多少次旅行？

输入描述

输入第一行包含一个正整数n，表示小团的购票记录数量。（$1 \leq n \leq 10000$）
接下来有$n$行，每行是两个长度不超过10的仅由小写字母组成的字符串$S_a$和$S_b$，表示购买了一张从$S_a$到$S_b$的车票。

输出描述

输出仅包含一个整数，表示小团的旅行次数。

示例1

样例输入

6
beijing nanjing
nanjing guangzhou
guangzhou shanghai
shanghai beijing
fuzhou beijing
beijing fuzhou

样例输出

2

限制

时间：1000MS
内存：65536KB

算法

() $O()$

54%

时间复杂度

C++ 代码

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

int n, ret;
string a, b;
stack<string> stk;

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ ) {
        cin >> a >> b;
        if (stk.empty()) {
            stk.push(a), stk.push(b);
        } else {
            if (stk.top() == a) {
                stk.pop();
                if (stk.top() == b) stk.pop(), ret ++ ;
                else stk.push(b);
            }
        }
    }

    cout << ret;

    return 0;
}

T3[小团的配送团队]

题目描述

小团是美团外卖的区域配送负责人，众所周知，外卖小哥一般都会同时配送若干单，小团在接单时希望把同一个小区的单子放在一起，然后由一名骑手统一配送。但是由于订单是叠在一起的，所以，他归类订单时只能知道新订单和已有的某个订单的小区是相同的，他觉得这样太麻烦了，所以希望你帮他写一个程序解决这个问题。
即给出若干个形如$a b$的关系，表示$a$号订单和$b$号订单是同一个小区的，请你把同一个小区的订单按照编号顺序排序，并分行输出，优先输出最小的订单号较小的小区订单集合。订单的编号是$1$到$n$。（可能存在同时出现$a b$和$b a$这样的关系，也有可能出现$a a$这样的关系）

输入描述

输入第一行是两个正整数$n$、$m$，表示接受的订单数量和已知的关系数量。（$1 \leq n, m \leq 10000$）
接下来有$m$行，每行两个正整数$a$和$b$，表示$a$号订单和$b$号订单属于同一个小区（$1 \leq a, b \leq n$）

输出描述

输出第一行包含一个整数x，表示这些订单共来自x个不同的小区。
接下来的输出包含x行，每行表示输出若干个订单编号，表示这些订单属于同一个小区，按照订单编号升序输出。优先输出最小的订单编号较小的小区。

示例1

样例输入

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

样例输出

1
1 2 3 4 5

限制

时间：1000MS
内存：65536KB

算法

(并查集) $O(n)$

1. 合并操作时，序号大的指向序号小的
2. 另开一个数组存不同集合的元素

时间复杂度

带路径压缩的并查集合并操作几乎是$O(1)$的，求每个集合的时间复杂度为$O(n)$

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 10010;

int n, m, ret;
int p[N];
vector<int> g[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m;

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

    for (int i = 0; i < m; i ++ ) {
        int a, b; cin >> a >> b;
        if (a != b) {
            int pa = find(a), pb = find(b);
            if (pa < pb) p[pb] = pa;
            else p[pa] = pb;
        }
    }

    for (int i = 1; i <= n; i ++ ) {
        if (p[i] == i) ret ++ ;
        int pi = find(i);
        g[pi].push_back(i);
    }

    cout << ret << endl;
    for (int i = 1; i <= n; i ++ )
        if (p[i] == i) {
            for (auto x: g[i])
                cout << x << ' ';
            cout << endl;
        }

    return 0;
}

T4[小团的车辆调度]

题目描述

小团是美团汽车租赁公司的调度师，某个时刻A和B两地都向该公司提交了租车的订单，分别需要$a$和$b$辆汽车。此时，公司的所有车辆都在外运营，通过北斗定位，可以得到所有车辆的位置，小团分别计算了每辆车前往$A$地和$B$地完成订单的利润。作为一名精明的调度师，当然是想让公司的利润最大化了。
请你帮他分别选择$a$辆车完成$A$地的任务，选择$b$辆车完成$B$地的任务。使得公司获利最大，每辆车最多只能完成一地的任务。

输入描述

输入第一行包含三个整数$n$、$a$、$b$，分别表示公司的车辆数量和$A$、$B$两地订单所需数量，保证$a + b \leq n$。（$1 \leq n \leq 2000$）

输出描述

输出仅包含一个正整数，表示公司最大获利的利润和。

示例1

样例输入

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

样例输出

18

限制

时间：2000MS
内存：131072KB

算法

() $O()$

18%

时间复杂度

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 2010;

int n, a, b;
int va[N], vb[N];
int f[N][N];

int main() {

    cin >> n >> a >> b;
    for (int i = 1; i <= n; i ++ ) cin >> va[i] >> vb[i];

    memset(f, -1, sizeof f);

    for (int k = 1; k <= n; k ++ )
        for (int i = 0; i <= k && i <= a; i ++ )
            for (int j = 0; j <= k - i && j <= b; j ++ ) {
                if (i && f[i - 1][j] != -1) f[i][j] = max(f[i][j], f[i - 1][j] + va[k]);
                if (j) f[i][j] = max(f[i][j], f[i][j - 1] + vb[k]);
            }

    cout << f[a][b];

    return 0;
}

Tips

T2 & T4有没有老铁能给出正解的