AtCoder Beginner Contest 218-ABCDEF 题解

https://atcoder.jp/contests/abc218/tasks

A - Weather Forecast

水题

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<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N=1e5+5;
const int M=1e5+5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int n,m;
int main(){
    //ios::sync_with_stdio(false);
    cin>>n;
    string s;
    cin>>s;
    if(s[n-1]=='o')cout<<"Yes";
    else{
        cout<<"No";
    }

    return 0;
}



B - qwerty

水题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N=1e5+5;
const int M=1e5+5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
inline ll read();
int n,m;
int a[30];
int main(){
    //ios::sync_with_stdio(false);
    for(int i=0;i<26;i++){
        cin>>a[i];
    }
    string s;
    for(int i=0;i<26;i++){
        s+=char(a[i]+'a'-1);
    }
    cout<<s;
    return 0;
}



C - Shapes

题意:

两个$NN$矩阵A,B都由和#构成,你可以对B进行任意次90度旋转(正逆时针都可)和对#图形进行整体的平移,如果最后B能和A完全一样输出Yes,否则输出No

题解:

枚举每一种有效的旋转(最多三次),然后每次都将A和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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 1e5 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

int n, m;
#define ll long long
#define INF 0x3f3f3f3f
const int maxn = 205;
char a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];
int cnt = 0;
map<pair<int, int>, int> ma;
vector<pair<int, int> > save1, save2;
bool ok = 0;

void check() {
    save1.clear();
    int mnr = INF, mnc = INF;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (c[i][j] == '#') {
                save1.push_back({i, j});
                mnr = min(mnr, i);
                mnc = min(mnc, j);
            }
        }
    for (int i = 0; i < save1.size(); i++) {
        save1[i].first -= mnr;
        save1[i].second -= mnc;
    }
    if (save1.size() != save2.size())return;
    for (auto it: save1) {
        if (!ma[it])return;
    }

    ok = 1;
}

void solve() {
    cin >> n;
    int mnr = INF, mnc = INF;
    for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> a[i][j], c[i][j] = a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> b[i][j];
            if (b[i][j] == '#') {
                save2.push_back({i, j});
                mnr = min(mnr, i);
                mnc = min(mnc, j);//找到最左上角的那个#
            }
        }
    for (int i = 0; i < save2.size(); i++) {
        save2[i].first -= mnr;//将所有#向左上角移
        save2[i].second -= mnc;
        ma[save2[i]] = 1;
    }
    for (int u = 0; u < 4; u++) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                c[j][n - i + 1] = a[i][j];
            }
        for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)a[i][j] = c[i][j];
        check();
    }

}

int main() {
    solve();
    if (ok)puts("Yes");
    else puts("No");
    return 0;
}


D - Rectangles

题意:

在二维平面上给n个坐标,求坐标能构成的所有平行于X,Y轴的矩形的数目.

题解:

以x坐标为基准,当y轴相等时,如果下一条边和这条边的长度、位置都相同,那就可以构成一个矩形.所以只需要枚举所有点,当两个点y坐标相同时记录下两点构成的线段的位置和长度,当下一次又出现同一位置和长度的线段时,就可以构成一个矩形… 以此类推.用一个map记录

代码:

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<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N=1e5+5;
const int M=1e5+5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
inline ll read();
int n,m;
int a[205][205];
int b[205][205];
vector<PII>v;
map<pair<ll,double > ,ll>cnt;
int main(){
    //ios::sync_with_stdio(false);
    ll ans=0;
    cin>>n;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        v.pb({x,y});
    }

    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++) {
            if (v[i].se == v[j].se) {
                ll len = abs(v[i].fi - v[j].fi);
                double xx = (v[i].fi + v[j].fi) * 1.0 / 2.0;
                ans += cnt[{len, xx}];
                cnt[{len, xx}]++;
            }
        }
    }
    cout<<ans;

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while(ch < '0' || ch > '9') {
        if(ch == '-')p = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}

