首页 > 代码库 > Codeforces Round #277.5 解题报告

Codeforces Round #277.5 解题报告

2024-08-02 21:10:15   223人阅读

又熬夜刷了cf，今天比正常多一题，比赛还没完但我知道F过不了了，一个半小时贡献给F还是没过……应该也没人Hack，写写解题报告吧= =！

解题报告如下：


A题：选择排序直接搞，因为不要求最优交换次数，代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <memory.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>

using namespace std;

#define Clear(f, nr) memset(f, nr, sizeof(f))
const int SIZE = 3001;
const int MSIZE = 10000;
const int INF = 1 << 30;
typedef long long ll;
pair<int, int> p[SIZE];

int main() {
    int n;
    int a[SIZE];
    while(cin >> n) {
        for(int i = 0; i < n; i ++)
            cin >> a[i];
        int k = 0;
        for(int i = 0; i < n - 1; i ++) {
            int Mi = a[i];
            int mark = i;
            for(int j = i + 1; j < n; j ++) {
                if(a[j] < Mi) {
                    Mi = a[j];
                    mark = j;
                }
            }
            if(mark != i) {
                swap(a[i], a[mark]);
                p[k ++] = make_pair(i, mark);
            }
        }
        cout << k << endl;
        for(int i = 0; i < k; i ++)
            cout << p[i].first << " " << p[i].second << endl;
    }
}

B题：贪心思想，排序后从小到大匹配即可：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <memory.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>

using namespace std;

#define Clear(f, nr) memset(f, nr, sizeof(f))
const int SIZE = 500;
const int MSIZE = 10000;
const int INF = 1 << 30;
typedef long long ll;

int main() {
    int n, m;
    int a[SIZE], b[SIZE];
    while(cin >> n) {
        for(int i = 0; i < n; i ++)
            cin >> a[i];
        cin >> m;
        for(int i = 0; i < m; i ++)
            cin >> b[i];
        sort(a, a + n);
        sort(b, b + m);
        int sum = 0;
        bool vis[SIZE];
        Clear(vis, 0);
        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < m; j ++) {
                if(!vis[j] && abs(a[i] - b[j]) <= 1) {
                    vis[j] = 1;
                    sum ++;
                    break;
                }
            }
        }
        cout << sum << endl;
    }
}

C题：贪心思想，如果是最小值，除去第一位尽可能放0，第一位尽可能放1。同理，最大值尽可能放9

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <memory.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>

using namespace std;

#define Clear(f, nr) memset(f, nr, sizeof(f))
const int SIZE = 500;
const int MSIZE = 10000;
const int INF = 1 << 30;
typedef long long ll;


string gMi(int m, int s) {
    string ans;
    int tmp = s - 9 * (m - 1);
    if(tmp <= 0) {
        ans += '1';
        s -= 1;
    }
    else {
        ans += tmp + '0';
        s -= tmp;
    }
    for(int i = 1; i < m; i ++) {
        int tmp = s - 9 * (m - i - 1);
        if(tmp <= 0) {
            ans += '0';
        }
        else {
            ans += tmp + '0';
            s -= tmp;
        }
    }
    return ans;
}

string gMx(int m, int s) {
    string ans;
    for(int i = 0; i < m; i ++) {
        if(s >= 9) {
            ans += '9';
            s -= 9;
        }
        else {
            ans += s + '0';
            s = 0;
        }
    }
    return ans;
}

int main() {
    int m, s;
    while(cin >> m >> s) {
        if(s > 9 * m || (m != 1 && s == 0)) {
            puts("-1 -1");
            continue;
        }
        if(m == 1 && s == 0) {
            puts("0 0");
            continue;
        }
        string Mi = gMi(m, s);
        string Mx = gMx(m, s);
        cout << Mi << " " << Mx << endl;
    }
}

D题：读题花了好久，题目意思就是找菱形（4个点构成），思路就是dfs2层，对于最后一层如果x点的入度为y，则x点构成的菱形个数为y * (y - 1) / 2

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <memory.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>

using namespace std;

#define Clear(f, nr) memset(f, nr, sizeof(f))
const int SIZE = 3030;
const int MSIZE = 10000;
const int INF = 1 << 30;
typedef long long ll;

vector<int> path[SIZE];
ll ans;
int in[SIZE];

void dfs(int x, int root, int flag) {
    if(flag == 0) {
        if(x != root)
            in[x] ++ ;
        return ;
    }
    for(int i = 0; i < path[x].size(); i ++) {
        int son = path[x][i];
        dfs(son, root, flag - 1);
    }
    return ;
}

int main() {
    int n, m;
    int x, y;
    while(cin >> n >> m) {
        for(int i = 0; i < n; i ++)
            path[i].clear();
        for(int i = 0; i < m; i ++) {
            cin >> x >> y;
            x --,y --;
            path[x].push_back(y);
        }
        ans = 0;
        for(int i = 0; i < n; i ++) {
            Clear(in, 0);
            dfs(i, i, 2);
            for(int j = 0; j < n; j ++) {
                //printf("i:%d, j:%d -> %d\n", i, j, in[j]);
                if(in[j] >= 2)
                    ans += in[j] * (in[j] - 1) / 2;
            }
        }
        cout << ans << endl;
    }
}

E题：没读


F题：一看就是dp，没啥子思路，坐等大神上代码

Codeforces Round #277.5 解题报告


联系
我们