2019

【190806】计蒜客-ECNA-2018

2019-08-06

目录

C题

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

using namespace std;

const int N = 26 + 4;
const int M = 2000 + 4;
const int INF = 0x3f3f3f3f;

int p[M];
char votes[M][N];

int dist[N][N];
bool ans[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
        scanf("%d%s", &p[i], votes[i]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dist[i][j] = i == j ? 0 : INF;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int ni = 0, nj = 0;
            for (int k = 0; k < m; k++)
            {
                int ipos = n + 1, jpos = n + 1;
                for (int t = 0; t < n; t++)
                {
                    if (votes[k][t] == 'A' + i)
                        ipos = t;
                    if (votes[k][t] == 'A' + j)
                        jpos = t;
                    if (ipos < n + 1 || jpos < n + 1)
                        break;
                }
                if (ipos < jpos)
                    ni += p[k];
                else
                    nj += p[k];
            }
            if (ni > nj)
                dist[i][j] = 1;
            else
                dist[j][i] = i;
        }
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    for (int i = 0; i < n; i++)
        ans[i] = true;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            if (dist[i][j] >= INF)
                ans[i] = false;
    }
    for (int i = 0; i < n; i++)
        printf("%c: %s\n", 'A' + i, ans[i] ? "can win" : "can't win");
    return 0;
}

B题

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

using namespace std;

const int N = 10000 + 1;

set<int> s;
int a[N];

int main()
{
    int r, m;
    scanf("%d%d", &r, &m);
    a[1] = r;
    int last = 1, ans = 0;
    bool end = false;
    for (int i = 1 ; i <= N; i++)
    {
        if (a[i] == m)
        {
            ans = i;
            break;
        }
        int next = 0;
        s.insert(a[i]);
        for (int j = 1; j < i; j++)
        {
            int t = a[i] - a[j];
            if (t < 4 * N)
                s.insert(t);
            if (t == m)
            {
                ans = i;
                end = true;
                break;
            }
        }
        if (end)
            break;
        for (int j = last; !next; j++)
            if (!s.count(j))
                next = j;
        last = next;
        a[i + 1] = a[i] + next;
    }
    printf("%d\n", ans);
    return 0;
}

J题

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

using namespace std;

const int N = 2500 + 5;

struct Edge
{
    int dest;
    Edge *next;
    Edge(int d, Edge *n = 0) : dest(d), next(n) {}
};

struct Vertex
{
    Edge *list;
    bool vis;
} G[N], invG[N];

stack<int> S;

int districtSizes[N];

void dfs(int v)
{
    G[v].vis = true;
    for (Edge *e = G[v].list; e != 0; e = e->next)
    {
        int w = e->dest;
        if (!G[w].vis)
            dfs(w);
    }
    S.push(v);
}

int findSize(int v)
{
    invG[v].vis = true;
    int size = 1;
    for (Edge *e = invG[v].list; e != 0; e = e->next)
    {
        int w = e->dest;
        if (!invG[w].vis)
            size += findSize(w);
    }
    return size;
}

int main()
{
    int n, cnt = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        G[i].list = 0;
        G[i].vis = false;
        invG[i].list = 0;
        invG[i].vis = false;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int x;
            scanf("%d", &x);
            if (x == 1)
            {
                G[i].list = new Edge(j, G[i].list);
                invG[j].list = new Edge(i, invG[j].list);
                cnt++;
            }
        }
    }
    for (int i = 0; i < n; i++)
        if (!G[i].vis)
            dfs(i);

    int k = 0;
    for (int i = 0; i < n; i++)
    {
        int v = S.top();
        S.pop();
        if (!invG[v].vis)
            districtSizes[k++] = findSize(v);
    }
    int sum = 0;
    for (int i = 0; i < k; i++)
    {
        int size = districtSizes[i];
        sum += size * (size - 1);
        for (int j = i + 1; j < k; j++)
            sum += size * districtSizes[j];
    }
    printf("%d\n", sum - cnt);
    return 0;
}

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
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
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn=300;
int a[maxn][maxn];
int n,m,sx,sy,ex,ey;
int cnt=INF,num=0;
int t1[maxn*maxn],t2[maxn*maxn];
int dir[4][2] = {0,1,-1,0,1,0,0,-1};
int f()
{
    for(int i=0; i<num; ++i)
        if(t1[i]>t2[i])
            return 1;
        else
        if(t1[i]<t2[i])
            return 0;
    return 0;
}
inline int inR(int x, int y)
{
    if(x>=0&&x<m&&y>=0&&y<n) return 1;
    return 0;
}
inline int isV(int x1,int y1, int x2, int y2)
{
    return inR(x1,y1)&&inR(x2,y2)&&a[x1][y1]==a[x2][y2]&&a[x1][y1]>=0;
}
void dfs(int x, int y, int pre=-1)
{
    if(x==ex&&y==ey)
    {
        if(num<cnt)
        {
            cnt=num;
            for(int i=0; i<cnt;++i)
                t1[i]=t2[i];
        } else
        if(cnt==num)
        {
            if(f())
            {
                for(int i=0; i<cnt;++i)
                    t1[i]=t2[i];
            }
        }
        return;
    }
    for(int k=0; k<4; ++k)
    {
        if(k+pre==3) continue;
        int x1=x+dir[k][0];
        int y1=y+dir[k][1];
        int x2=x+dir[k][0]*2;
        int y2=y+dir[k][1]*2;
        if(!isV(x1,y1,x2,y2)) continue;
        int t=a[x1][y1];
        a[x][y]=t;
        a[x2][y2]=-1;
        t2[num++]=t;

        dfs(x2,y2,k);

        a[x2][y2]=t;
        a[x][y]=-1;
        --num;
    }
    return;
}
int main()
{
    memset(t1,0,sizeof(t1));
    memset(t2,0,sizeof(t2));
    scanf("%d%d",&m,&n);
    for(int i=0; i<m; ++i)
        for(int j=0; j<n; ++j)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j]==-1)
            {
                sx=i;
                sy=j;
            }
        }
    scanf("%d%d",&ex,&ey);
    --ex;
    --ey;
    dfs(sx,sy,-1);
    if(cnt==INF)
        printf("impossible\n");
    else
    {
        for(int i=0; i<cnt; ++i)
        {
            printf("%d",t1[i]);
            if(i!=cnt-1) printf(" ");
        }
        printf("\n");
    }
    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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int bases[28] = {1000, 900, 800, 700, 600, 500, 400, 300, 200, 100, 90, 80, 70, 60, 50, 40, 30, 20, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
const string romans[28] = {"M", "CM", "DCCC", "DCC", "DC", "D", "CD", "CCC", "CC",
                           "C", "XC", "LXXX", "LXX", "LX", "L", "XL", "XXX", "XX",
                           "X", "IX", "VIII", "VII", "VI", "V", "IV", "III", "II", "I"};

void make_roman(int x, string &ans, int &prefix)
{
    ans = "";
    while (x > 0)
    {
        int pos = 0;
        while (x < bases[pos])
            pos++;
        x = x - bases[pos];
        if (pos != 0)
            ans = ans + romans[pos];
        else
            prefix++;
    }
}

int Find(const vector<string> &v, string &key)
{
    for (int i = 0; i < v.size(); i++)
        if (v[i] == key)
            return i;
    return -1;
}

vector<string> list;

int main()
{
    for (int i = 1; i < 1000; i++)
    {
        int prefix = 0;
        string roman;
        make_roman(i, roman, prefix);
        list.push_back(roman);
    }
    sort(list.begin(), list.end());
    int big_start = 0;
    while (list[big_start] < "M")
        big_start++;

    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        string roman;
        int prefix = 0;
        make_roman(x, roman, prefix);
        if (roman.size() == 0)
        {
            cout << prefix * (big_start + 1) << endl;
        }
        else if (roman[0] < 'M')
        {
            int ans = Find(list, roman) + 1 + prefix * (big_start + 1);
            cout << ans << endl;
        }
        else
        {
            int ans = list.size() - Find(list, roman);
            ans = ans * -1 - prefix * (list.size() - big_start);
            cout << ans << endl;
        }
    }
    return 0;
}

【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]);
}

【190801】计蒜客-Hong-Kong_2017

2019-08-01

目录

D题