E - Destruction

题意:

给一个无向图,让你从中选出几个边,要求选出的边权总和最大并且剩下的图要是一个连通图.

题解:

要选出的边权总和最大,那就是让剩下的连通图边权总和最小,我们可以很容易想到最小生成树.但直接跑最小生成树是不行的,因为它有负边权.而负边我们是肯定不会选的,所以我们只需要特判一下,只要我们在跑最小生成树只要碰到负边权我们就给把它放进图里.(这样虽然不是树了但可以保证我们得到正确的答案)

代码:

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

using namespace std;
#define ll long long
const int N = 200010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int p[N];

struct Edge {
    int a, b, w;

    bool operator<(const Edge &W) const //重载运算符以便于能直接sort
    {
        return w < W.w;
    }
} edges[M];

int find(int x) //并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

ll kruskal() {
    sort(edges, edges + m);

    for (int i = 1; i <= n; i++) p[i] = i;    // 初始化并查集

    ll res = 0, cnt = 0;
    for (int i = 0; i < m; i++) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)//找到的祖宗不相等说明不连通
        {
            p[a] = b;
            res += w;
            cnt++;
        }
        else {
            if (w < 0)res += w;
        }
    }

    return res;
}

int main() {
    ll sum = 0;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
        sum += w;
    }

    cout << sum - kruskal();


    return 0;
}

F - Blocked Roads

题意:

给定一个n个点,m条边的有向图,边权为1,对每个边i,求把这个边去掉的1-n的最短距离.

题解:

因为m最大是400399.所以不能直接枚举边bfs.但我们可以想到,对于1->n的最短路来说,最多应该只有n-1条边是有效的,所以我们可以先bfs求一遍正常的1->n的最短路,把有效的边标记出来.然后再枚举m条边,如果这条边没有被标记过,说明去不去掉它对1-n的最短距离没有影响,所以直接输出1-n的最短距离.否则,就再在原图上求一次去掉边i的bfs,时间复杂度是$O_{(N*(N+M))}$

代码:

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>

#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define PII pair<int,int>
#define PIII pair<pair<int,int>,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define debug(a) cout << #a << " " << a << '\n';
const int N = 500;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;

inline ll read();

int n, m;
vector<int> g[N*N];
int dis[N], dis2[N];
int pre[N];
bool st[N*N];
map<PII, int> mp;
map<int, PII > mp2;

void bfs() {
    memset(dis,-1,sizeof dis);
    queue<int> q;
    dis[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int t = q.front();

        q.pop();
        for (int i = 0; i < g[t].size(); i++) {
            int j = g[t][i];
            if (dis[j]!=-1)continue;
            dis[j] = dis[t] + 1;
            pre[j] = t;
            //cout<<j<<' '<<t<<'\n';
            q.push(j);
        }
    }
}

void bfs2(int x, int y) {
    queue<int> q;
    dis2[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int t = q.front();

        q.pop();
        for (int i = 0; i < g[t].size(); i++) {
            int j = g[t][i];
            if (t == x && j == y)continue;
            if (dis2[j] != -1)continue;
            dis2[j] = dis2[t] + 1;
            q.push(j);
        }
    }
}


int main() {
    //ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        mp[{a, b}] = i;
        mp2[i] = {a, b};
    }
    bfs();
    int now = n;
    while (true) {
        if (mp[{pre[now], now}]) {
            st[mp[{pre[now], now}]] = true;//标记有效边

        }
        now = pre[now];
        if (now == 1 || !now)break;
    }

    for (int i = 1; i <= m; i++) {
        if (!st[i])cout << dis[n] << '\n';
        else {
            memset(dis2, -1, sizeof dis2);
            int x = mp2[i].fi;
            int y = mp2[i].se;
            bfs2(x, y);

            cout << dis2[n] << '\n';
        }
    }

    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}