标签归档：USACO

洛谷/USACO 丑数 Humble Numbers

发表评论

洛谷题号：P2723
参考题解：作者: redbag 管理员 更新时间: 2016-08-01 23:15 https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P2723
这个暴力还是有一定思想的，一般人根本想不到的…………

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<cassert>
#include<map>
#include<queue>
using namespace std;
int k, n;
long long a[105], s[200000], f[200000];
int main(){
    ios::sync_with_stdio(false);
    cin >> k >> n;
    for (int i = 1; i <= k; i++){
        cin >> a[i];
    }
    f[0] = 1;
    for (int i = 1; i <= n; i++){
        long long m = 2e10;
        for (int j = 1; j <= k; j++){
            while (a[j] * f[s[j]] <= f[i - 1])s[j]++;
            m = min(a[j] * f[s[j]], m);
        }
        f[i] = m;
    }
    cout << f[n] << endl;
}

洛谷/USACO 01串 Stringsobits

发表评论

洛谷题号：P2727
参考题解：作者: 罗进瑶 更新时间: 2017-08-04 10:49 https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P2727

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<cassert>
#include<map>
#include<queue>
using namespace std;
long long dp[40][40];//dp[i][j]表示长度为i，最多含有j个1的二进制数的个数
int main(){
    ios::sync_with_stdio(false);
    long long n, l, i;
    cin >> n >> l >> i;
    for (int i = 0; i <= n; i++)dp[i][0] = dp[0][i] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= l; j++){
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
        }
    }
    long long k = i;
    for (int i = n; i >= 1; i--){
        if (k > dp[i - 1][l]){
            cout << "1";
            k -= dp[i - 1][l];
            l--;
        }
        else cout << "0";
    }
    cout << endl;
}

洛谷/USACO 联系 Contact

发表评论

洛谷题号：P2724

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<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<cassert>
#include<map>
using namespace std;
map<string, int> m;
string s,st;
int a, b, n;
struct sorted{
    int times;
    string str;
    bool operator < (sorted & s2){
        if (times != s2.times)return times>s2.times;
        else if (str.length() != s2.str.length())return str.length() < s2.str.length();
        else{
            for (int i = 0; i < str.length(); i++){
                if (str[i] != s2.str[i]){
                    return str[i] < s2.str[i];
                }
            }
            return true;
        }
    }
}sarr[200000];
int sarr_iter = 0;
int main(){
    ios::sync_with_stdio(false);
    cin >> a >> b >> n;
    while (cin >> st)s.append(st);
    for (int len = a; len <= b; len++){
        if (len > s.length())break;
        for (int i = 0; i <= s.length() - len; i++){
            m[s.substr(i, len)]++;
        }
    }
    for (auto i = m.begin(); i != m.end(); i++){
        sarr[++sarr_iter].times = (*i).second;
        sarr[sarr_iter].str = (*i).first;
    }
    sort(sarr + 1, sarr + sarr_iter + 1);
    int cur_freq_num = 0;
    int cur_freq_value = -1, cur_value_times = 0;
    for (int i = 1; cur_freq_num<=n&&i<=sarr_iter; i++){
        if (sarr[i].times != cur_freq_value){
            cur_freq_num++;
            if (cur_freq_num > n)break;
            if (cur_value_times % 6 != 0)cout << endl;
            cur_freq_value = sarr[i].times;
            cur_value_times = 1;
            cout << cur_freq_value << endl << sarr[i].str;
        }
        else{
            if (cur_value_times % 6 != 0)cout << " ";
            cout << sarr[i].str;
            cur_value_times++;
            if (cur_value_times % 6 == 0)cout << endl;
        }
    }
    if (cur_value_times % 6 != 0)cout << endl;
}

洛谷 牛的旅行 Cow Tours

发表评论
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
66
67
68
69
70
71
72
73
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<list>
#include<functional>
#include<string>
#define INF 0x7fffffff
using namespace std;
int n;
int posx[200], posy[200];
double arr[200][200];
double sglgdis[200];
inline double distance(int x1, int y1, int x2, int y2) { //最后开根号，函数中未开根号
    return sqrt((double)(x1 - x2)*(x1 - x2) + (double)(y1 - y2)*(y1 - y2));
}
void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (arr[i][j] > arr[i][k] + arr[k][j]) {
                    arr[i][j] = arr[i][k] + arr[k][j];
                }
            }
        }
    }
}

int main() {
    for (int i = 0; i <= 199; i++) {
        for (int j = 0; j <= 199; j++) {
            arr[i][j] = INF;
        }
    }
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &posx[i], &posy[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int t;
            scanf("%1d", &t);
            arr[i][j] = (t||i==j) ? distance(posx[i], posy[i], posx[j], posy[j]) : INF;
            if (i == j)arr[i][j] = 0;
        }
    }
    floyd();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] != INF&&arr[i][j] > sglgdis[i]) {
                sglgdis[i] = arr[i][j];
            }
        }
    }
    double mmm = INF;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] < INF)continue;
            double t = sglgdis[i] + sglgdis[j] + distance(posx[i], posy[i], posx[j], posy[j]);
            if (t < mmm)mmm = t;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (sglgdis[i] > mmm)mmm = sglgdis[i];
    }
    printf("%.6lf\n", mmm);
}