最短路。

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
#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=1000+100;
struct Qnode
{
    int v;
    int c;
    Qnode(int _v=0, int _c=0):v(_v),c(_c){}
    bool operator<(const Qnode &r) const
    {
        return c>r.c;
    }
};
struct Edge
{
    int v;
    int cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}

};
vector<Edge> E[MAXN];
bool vis[MAXN];
int dist[MAXN];
int n,a,b,c,st,ed;
void Dijkstra(int n,int start)
{
    memset(vis,0,sizeof(vis));
    for(int i=0;i<=n;++i) dist[i]=INF;
    priority_queue<Qnode> que;
    while(!que.empty()) que.pop();
    dist[start]=0;
    que.push(Qnode(start,0));
    Qnode tmp;
    int u,v,cost;
    while(!que.empty())
    {
        tmp=que.top();
        que.pop();
        u=tmp.v;
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=0; i<E[u].size(); ++i)
        {
            v=E[tmp.v][i].v;
            cost=E[u][i].cost;
            if(!vis[v]&&dist[v]>dist[u]+cost)
            {
                dist[v]=dist[u]+cost;
                que.push(Qnode(v,dist[v]));
            }
        }
    }
}
void addEdge(int u, int v, int w)
{
    E[u].push_back(Edge(v,w));
}

void init()
{
    for(int i=0;i<=n;++i) E[i].clear();
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        init();
        scanf("%d%d",&st,&ed);
        while(~scanf("%d",&a)&&a)
        {
            scanf("%d%d",&b,&c);
            addEdge(a,b,c);
            addEdge(b,a,c);
        }
        Dijkstra(n,st);
        printf("%d\n",dist[ed]);
    }
    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
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
const int maxm = 1e3+10;
const double eps = 1e-12;
struct point
{
    double x,y;
};
point bi[maxm],user[maxn];//每个人的坐标不用存
double s[maxn];
char ss[maxn*10];//读取字符串
int n,m;
double get_dis(point a,point b)
{
    double t1 = a.x-b.x;
    double t2 = a.y-b.y;
    double res = sqrt(t1*t1 + t2*t2);
    return res;
}
void solve(int number )
{
    int ans = 0;
    double dis=0;
    for(int i=1;i<=m;i++)
    {
        dis = get_dis(user[number],bi[i]);
        if(dis - s[number] <=eps)
        {
            ans++;
        }

    }
    if(number==n)
    {
        printf("%d\n",ans);
    }
    else
    {
        printf("%d ",ans);
    }
    return ;
}

int main()
{


    while(~scanf("%d%d",&m,&n))
    {
        if(m==0&&n==0)
            break;
        for(int i=1;i<=m;i++)
            {
                scanf("%s",ss);
                sscanf(ss,"(%lf,%lf)",&bi[i].x,&bi[i].y);
            }
        for(int i=1;i<=n;i++)
        {
            scanf("%s",ss);
            sscanf(ss,"(%lf,%lf)",&user[i].x,&user[i].y);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%lf",&s[i]);
        }
        for(int i=1;i<=n;i++)
            solve(i);
    }
    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
//只要用的尽量少的硬币就好了,总数量尽量少
//因为题目保证升序，所以我正常顺序写就可以保证低额度的用的多
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;//这个可以用mem
const int maxn = 20+10;//最多10种硬币
const int maxv = 20000+10;//最多这么多。。但是考虑面值问题
int dp[maxv];
int ans[maxv][maxn];//达到V的时候每一个的最小花销
int money[maxn];
int n,v;
int main()
{
    while(~(scanf("%d%d",&v,&n)))
    {
        memset(dp,inf,sizeof(dp));
        memset(ans,0,sizeof(ans));
        dp[0] = 0;
        //一个完全背包,而且必须用完
        for(int i=1;i<=n;i++)
            scanf("%d",&money[i]);
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=v;j++)
            {
                if(j+money[i]>v)
                    break;
                else
                {
                    if(dp[j+money[i]] >= dp[j] +1)//尽量用面值小的
                    {
                        dp[j+money[i]] = dp[j] +1;
                        //维护最小花销,传递闭包
                        for(int k=1;k<=n;k++)
                            ans[j+money[i]][k] = ans[j][k];
                        ++ans[j+money[i]][i];
                    }
                }
            }
        }
        if(dp[v]==inf)
            printf("-1\n");
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(i==n)
                    printf("%d\n",ans[v][i]);
                else
                    printf("%d ",ans[v][i]);
            }
        }
    }
    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
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100000 + 10;
int a[N];
int L, S;

bool check(int mid)
{
    int l = 1;
    int num = L - 1;
    for (int i = 2; i <= S; ++i)
    {
        if (a[i] - a[l] >= mid)
        {
            l = i;
            --num;
            if (num == 0)
                return true;
        }
    }
    return false;
}

int main()
{
    while (scanf("%d%d", &S, &L) == 2 && L && S)
    {
        for (int i = 1; i <= S; i++)
            scanf("%d", &a[i]);
        sort(a + 1, a + 1 + S);
        int l = 0, r = a[S];
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (check(mid))
                l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%d\n", r);
    }
}

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
import java.lang.*;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    static BigInteger a[] = new BigInteger[201];
    static BigInteger p[] = new BigInteger[201];
    static BigInteger TWO = new BigInteger("2");
    static BigInteger TRI = new BigInteger("3");

    public static BigInteger f(BigInteger n) {
        int x = 0;
        for (int i = 0; i < 201; i++) {
            if (n.compareTo(p[i]) < 0) {
                x = i - 1;
                break;
            }
        }
        BigInteger t = n.subtract(p[x]);
        if (t.compareTo(BigInteger.ZERO) == 0)
            return a[x];
        BigInteger res = t.multiply(p[x].add(p[x]).subtract(BigInteger.ONE).subtract(t)).divide(TWO);
        return a[x].add(f(t).multiply(TWO)).add(res);
    }

    public static void main(String[] args) {
        p[0] = BigInteger.ONE;
        for (int i = 1; i < 200; i++) {
            p[i] = p[i - 1].multiply(TWO);
        }
        a[0] = a[1] = BigInteger.ZERO;
        for (int i = 2; i < 200; i++) {
            BigInteger t = p[i - 1].multiply(p[i - 1].subtract(BigInteger.ONE)).divide(TWO);
            a[i] = a[i - 1].multiply(TRI).add(t);
        }
        Scanner sc = new Scanner(System.in);
        BigInteger n;
        while (sc.hasNext()) {
            n = sc.nextBigInteger();
            System.out.println(f(n.add(BigInteger.ONE)));
        }
    }
}

A题

枚举y二分x。

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
import java.util.*;
import java.math.BigInteger;

public class Main {
    static BigInteger pow[][] = new BigInteger[100005][11];

    public static void main(String[] args) {

        for (int i = 1; i <= 100000; i++) {
            pow[i][0] = BigInteger.ONE;
            for (int j = 1; j <= 10; j++) {
                pow[i][j] = pow[i][j - 1].multiply(BigInteger.valueOf(i));
            }
        }
        String INF = "1";
        for (int i = 1; i <= 60; i++)
            INF = INF + "0";
        Scanner sc = new Scanner(System.in);
        int ca = sc.nextInt();

        while (ca-- != 0) {
            int n = sc.nextInt(), z = sc.nextInt();
            int X = 0, Y = 0;
            BigInteger ans = new BigInteger(INF);
            for (int i = 2; i < z; i++) {
                BigInteger num = pow[1][n].add(pow[i][n]).subtract(pow[z][n]);
                if (num.compareTo(BigInteger.ZERO) >= 0) {
                    if (num.compareTo(ans) == -1) {
                        ans = num;
                        X = 1;
                        Y = i;
                    }
                    continue;
                }
                int l = 1, r = i - 1;
                while (l < r) {
                    int mid = (l + r + 1 >> 1);
                    num = pow[mid][n].add(pow[i][n]).subtract(pow[z][n]);
                    if (num.compareTo(BigInteger.ZERO) == -1) {
                        l = mid;
                    } else
                        r = mid - 1;
                }
                num = pow[l][n].add(pow[i][n]).subtract(pow[z][n]);
                num = num.multiply(BigInteger.valueOf(-1));

                if (num.compareTo(ans) == -1) {
                    ans = num;
                    X = l;
                    Y = i;
                }
                if (l < i - 1) {
                    l++;
                    num = pow[l][n].add(pow[i][n]).subtract(pow[z][n]);
                    if (num.compareTo(ans) == -1) {
                        ans = num;
                        X = l;
                        Y = i;
                    }
                }
            }
            System.out.printf("%d %d ", X, Y);
            System.out.println(ans);
        }
        sc.close();
    }
}

