【190803】计蒜客-MCPC-2017

2019-08-06

目录

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
#include <cstdio>
#include <cstring>

char G[6][6];

const int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
const int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

int main()
{
    for (int i = 0; i < 5; i++)
        scanf("%s", G[i]);
    int cnt = 0;
    bool ok = true;
    for (int i = 0; ok && i < 5; i++)
        for (int j = 0; ok && j < 5; j++)
            if (G[i][j] == 'k')
            {
                cnt++;
                int nx, ny;
                for (int k = 0; ok && k < 8; k++)
                {
                    nx = i + dx[k];
                    ny = j + dy[k];
                    if (0 <= nx && nx < 5 && 0 <= ny && ny < 5)
                        ok = G[nx][ny] == '.';
                }
            }
    if (ok && cnt == 9)
        printf("valid\n");
    else
        printf("invalid\n");
    return 0;
}

B题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>

int main()
{
    int n, x, sum = 0, tot = 0;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%d", &x);
        if (x >= 0)
        {
            sum += x;
            tot++;
        }
    }
    printf("%lf\n", double(sum) / double(tot));
    return 0;
}

D题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <iostream>
#include <string>
#include <set>

using namespace std;
set<string> G;

int main()
{
    string word;
    bool ok = true;
    while (cin >> word)
    {
        if (G.count(word) != 0)
            ok = false;
        else
            G.insert(word);
    }
    printf("%s\n", ok ? "yes" : "no");
    return 0;
}

F题

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 <cstdio>
#include <cstring>

const int N = 100000 + 5;

char a[N], b[N];

int main()
{
    scanf("%s%s", a, b);
    int l = 0, len = strlen(a), r = len - 1;
    while (a[l] == b[l])
        l++;
    while (a[r] == b[r])
        r--;
    for (int p = l, q = r; p <= r; p++, q--)
        if (a[p] != b[q])
        {
            printf("0\n");
            return 0;
        }
    int ans = 1;
    while (l - ans >= 0 && r + ans < len && a[l - ans] == b[r + ans])
        ans++;
    printf("%d\n", ans);
    return 0;
}

G题

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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1005;

int dis[N], g[N][N], n, m;
bool vis[N];

void dijkstra()
{
    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    dis[1] = 0;
    for (int i = 1; i <= n; i++)
    {
        int k = -1, minz = INF;
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && dis[j] < minz)
            {
                minz = dis[j];
                k = j;
            }
        }
        vis[k] = 1;
        for (int j = 1; j <= n; j++)
            if (!vis[j])
                dis[j] = min(dis[j], dis[k] + g[k][j]);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    int vis_node[1005] = {0}, vis_tn[1005] = {0};
    memset(g, INF, sizeof(g));
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        if (u < 0)
        {
            g[-u][v] = 0;
            vis_node[-u] = 1;
        }
        else
        {
            g[u][v] = 1;
        }
        vis_tn[abs(u)] = 1;
        vis_tn[v] = 1;
    }
    dijkstra();
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (dis[i] <= 1 && vis_node[i] == 0 && vis_tn[i] == 1)
            ans++;
    printf("%d\n", ans);
    return 0;
}

H题

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
#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;
const int N = 1e6 + 5;

ll qpow(ll a, ll b)
{
    ll r = 1, t = a;
    while (b)
    {
        if (b & 1)
            r = (r * t) % MOD;
        b >>= 1;
        t = (t * t) % MOD;
    }
    return r;
}

ll fac[N], inv[N];

