1. 特殊的逆序对

如果一个数的四倍是它的逆序数，那么这两个数就构成了一个逆序数对。给一个正整数n，求不大于n的正整数构成的逆序数对。

提示：

1
1234的逆序数是4321，1100的逆序数是11

输入：

1
输入正整数n

输出：

1
2
第一行输出共有多少对逆序数
从第二行开始每行输出一对逆序数，按第一个数从小到达开始输出，没有就不输出

示例：

1
2
3
4
5
输入：
10000
输出：
1
2178 8712

*没有考虑到4i可能已经超出了n，最终代码只通过了55%：**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        List<int[]> list = new ArrayList<>();

        for(int i = 1; i <= n; i++){
            int t = i * 4; 
            if(t <= n && judge(i)){   // 丢掉了重要条件
                list.add(new int[]{i, t});
            }
        }

        System.out.println(list.size());
        for(int[] arr : list){
            System.out.println(arr[0] + " " + arr[1]);
        }

    }

    private static boolean judge(int a) {

        String str1 = String.valueOf(a);
        int b = Integer.valueOf(new StringBuilder(str1).reverse().toString());

        return a*4 == b;

    }
}

2. 统计旅行次数

每次旅行会从一个城市出发，经过若干城市后回到出发的城市。现给出若干次旅行所有的城市之间的通行信息，请你找出总共旅行了多少次。其中不会包括无效的旅行信息。

输入：

1
2
第一行输入n，代表通行信息条数
此后每行输入出发城市，到达城市

输出：

1
一共旅行了多少次

示例：

1
2
3
4
5
6
7
8
9
10
输入：
6
beijing chongqing
chongqing hangzhou
hangzhou beijing
beijing xian
xian beijing

输出：
2

看评论才知道，要考虑A-A这种情况（但自己的代码没问题啊），代码只通过了91%：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

import java.util.*;

/**
 * @author shkstart
 * @create 2020-08-15 16:36
 */
public class Two {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = Integer.valueOf(scan.nextLine());

        Map<String, List<String>> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            String[] strs = scan.nextLine().split(" ");
            List<String> list = map.getOrDefault(strs[0], new ArrayList<>());
            list.add(strs[1]);
            map.put(strs[0], list);
        }

        int ct = 0;
        for(String key : map.keySet()){
            List<String> list = map.get(key);
            while(list.size() > 0){
                if(dfs(key, key, map)){
                    ct++;
                }
            }
        }

        System.out.println(ct);

    }

    private static boolean dfs(String start, String key, Map<String, List<String>> map) {

        List<String> list = map.get(key);

        int i = 0;
        boolean res = false;

        for(i = 0; i < list.size(); i++){
            String next = list.get(i);
            if(next.equals(start)){
                res = true;
            }
            else{
                res = dfs(start, next, map);
            }
            if(res){
                break;
            }
        }

        if(res){
            list.remove(i);
        }

        return res;

    }
}

补充：

真无语，难道真的是自己审题有问题吗，看到有人居然一遍遍历就过了，把题想难了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int count;
    cin>>count;
    vector<pair<string,string>>res;
    string str1,str2;
    for(int i = 0;i < count;i++){
        cin>>str1>>str2;
        res.push_back({str1,str2});
    }
    int len = 1;
    count = res.size();
    for(int i = 0;i < count - 1;i++){
        if(res[i].second != res[i + 1].first)len++;
    }
    cout<<len<<endl;
    return 0;
}

3. 小区人员划分

有n个人编号1-n，给出关系<a, b>代表a和b同属一个小区。请你根据给出的关系，对人员进行划分。

输入：

1
2
第一行输入n，m分别代表人员数，和关系数
第二行开始每行输入关系a b , 共输入m行

输出：

1
2
3
第一行输出n个人共有几个小区
此后每行，输出每个小区的人员，编号递增
小区顺序：编号最小的人员的编号越小，越优先输出

示例：

1

通过并查集思想，不难解决，此次笔试唯一AC的题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.*;

/**
 * @author shkstart
 * @create 2020-08-15 17:24
 */
public class Three {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[] mark = new int[n+1];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i = 1; i <= n ;i++){
            mark[i] = i;
            List<Integer> list = new ArrayList<>();
            list.add(i);
            map.put(i, list);
        }

        for(int i = 1; i <= n; i++){
            int a = scan.nextInt(), b = scan.nextInt();
            int c_a = mark[a], c_b = mark[b];
            if(c_a == c_b){
                continue;
            }
            List<Integer> listA= map.get(c_a);
            List<Integer> listB = map.get(c_b);
            for(int t : listB){
                mark[t] = c_a;
                listA.add(t);
            }
            map.remove(c_b);
        }

        System.out.println(map.size());
        Set<Integer> set = new HashSet<>();
        for(int i = 1; i <= n; i++){
            int c = mark[i];
            if(set.contains(c)){
                continue;
            }
            List<Integer> list = map.get(c);
            Collections.sort(list);
            for(int num : list){
                System.out.print(num + " ");
            }
            System.out.println();
            set.add(c);
        }
    }
}

4. 运输的最高收益

运输公司有n辆车，位于不同位置。现有两个地方都要用车，每辆车由于位置不同到两地的运输收益也不同。连个地方分别要a辆车，b辆车。请你计算出运输的最大收益。

输入：

1
2
3
第一行：n, a, b
第二行：a1 a2 ... an  每辆车到第一个地方的收益
第二行：b1 b2 ... bn  每辆车到第二个地方的收益

输出：

1
最大收益

示例：

1
2
3
4
5
6
输入：
5 2 2
4 3 5 5 1
2 3 4 3 5
输出：
18

这道题应该是道动态规划的题，和背包也挺像的，暂时没思路：

1