B题

线段树，扫描线。

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
#include<bits/stdc++.h>
using namespace std;
#define ls(x) x<<1
#define rs(x) x<<1|1
#define lson l,mid,ls(root)
#define rson mid+1,r,rs(root)
const int maxn = 1e4+100;
int tree[maxn<<2];//求和
int tag[maxn<<2];//标记
void rev(int l,int r,int root)
{
    tag[root] ^= 1;//区间反转
    tree[root] = (r-l+1) - tree[root];//其实只有0 和(r-l+1)这两种情况。。
}
void push_down(int l,int r,int root)
{
    if(tag[root]==0)//没有被标记
    {
        return ;
    }
    else
    {
        int mid = l + ((r-l)>>1);
        rev(lson);
        rev(rson);
        tag[root] = 0;
        return ;
    }
}
void push_up(int root)
{
    tree[root] = tree[ls(root)]+tree[rs(root)];
}
void update(int x,int y,int number, int l,int r,int root)
{
    if(x<=l&&y>=r)
    {

        rev(l,r,root);
        return ;
    }
    push_down(l,r,root);//标记下传
    int mid = l + ((r-l)>>1);
    if(x<=mid) update(x,y,number,lson);
    if(y>mid) update(x,y,number,rson);
    push_up(root);
}
struct Node
{
    int x1,x2,y,flag;
    Node()
    {

    }
    Node(int x1,int x2,int y,int flag)
    {
        this->x1 = x1;
        this->x2 = x2;
        this->y = y;
        this->flag = flag;
    }
}node[maxn<<2];
bool cmp(Node a,Node b)//保证有序
{
    if(a.y==b.y)
        return a.flag>b.flag;
    else
        return a.y<b.y;
}
int main()
{
    int cnt = 0;
    int ans = 0;
    int j = 1;
    int x1,y1,x2,y2;
    int T;
    int n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(tree,0,sizeof(tree));
        memset(tag,0,sizeof(tag));
        cnt = 0;
        ans =0;
        for(int i=1;i<=m;i++)
        {

            scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
            node[++cnt] = Node(x1,x2,y1,1);//下位线
            node[++cnt] = Node(x1,x2,y2,-1);//上位线
        }
        sort(node+1,node+cnt+1,cmp);
        j = 1;//上位线本身算一个所以上位线本身不恢复
        for(int i=1 ; i<=n;i++)
        {
            while(node[j].y<=i&&node[j].flag==1&&j<=cnt)
            {
                update(node[j].x1,node[j].x2,1,1,n,1);
                j++;
            }
            ans += tree[1];
            while(node[j].y<=i&&j<=cnt)
            {
                update(node[j].x1,node[j].x2,1,1,n,1);
                j++;
            }
        }
        printf("%d\n",ans);
    }
}

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
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
179
180
181
182
183
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1005;
const int M = 10005;
const int J = 10000000;

int n, m;
LL k[M];
char ch[N];

void print(LL a[])
{
    printf("%lld", a[a[0]]);
    for (int i = a[0] - 1; i; i--)
        printf("%07lld", a[i]);
    printf("\n");
}
int compare(LL a[], LL b[]) //-1:a=b  0:a<b  1:a>b
{
    if (a[0] != b[0])
        return a[0] > b[0];
    for (int i = a[0]; i; i--)
        if (a[i] != b[i])
            return a[i] > b[i];
    return -1;
}
void toBigInt(char s[], LL a[])
{
    int i, j, l = strlen(s);
    for (i = l, a[0] = 1; i > 6; i -= 7, a[0]++)
    {
        for (j = 0; j < 7; j++)
            a[a[0]] = a[a[0]] * 10 + s[i - 7 + j] - '0';
    }
    for (j = 0; j < i; j++)
        a[a[0]] = a[a[0]] * 10 + s[j] - '0';
}
void add(LL a[], LL b[], LL c[])
{
    LL t[M] = {0};
    t[0] = max(a[0], b[0]);
    for (int i = 1; i <= t[0]; i++)
        t[i] = a[i] + b[i];
    for (int i = 1; i <= t[0]; i++)
        t[i + 1] += t[i] / J, t[i] %= J;
    while (t[t[0] + 1])
        t[0]++;
    while (!t[t[0]] && t[0] > 1)
        t[0]--;
    memcpy(c, t, sizeof(t));
}
void sub(LL a[], LL b[], LL c[])
{
    LL t[M] = {0};
    t[0] = a[0];
    for (int i = 1; i <= t[0]; i++)
        t[i] = a[i] - b[i];
    for (int i = 1; i < t[0]; i++)
        if (t[i] < 0)
            t[i + 1]--, t[i] += J;
    while (!t[t[0]] && t[0] > 1)
        t[0]--;
    memcpy(c, t, sizeof(t));
}
void mul(LL a[], LL b[], LL c[])
{
    LL t[M] = {0};
    t[0] = a[0] + b[0];
    for (int i = 1; i <= a[0]; i++)
        for (int j = 1; j <= b[0]; j++)
            t[i + j - 1] += a[i] * b[j];
    for (int i = 1; i <= t[0]; i++)
        t[i + 1] += t[i] / J, t[i] %= J;
    while (t[t[0] + 1])
        t[0]++;
    while (!t[t[0]] && t[0] > 1)
        t[0]--;
    memcpy(c, t, sizeof(t));
}
void qpow(LL a[], LL x)
{
    LL t[M] = {1, 2, 0};
    a[0] = a[1] = 1;
    while (x)
    {
        if (x & 1)
            mul(a, t, a);
        mul(t, t, t);
        x >>= 1;
    }
}
void sum(LL t[], LL mid, LL tt[])
{
    qpow(t, mid - 1);
    tt[1] = n - 3;
    mul(t, tt, t);
    tt[1] = mid * 3;
    add(t, tt, t);
    tt[1] = n;
    sub(t, tt, t);
}

void solve()
{
    int l = 1, r = 4000, mid;
    LL t[M] = {0}, tt[M] = {1, 0};
    while (l < r)
    {
        mid = (l + r + 1) >> 1;
        sum(t, mid, tt);
        int cmp = compare(k, t);
        if (cmp == -1)
        {
            qpow(t, mid - 2);
            tt[1] = n - 1;
            mul(t, tt, t);
            tt[1] = 1;
            add(t, tt, t);
            print(t);
            return;
        }
        if (cmp)
            l = mid;
        else
            r = mid - 1;
    }
    sum(t, r, tt);
    sub(k, t, k);
    qpow(t, r);
    tt[1] = 2;
    sub(t, tt, t);
    add(k, t, t);
    print(t);
}
int main()
{
    while (scanf("%d", &n) == 1)
    {
        memset(k, 0, sizeof(k));
        if (n < 4)
        {
            scanf("%d", &m);
            if (n == 1)
            {
                if (m == 1)
                    printf("1\n");
                else
                    printf("-1\n");
            }
            else if (n == 2)
            {
                if (m < 3)
                    printf("%d\n", m);
                else
                    printf("-1\n");
            }
            else if (n == 3)
            {
                qpow(k, (m + 2) / 3);
                if (m % 3 == 1)
                    k[1]--;
                else if (m % 3 == 0)
                    k[1]++;
                print(k);
            }
        }
        else
        {
            scanf("%s", ch);
            toBigInt(ch, k);
            if (k[0] == 1 && k[1] <= n)
                print(k);
            else
                solve();
        }
    }
    return 0;
}

【190730】计蒜客 SEERC 2018

2019-07-30

目录

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

using namespace std;

const int N = 200000 + 5;

int x[N], y[N];

struct man
{
    int x, id;
    bool operator<(const man &b) const
    {
        return x < b.x;
    }
};
man b[N];
vector<int> v;
int f[N], ans[N];

