月度归档：2017年10月

洛谷/USACO “破锣摇滚”乐队 Raucous Rockers

发表评论

洛谷题号：P2736
又是动规，只会DFS……

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#include<cstring>
#include<cassert>
using namespace std;
int n, t, m;
int song[25];
int dfs(int cur_song, int cur_cd, int rem_min){
    if (cur_song == n + 1){
        if (cur_cd <= m){
            return 0;
        }
        return -2e9;
    }
    if (song[cur_song] <= rem_min){
        return max(dfs(cur_song + 1, cur_cd, rem_min), dfs(cur_song + 1, cur_cd, rem_min - song[cur_song]) + 1);
    }
    else{//song[cur_song]>rem_min
        return max(dfs(cur_song + 1, cur_cd, rem_min), dfs(cur_song + 1, cur_cd + 1, t - song[cur_song]) + 1);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> t >> m;
    for (int i = 1; i <= n; i++){
        cin >> song[i];
        if (song[i] > t){
            i--;
            n--;
        }
    }
    if (n == 0){
        cout << 0 << endl;
        return 0;
    }
    cout << dfs(1, 1, t) << endl;
}

洛谷/USACO 电网 Electric Fences

发表评论

洛谷题号：P2735
用的什么皮克定理，从来没听说过，看的题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#include<cstring>
#include<cassert>
using namespace std;
int n, m, p;
int gcd(int x, int y){
    if (x == 0)return y;
    return gcd(y%x, x);
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> p;
    int e = gcd(n, m) + gcd(abs(p - n), m) + p;
    printf("%d", p*m/2 + 1 - e / 2);
}

洛谷/USACO 商店购物 Shopping Offers

发表评论

洛谷题号：P2732
实在是被这五维的完全背包恶心了一把……

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
int s, b;
int dp[6][6][6][6][6];
int goods[1000];
int buy[6];
struct plan{
    int n;
    int k[6];
    int p;
}plans[200];
int No = 0;
int main(){
    ios::sync_with_stdio(false);
    cin >> s;
    for (int i = 1; i <= s; i++){
        cin >> plans[i].n;
        for (int j = 1; j <= plans[i].n; j++){
            int ci, ki;
            cin >> ci >> ki;
            if (goods[ci] == 0)goods[ci] = ++No;
            plans[i].k[goods[ci]] = ki;
        }
        cin >> plans[i].p;
    }
    cin >> b;
    for (int i = 1; i <= b; i++){
        int ci, pi, ki;
        cin >> ci >> ki >> pi;
        if (goods[ci] == 0)goods[ci] = ++No;
        buy[goods[ci]] = ki;
        s++;
        plans[s].n = 1;
        plans[s].k[goods[ci]] = 1;
        plans[s].p = pi;
    }
    memset(dp, 0x7f, sizeof(dp));
    dp[0][0][0][0][0] = 0;
    for (int z = 1; z <= s; z++){
        for (int i = plans[z].k[1]; i <= buy[1]; i++){
            for (int j = plans[z].k[2]; j <= buy[2]; j++){
                for (int l = plans[z].k[3]; l <= buy[3]; l++){
                    for (int x = plans[z].k[4]; x <= buy[4]; x++){
                        for (int y = plans[z].k[5]; y <= buy[5]; y++){
                            dp[i][j][l][x][y] = min(dp[i][j][l][x][y], dp[i - plans[z].k[1]][j - plans[z].k[2]][l - plans[z].k[3]][x - plans[z].k[4]][y - plans[z].k[5]]+plans[z].p);
                        }
                    }
                }
            }
        }
    }
    cout << dp[buy[1]][buy[2]][buy[3]][buy[4]][buy[5]] << endl;
}

洛谷/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;
    }
}