Codeforces Round #516 (Div. 2, by Moscow Team Olympiad)

原题地址

#	题目	分数	是否AC
A	Make a triangle!	800	✅
B	Equations of Mathematical Magic	1200	✅
C	Oh Those Palindromes	1300	✅
D	Labyrinth	1800	✅
E	Dwarves, Hats and Extrasensory Abilities	1900	❌
F	Candies for Children	2600	❌

A. Make a triangle!

题目类型   数学

题意

   有三个长度分别为 a 、 b 、 c a、b、c a、b、c 的木棍，在 1 1 1 分钟内你一可以讲任意一根木棍的长度增加 1 1 1。现在问至少需要花费几分钟才能将这三根木棍首尾相接拼成一个三角形。

分析

  要能拼成三角形一定要满足任意两边之和大于第三边。那么只有较短的两边之和大于最长的边即可。如果不满足则花费为 最 长 边 − 其 余 两 条 边 的 和 + 1 最长边 - 其余两条边的和 + 1 最长边−其余两条边的和+1。

时间复杂度

   O ( 1 ) O(1) O(1)

代码

    public static void solve() throws IOException {
        int[] a = new int[3];
 
        for (int i = 0; i < 3; i++) a[i] = nextInt();
 
        Arrays.sort(a);
 
        if (a[0] + a[1] > a[2]) pw.println(0);
        else pw.println(a[2] - (a[0] + a[1]) + 1);
    }

B. Equations of Mathematical Magic

题目类型   数学 排列组合

题意

   给定 a a a，求 a − ( a ⊕ x ) − x = 0 a − ( a ⊕ x ) − x = 0 a−(a⊕x)−x=0 非负整数解的个数。

分析

   将式子移项得： a ⊕ x = a − x a ⊕ x = a - x a⊕x=a−x，再观察一下式子

   1 ⊕ 1 = 0 1 ⊕ 1 = 0 1⊕1=0     1 − 1 = 0 1 - 1 = 0 1−1=0
   1 ⊕ 0 = 1 1 ⊕ 0 = 1 1⊕0=1     1 − 0 = 1 1 - 0 = 1 1−0=1
   0 ⊕ 0 = 0 0 ⊕ 0 = 0 0⊕0=0     0 − 0 = 0 0 - 0 = 0 0−0=0
   0 ⊕ 1 = 1 0 ⊕ 1 = 1 0⊕1=1     0 − 1 = − 1 0 - 1 = -1 0−1=−1

  可以发现当 a a a 取 1 1 1 时 x x x 取 1 1 1 和 0 0 0 都是可以的，但是当 a a a 取 0 0 0 时 x x x 只能取 0 0 0。所以统计 a a a 二进制中 1 1 1 的个数，根据乘法原理求出结果。

时间复杂度

   O ( log ⁡ n ) O(\log n) O(logn)

代码

public static void solve() throws IOException {
    long n = nextLong();

    long ans = 1;
    while (n > 0) {
        if ((n & 1) == 1) ans <<= 1;
        n >>= 1;
    }

    pw.println(ans);
}

C. Oh Those Palindromes

题目类型   字符串 思维

题意

  输入一个字符串，然后重排这个字符串使其含有的回文子串的个数最多（如果有多种解输出任意一个）。

分析

   将相同的字符放在一起即可（可以直接排序）

时间复杂度

   O ( n log ⁡ n ) O(n\log n) O(nlogn)

代码

    public static void solve() throws IOException {
        int n = nextInt();

        char[] s = next().toCharArray();

        Arrays.sort(s);

        pw.println(s);
    }

D. Labyrinth

题目类型   搜索

题意

   在一个 n × m n \times m n×m 大小的迷宫中 . . . 代表空地 ∗ * ∗ 代表障碍。在不越过边界和触碰障碍的情况下你可以向上下左右任意方向行走，但是向左和向右移动的次数是有限制的。给定起点，求地图中最多有多少个点是可以到达的。

分析

   可以想到用 BFS 来解决这个问题，但是因为向左和向右移动的次数是有限制的，那么想要到达更多的点就优先向上下走，所以使用双端队列或优先队列来改变搜索的优先级，优先上下然后再左右。

时间复杂度

   O ( n × m ) O(n \times m) O(n×m)

代码

    public static void solve() throws IOException {
        int n = nextInt();
        int m = nextInt();
        int r = nextInt() - 1;
        int l = nextInt() - 1;
        int x = nextInt();
        int y = nextInt();
 
        char[][] G = new char[n][m];
        for (int i = 0; i < n; i++) G[i] = next().toCharArray();
 
        int ans = bfs(G, n, m, r, l, x, y);
 
        pw.println(ans);
    }
 
    public static int bfs(char[][] G, int n, int m, int r, int l, int x, int y) {
        boolean[][] vis = new boolean[n][m];
 
        Deque<Node> q = new ArrayDeque<>();
        q.addLast(new Node(r, l, x, y));
        vis[r][l] = true;
 
        while (!q.isEmpty()) {
            Node e = q.pollFirst();
 
            int nx, ny;
 
            nx = e.xx - 1;
            ny = e.yy;
            if (nx >= 0 && !vis[nx][ny] && G[nx][ny] == '.') {
                vis[nx][ny] = true;
                q.addFirst(new Node(nx, ny, e.x, e.y));
            }
 
            nx = e.xx + 1;
            ny = e.yy;
            if (nx < n && !vis[nx][ny] && G[nx][ny] == '.') {
                vis[nx][ny] = true;
                q.addFirst(new Node(nx, ny, e.x, e.y));
            }
 
            nx = e.xx;
            ny = e.yy - 1;
            if (ny >= 0 && !vis[nx][ny] && e.x > 0 && G[nx][ny] == '.') {
                vis[nx][ny] = true;
                q.addLast(new Node(nx, ny, e.x - 1, e.y));
            }
 
            nx = e.xx;
            ny = e.yy + 1;
            if (ny < m && !vis[nx][ny] && e.y > 0 && G[nx][ny] == '.') {
                vis[nx][ny] = true;
                q.addLast(new Node(nx, ny, e.x, e.y - 1));
            }
        }
 
        int re = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (vis[i][j]) re++;
 
        return re;
    }
 
 
    /*******************************************************************************************************************************/
 
    static class Node {
        int xx, yy, x, y;
 
        public Node(int xx, int yy, int x, int y) {
            this.xx = xx;
            this.yy = yy;
            this.x = x;
            this.y = y;
        }
    }