int main()
{
    int n, m, l;
    scanf("%d%d%d", &n, &m, &l);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &x[i], &y[i]);
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &b[i].x);
        v.push_back(b[i].x);
        b[i].id = i;
    }
    sort(v.begin(), v.end());
    sort(b, b + m);
    for (int i = 0; i < n; i++)
    {
        if (y[i] > l)
            continue;
        int d = l - y[i];
        int lx = x[i] - d, rx = x[i] + d;
        int lid = lower_bound(v.begin(), v.end(), lx) - v.begin();
        int rid = upper_bound(v.begin(), v.end(), rx) - v.begin();
        f[lid]++;
        f[rid]--;
    }
    for (int i = 0; i < m; i++)
        f[i + 1] += f[i];
    for (int i = 0; i < m; i++)
        ans[b[i].id] = f[i];
    for (int i = 0; i < m; i++)
        printf("%d\n", ans[i]);
    return 0;
}

B题

按奇偶分类推公式，再考虑三指针长度相同、两相同、各不同。

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

using namespace std;

typedef unsigned long long ULL;

ULL s2(ULL x)
{
    ULL y = x + 1;
    if (x & 1)
        y /= 2;
    else
        x /= 2;
    return x * y;
}

ULL s3(ULL n)
{
    ULL f[3] = {n, n + 1, 2 * n + 1};
    for (int i = 0; i < 3; i++)
        if (f[i] % 2 == 0)
        {
            f[i] /= 2;
            break;
        }
    for (int i = 0; i < 3; i++)
        if (f[i] % 3 == 0)
        {
            f[i] /= 3;
            break;
        }
    return f[0] * f[1] * f[2];
}

ULL solve(ULL n)
{
    if (n & 1)
    {
        n /= 2;
        return s3(n);
    }
    else
    {
        n /= 2;
        n--;
        return 3 * s2(n) + s3(n);
    }
}

int main()
{
    int a[4];
    ULL n;
    for (int i = 0; i < 3; i++)
        scanf("%d", &a[i]);
    scanf("%llu", &n);
    ULL ans = solve(n);
    sort(a, a + 3);
    int d = unique(a, a + 3) - a;
    if (d == 2)
        ans *= 3;
    else if (d == 3)
        ans *= 6;
    printf("%llu\n", ans);
}

I题

拓扑序DP。

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100+10;
ll dp[maxn];
int g[maxn][maxn];
int n,m,u,v;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0; i<=n+1; ++i)
        memset(g[i],0,sizeof(g[i]));
    memset(dp,0,sizeof(dp));
    for(int i=0; i<m; ++i)
    {
        scanf("%d%d",&u,&v);
        g[u][v]=1;
        g[v][u]=1;
    }
    dp[0]=1;
    for(int i=1; i<=n+1; ++i)
    {
        for(int j=0; j<i; ++j)
        {
            if(g[i][j]) continue;
            int flag=1;
            for(int k=j+1; k<i; ++k)
            {
                if(!g[i][k]&&!g[j][k])
                {
                    flag=0;
                    break;
                }
            }
            dp[i]+=dp[j]*flag;
        }
    }
    printf("%lld\n",dp[n+1]);
    return 0;
}

C题

枚举树直径，检验条件并更新最小值。

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

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 105;
bool color[N];
int d[N][N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d", &color[i]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            d[i][j] = i == j ? 0 : INF;
    int x, y;
    for (int i = 0; i < n - 1; i++)
    {
        scanf("%d%d", &x, &y);
        d[x - 1][y - 1] = d[y - 1][x - 1] = 1;
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    int ans = INF;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            if (color[i] && color[j])
            {
                int cnt = 0, t = d[i][j];
                for (int k = 0; k < n; k++)
                    if (color[k] && d[i][k] <= t && d[k][j] <=t)
                        cnt++;
                if (cnt >= m)
                    ans = min(ans, t);
            }
    printf("%d\n", ans);
    return 0;
}

F题

有解当且仅当B相邻合并后为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
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
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
struct ddd
{
    int x,l,r;
};
ddd e[maxn];
int a[maxn],b[maxn],pos[maxn];
int n,cnt=0,now=1,ans=0;
char ch[maxn*2];
int L[maxn*2],R[maxn*2];
void add(char c, int l, int r)
{
    if(l>=r) return;
    ch[ans]=c;
    L[ans]=l;
    R[ans]=r;
    ++ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
    for(int i=1; i<=n; ++i) scanf("%d",&b[i]);
    now=1;
    for(int i = 1;i <= n;i++)
    {
        while(now <= n && a[now] != b[i]) ++now;
        if(now > n)
        {
            printf("-1\n");
            return 0;
        }
        pos[i] = now;
    }
    now=1;
    cnt=0;
    for(int i = 1;i <= n;i++)
    {
        if(pos[i] == pos[i+1]) continue;
        e[cnt++] = (ddd){pos[i], now, i};
        now = i + 1;
    }
    ans=0;
    for(int i=cnt-1; i>=0; --i)
    {
        if(e[i].x >= e[i].l) continue;
        if(a[e[i].x] >= a[e[i].x+1])
        {
            add('m', e[i].x+1, e[i].r);
            add('M', e[i].x, e[i].r);
        }
        else
        {
            add('M', e[i].x+1, e[i].r);
            add('m', e[i].x, e[i].r);
        }
    }
    for(int i=0; i<cnt; ++i)
    {
        if(e[i].x <= e[i].r) continue;
        if(a[e[i].x] <= a[e[i].x-1])
        {
            add('M', e[i].l, e[i].x-1);
            add('m', e[i].l, e[i].x);
        }
        else
        {
            add('m', e[i].l, e[i].x-1);
            add('M', e[i].l, e[i].x);
        }
    }
    for(int i=0; i<cnt; ++i)
    {
        if(e[i].l > e[i].x || e[i].r < e[i].x) continue;
        if(e[i].x > e[i].l)
        {
            if(a[e[i].x] >= a[e[i].x-1])
            {
                add('m', e[i].l, e[i].x-1);
                add('M', e[i].l, e[i].x);
            }
            else
            {
                add('M', e[i].l, e[i].x-1);
                add('m', e[i].l, e[i].x);
            }
        }
        if(e[i].x < e[i].r)
        {
            if(a[e[i].x] >= a[e[i].x+1])
            {
                add('m', e[i].x+1, e[i].r);
                add('M', e[i].x, e[i].r);
            }
            else
            {
                add('M', e[i].x+1, e[i].r);
                add('m', e[i].x, e[i].r);
            }
        }
    }
    printf("%d\n",ans);
    for(int i=0; i<ans; ++i)
        printf("%c %d %d\n",ch[i],L[i],R[i]);
    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
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <vector>
using namespace std;
const int N = 200000 + 5;
vector<int> ans;
int u[N], v[N];
int k[N];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++)
            scanf("%d%d", &u[i], &v[i]);
        do
        {
            ans.clear();
            for (int i = 1; i <= n; i++)
                k[i] = rand() % 2;
            for (int i = 1;i <= m; i++)
                if (k[u[i]] == 0 && k[v[i]] == 1)
                    ans.push_back(i);
        } while (ans.size() <= m / 4);
        printf("%d\n", ans.size());
        int t = ans.back();
        ans.pop_back();
        for (int id : ans)
            printf("%d ", id);
        printf("%d\n", t);
    }
    return 0;
}

【190727】计蒜客 North America Qualifier 2018

2019-07-30

目录

B题

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
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
int lcm(int a,int b)
{
    int res = a*b/gcd(a,b);
    return res;
}
int main()
{

    int p,q,s;
    scanf(" %d %d %d",&p,&q,&s);
    if(lcm(p,q)<=s)
        printf("yes\n");
    else
        printf("no\n");
    return 0;
}