洛谷 穿越栅栏 Overfencing

发表评论

题号：1519

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
66
67
68
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<list>
#include<functional>
#include<string>
using namespace std;
int w, h, m=0;
char graph[300][300];
bool visited[300][300];
int steps[300][300];
int check_x[5] = {0,1,-1,0,0},
check_y[5] = {0,0,0,1,-1},
step_x[5] = {0,2,-2,0,0},
step_y[5] = {0,0,0,2,-2};
struct node {
    int x, y, step;
    node(int x1,int y1,int step1) {
        x = x1; y = y1; step = step1;
    }
};
bool check(int cx, int cy, int sx, int sy) {
    if (!visited[sx][sy] && graph[cx][cy] == ' '&&sx % 2 == 0 && sy % 2 == 0 && sx < 2 * h + 1 && sx>1 && sy < 2 * w + 1 && sy>1)return true;
    return false;
}
void BFS(int x,int y) {
    int maxstep = 0;
    queue<node> q;
    memset(visited, false, sizeof(visited));
    q.push(node(x, y, 0));
    while (!q.empty()) {
        node t = q.front(); q.pop();
        if (steps[t.x][t.y]> t.step)steps[t.x][t.y] = t.step;
        if (visited[t.x][t.y])continue;
        visited[t.x][t.y] = true;
        for (int i = 1; i <= 4; i++) {
            if (check(t.x + check_x[i], t.y + check_y[i], t.x + step_x[i], t.y + step_y[i]))q.push(node(t.x + step_x[i], t.y + step_y[i], t.step + 1));
        }
    }
}
int main() {
    cin >> w >> h;
    cin.getline(graph[0] + 1, 280);
    memset(steps, 0x7f, sizeof(steps));
    for (int i = 1; i <= 2 * h + 1; i++) {
        cin.getline(graph[i] + 1, 280);
    }
    for (int i = 2; i <= 2 * w; i++) {
        if (graph[1][i] == ' ')BFS(2, i);
        if (graph[2 * h + 1][i] == ' ')BFS(2 * h, i);
    }
    for (int i = 2; i <= 2 * h; i++) {
        if (graph[i][1] == ' ')BFS(i, 2);
        if (graph[i][2 * w + 1] == ' ')BFS(i, 2 * w);
    }
    for (int i = 2; i <= 2 * h; i+=2) {
        for (int j = 2; j <= 2 * w; j += 2) {
            if (steps[i][j] > m&&steps[i][j]!=0x7f7f7f7f)m = steps[i][j];
        }
    }
    cout << m+1 << endl;
}

洛谷 奶牛家谱 Cow Pedigrees

发表评论

毫不夸张的说：USACO里2.3节最难的动规、、、
基本是照着题解一个字一个字对的。。。。
题号：1472

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
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#define MOD 9901
using namespace std;
int n, k;
long long f[210][110],dp[210][110]; //必须是long long
int main(){
    cin >> n >> k;
    //if (n % 2 == 0){
    //  cout << 0 << endl;
    //  return 0;
    //}
    dp[1][1] = 1; f[0][0] = 1;
    for (int i = 1; i <= k; i++)f[1][i] = f[0][i] = 1;
    for (int i = 3; i <= n; i += 2){ //i:Node Num;j:depth
        int j = 1; while ((1 << j) - 1 < i)j++;
        for (; j <= k; j++){
            for (int l = 1; l <= i - 1; l += 2){
                dp[i][j] += dp[l][j - 1] * f[i - l - 1][j - 2];
                dp[i][j] += f[l][j - 2] * dp[i - l - 1][j - 1];
                dp[i][j] += dp[l][j - 1] * dp[i - l - 1][j - 1];
            }
            dp[i][j] %= MOD;
        }
        for (int j = 1; j <= k; j++)f[i][j] = (f[i][j - 1] + dp[i][j]) % MOD;
    }
    cout << dp[n][k] << endl;
}

USACO Section 2.3 Controlling Companies

发表评论