ll init()
{
    fac[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = fac[i - 1] * i % MOD;
    inv[N - 1] = qpow(fac[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; i--)
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    return 0;
}

ll C(ll n, ll m)
{
    if (n < m)
        return 0;
    return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

int main()
{
    ll n, x, y;
    init();
    scanf("%lld%lld%lld", &n, &x, &y);
    ll m = min(n / x, n / y);
    ll ans = 0;
    for (ll i = 1; i <= m; i++)
        ans = (ans + C(n - i * (x - 1) - 1, i - 1) % MOD * C(n - i * (y - 1) - 1, i - 1) % MOD) % MOD;
    printf("%lld\n", ans);
    return 0;
}

E题

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;

int r, n, a, b, x, vis[3100];

vector<int> vct[1200];
int head[3100], cnt, ok[3100];

struct Edge
{
    int v, next, w;
} edge[210000];

struct Node
{
    int x, steps;
};

void add(int u, int v, int w)
{
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    edge[cnt].w = w;
    head[u] = cnt++;
}

int main()
{
    memset(vis, 0, sizeof(vis));
    memset(head, -1, sizeof(head));
    cnt = 0;
    scanf("%d%d%d%d%d", &r, &n, &a, &b, &x);
    int d, num = 1;
    for (int i = 0; i < x; i++)
    {
        scanf("%d", &d);
        vis[d] = 1;
    }
    d = r;
    for (int i = 1; i <= r; i++)
    {
        for (int j = 0; j < d; j++)
            vct[i].push_back(num), num++;
        d++;
    }
    d = 2 * r - 2;
    for (int i = r + 1; i <= 2 * r - 1; i++)
    {
        for (int j = 0; j < d; j++)
            vct[i].push_back(num), num++;
        d--;
    }

    int x, y;
    for (int i = 1; i < r; i++)
    {
        for (int j = 0; j < vct[i].size(); j++)
        {
            x = i - 1;
            y = j;
            if (x > 0 && y < vct[x].size())
                add(vct[i][j], vct[x][y], 1);
            y = j - 1;
            if (x > 0 && y >= 0)
                add(vct[i][j], vct[x][y], 1);

            x = i;
            y = j - 1;
            if (y >= 0)
                add(vct[i][j], vct[x][y], 1);
            y = j + 1;
            if (y < vct[x].size())
                add(vct[i][j], vct[x][y], 1);

            x = i + 1;
            y = j;
            add(vct[i][j], vct[x][y], 1);
            y = j + 1;
            add(vct[i][j], vct[x][y], 1);
        }
    }

    for (int j = 0; j < vct[r].size(); j++)
    {
        x = r - 1;
        y = j;
        if (y < vct[x].size())
            add(vct[r][j], vct[x][y], 1);
        y = j + 1;
        if (y < vct[x].size())
            add(vct[r][j], vct[x][y], 1);

        y = j - 1;
        if (y >= 0)
            add(vct[r][j], vct[r][y], 1);
        y = j + 1;
        if (y < vct[r].size())
            add(vct[r][j], vct[r][y], 1);

        x = r + 1;
        y = j - 1;
        if (y >= 0)
            add(vct[r][j], vct[x][y], 1);
        y = j;
        if (y < vct[x].size())
            add(vct[r][j], vct[x][y], 1);
    }

    for (int i = r + 1; i <= 2 * r - 1; i++)
    {
        for (int j = 0; j < vct[i].size(); j++)
        {
            x = i - 1;
            y = j;
            add(vct[i][j], vct[x][y], 1);
            y = j + 1;
            add(vct[i][j], vct[x][y], 1);

            x = i;
            y = j - 1;
            if (y >= 0)
                add(vct[i][j], vct[x][y], 1);
            y = j + 1;
            if (y < vct[x].size())
                add(vct[i][j], vct[x][y], 1);

            x = i + 1;
            y = j;
            if (x < 2 * r && y < vct[x].size())
                add(vct[i][j], vct[x][y], 1);
            y = j - 1;
            if (x < 2 * r && y >= 0)
                add(vct[i][j], vct[x][y], 1);
        }
    }
    memset(ok, 0, sizeof(ok));
    queue<Node> q;
    Node no;
    no.x = a, no.steps = 0;
    ok[a] = 1;
    q.push(no);
    int ans = INF;
    while (!q.empty())
    {
        no = q.front();
        q.pop();
        if (no.steps > n)
            break;
        if (no.x == b)
        {
            ans = min(ans, no.steps);
            break;
        }
        for (int i = head[no.x]; ~i; i = edge[i].next)
        {
            int v = edge[i].v;
            if (!vis[v] && !ok[v])
            {
                Node nod;
                nod.x = v, nod.steps = no.steps + 1;
                q.push(nod);
                ok[v] = 1;
            }
        }
    }
    if (ans <= n)
        printf("%d\n", ans);
    else
        printf("No");
    return 0;
}

I题

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+100;
const int maxt = 1e6;
struct node
{
    int a,b,s;
    node()
    {

    }
    node(int a,int b,int s)
    {
        this->a = a;
        this->b = b;
        this->s = s;
    }
};
node my_data[maxn];
double ans[maxt+100];
double cnt[maxt+100];
int n ;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int a,b,s;
        scanf("%d%d%d",&s,&a,&b);
        my_data[i] = node(a,b,s);

    }
    memset(ans,0,sizeof(ans));
    memset(cnt,0,sizeof(cnt));
    //背包
    int j = n;
    for(int i = maxt ; i>=1;i--)
    {
        ans[i] = ans[i+1];//可以不选
        while(j && my_data[j].s == i)
        {
            //防止溢出
            int a = min(my_data[j].a+i,maxt);
            int b = min(my_data[j].b+i+1,maxt);
            double temp = 1+(cnt[a] - cnt[b])/(my_data[j].b-my_data[j].a+1);
            ans[i] = max(ans[i],temp);
            j--;
        }
        cnt[i] = ans[i] + cnt[i+1];
    }
    printf("%.4f\n",ans[1]);
}
© 2019 blog - Powered by Hexo - Theme Chan