K题

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
#include<bits/stdc++.h>
using namespace std;
void solveE(string ss)
{
    string res="";
    char last=' ',cur=' ';
    int cnt = 1;
    for(int i=0;i<ss.length();i++)
    {
        cur = ss[i];
        if(last==' ')
        {
            res += cur;
            last = cur;
            continue;
        }
        else if(last==cur)
        {
            cnt++;
            continue;

        }
        else //last !=cur
        {

            res+=char(cnt+48);
            cnt = 1;
            res+=cur;
            last = cur;
        }
    }
    res+=char(cnt+48);
    cout<<res<<endl;
}
void solveD(string ss)
{
    string res="";
    char last=' ',cur=' ';
    int cnt;
    for(int i=0;i<ss.length();i++)
    {
        cur = ss[i];
        if(last==' ')
        {
            res += cur;
            last = cur;
        }
        else if(isdigit(cur))
        {
            cnt = int(cur-49);//因为已经算了一个了
            while(cnt--)
                res+=last;
            continue;
        }
        else
        {
            res += cur;
            last = cur;
            continue;
        }
    }
    cout<<res<<endl;

}
int main()
{
    char flag;//E or D
    string ss;
    cin>>flag>>ss;
    if(flag=='E')
    {
        solveE(ss);
    }
    else if(flag=='D')
    {
        solveD(ss);
    }
    return 0;
}

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100+20;
int ans[maxn][10][10];
int n;
bool  check(int a,int b,int rowa,int rowb,int num)//要检测其他的数据能否让其他的行先赢,哪怕是同时赢也可以字典序最小
{
    set<int> temp;
    for(int j=1;j<=5;j++)
    {
        if(ans[a][rowa][j]!=num)
            temp.insert(ans[a][rowa][j]);
        if(ans[b][rowb][j]!=num)
            temp.insert(ans[b][rowb][j]);
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=5;i++)
        {
            bool flag = true;
            for(int j=1;j<=5;j++)
            {
                if(temp.count(ans[k][i][j]))
                {
                    continue;
                }
                else
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
                return false;//no tie
            else
                continue;
        }
    return true;
}
int main()
{
    cin>>n;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=5;i++)
            for(int j=1;j<=5;j++)
                cin>>ans[k][i][j];
    for(int a=1;a<=n;a++)
        for(int b=a+1;b<=n;b++)
        {
            int num;
            for(int i=1;i<=5;i++)
                for(int j=1;j<=5;j++)
                {
                    num = ans[a][i][j];
                    for(int row=1;row<=5;row++)
                        for(int col=1;col<=5;col++)
                            if(ans[b][row][col]==num)
                            {
                                if(check(a,b,i,row,num))
                                {
                                    cout<<a<<" "<<b<<endl;
                                    return 0;
                                }
                            }
                }

        }
    cout<<"no ties"<<endl;
    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
//维护RR之间的逆序区间，逆序输出
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+20;
int n;
char ss[maxn];
int maxx = 1,num=1;//R自己本来算一个
inline void out(int x) {
    if(x>9) out(x/10);
    putchar(x%10+'0');
}
int main()
{
    scanf("%d",&n);
    scanf("%s",ss);

    for(int i=0;i<n;i++)
    {
        if(ss[i]=='R')
        {
            for(int k=1;k<=num;k++)
            {
                out(maxx-k+1);
                putchar('\n');
            }
            maxx++;
            num=1;//维护从上一次的最左边的L然后到这一次的R的数量
        }
        else
        {
            num++;
            maxx++;
        }
        if(i==n-2)//总共就这么多个
        {
            for(int k=1;k<=num;k++)
            {
                out(maxx-k+1);
                putchar('\n');
            }
        }
    }
    return 0;
}

L题

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
//对于每一行我需要知道每一个数据被填入的位置
//遍历每一行
//对于每一列我需要知道这一列中已经出现了哪些值,还可以填入什么
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100+10;
bool visc[maxn][maxn];//表示第j列k是否出现过
bool visr[maxn];//当前行是否出现过
bool vis[maxn];//匹配，表示当前数据是否在当前列被匹配过
int res[maxn][maxn];
int pos[maxn];//每一行出现的位置,用于调整
int n,k;
//首先要检查一遍
bool dfs(int row,int col)//匹配每一行
{
    for(int ans = 1;ans<=n;ans++)
    {
        if(!vis[ans]&&!visc[col][ans])
        {
            vis[ans] = true;//匹配数,并不是行数据，而是预备数据
            if(!visr[ans]||dfs(row,pos[ans]))
               {
                   res[row][col] = ans;
                   pos[ans] = col;
                   visr[ans] =true;
                   return true;
               }
        }

    }
    return false;

}
void solve()
{
    for(int row = k+1;row<=n;row++)
    {
        memset(pos,-1,sizeof(pos));
        memset(visr,false,sizeof(visr));
        for(int col = 1;col<=n;col++)
        {
            memset(vis,false,sizeof(vis));//关键就是这里，在这一次匹配的时候记录已经尝试过的方案
            dfs(row,col);
        }
        for(int col=1;col<=n;col++)
        {
            visc[col][res[row][col]] = true;//第col列这个数是否出现过
        }
    }
    for(int i = 1;i<=n;i++)
       {
           for(int j=1;j<=n;j++)
            {
                if(j!=n)
                printf("%d ",res[i][j]);
                else
                printf("%d\n",res[i][j]);
            }
       }
}
int main()
{

    memset(visc,false,sizeof(visc));
    scanf("%d%d",&n,&k);
    int flag =  false;//确定是否有解
    for(int i=1;i<=k;i++)
    {
        memset(pos,-1,sizeof(pos));
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&res[i][j]);
            if(visc[j][res[i][j]]==true)
                flag = true;
            else
                visc[j][res[i][j]] = true;
            if(pos[res[i][j]]!=-1)
                flag = true;
            else
                pos[res[i][j]] = j;
        }
    }
    if(flag == true)
    {
        printf("no\n");
    }
    else
    {
        printf("yes\n");
        solve();
    }
    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
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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
//每次行动之前都清空数组然后，只要能计算下一次的位置就好了,注意会有新的车子出来
//每一次移动前都把下一次的障碍区设置好了，然后看是否会撞到，无非就是更新障碍区
//每次维护每一行最左边的那一个的位置就好了
//只要超过了间隔就更新这一行最左边的那个，最上面是从左往右
//从右往左更新最右边的那个
//点灯的时候记住边界
//说白了就是起始点变化的等差数列
#include<bits/stdc++.h>
using namespace std;//第一行从左往右
const int maxl = 10+10;
const int maxw = 20+10;
 int l,w;//行数，列数
 struct point
{
    int x,y;
};

struct Lane
{

    int start_point;
    int interval;
    int speed;
}lane[maxl];
bool g[maxl][maxw];
int pos[maxl];//每条跑道最边上的那个车子在哪
void gen_map()//从上到下更新map
{
    for(int i=0;i<l;i++)
    {
        int start_point , speed , interval;
        start_point = pos[i];
        speed = lane[i].speed;
        interval= lane[i].interval;
        int cur_point,last_point;
        int cnt ;//用来遍历和计时
        if(i%2==0)//偶数从左到右,反向点灯
        {

            start_point += speed;//得到当前位置
            while(start_point>=interval)//维护最小值,
            {
                pos[i] = start_point - interval;
                start_point = pos[i];
//                cout<<i<<"p\t"<<pos[i]<<endl;
            }
            pos[i] = start_point;
//            cout<<i<<"p\t"<<pos[i]<<endl;
            last_point = cur_point = start_point;
            while(last_point-speed < w )
            {
//                cout<<i<<"l\t"<<last_point<<endl;
                cnt = speed;
                if(!(cur_point>=0&&cur_point<w))//防止speed为0的情况
                {
                }
                else
                    g[i][cur_point] = true;
                while(cnt)
                {
                    if(!(cur_point>=0&&cur_point<w))
                        {
                            --cur_point;
                            --cnt;
                            continue;
                        }
                    g[i][cur_point] = true;
                    --cur_point;
                    --cnt;
                }
                last_point+=interval;
                cur_point=last_point;
            }
        }
        else
        {
            start_point-=speed;
            while(w-start_point-1>=interval)//出现新的车子了
            {
                pos[i] = start_point+interval;
                start_point = pos[i];
//                cout<<i<<"\t"<<pos[i]<<endl;
            }
            pos[i] = start_point;//维护最小值
//            cout<<i<<"\t"<<pos[i]<<endl;
            last_point = cur_point = start_point;
            while(last_point+speed>=0)
            {
                if(!(cur_point>=0&&cur_point<w))//防止speed为0的情况
                {
                }
                else
                    g[i][cur_point] = true;

                cnt = speed;
                while(cnt)
                {
                    if(!(cur_point>=0&&cur_point<w))
                    {
                        --cnt;
                        ++cur_point;
                        continue;
                    }
                    g[i][cur_point] = true;
                    ++cur_point;
                    --cnt;
                }
                last_point-=interval;
                cur_point =last_point;
            }
        }
    }

}
point get_cur_pos(char dir,point last_pos)
{
    point cur_pos;
    if(dir == 'U')
    {
        cur_pos.x = last_pos.x+1 ;
        cur_pos.y = last_pos.y ;
    }
    else if(dir == 'D')
    {
        cur_pos.x =last_pos.x-1 ;
        cur_pos.y = last_pos.y;
    }
    else if(dir == 'L')
    {
        cur_pos.x =last_pos.x ;
        cur_pos.y = last_pos.y-1;
    }
    else if(dir == 'R')
    {
        cur_pos.x =last_pos.x ;
        cur_pos.y = last_pos.y+1;
    }
    return cur_pos;

}