STDIN/STDOUT

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<algorithm>
#include<map>
#include<vector>
#include<list>
#include<functional>
#include<string>
using namespace std;
int u[10005], v[10005], w[10005], first[105], nxt[10005];
int n, m;
bool control[105],visited[105];
int percentage[105];
void dfs(int node) {
    if (visited[node])return;
    visited[node] = true;
    for (int e = first[node]; e != -1; e = nxt[e]) {
        percentage[v[e]] += w[e];
        if (percentage[v[e]] > 50) {
            control[v[e]] = true;
            dfs(v[e]);
        }
    }
}
int main() {
    memset(first, -1, sizeof(first));
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> u[i] >> v[i] >> w[i];
        nxt[i] = first[u[i]];
        first[u[i]] = i;
        m = max(m, max(u[i], v[i]));
    }
    for (int i = 1; i <= m; i++) {
        memset(visited, false, sizeof(visited));
        memset(control, false, sizeof(control));
        memset(percentage, 0, sizeof(percentage));
        dfs(i);
        for (int j = 1; j <= m; j++) {
            if (i != j&&control[j])cout << i << " " << j << endl;
        }
    }
}

洛谷 序言页码 Preface Numbering

发表评论

也是一道恶心的题，相比上面那一道一点不会2333.
题号：1465

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
char str[31][5] = {
    " ", "I", "II", "III", "IV", "V", "VI", "VII", "VIII",
    "IX", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX",
    "XC", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC",
    "CM", "M", "MM", "MMM"
};
char arr1[8] = "IVXLCDM";
int num[31] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200,
    300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000
};
int a[26];
void _find(int x){
    int j = 30;
    while (num[j] > x)j--;
    for (; j >= 1; j--){
        if (x >= num[j]){
            x -= num[j];
            for (int i = 0; i < strlen(str[j]); i++){
                a[str[j][i] - 'A']++;
            }
        }
        if (x == 0)return;
    }
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        _find(i);
    }
    if (a[int('I') - 65] != 0) printf("I %d\n", a[int('I') - 65]);
    if (a[int('V') - 65] != 0) printf("V %d\n", a[int('V') - 65]);
    if (a[int('X') - 65] != 0) printf("X %d\n", a[int('X') - 65]);
    if (a[int('L') - 65] != 0) printf("L %d\n", a[int('L') - 65]);
    if (a[int('C') - 65] != 0) printf("C %d\n", a[int('C') - 65]);
    if (a[int('D') - 65] != 0) printf("D %d\n", a[int('D') - 65]);
    if (a[int('M') - 65] != 0) printf("M %d\n", a[int('M') - 65]);
}

只有这样才能过……

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
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
char str[31][5] = {
    " ", "I", "II", "III", "IV", "V", "VI", "VII", "VIII",
    "IX", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX",
    "XC", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC",
    "CM", "M", "MM", "MMM"
};
char arr[8] = "IVXLCDM";
int num[31] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200,
    300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000
};
int a[26];
void _find(int x){
    int j = 30;
    while (num[j] > x)j--;
    for (; j >= 1; j--){
        if (x >= num[j]){
            x -= num[j];
            for (int i = 0; i < strlen(str[j]); i++){
                a[str[j][i] - 'A']++;
            }
        }
        if (x == 0)return;
    }
}
int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        _find(i);
    }
    for (int i = 0; i < 8; i++){
        if (a[arr[i] - 'A'] != 0)cout << (char)(arr[i]) << " " << a[arr[i] - 'A'] << endl;
    }
}

这样莫名其妙多出来一行输出@_500，根本不知道怎么回事……

洛谷 派对灯 Party Lamps

发表评论

USACO原题，比较恶心……看得题解
表示DFS只有三十分，就不用尝试DFS了，去看洛谷题解吧
题号：1468
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1468
作者: ☜闪耀星空☞ 更新时间: 2017-08-10 10:11

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
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int n, c, a, t;
bool light[10], dark[10],flag;
int map[10][10] = {
    { 0, 1, 1, 1, 1, 1, 1 }, //0
    { 0, 0, 0, 0, 0, 0, 0 }, //1
    { 0, 0, 1, 0, 1, 0, 1 }, //2
    { 0, 1, 0, 1, 0, 1, 0 }, //3
    { 0, 0, 1, 1, 0, 1, 1 }, //4
    { 0, 1, 0, 0, 1, 0, 0 }, //1,4
    { 0, 1, 1, 0, 0, 0, 1 }, //2,4
    { 0, 0, 0, 1, 1, 1, 0 }, //3,4
};
void print(int x){
    for (int i = 1; i <= 6; i++){
        if (light[i] && !map[x][i] || dark[i] && map[x][i])return;
    }
    flag = true;
    for (int i = 0; i < n; i++)cout << map[x][i % 6 + 1];
    cout << endl;
}
int main(){
    cin >> n >> c;
    while (cin >> t, t != -1)light[(t - 1) % 6 + 1] = true;
    while (cin >> t, t != -1)dark[(t - 1) % 6 + 1] = true;
    c = min(3, c);
    switch (c){
    case 0:print(0); break;
    case 1:print(1); print(2); print(4); print(3); break;
    case 2:print(1); print(7); print(2); print(4); print(3); print(6); print(0); break;
    case 3:print(1); print(7); print(2); print(4); print(5); print(3); print(6); print(0); break;
    }
    if (!flag)cout << "IMPOSSIBLE" << endl;
}