gongel – gongel-coder

Round A 2019 – Kick Start 2019

#include<bits/stdc++.h>

using namespace std;
const int N = 100000, INF = 0x3f3f3f3f;
int T, n, p;
int a[N], sum[N + 1];

/**
 * sum[i] - sum[i - p] = a[i-p+1] + a[i-p+2] +...+ a[i]
 * p * a[i] - (sum[i] - sum[i - p])=(p-1)*a[i] - (a[i-p+1] + a[i-p+2] + ... +  a[i-1])
 * 假设p=3，i=5
 * 那么有3*a[5]- (sum[5] - sum[2])=2 * a[5] - (a[3] + a[4]) = (a[5] - a[3]) + (a[5] - a[4])
 * 即每次计算当前元素和前面p-1个元素的差的和，依次遍历取最小值,利用前缀和来优化
 * */
int main() {
    cin >> T;
    int cnt = 1;
    while (T-- > 0) {
        cin >> n >> p;
        for (int i = 1; i < n + 1; i++) {
            cin >> a[i];
        }
        sort(a + 1, a + n + 1);
        int ans = INF;
        for (int i = 1; i < n + 1; i++) {
            sum[i] = sum[i - 1] + a[i];
        }
        for (int i = p; i < n + 1; i++) {
            ans = min(ans, p * a[i] - (sum[i] - sum[i - p]));
        }
        printf("Case #%d: %d\n", cnt, ans);
        cnt++;
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 100000, INF = 0x3f3f3f3f;

int T, n, p;

int a[N], sum[N + 1];

/**

* sum[i] - sum[i - p] = a[i-p+1] + a[i-p+2] +...+ a[i]

* p * a[i] - (sum[i] - sum[i - p])=(p-1)*a[i] - (a[i-p+1] + a[i-p+2] + ... + a[i-1])

* 假设p=3，i=5

* 那么有3*a[5]- (sum[5] - sum[2])=2 * a[5] - (a[3] + a[4]) = (a[5] - a[3]) + (a[5] - a[4])

* 即每次计算当前元素和前面p-1个元素的差的和，依次遍历取最小值,利用前缀和来优化

* */

int main() {

cin >> T;

int cnt = 1;

while (T-- > 0) {

cin >> n >> p;

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

cin >> a[i];

}

sort(a + 1, a + n + 1);

int ans = INF;

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

sum[i] = sum[i - 1] + a[i];

}

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

ans = min(ans, p * a[i] - (sum[i] - sum[i - p]));

}

printf("Case #%d: %d\n", cnt, ans);

cnt++;

}

return 0;

}

分治：为运算表达式设计优先级

241. 为运算表达式设计优先级

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2
示例 2:

输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: "2-1-1"

输出: [0, 2]

解释:

((2-1)-1) = 0

(2-(1-1)) = 2

示例 2:

输入: "2*3-4*5"

输出: [-34, -14, -10, -10, 10]

解释:

(2*(3-(4*5))) = -34

((2*3)-(4*5)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10

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

public class Twohundred_fortyOne {
    /**
     * 分治法
     */
    public List<Integer> diffWaysToCompute(String input) {
        if (input == null || input.length() == 0)
            return new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            char opt = input.charAt(i);
            if (opt == '+' || opt == '-' || opt == '*') {
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));
                for (int l : left) {
                    for (int r : right) {
                        switch (opt) {
                            case '+':
                                ans.add(l + r);
                                break;
                            case '-':
                                ans.add(l - r);
                                break;
                            case '*':
                                ans.add(l * r);
                                break;
                        }
                    }
                }
            }
        }
        if (ans.size() == 0) {
            ans.add(Integer.valueOf(input));
        }
        return ans;
    }
}

import java.util.ArrayList;

import java.util.List;

public class Twohundred_fortyOne {

/**

* 分治法

public List<Integer> diffWaysToCompute(String input) {

if (input == null || input.length() == 0)

return new ArrayList<>();

List<Integer> ans = new ArrayList<>();

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

char opt = input.charAt(i);

if (opt == '+' || opt == '-' || opt == '*') {

List<Integer> left = diffWaysToCompute(input.substring(0, i));

List<Integer> right = diffWaysToCompute(input.substring(i + 1));

for (int l : left) {

for (int r : right) {

switch (opt) {

case '+':

ans.add(l + r);

break;

case '-':

ans.add(l - r);

break;

case '*':

ans.add(l * r);

break;

}

if (ans.size() == 0) {

ans.add(Integer.valueOf(input));

}

return ans;

}

ELECTRA: 超越BERT, 19年最佳NLP预训练模型

ref：wx

最长数对链

646. 最长数对链

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例 :

输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的数对链是 [1,2] -> [3,4]
注意：

给出数对的个数在 [1, 1000] 范围内。

给出 n 个数对。在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例 :

输入: [[1,2], [2,3], [3,4]]

输出: 2

解释: 最长的数对链是 [1,2] -> [3,4]

注意：

给出数对的个数在 [1, 1000] 范围内。

import java.util.*;

public class Sixhundred_fortySix {
    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0 || pairs[0].length == 0)
            return 0;
        Arrays.sort(pairs, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int ans = 1;
        int temp = pairs[0][1];
        for (int i = 1; i < pairs.length; i++) {
            if (pairs[i][0] > temp) {
                ans += 1;
                temp = pairs[i][1];
            }
        }
        return ans;
    }
}

import java.util.*;

public class Sixhundred_fortySix {

public int findLongestChain(int[][] pairs) {

if (pairs == null || pairs.length == 0 || pairs[0].length == 0)

return 0;

Arrays.sort(pairs, new Comparator<int[]>() {

public int compare(int[] o1, int[] o2) {

return o1[1] - o2[1];

}

});

int ans = 1;

int temp = pairs[0][1];

for (int i = 1; i < pairs.length; i++) {

if (pairs[i][0] > temp) {

ans += 1;

temp = pairs[i][1];

}

return ans;

}

信息抽取的几个challenges

模型层面：
- 一个字符一个标签的假定无法处理重叠或嵌套块（例如中国教育部部长，部长）
- 以词为基本单位的设定难以应用到无自然边界的语言（如汉语），而以字为基本单位有歧义
数据层面：
- 有监督学习依赖于高成本的人工标注数据
优化层面：
- 与分类任务不同，信息抽取任务的类别分布有显著差异：正例样本远远少于负例样本；错误和歧义通常集中于某几个特定的类别对之间

一	二	三	四	五	六	日
« 10月
				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