int main()
{
    int o,i,s;//每一行o,i,s表示第一辆车子的位置，车子之间的间隔，车子的速度
    int p;//表示青蛙开始的位置
    string ss;//表示青蛙的移动轨迹
    bool hit=false;
    cin>>l>>w;//奇数向右偶数向左
    for(int it=0;it<l;it++)
    {
        cin>>o>>i>>s;
        lane[it].interval = i;
        lane[it].start_point = o;
        lane[it].speed = s;
        if(it&1)
        {
            pos[it] = w-o-1;//偏移量

        }
        else
        {
            pos[it] = o;
        }
    }
    point frag;
    cin>>p>>ss;
    frag.x = -1;
    frag.y = p;
    for(int i=0;i<ss.length();i++)
    {
        char cur_dir = ss[i];//当前方向,更新地图
        memset(g,false,sizeof(g));
        gen_map();
        frag = get_cur_pos(cur_dir,frag);
        if(frag.x<0||frag.x>=l||frag.y<0||frag.y>=w)
            continue;
        else if(g[l-1-frag.x][frag.y])
        {
            hit = true;
            break;
        }
        else
        {
            continue;
        }
    }
    if(frag.x!=l)
        hit = true;
    if(hit)
        cout<<"squish"<<endl;
    else
        cout<<"safe"<<endl;
    return 0;
}

J题

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<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int a[5][5];
int point[2];
int d1[6][2]={-2,0,2,0,0,-2,0,2,2,2,-2,-2};
int d2[6][2]={-1,0,1,0,0,-1,0,1,1,1,-1,-1};
bool f(int x, int y)
{
    return x>=0 && x<5 && y>=0 && y<5 && x>=y;
}

int dfs(int flag)
{
    int endd=1;
    int maxx;
    if(flag==0) maxx=-INF;
    else maxx=INF;
    for(int x=0; x<5; ++x)
    {
        for(int y=0; y<=x; ++y)
        {
            if(a[x][y]) continue;
            for(int k=0; k<6; ++k)
            {
                int x1=x+d1[k][0];
                int y1=y+d1[k][1];
                int x2=x+d2[k][0];
                int y2=y+d2[k][1];
                if(f(x1,y1)&&f(x2,y2)&&a[x1][y1]&&a[x2][y2])
                {
                    endd=0;
                    int p1=a[x1][y1];
                    int p2=a[x2][y2];
                    a[x][y]=p1;
                    a[x1][y1]=0;
                    a[x2][y2]=0;
                    point[flag]+=p1*p2;
                    int t=dfs(1-flag);
                    if(flag==0) maxx=max(maxx,t);
                    else maxx=min(maxx,t);
                    a[x][y]=0;
                    a[x1][y1]=p1;
                    a[x2][y2]=p2;
                    point[flag]-=p1*p2;
                }
            }
        }
    }
    if (endd)
        return point[0]-point[1];
    else
        return maxx;
}

int main()
{
    for (int i = 0; i < 5; ++i)
        for (int j = 0; j <= i; ++j)
            scanf("%d", &a[i][j]);
    printf("%d\n",dfs(0));
    return 0;
}

19-07-25 计蒜客

2019-07-26

目录

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
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
//优先级按照礼物大小和时间来定
#include<bits/stdc++.h>
using namespace std;
const int maxs = 200+10;
const int maxq = 100+10;
const int maxk = 150000+10;
const int inf =0x7fffffff;
int T,k,m,q;//k是朋友的数量,m是打开m次，q是q次查询
int t,p;//第l个朋友来的时候放进来p个人
string ans[maxk];//这样是很浪费时间的
int query[maxq];
struct node
{
    string name;
    int time;//时间戳
    int value;
    friend bool operator < (node a,node b)//这里要和自己所想的相反
    {
        if(a.value==b.value)
            return a.time > b.time;
        else
            return a.value < b.value;
    }
    node(){}
    node(string  name ,int time,int value)
        {
            this->name = name;
            this->value = value;
            this->time  = time;
        }
};
struct open_gate
{
    int time;
    int number;
};
priority_queue<node> que;
node data[maxk];//记录朋友
open_gate open[maxk];//记录打开的次数
bool cmp1(open_gate a, open_gate b)
{
    return a.time<b.time;
}
int main()
{
    cin.tie(0);
    std::ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
        while(!que.empty()) que.pop();
        string name;
        int value;
        int n;
        cin>>k>>m>>q;
        for(int i=1;i<=k;i++)
        {
            cin>>name>>value;
            data[i] = node(name,i,value);
        }
        for(int i=1;i<=m;i++)
        {
            cin>>t>>p;
            open[i].time =t;
            open[i].number = p;
        }
        for(int i=1;i<=q;i++)
        {
            cin>>n;
            query[i] = n;
        }
    sort(open+1,open+m+1,cmp1);//保证升序
    int it = 0;
    int order = 0;
    int time ,number ;
    for(int i=1;i<=m;i++)
    {
        time = open[i].time;
        number = open[i].number;
        while(it<time)
        {
            que.push(data[++it]);
        }
        while(number--)
        {
            if(que.empty())//太毒瘤了。。这。。
                break;
            ans[++order] = que.top().name;
            que.pop();
        }
    }
    while(it<k)
        que.push(data[++it]);
    while(!que.empty())
    {
        ans[++order] = que.top().name;
        que.pop();
    }
    for(int i=1;i<=q;i++)
    {
        cout<<ans[query[i]];
        if(i!=q)
            cout<<" ";
        else
            cout<<endl;
    }
    }
    return 0;
}

B题 暴力

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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4+10;//边数
const int maxm = 1e5+10;//点数
vector<int> edge[maxn],connect_part;
int vis[maxn],vis1[maxn];//两个dfs
int t,n,m,u,v;
ll value[maxn];
void ini()//边不用clear
{
    memset(vis,false,sizeof(vis));
    memset(vis1,false,sizeof(vis1));
}
bool judge(int from)
{
    int ans =0;
    for (auto to : edge[from] )
    {
        if(!vis[to])//没有被销毁,应该与顺序无关
        {
            ans++;
        }
    }
    return ans<2;//less than
}
void dfs(int from)
{
    vis[from] = true;
    for(auto to : edge[from])
    {
        if(!vis[to]&&judge(to))
        {
            dfs(to);
        }
    }
}
void dfs1(int from)//计算数目
{
    vis1[from] = true;
    for(auto to :edge[from])
    {
        if(!vis[to]&&!vis1[to])
        {
            connect_part.push_back(to);
            dfs1(to);
        }
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        ini();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%lld",&value[i]);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&judge(i))//遍历每一个联通快
                dfs(i);
        }
        for(int i=1;i<=n;i++)
        {
            if(vis[i])
                continue;
            else if(!vis1[i])//联通块为奇数
                {
                    connect_part.clear();
                    connect_part.push_back(i);
                    dfs1(i);
                    if(connect_part.size()%2==0)
                    {
                        for(auto to : connect_part)//挺好玩的
                            vis1[to] = 2;
                    }
                }
        }
        ll res = 0;
        for(int i=1;i<=n;i++)
        {
            if(vis[i])//虽然肯定不会有
                continue;
            if(vis1[i]==1)
            {
                res += value[i];
            }
        }
        printf("%lld\n",res);
        for(int i=1;i<=n;i++)
            edge[i].clear();
    }

}

注意清空数组，注意数据范围long long

G题

