书脊 | 倾城与倾国, 佳人难再得

Educational Codeforces Round 3 C – Load Balancing

链接: https://codeforces.com/contest/609/problem/C

public class TaskC {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int[] ary = in.readIntArray(n);
        long res = 0;
        Arrays.sort(ary);
        int sum = 0;
        for (int i:ary) {
            sum+=i;
        }
        for (int i = 0; i &lt; n/2; i++) {
            int b = sum / (n - i);
            res += Math.abs(ary[i] - b);
            sum -= b;
        }
        out.print(res);
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

public class TaskC {

public void solve(int testNumber, InputReader in, OutputWriter out) {

int n = in.readInt();

int[] ary = in.readIntArray(n);

long res = 0;

Arrays.sort(ary);

int sum = 0;

for (int i:ary) {

sum+=i;

}

for (int i = 0; i < n/2; i++) {

int b = sum / (n - i);

res += Math.abs(ary[i] - b);

sum -= b;

}

out.print(res);

}

公式推导题, 先要排序ary, 然后算出数组的和sum. 然后可以观察到, 我们可以把相对大的数给相对小的数以便于达到平衡, 这种平衡有两个可能性, 一种是两数合为奇数, 比如数组 1 2 4, 4+1=5, 5是奇数, 这种情况下给完后的差是1, 即2 2 3, 3-2=1. 另外一种情况是两数合为偶数, 比如 1 2 3, 3+1=4, 4是偶数. 这种情况下给完后的差是0, 即2 2 2, 2-2=0. 所以可以证明这种先排序后两端互相给的方法, 是答案要的方法, 即miimize(Ma – Mb), where a is the most loaded server and b is the least loaded one.

最后我们需要找到平衡数组b, 通过观察我们知道, 我们只需要遍历一半的数组就可以得到答案, 因为我们是通过”给数”的方法, 所以我们用一个循环遍历一半的数组. 通过再次观察不难发现, 比如数组 1 2 3 4 的平衡数组是2 2 3 3 (4给1 1次). 这个平衡数组的sum是1+2+3+4 = 10. 如果我们把10均分, 那么久变成10/4 = 2, 10 mod 4 = 2, 这里的意思是平衡数组中绝大部分是10/4 = 2, 其中有10 mod 4个数比其他数多1. 再举例, 1 2 3 4 5, sum = 15. 15/5 = 3, 15 mod 5 = 0 (整除). 这里说明它的平衡数组是 3 3 3 3 3, 有0个(没有)数比其他数多1. 现在我们验证一下, 5给1 两次, 数组变成 3 2 3 4 3, 4 给2 一次变成3 3 3 3 3. 结束

上面的code并不是这个答案的code. 上面的code用了一个更好的数学方法. 通过上面的观察可以看出, ary的数字a是由两部分组成, 一个数组的均值(sum/n)+多的1(如果有). 这个题问的是第二部分数字的合, 我们现在已知前边两个部分那么只需要用数字ary[i] – 当前数组的均值sum/n, 即Math.abs(ary[i] – b), 然后不要忘了计算下一个数字均值的时候, 应该减去当前的均值.

Date March 18, 2019
Author Readman
Comments No Comments

Educational Codeforces Round 3 B. The Best Gift

链接: https://codeforces.com/contest/609/problem/B

public class TaskB {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int m = in.readInt();
        int[] ary = in.readIntArray(n);
        int[] count = new int[m];
        long res = 0;
        for (int i = 0; i &lt; ary.length; i++) {
            count[ary[i]-1]++;
        }
        for (int i = 0; i &lt; m; i++) {
            for (int j = i+1; j &lt; m; j++) {
                res += count[i]*count[j];
            }
        }
        out.print(res);
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

public class TaskB {

public void solve(int testNumber, InputReader in, OutputWriter out) {

int n = in.readInt();

int m = in.readInt();

int[] ary = in.readIntArray(n);

int[] count = new int[m];

long res = 0;

for (int i = 0; i < ary.length; i++) {

count[ary[i]-1]++;

}

for (int i = 0; i < m; i++) {

for (int j = i+1; j < m; j++) {

res += count[i]*count[j];

}

out.print(res);

}

就是普通的排序问题, 从m个不同类的物品中, 抽取(不重复)2个不同的物品. 物品没有先后顺序.

第一个循环计算每种物品的个数, 第二个循环外边遍历每种物品, 里面遍历当前物品外的物品, 中间因为物品没有顺序所以是乘法

Date March 14, 2019
Author Readman
Comments No Comments

Educational Codeforces Round 3 A – USB Flash Drives

链接: https://codeforces.com/contest/609/problem/A

public class TaskA {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int m = in.readInt();
        int res = 0;
        int[] ary = in.readIntArray(n);
        Arrays.sort(ary);
        for(int i = ary.length - 1; i>=0; i--) {
            if (m > 0 &amp;&amp; ary[i] &lt;= m){
                m -= ary[i];
                res++;
            }
            else if (m > 0 &amp;&amp; ary[i] > m) {
                m -= ary[i];
                res++;
            }
        }
        out.print(res);
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

public class TaskA {

public void solve(int testNumber, InputReader in, OutputWriter out) {

int n = in.readInt();

int m = in.readInt();

int res = 0;

int[] ary = in.readIntArray(n);

Arrays.sort(ary);

for(int i = ary.length - 1; i>=0; i--) {

if (m > 0 && ary[i] <= m){

m -= ary[i];

res++;

}

else if (m > 0 && ary[i] > m) {

m -= ary[i];

res++;

}

out.print(res);

}

先排序一下, 然后从大往小用贪婪思想选数, 注意选的时候的两个情况有先后, 第二种情况出现是选最后一个数的时候.

Date March 14, 2019
Author Readman
Comments No Comments

Educational Codeforces Round 2 E – Lomsat gelral

链接:https://codeforces.com/contest/600/problem/E

public class TaskE {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int[] res = new int[n];
        int[] colorAry = in.readIntArray(n);
        //the number of occurences for each colour for each vertexs
        Map&lt;Integer, Integer>[] colorsMap = new Map[n];
        //total count of sums for each vertexs(result)
        long[] totalColorSums = new long[n];
        // total count for each color
        int[] totalColorCounts = new int[n];
        //read graph
        ArrayList&lt;Integer>[] g = new ArrayList[n];
        for(int i = 0 ; i &lt; n ; i++) {
            g[i] = new ArrayList&lt;>();
        }
        for(int i = 0 ; i &lt; n - 1; i++){
            int a = in.readInt()-1;
            int b=  in.readInt()-1;
            g[a].add(b);
            g[b].add(a);
        }
        dfs(0, -1, colorAry, g, colorsMap,totalColorSums, totalColorCounts);
        out.printLine(totalColorSums);
    }

    private void dfs(int current, int parentNode, int[] colorAry,  ArrayList&lt;Integer>[] g,Map&lt;Integer, Integer>[] colorsMap,  long[] totalColorSums,  int[] totalColorCounts) {
        int currentColor = colorAry[current];
        Map&lt;Integer, Integer> currentNodeColorCount = new HashMap&lt;>();
        currentNodeColorCount.put(currentColor, 1);
        int count = 1;
        long sum = currentColor;
        for (int next : g[current]) {
            if (next == parentNode ) {
                continue;
            }
            //dfs to all connected nodes
            dfs(next, current, colorAry, g, colorsMap, totalColorSums, totalColorCounts);
            Map&lt;Integer, Integer> connectedNodeColorCount = colorsMap[next];
            if (connectedNodeColorCount.size() > currentNodeColorCount.size()) {// merge small to large
                connectedNodeColorCount = currentNodeColorCount;
                currentNodeColorCount = colorsMap[next];// move to next
                count = totalColorCounts[next];
                sum = totalColorSums[next];
            }

            for (Map.Entry&lt;Integer, Integer> connectedNode : connectedNodeColorCount.entrySet()) { //merge color and counts
                int connectedNodeColor = connectedNode.getKey();
                int connectedNodeCount = connectedNode.getValue();
                currentNodeColorCount.put(connectedNodeColor,  currentNodeColorCount.getOrDefault(connectedNodeColor, 0) +connectedNodeCount); // update current node's color count
                if (count &lt; currentNodeColorCount.get(connectedNodeColor)) { // if total color is less than the current color count, in other words, we found larger count of some color.
                    count = currentNodeColorCount.get(connectedNodeColor);// then we need to update the current max color and count.
                    sum = connectedNodeColor;
                }
               else if (count == currentNodeColorCount.get(connectedNodeColor)){// if the total color is same to current color count, in other words,  two color has same color count and the count is the largest count.
                    sum += connectedNodeColor;// we need to add two color together.
                }
            }
        }

        colorsMap[current] = currentNodeColorCount;
        totalColorCounts[current] = count;
        totalColorSums[current] = sum;
    }
}

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

65

public class TaskE {

public void solve(int testNumber, InputReader in, OutputWriter out) {

int n = in.readInt();

int[] res = new int[n];

int[] colorAry = in.readIntArray(n);

//the number of occurences for each colour for each vertexs

Map<Integer, Integer>[] colorsMap = new Map[n];

//total count of sums for each vertexs(result)

long[] totalColorSums = new long[n];

// total count for each color

int[] totalColorCounts = new int[n];

//read graph

ArrayList<Integer>[] g = new ArrayList[n];

for(int i = 0 ; i < n ; i++) {

g[i] = new ArrayList<>();

}

for(int i = 0 ; i < n - 1; i++){

int a = in.readInt()-1;

int b= in.readInt()-1;

g[a].add(b);

g[b].add(a);

}

dfs(0, -1, colorAry, g, colorsMap,totalColorSums, totalColorCounts);

out.printLine(totalColorSums);

}

private void dfs(int current, int parentNode, int[] colorAry, ArrayList<Integer>[] g,Map<Integer, Integer>[] colorsMap, long[] totalColorSums, int[] totalColorCounts) {

int currentColor = colorAry[current];

Map<Integer, Integer> currentNodeColorCount = new HashMap<>();

currentNodeColorCount.put(currentColor, 1);

int count = 1;

long sum = currentColor;

for (int next : g[current]) {

if (next == parentNode ) {

continue;

}

//dfs to all connected nodes

dfs(next, current, colorAry, g, colorsMap, totalColorSums, totalColorCounts);

Map<Integer, Integer> connectedNodeColorCount = colorsMap[next];

if (connectedNodeColorCount.size() > currentNodeColorCount.size()) {// merge small to large

connectedNodeColorCount = currentNodeColorCount;

currentNodeColorCount = colorsMap[next];// move to next

count = totalColorCounts[next];

sum = totalColorSums[next];

}

for (Map.Entry<Integer, Integer> connectedNode : connectedNodeColorCount.entrySet()) { //merge color and counts

int connectedNodeColor = connectedNode.getKey();

int connectedNodeCount = connectedNode.getValue();

currentNodeColorCount.put(connectedNodeColor, currentNodeColorCount.getOrDefault(connectedNodeColor, 0) +connectedNodeCount); // update current node's color count

if (count < currentNodeColorCount.get(connectedNodeColor)) { // if total color is less than the current color count, in other words, we found larger count of some color.

count = currentNodeColorCount.get(connectedNodeColor);// then we need to update the current max color and count.

sum = connectedNodeColor;

}

else if (count == currentNodeColorCount.get(connectedNodeColor)){// if the total color is same to current color count, in other words, two color has same color count and the count is the largest count.

sum += connectedNodeColor;// we need to add two color together.

}

colorsMap[current] = currentNodeColorCount;

totalColorCounts[current] = count;

totalColorSums[current] = sum;

}

上面code的idea不是我自己想的, 是我看了答案后, 找到另一个人的解法, 然后优化出来的. 答案里写的方法有点太难了, 我看了另一个文章还有用dsu(union-find) in tree优化的. 题目边上的Problem tags里也有dsu. dsu在这里优化主要是用来减少dfs中合并子树中color count, 但是我感觉其实并不需要这样做:

首先, 用dsu就需要标记leaf和root, 然而我们的本意只是想找到leaf的color count, 然后合并, 所以其实只要记录并比较当前dfs节点上的count大小和我们记录下的与其相邻的节点大小, 就可以知道谁是leaf, 谁是root (dfs原理). 这样在dfs经过leaf的时候, 我们只需要记录当前的count就可以, 在dfs经过root的时候, 我们通过parent 这个变量, 就知道上次调用的节点数据.

其次, dsu合并的均摊是logn, 但是使用dsu需要维护另一个数组, 并且构图的时候也要多构造一个dsu. 而这里我们使用两个变量, sum和count, sum记录当前node下属所有节点的有最大count的color的合, count记录当前node下属所有节点的有最大count. 这里我们把这两个关键数据放在dfs的外侧, 作为闭包内的变量, 然后用totalColorCounts和totalColorSums记录全局数据. 这样我们在每次访问节点的时候, 就可以通过更新sum和count计算出当前节点的答案, 记录在
totalColorCounts和totalColorSums里.

这个题我觉得最难的是找到更新和维护connectedNodeColorCount和currentNodeColorCount, 一个是子节点的color和count数据, 另一个是这个子节点的父节点的color和count数据. 这两组数据决定了最后的total color和total sum. 另外, 语句connectedNodeColorCount.size() > currentNodeColorCount.size(), 确保了在当前节点为子节点的情况下, 需要交换connectedNodeColorCount和currentNodeColorCount, 这样就和dsu一样,确保了merge是从小的map到大的map.

Date March 13, 2019
Author Readman
Comments No Comments

Educational Codeforces Round 2 D – Area of Two Circles’ Intersection

链接: http://codeforces.com/contest/600/problem/D

public class TaskD {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        double x1 = in.readDouble();
        double y1 = in.readDouble();
        double r1 = in.readDouble();
        double x2 = in.readDouble();
        double y2 = in.readDouble();
        double r2 = in.readDouble();
        MathContext mc = new MathContext(40, RoundingMode.HALF_UP);
        //两圆,圆心距
        BigDecimal c = BigDecimal.valueOf(Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2)));
        if (r1 + r2 &lt;= c.doubleValue()) {
            out.printFormat("%.20f\n", (double) 0.0);
            return;
        } //如果两圆不相交
        else if (Math.abs(r2 - r1) >= c.doubleValue()) {
            out.printFormat("%.20f\n", Math.PI * Math.pow(Math.min(r1, r2), 2)); // 面积是内圆的面积
            return;
        } else {
            //1的圆心角
            double r1_ang = Math.acos(BigDecimal.valueOf(r1).pow(2,mc).add(c.pow(2,mc)).subtract(BigDecimal.valueOf(r2).pow(2),mc).divide(BigDecimal.valueOf(2), 20, RoundingMode.CEILING).divide(BigDecimal.valueOf(r1),20, RoundingMode.CEILING).divide(c,20, RoundingMode.CEILING).doubleValue());
            //2的圆心角
            double r2_ang = Math.acos(BigDecimal.valueOf(r2).pow(2,mc).add(c.pow(2,mc)).subtract(BigDecimal.valueOf(r1).pow(2),mc).divide(BigDecimal.valueOf(2), 20, RoundingMode.CEILING).divide(BigDecimal.valueOf(r2),20, RoundingMode.CEILING).divide(c,20, RoundingMode.CEILING).doubleValue());
            //1的面积
            double a1 = r1_ang * Math.pow(r1, 2) - 0.5 * Math.pow(r1, 2) * Math.sin(r1_ang * 2);
            //2的面积
            double a2 = r2_ang * Math.pow(r2, 2) - 0.5 * Math.pow(r2, 2) * Math.sin(r2_ang * 2);
            out.printFormat("%.20f\n", (a1 + a2));
        }
    }
}

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

public class TaskD {

public void solve(int testNumber, InputReader in, OutputWriter out) {

double x1 = in.readDouble();

double y1 = in.readDouble();

double r1 = in.readDouble();

double x2 = in.readDouble();

double y2 = in.readDouble();

double r2 = in.readDouble();

MathContext mc = new MathContext(40, RoundingMode.HALF_UP);

//两圆,圆心距

BigDecimal c = BigDecimal.valueOf(Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2)));

if (r1 + r2 <= c.doubleValue()) {

out.printFormat("%.20f\n", (double) 0.0);

return;

} //如果两圆不相交

else if (Math.abs(r2 - r1) >= c.doubleValue()) {

out.printFormat("%.20f\n", Math.PI * Math.pow(Math.min(r1, r2), 2)); // 面积是内圆的面积

return;

} else {

//1的圆心角

double r1_ang = Math.acos(BigDecimal.valueOf(r1).pow(2,mc).add(c.pow(2,mc)).subtract(BigDecimal.valueOf(r2).pow(2),mc).divide(BigDecimal.valueOf(2), 20, RoundingMode.CEILING).divide(BigDecimal.valueOf(r1),20, RoundingMode.CEILING).divide(c,20, RoundingMode.CEILING).doubleValue());

//2的圆心角

double r2_ang = Math.acos(BigDecimal.valueOf(r2).pow(2,mc).add(c.pow(2,mc)).subtract(BigDecimal.valueOf(r1).pow(2),mc).divide(BigDecimal.valueOf(2), 20, RoundingMode.CEILING).divide(BigDecimal.valueOf(r2),20, RoundingMode.CEILING).divide(c,20, RoundingMode.CEILING).doubleValue());

//1的面积

double a1 = r1_ang * Math.pow(r1, 2) - 0.5 * Math.pow(r1, 2) * Math.sin(r1_ang * 2);

//2的面积

double a2 = r2_ang * Math.pow(r2, 2) - 0.5 * Math.pow(r2, 2) * Math.sin(r2_ang * 2);

out.printFormat("%.20f\n", (a1 + a2));

}

这题不难,就是个公式, 但是Java的double不够精度, 需要用BigDecimal. 然而Java三角函数acos最多支持double, 不支持BigDecimal. 所以难点是要自己写acos(我是肯定不会写展开式的啊)…所以上面code是最高精度.

Btw, 我搜了所有code, 基本都是c++…..c++的long double还是好用啊

Date March 5, 2019
Author Readman
Comments No Comments

Educational Codeforces Round 2 C. Make Palindrome

链接: http://codeforces.com/contest/600/problem/C

public void solve(int testNumber, InputReader in, OutputWriter out) {
        String s = in.readString();
        int[] count = new int[26];
        /**
         * counting the  occurences
         */
        for(int i = 0; i &lt; s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }

        int i = 0;
        int j  = 25;
        while (i &lt;= j) {
            while (i &lt; count.length &amp;&amp; count[i] % 2 == 0) { // find the left side first odd
                i ++;
            }
            while (j >=0 &amp;&amp; count[j] % 2 == 0) { // find the right side first odd
                j --;
            }
            // move right to first (because it is asked for the lexicographically (alphabetically) smallest palindrome)
            if (i &lt; count.length) {
                count[i++] ++;
            }
            if (j >=0) {
                count[j--]--;
            }
        }
        StringBuilder sb = new StringBuilder();
        int odd_Index = -1;
        for (int k = count.length - 1; k >=0 ; k--) {
            if (count[k] % 2 != 0) { // we know there is no more than 1 odd number in our count array
                odd_Index = k;
                count[k] --;
            }
            for (int l = 0; l &lt; count[k]; l++) {
                if (l % 2 == 0) {
                    sb.append((char)('a' + k));
                }
                else {
                    sb.insert(0,(char)('a' + k));
                }
            }
        }
        if (odd_Index != -1) {
            sb.insert(sb.length()/2, (char)('a' + odd_Index)); // put the only odd number (if it has) in the middle
        }
        out.print(sb.toString());
    }

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

public void solve(int testNumber, InputReader in, OutputWriter out) {

String s = in.readString();

int[] count = new int[26];

/**

* counting the occurences

*/

for(int i = 0; i < s.length(); i++) {

count[s.charAt(i) - 'a']++;

}

int i = 0;

int j = 25;

while (i <= j) {

while (i < count.length && count[i] % 2 == 0) { // find the left side first odd

i ++;

}

while (j >=0 && count[j] % 2 == 0) { // find the right side first odd

j --;

}

// move right to first (because it is asked for the lexicographically (alphabetically) smallest palindrome)

if (i < count.length) {

count[i++] ++;

}

if (j >=0) {

count[j--]--;

}

StringBuilder sb = new StringBuilder();

int odd_Index = -1;

for (int k = count.length - 1; k >=0 ; k--) {

if (count[k] % 2 != 0) { // we know there is no more than 1 odd number in our count array

odd_Index = k;

count[k] --;

}

for (int l = 0; l < count[k]; l++) {

if (l % 2 == 0) {

sb.append((char)('a' + k));

}

else {

sb.insert(0,(char)('a' + k));

}

if (odd_Index != -1) {

sb.insert(sb.length()/2, (char)('a' + odd_Index)); // put the only odd number (if it has) in the middle

}

out.print(sb.toString());

}

这题开始做的时候, 还是很费脑的, 首先要关注题中要求的回文问题, 不难看出是需要计算字符串中字频的奇偶,

然后可以想到, 回文只能有不能超过一种奇数的字符. 但是后边很难想的是, 如何修改才能满足 lexicographically (alphabetically) smallest palindrome(字典序下最小回文). 这时可以看到题中给出的回文都是lower case, 所以用双指针的方法, 前后两个指针扫描字频数组, 找到奇数字频的回文, 然后把字典序大的回文给字典序小的回文.

最后一个考点是重构回文, 这里需要注意的是, 我们上一步中已经通过交换的方式消灭了奇数字频的回文, 但是真的完全消灭了么? 其实不然, 回文是可以有一个奇数的字频的字符存在的, 这个字频的字符应该放在中间. 所以我们这里用odd_index, 起始值为-1(表示没有奇数字频), 如果上一步后odd_index不是-1, 这表示我们发现一个字频

这里有两个小技巧:

第一, 当重构回文的时候, 因为题中要求 If there are several ways to do that you should get the lexicographically (alphabetically) smallest palindrome. 我们需要从大的字符往小的字符扫描count数组重构回文, 因为我们想把大的字符放在中间, 把小的字符放到两边, 这种构建方法确保了构建后的回文是字典序最小的回文. 我们可以用反证法证明这个理论,即, 如果存在一种构建方法,使得构建的回文字典序小于上面的构建方法构建的回文, 那么这种方法构建的回文中的字符在字典序下, 肯定有一位小于上面的方法构建的回文, 字典序是要求字符串从左到右的字符从小到大排列, 而回文是从中间左右对称的, 所以如果存在另一个构建方法, 那么这种构建方法构建的回文左边一定比右边要小, 然而这就是我们上述中的构建方法. 所以并不存在另一个构建方法.

第二, 奇数字频字符的选择. 在出现多个奇数字频字符时, 比如aaabbbccc时, 这里有3a,3b,3c. 那么结果是什么. 正确答案是aabcbcbaa, 数一下, 这里有4a,3b,2c, 我们可以看到我们选择保留中间的b作为仅有的奇数字频字符, 这里为什么我们不选择字典序更小的a? 如果选择a, 我们就有 3a,4b,2c, 这里直观的就可以看出, 这个组成的字符串肯定字典序大于给出的算法. 那如果选择c呢? 我们既有4a,2b,3c, 这个看起来不错? 这个组成的是aabcccbaa, 对比一下aabcbcbaa. 我们发现在第5位的时候, 算法给出的是b,而这种方法是c, 所以还是算法的字典序小, 这个也可以用反证法证明. 所以要保留的奇数字频字符只能是中间的字符, 即这里的b.

Date March 1, 2019
Author Readman
Comments No Comments

Educational Codeforces Round 2 B. Queries about less or equal elements

链接: http://codeforces.com/contest/600/problem/B

public class TaskB {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int a = in.readInt();
        int b = in.readInt();
        int[] ary_a = in.readIntArray(a);
        int[] ary_b = in.readIntArray(b);
        shuffle(ary_a);
        Arrays.sort(ary_a);
        for (int i = 0; i &lt; ary_b.length; i++) {
            out.print(count(ary_a, ary_b[i]) + " ");
        }
    }

    /**
     * test20卡中了sort的最慢时间, 需要先shuffle再sort
     * @param a
     */
    private static void shuffle(int[] a) {
        int n = a.length, tmp;
        for (int i = 0; i &lt; n; ++i) {
            int r = i + (int) (Math.random() * (n - i));
            tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }
    private static int count(int[] ary, int n) {
        int start = 0;
        int end = ary.length;
        while (end > start) {
            int mid = start + (end - start) / 2;
            if (n >= ary[mid]) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }

}

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

public class TaskB {

public void solve(int testNumber, InputReader in, OutputWriter out) {

int a = in.readInt();

int b = in.readInt();

int[] ary_a = in.readIntArray(a);

int[] ary_b = in.readIntArray(b);

shuffle(ary_a);

Arrays.sort(ary_a);

for (int i = 0; i < ary_b.length; i++) {

out.print(count(ary_a, ary_b[i]) + " ");

}

/**

* test20卡中了sort的最慢时间, 需要先shuffle再sort

* @param a

*/

private static void shuffle(int[] a) {

int n = a.length, tmp;

for (int i = 0; i < n; ++i) {

int r = i + (int) (Math.random() * (n - i));

tmp = a[i];

a[i] = a[r];

a[r] = tmp;

}

private static int count(int[] ary, int n) {

int start = 0;

int end = ary.length;

while (end > start) {

int mid = start + (end - start) / 2;

if (n >= ary[mid]) {

start = mid + 1;

} else {

end = mid;

}

return start;

}

这题有个test20, 卡了最差时间, 所以只是sort不行, 需要先shuffle一下. 其他就是找upper bound, 如果用c++可以直接调用模板, java没有这个函数, 所以需要写一下. count函数就是c++的upper bound, 区别只是count返回index(个数) 而upper bound返回array的元素

Date February 28, 2019
Author Readman
Comments No Comments

Educational Codeforces Round 2 A. Extract Numbers

链接: http://codeforces.com/contest/600/problem/A

public class TaskA {
    public void solve(int testNumber, Scanner in, PrintWriter out) {
        String word = in.nextLine();
        StringBuffer tmp = new StringBuffer();
        StringBuffer a = new StringBuffer();
        a.append('"');
        StringBuffer b = new StringBuffer();
        b.append('"');
        String[] words = word.split(",", -1);
        for (String w : words) {
            for (String s : w.split(";", -1)) {
                if (isDigit(s) &amp;&amp; (s.charAt(0) != '0' || s.equals("0"))) {
                    a.append(s);
                    a.append(',');
                }
                else {
                    b.append(s);
                    b.append(',');
                }
            }
        }
        if (a.length() == 1) {
            out.println('-');
        }
        else {
            out.println(a.substring(0, a.length()-1)+'"');
        }
        if (b.length() == 1) {
            out.println('-');
        }
        else {
            out.println(b.substring(0, b.length()-1)+'"');
        }
    }

    private boolean isDigit(String s) {
        if (s.isEmpty()) {
            return false;
        }
        for (Character c : s.toCharArray()) {
            if (!Character.isDigit(c)) {
                return false;
            }
        }
        return true;
    }
}

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

public class TaskA {

public void solve(int testNumber, Scanner in, PrintWriter out) {

String word = in.nextLine();

StringBuffer tmp = new StringBuffer();

StringBuffer a = new StringBuffer();

a.append('"');

StringBuffer b = new StringBuffer();

b.append('"');

String[] words = word.split(",", -1);

for (String w : words) {

for (String s : w.split(";", -1)) {

if (isDigit(s) && (s.charAt(0) != '0' || s.equals("0"))) {

a.append(s);

a.append(',');

}

else {

b.append(s);

b.append(',');

}

if (a.length() == 1) {

out.println('-');

}

else {

out.println(a.substring(0, a.length()-1)+'"');

}

if (b.length() == 1) {

out.println('-');

}

else {

out.println(b.substring(0, b.length()-1)+'"');

}

private boolean isDigit(String s) {

if (s.isEmpty()) {

return false;

}

for (Character c : s.toCharArray()) {

if (!Character.isDigit(c)) {

return false;

}

return true;

}

就是普通的字符串处理, 非常烦的是有很多的corner cases. 比如 test 5的 ;;;;;真是变态

Date February 7, 2019
Author Readman
Comments No Comments

新版CHelper插件在Intellij Idea中的使用

我今天安装时, 发现新版的CHelper对目录名称有了强制定义. 比如, 如下设置的chelper.properties

smartTesting=true
archiveDirectory=archive
defaultDirectory=main/readman
extensionProposed=true
outputClass=java.io.PrintWriter
excludePackages=java.,javax.,com.sun.
outputDirectory=output
author=readman
failOnIntegerOverflowForNewTasks=false
inputClass=java.util.Scanner
enableUnitTests=true
testDirectory=lib/test
libraryVersion=2

1

2

3

4

5

6

7

8

9

10

11

12

13

smartTesting=true

archiveDirectory=archive

defaultDirectory=main/readman

extensionProposed=true

outputClass=java.io.PrintWriter

excludePackages=java.,javax.,com.sun.

outputDirectory=output

author=readman

failOnIntegerOverflowForNewTasks=false

inputClass=java.util.Scanner

enableUnitTests=true

testDirectory=lib/test

libraryVersion=2

对应的目录结构必须是:

其中main需要标记为源文件目录, lib/output标记成普通目录. archive被idea自动标记为普通目录

Date January 26, 2019
Author Readman
Comments No Comments

[财经一日谈] 牛市? 熊市?

2018年一整年就不是一个安稳的年. 年初美股就大振, 当时高盛就放出话说美股见顶. 高盛是一个大反指的投资银行, 自然没人理的. 但是它说话又不能不听. 眼见这都10月了, 股票喋喋不休, 都崩到好几轮了, 已经回到年初的水平.

而q3这个季度, 美股中的Amazon和Google全不及花街预期. 眼见又是一轮大跌必不可免. 这一跌怕是又奔着12月去了, 然而12月美联储还有一次加息. 这次加息怕是真的要把美股加崩了. 当然人家美其名曰为了去泡沫.

这边川普执政美国制造业确实有发展, 很多企业美国建厂, 失业率年年刷新史低. 然而失业率低真的是好事么? 日本平成大萧条前夜, 失业率就是0啊, 失业率0是什么概念? 就是大街上每个人都忙的一比. 一个刚毕业的大学生平均能拿到3~5个offer. 薪水与日俱增, 看似国泰民安, 欣欣向荣. 然而等待他们的是近乎20年的大萧条. 直至今日, 日本gdp依旧很低. 我没记错的话…1.x吧…

为什么每个人都努力工作, 社会却不发展, 反而经济危机? 因为社会的生产力取决于新兴科技的发展, 而不是努力工作. 科技创新的爆点, 才能挽救一个国家的制造业. 然而科技的目的就是为了解放双手. 比如一台纺织机器取代几个纺织工人的劳作. 这几个纺织工人如果不很快学会如何操作纺织机, 他们就会被淘汰, 淘汰就是失业. 由此可看失业率在决定国家制造业是否发展中, 是一个很悖论的因素.

然而, 失业率太高,社会就会动荡. 我曾在十年前去过埃及, 那时候的埃及正在革命的前夜. 大街上的青年人无所事事, 没有工作, 这帮人因为自己在学校学的东西过于一致, 没有一技之长而被社会淘汰. 但是高等教育告诉他们, 贩毒/走私等社会不良行为更是不可取之路. 于是他们在自我矛盾中, 慢慢的堕落, 最后成为了革命的中坚力量. 为什么革命? 因为他们不知道还能做什么. 起码有事情做也是好的.

最后, 鉴于我生活在美国, 我个人还是希望股市能在correction后, 不要跌入熊市. 美国的经济萧条可是爆发式的, 不会有漫长的潜伏期. 这个最大的举债国, 已经到了生死存亡的时刻. Good luck America.

Date October 26, 2018
Author Readman
Comments No Comments

Educational Codeforces Round 3 C – Load Balancing

Educational Codeforces Round 3 B. The Best Gift

Educational Codeforces Round 3 A – USB Flash Drives

Educational Codeforces Round 2 E – Lomsat gelral

Educational Codeforces Round 2 D – Area of Two Circles’ Intersection

Educational Codeforces Round 2 C. Make Palindrome

Educational Codeforces Round 2 B. Queries about less or equal elements

Educational Codeforces Round 2 A. Extract Numbers

新版CHelper插件在Intellij Idea中的使用

[财经一日谈] 牛市? 熊市?

书脊

倾城与倾国, 佳人难再得

Categories

Tags

Links

March 2019
M	T	W	T	F	S	S
« Feb
				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