日度归档：1 10 月, 2017

洛谷/USACO 游戏 A Game

发表评论

洛谷题号：P2734
挺难的一道区间型动规，并不会做，看的题解，需要继续学习：
参考题解：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P2734 作者: redbag 管理员 更新时间: 2016-08-12 11:04

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#include<cstring>
#include<cassert>
using namespace std;
int n;
int num[105],sum[105];
int f[105][105];
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> num[i];
        sum[i] = sum[i - 1] + num[i];
        f[i][i] = num[i];
    }
    for (int i = n - 1; i >= 1; i--){
        for (int j = i + 1; j <= n; j++){
            f[i][j] = max(sum[j] - sum[i - 1] - f[i + 1][j], sum[j] - sum[i - 1] - f[i][j - 1]);
        }
    }
    cout << f[1][n] << " " << sum[n] - f[1][n] << endl;
}

洛谷/USACO 美国血统 American Heritage

发表评论

洛谷题号：P1827
做过二百遍的二叉树重构了，老套路：

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#include<cstring>
#include<cassert>
using namespace std;
char in[30],pre[30];
#define NULL 0
struct node{
    char value;
    node * left;
    node * right;
    node(){
        value = '\0';
        left = NULL;
        right = NULL;
    }
};
int find_in(int in_s, int in_e, char node){
    for (int i = in_s; i <= in_e; i++){
        if (in[i] == node)return i;
    }
    assert(0);
    return -1;
}
void BuildTree(int in_s, int in_e, int pre_s, int pre_e, node * root){
    if (in_s == in_e&&pre_s == pre_e){
        root->value = pre[pre_s];
        return;
    }
    if (in_s > in_e || pre_s > pre_e){
        return;
    }
    root->value = pre[pre_s];
    int pos_in = find_in(in_s, in_e, pre[pre_s]);
    root->left = new node;
    BuildTree(in_s, pos_in - 1, pre_s + 1, pre_s + pos_in - in_s, root->left);
    root->right = new node;
    BuildTree(pos_in + 1, in_e, pre_s + pos_in - in_s + 1, pre_e, root->right);
}
void postorder_traversal(node * ptr){
    if (ptr->left != NULL)postorder_traversal(ptr->left);
    if (ptr->right != NULL)postorder_traversal(ptr->right);
    if (ptr->value != '\0')cout << ptr->value;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> in+1 >> pre+1;
    int len = 1;
    while (in[len])len++;
    len--;
    node * root = new node;
    BuildTree(1, len, 1, len, root);
    postorder_traversal(root);
    cout << endl;
}

洛谷/USACO 家的范围 Home on the Range

发表评论

洛谷题号：P2733
思路很简单，我是参考洛谷 最大正方形这道题来写的，都是二维前缀和。

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
int n;
int arr[260][260];
int sum[260][260];
int cow[260];
inline int getSquareSum(int x, int y, int e){
    x--; y--;
    return sum[x + e][y + e] - sum[x + e][y] - sum[x][y + e] + sum[x][y];
}
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            scanf("%1d", &arr[i][j]);
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
        }
    }
    cow[1] = 1;
    for (int e = 2; e <= 250 && cow[e - 1] > 0; e++){
        for (int x = 1; x <= n - e + 1; x++){
            for (int y = 1; y <= n - e + 1; y++){
                if (getSquareSum(x, y, e) == e*e)
                    cow[e]++;
            }
        }
    }
    for (int i = 2; i <= 250 && cow[i] > 0; i++){
        printf("%d %d\n", i, cow[i]);
    }
}

洛谷/USACO 骑马修栅栏 Riding the Fences

发表评论

洛谷题号：P2731
参考题解：作者: 约修亚_RK 更新时间: 2016-10-28 23:59
作者: 曹彦臣 更新时间: 2016-09-07 21:31
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P2731

一开始用的是Fleury’s algorithm，T了1个点：

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
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#include<cstring>
using namespace std;
int f, rk = 0, mnode = 0,ans;
int arr[505][505];
int path[10000];
int degree[505];
bool check(int num){
    for (int i = 1; i <= mnode; i++){
        for (int j = 1; j <= mnode; j++){
            if (arr[i][j]!=0)
                return false;
        }
    }
    ans = num;
    return true;
}
bool dfs(int node,int depth){
    path[depth] = node;
    bool flag = false;
    for (int i = 1; i <= mnode; i++){
        if (arr[node][i]){
            flag = true;
            arr[node][i]--;
            arr[i][node]--;
            if (dfs(i, depth + 1))return true;
            arr[node][i]++;
            arr[i][node]++;
        }
    }
    if (!flag&&check(depth))return true;
    path[depth] = 0;
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> f;
    for (int i = 1; i <= f; i++){
        int u, v;
        cin >> u >> v;
        arr[u][v]++;
        arr[v][u]++;
        degree[u]++;
        degree[v]++;
        mnode = max(mnode, u);
        mnode = max(mnode, v);
    }
    bool odd = false;
    for (int i = 1; i <= mnode; i++){
        if (degree[i] % 2 == 1){
            odd = true;
            if (dfs(i, 1))break;
        }
    }
    if (!odd)dfs(1, 1);
    for (int i = 1; i <= ans; i++){
        cout << path[i] << endl;
    }
}

后来改用Hierholzer’s algorithm，A了。

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
int f, rk = 0, mnode = 0,ans;
int arr[505][505];
int path[10000];
int degree[505];
bool check(int num){
    for (int i = 1; i <= mnode; i++){
        for (int j = 1; j <= mnode; j++){
            if (arr[i][j]!=0)
                return false;
        }
    }
    ans = num;
    return true;
}
void Euler(int node){ //新版本
    for (int i = 1; i <= mnode; i++){
        while (arr[node][i] > 0){
            arr[node][i]--;
            arr[i][node]--;
            Euler(i);
        }
    }
    path[++ans] = node;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> f;
    for (int i = 1; i <= f; i++){
        int u, v;
        cin >> u >> v;
        arr[u][v]++;
        arr[v][u]++;
        degree[u]++;
        degree[v]++;
        mnode = max(mnode, u);
        mnode = max(mnode, v);
    }
    bool odd = false;
    for (int i = 1; i <= mnode; i++){
        if (degree[i] % 2 == 1){
            odd = true;
            Euler(i);
            break;
        }
    }
    if (!odd)Euler(1);
    for (int i = ans; i >=1; i--){
        cout << path[i] << endl;
    }
}