RMQ板子

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
#include<bits/stdc++.h>
#define root 1,n,1
#define lson(x) x<<1
#define rson(x) x<<1|1
#define lroot l,mid,lson(p)
#define rroot mid+1,r,rson(p)
using namespace std;
const int maxn = 1e3+10;
const int inf =0x7fffffff;
int tree[(maxn<<2)+10];
int a[maxn];
int t,n,q,l,r;
void push_up(int p)
{
    tree[p] = max(tree[lson(p)],tree[rson(p)]);
    return ;
}
void build_tree(int l,int r,int p)
{
    if(l==r)
    {
        tree[p] = a[l];
        return ;//关键
    }
    int mid = l + ((r-l)>>1);
    build_tree(lroot);
    build_tree(rroot);
    push_up(p);
}
int query(int x,int y,int l,int r,int p)
{
    int res = -inf;
    if(x<=l&&y>=r)//子集
    {
        return tree[p];
    }
    int mid = l+((r-l)>>1);
    if(x<=mid) res = max(res,query(x,y,lroot));
    if(y>mid) res = max(res,query(x,y,rroot));
    return res;
}

int main()
{
    scanf(" %d",&t);
    while(t--)
    {
        scanf(" %d",&n);
        for(int i=1;i<=n;i++)
            scanf(" %d",&a[i]);
        build_tree(root);
        scanf(" %d",&q);
        for(int i=1;i<=q;i++)
        {
            scanf("%d %d",&l,&r);
            printf("%d\n",query(l,r,root));
        }
    }

}

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
//并查集建立联同
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 20000+10;
const int maxm =100000+10;
const int maxq = 5000+10;
int f[maxn];
ll cnt[maxn];
int t,n,m,q,u,v,w;
struct EDGE
{
    int from,to,cost;
    bool friend operator<(EDGE a,EDGE b)
    {
        return a.cost<b.cost;
    }
};
EDGE edge[maxm];
struct query
{
    int time;
    ll res;
    int ques;
}ans[maxq];
void ini()
{
    for(int i=1;i<=n;i++)
        {
            f[i] = i;
            cnt[i] = 1;
        }

}
int getf(int x)
{
    return x==f[x]?x:f[x]=getf(f[x]);
}
void merge(int x,int y)
{
    int t1 = getf(x), t2=getf(y);
    if(t1==t2)
    {
        return ;
    }
    else//可以合并
    {
        f[t2]= t1;
        cnt[t1] += cnt[t2];
        cnt[t2] = 0;
        return ;
    }
}
bool cmp1(query a,query b)
{
    return a.ques<b.ques;
}
bool cmp2(query a,query b)
{
    return a.time<b.time;
}
ll get_ans(ll x)
{
    ll res = x*(x-1);//c(n,2)*2
    return res;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&q);
        ini();
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            edge[i].from = u;
            edge[i].to = v;
            edge[i].cost = w;
        }
        sort(edge+1,edge+m+1);
        for(int i=1;i<=q;i++)
           {
                scanf("%d",&ans[i].ques);
                ans[i].time = i;
           }
        sort(ans+1,ans+q+1,cmp1);
        int limit=-1;//cnt记录联同集
        int it=1;//用于遍历边数组
        int from,to;
        for(int i=1;i<=q;i++)
        {
            ll res = 0;
            limit = ans[i].ques;
            while(it<=m&&edge[it].cost<=limit)
            {
                from = edge[it].from;
                to = edge[it].to;
                merge(from,to);
                it++;
            }
            for(int j=1;j<=n;j++)
            {
                if(cnt[j]<=1)
                    continue;
                if(f[j]==j)
                {
                    res+=get_ans(cnt[j]);//只找爸爸
                }
            }
            ans[i].res = res;
        }
        sort(ans+1,ans+q+1,cmp2);
        for(int i=1;i<=q;i++)
            printf("%lld\n",ans[i].res);
    }
}

I

多重背包+二进制优化（可以看背包九讲）

注意清空tot，两次多重背包，首先找到最小容量然后根据最小容量找到最小卡车花销。

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
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x7fffffff;
const int maxn = 2000+10;
const int maxm = 2000+10;
const int maxp = 50000;
const int maxcost = 50000;
int tot = 0;//用于第一个DP打包
int n,m,p;
int T;
int t,u,v;
int x,y,z;
int cost[maxn];//体积占比
int value[maxn];//提供能量占比
int dp[maxp+200];
int  pack1()//计算最小需要的容量
{
    for(int i=0;i<=p+100;i++)
        dp[i] = inf;
    dp[0] = 0;//可行解,传递闭包
    for(int i=1;i<=tot;i++)
    {
        for(int j=p+100;j>=value[i];j--)
            {
                if(dp[j-value[i]]==inf)
                    continue;
                dp[j] = min(dp[j],dp[j-value[i]]+cost[i]);
            }
    }
    //能得到需求能量的前提下的最小花销,内部能量外部花销
    int min_v = inf;
    for(int i=p;i<=p+100;i++)
    {
        min_v = min(dp[i],min_v);
    }
    return min_v;

}
int pack2(int min_v)//计算最小容量的最小花销，最小花销不能过大
{
    memset(dp,0,sizeof(dp));//可以不装满
    for(int i=1;i<=tot;i++)
    {
        for(int j=maxcost;j>=cost[i];j--)
        {
            dp[j] = max(dp[j],dp[j-cost[i]]+value[i]);
        }
    }
    //这里是满足容量下的最小花销，内部花销外部容量
    for(int i=1;i<=maxcost;i++)
        if(dp[i]>=min_v)
            return i;//最小花销
    return inf;

}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&p);
        tot = 0;//初始化操作
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&t,&u,&v);
            for(int k=1;v;k<<=1)
            {
                int num = min(k,v);
                cost[++tot] = num*u;
                value[tot] = num*t;
                v -= num;
            }
        }
        int min_v = pack1();//最小容量
        tot = 0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            for(int k=1;z;k<<=1)
            {
                int num = min(k,z);
                cost[++tot] = num*y;//所需要的花销
                value[tot] = num*x;//能提供的体积
                z-= num;
            }
        }
        if(min_v==inf)
            {
                printf("TAT\n");
                continue;
            }
        int ans = pack2(min_v);
        if(ans==inf)
            {
               printf("TAT\n");
               continue;
            }
        else
            printf("%d\n",ans);

    }
    return 0;
}

【补题】18年多校3

2019-04-29

目录

Euler Function

Description

Giving an integer $k$, your task is to find the $k-th$ smallest positive integer $n$, that $\phi(n)$ is a composite number.

Solution

由$gcd(n,\ k)=gcd(n,\ n-k)$，易得$n>2$时$\phi(n)$为偶数，则不难证明当$n\le 7$时，$\phi(n)$恒为合数。

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

int main()
{
    int T;
    scanf("%d", &T);
    for (int tt = 1; tt <= T; tt++)
    {
        int k;
        scanf("%d", &k);
        printf("%d\n", k == 1 ? 5 : 5 + k);
    }
    return 0;
}

Grab The Tree

Description

Giving an integer $k$, your task is to find the $k-th$ smallest positive integer $n$, that $\phi(n)$ is a composite number.

Solution

由$gcd(n,\ k)=gcd(n,\ n-k)$，易得$n>2$时$\phi(n)$为偶数，则不难证明当$n\le 7$时，$\phi(n)$恒为合数。

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

int main()
{
    int T;
    scanf("%d", &T);
    for (int tt = 1; tt <= T; tt++)
    {
        int k;
        scanf("%d", &k);
        printf("%d\n", k == 1 ? 5 : 5 + k);
    }
    return 0;
}

【补题】18年多校2

2019-04-18

目录

Game

Description

Alice and Bob are playing a game.
The game is played on a set of positive integers from 1 to $n$.

In one step, the player can choose a positive integer from the set, and erase all of its divisors from the set. If a divisor doesn’t exist it will be ignored.

Alice and Bob choose in turn, the one who cannot choose (current set is empty) loses.
Alice goes first, she wanna know whether she can win. Please judge by outputing Yes or No.

Solution

考虑$n>1$时先手取1等价于互换先后手，故Alice必胜。

1
2
3
4
5
6
7
8
9
#include <cstdio>

int main()
{
    int n;
    while (scanf("%d", &n) == 1)
        printf("Yes\n");
    return 0;
}

Swaps and Inversions

Description

Long long ago, there was an integer sequence a.
Tonyfang think this sequence is messy, so he will count the number of inversions in this sequence. Because he is angry, you will have to pay $x$ yuan for every inversion in the sequence.

You don’t want to pay too much, so you can try to play some tricks before he sees this sequence. You can pay $y$ yuan to swap any two adjacent elements.
What is the minimum amount of money you need to spend?

Solution

交换相邻项使数组有序需要的最小次数等于逆序数。

