Codeforces Round #375 (Div. 2) ABCDE

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

A - The New Year: Meeting Friends

水

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

    int a,b,c;

    cin>>a>>b>>c;

    cout<<max(a,max(b,c)) - min(a,min(b,c)) <<endl;

    return ;

}

B - Text Document Analysis

字符串暴力模拟，感觉还是需要一点技巧的，我写的太慢了。

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <iostream>

using namespace std;

const int N = ;

char a[N];

//37

//_Hello_Vasya(and_Petya)__bye_(and_OK)

bool is_s(char ch) {

    if (ch == '_' || ch == '(' || ch == ')' || ch == ) return true;

    return false;

}

int read(char str[]) {

    int idx = ;

    int ans = ;

    while (!is_s(str[idx++])) ans++;

    return ans;

}

int main() {

    //freopen("in.txt", "r", stdin);

    int ans1 = , ans2 = , n = ;

    scanf("%d", &n);

    scanf("%s", a);

    bool fg = false;

    for (int i = ; i <= n;) {

        if (a[i] == '(') fg = true;

        if (a[i] == ')') fg = false;

        if (is_s(a[i])) {

            i++;

        } else {

            int tmp = read(a+i);

            if (!fg) ans1 = max(ans1, tmp);

            else ans2++;

            i += tmp;

        }

    }

    cout << ans1 << " " << ans2;

    return ;

}

C - Polycarp at the Radio

应该也是sb暴力题，map乱搞的(队友写的==

#include <cstdio>

#include <map>

#include <queue>

using namespace std;

const int maxn = ;

map<int, int> mp;

queue<int> q;

int a[maxn], n, m;

int main() {

    scanf("%d%d", &n, &m);

    for (int i = ; i <= n; i++) scanf("%d", &a[i]), mp[a[i]]++;

    int ans = n / m;

    for (int i = ; i <= m; i++) if (mp[i] < ans) q.push(i);

    int cnt = ;

    while (!q.empty()) {

        int v = q.front(); q.pop();

        for (int i = ; i <= n; i++) {

            if (a[i] > m || mp[a[i]] > ans) mp[a[i]]--, a[i] = v, mp[v]++, cnt++;

            if (mp[v] >= ans) break;

        }

    }

    printf("%d %d\n", ans, cnt);

    for (int i = ; i <= n; i++) printf("%d%c", a[i], i==n?'\n':' ');

    return ;

}

D - Lakes in Berland

简单搜索。因为数据小，随便暴力。

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

const int N = ;

char mp[N][N];

int vis[N][N], n, m, k;

int dir[][] = {, , , -, , , -, };

int dfs(int x, int y, int cnt) {

    if (x <  || x >= n || y <  || y >= m) return -;

    if (mp[x][y] == '*' || vis[x][y]) return ;

    vis[x][y] = cnt;

    int ans = ;

    for (int i = ; i < ; ++i) {

        int tmp = dfs(x+dir[i][], y+dir[i][], cnt);

        if (ans != -) {

            if (tmp == -) ans = -;

            else ans += tmp;

        }

    }

    return ans;

}

vector<pair<int, int> > g;

int main() {

    while (~scanf("%d%d%d", &n, &m, &k)) {

        for (int i = ; i < n; ++i) scanf("%s", mp[i]);

        int cnt = , tmp, ans = ;

        for (int i = ; i < n; ++i)

            for (int j = ; j < m; ++j)

                if (!vis[i][j] && mp[i][j] == '.')

                    if ((tmp = dfs(i, j, ++cnt)) != -) g.push_back(make_pair(tmp, cnt));

        sort(g.begin(), g.end());

        tmp = g.size() - k;

        for (int i = ; i < tmp; ++i) ans += g[i].first;

        printf("%d\n", ans);

        for (int k = ; k < tmp; ++k)

            for (int i = ; i < n; ++i)

                for (int j = ; j < m; ++j)

                    if (vis[i][j] == g[k].second) mp[i][j] = '*';

        for (int i = ; i < n; ++i) printf("%s\n", mp[i]);

    }

    return ;

}

E. One-Way Reform

给一个无向图，要求把每个边都变成有向边，使尽可能多的点入度等于出度，问最多能满足多少个点，并输出每条边。（任意顺序）

感觉很厉害的一道题。

无向图存在欧拉回路的充要条件：一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。

有向图存在欧拉回路的充要条件：一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。

首先可以知道奇数度的点是不可能到达要求的。找出奇数度的点，两两一对连接，记做虚边，这样就可以保证每个点的度数都是偶数，那么就可以找到一条欧拉回路，保证每个点入度等于出度。

因为总度数是偶数，所以奇数度的点一定是偶数个。

如果图不连通，对每一个连通图求欧拉回路就好了。

然后输出图中非虚边就ok了。

好难想到啊= =队友花了半天给我讲明白的……然后还是WA了好多好多次（我是有多蠢啊T^T

#include <bits/stdc++.h>

using namespace std;

const int N = ;

struct Edge {

    int next, from, to, fg; // fg: 0,2未处理 1选 -1不选

} e[N*N];

int head[N], cntE;

void addedge(int u, int v, int fg) {

    e[cntE].to = v; e[cntE].from = u;

    e[cntE].next = head[u]; e[cntE].fg = fg;

    head[u] = cntE++;

}

int deg[N];

void dfs(int u) {

    for (int i = head[u]; ~i; i = e[i].next) {

        if (e[i].fg == ) {

            e[i].fg = ;

            e[i^].fg = -;

            dfs(e[i].to);

        } else if (e[i].fg == ) {

            e[i].fg = e[i^].fg = -;

            dfs(e[i].to);

        }

    }

}

int main() {

    #ifndef ONLINE_JUDGE

       freopen("in.txt", "r", stdin);

    #endif // ONLINE_JUDGE

    int T, n, m, u, v;

    scanf("%d", &T);

    while (T--) {

        memset(head, -, sizeof head); cntE = ;

        memset(deg, , sizeof deg);

        scanf("%d%d", &n, &m);

        for (int i = ; i < m; ++i) {

            scanf("%d%d", &u, &v);

            addedge(u, v, );

            addedge(v, u, );

            deg[u]++, deg[v]++;

        }

        int last = , odd = ;

        for (int i = ; i <= n; ++i) {

            if (deg[i] & ) {

                ++odd;

                if (last) addedge(last, i, ), addedge(i, last, ), last = ;

                else last = i;

            }

        }

        for (int i = ; i <= n; ++i) dfs(i);

        printf("%d\n", n - odd);

        for (int i = ; i < cntE; ++i)

            if (e[i].fg == ) printf("%d %d\n", e[i].from, e[i].to);

    }

    return ;

}