【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;
}
© 2019 blog - Powered by Hexo - Theme Chan