故所求为逆序数$\ *min(x, y)$。逆序数使用归并排序求出。

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>

typedef long long LL;
const int MAXN = 100000 + 10;
int A[MAXN], B[MAXN];

LL min(LL x, LL y) { return x < y ? x : y; }

LL merge(int A[], int L[], int R[], int left, int right)
{
    int i = 0, j = 0, k = 0;
    LL res = 0;
    while (i < left && j < right)
    {
        if (L[i] <= R[j])
        {
            A[k++] = L[i++];
        }
        else
        {
            A[k++] = R[j++];
            res += left - i;
        }
    }
    while (i < left)
        A[k++] = L[i++];
    while (j < right)
        A[k++] = R[j++];
    return res;
}

LL merge_sort(int A[], int n)
{
    if (n < 2)
        return 0ll;
    int mid = n / 2;
    int *L = new int[mid];
    int *R = new int[n - mid];
    int i = 0;
    for (i = 0; i < mid; i++)
        L[i] = A[i];
    for (i = mid; i < n; i++)
        R[i - mid] = A[i];
    LL inv = merge_sort(L, mid);
    inv += merge_sort(R, n - mid);
    inv += merge(A, L, R, mid, n - mid);
    delete[] L;
    delete[] R;
    return inv;
}

int main()
{
    int n, x, y;
    while (scanf("%d%d%d", &n, &x, &y) == 3)
    {
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        LL ans = merge_sort(A, n);
        ans *= min(x, y);
        printf("%lld\n", ans);
    }
    return 0;
}

【补题】18年多校1

2019-04-07

目录

Maximum Multiple

Description

Given an integer $n$, Chiaki would like to find three positive integers $x,\ y$ and $z$ such that: $n=x+y+z\ (1<n<10^6),\ x∣n,\ y∣n,\ z∣n$ and $xyz$ is maximum.

Solution

  1. $n<3$时，无解。

  2. $n|3$时，$max(xyz)=(n/3)^3$。

  3. $n|4$时，$max(xyz)=2(n/4)^3$。

  4. 其他时候，$x=y=z$显然不是解；不妨设$x<y$，可知$x\leq \frac{1}{5}n,\ y\leq\frac{1}{2}n$，显然也无解。

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

int main()
{
    int T;
    scanf("%d", &T);
    for (int tt = 1; tt <= T; tt++)
    {
        long long n;
        scanf("%lld", &n);
        if (n < 3)
            printf("-1\n");
        else if (n % 3 == 0)
            printf("%lld\n", n * n * n / 27);
        else if (n % 4 == 0)
            printf("%lld\n", n * n * n / 32);
        else
            printf("-1\n");
    }
    return 0;
}

Triangle Partition

Description

Chiaki has $3n,\ 1<n<1000$ points $p_1,\ p_2,\ …,\ p_{3n}$. It is guaranteed that no three points are collinear.

Chiaki would like to construct n disjoint triangles where each vertex comes from the $3n$ points.

Solution

贪心。按坐标从小到大排序，三个一组依次输出即可。

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

const int maxn = 1000 + 1;
struct P
{
    int x, y, id;
    bool operator<(const P& b) const
    {
        if (x != b.x)
            return x < b.x;
        else
            return y < b.y;
    }
};
P a[3 * maxn];

int main()
{
    int T;
    scanf("%d", &T);
    for (int tt = 1; tt <= T; tt++)
    {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < 3 * n; i++)
        {
            scanf("%d%d", &a[i].x, &a[i].y);
            a[i].id = i + 1;
        }
        sort(a, a + 3 * n);
        for (int i = 0; i < n; i++)
            printf("%d %d %d\n", a[3 * i].id, a[3 * i + 1].id, a[3 * i + 2].id);
    }
    return 0;
}

Time Zone

Description

Chiaki often participates in international competitive programming contests. The time zone becomes a big problem.

Given a time in Beijing time (UTC +8), Chiaki would like to know the time in another time zone s.

Solution

简单模拟。经由时间戳进行计算。

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

int main()
{
    int T;
    scanf("%d", &T);
    for (int tt = 1; tt <= T; tt++)
    {
        int x, y;
        double z;
        scanf("%d%d UTC%lf", &x, &y, &z);
        int sum = (x - 8) * 60 + y;
        if (z > 0)
            sum += int((z * 10 + 0.1) * 6);
        else
            sum += int((z * 10 - 0.1) * 6);
        if (sum < 0)
            sum += 1440;
        sum %= 1440;
        printf("%02d:%02d\n", sum / 60, sum % 60);
    }
    return 0;
}

Balanced Sequence

Description

Chiaki has $n$ strings $s_1,\ s_2,\ \dots,\ s_n$ consisting of ‘(‘ and ‘)’. A string of this type is said to be balanced:

  • if it is the empty string
  • if A and B are balanced, AB is balanced,
  • if A is balanced, (A) is balanced.

Chiaki can reorder the strings and then concatenate them get a new string t. Let $f(t)$ be the length of the longest balanced subsequence (not necessary continuous) of t. Chiaki would like to know the maximum value of $f(t)$ for all possible t.

Solution

首先对每个串进行处理，消除匹配后的串为左侧若干个右括号（数量记为r）和右侧若干个左括号（数量记为l）组成。

为了使括号匹配尽可能多而排列所有串。显然应将所有$l-r > 0$的串放在所有$l-r < 0$的串左侧。
对于$l-r > 0$的串，从左至右依次放置时，显然未匹配的左括号数L不断增大；故为尽可能匹配，应该将r小的串排在前面。
同理，对于$l-r < 0$的串，应将l大的串放在前面。

依上述策略排序，然后再处理一次，得到最后剩下未匹配括号的数量。

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

using namespace std;
const int MAXN = 100000 + 10;
char str[MAXN];
int cnt = 0;

struct Pair
{
    int id, l, r;
    int v;
    Pair(int id = 0, int l = 0, int r = 0) : id(id), l(l), r(r)
    {
        v = l - r;
    }
    bool operator<(const Pair &b) &
    {
        if (v >= 0 && b.v <= 0)
            return true;
        else if (v <= 0 && b.v >= 0)
            return false;
        else if (v > 0 && b.v > 0)
            return r < b.r;
        else if (v < 0 && b.v < 0)
            return l > b.l;
    }
}a[MAXN];

void analyse(char *s)
{
    int l = 0, r = 0;
    for ( ; *s; ++s)
    {
        if (*s == '(') //)
            l++;
        else if (l)
            l--;
        else
            r++;
    }
    a[cnt] = Pair(cnt, l, r);
    cnt++;
}

int solve(int n)
{
    sort(a, a + n);
    int L = 0, R = 0;
    for (int i = 0; i < n; i++)
    {
        if (L < a[i].r)
        {
            R += a[i].r - L;
            L = a[i].l;
        }
        else
        {
            L += a[i].v;
        }
    }
    return L + R;
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int tt = 1; tt <= T; tt++)
    {
        cnt = 0;
        int n;
        scanf("%d%d", &n);
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%s", str);
            sum += strlen(str);
            analyse(str);
        }
        printf("%d\n", sum - solve(n));
    }
    return 0;
}

Distinct Values

Description

Chiaki often participates in international competitive programming contests. The time zone becomes a big problem.

Given a time in Beijing time (UTC +8), Chiaki would like to know the time in another time zone s.

Solution

简。

Chiaki Sequence Revisited

Description

Chiaki is interested in an infinite sequence $a_1,\ a_2,\ a_3,\ …,$ which is defined as follows:

Chiaki would like to know the sum of the first n terms of the sequence, i.e. $\sum\limits_{i=1}^{n}a_i$. As this number may be very large, Chiaki is only interested in its remainder modulo (1e9+7).

Solution

通项难以通过化简得出，于是打表找规律。

观察发现数列从1开始递增，并且每个数字重复出现若干次数。不考虑$a_1$从第二项开始计数，则设数列$b_n$为数字n在$a_n$中出现的次数，不难得到 $b_{2^n}=n+1$，$b_{2^nk}=b_{2^n}=n+1$。

测试

2019-03-24

测试
test
テスト

这是为了测试各种东西的页面。

Item Value Qty
Computer 1600 USD 5
Phone 12 USD 12
Pipe 1 USD 234

a,b,c

$ fun^{10} \times int^{40}=Ir_2 $


玄学的行

© 2019 blog - Powered by Hexo - Theme Chan