Codeforces Round #277.5 解题报告

时间：2024-08-05 14:04:20

又熬夜刷了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题：看了别人的报告。

思路就是：记录每列1的个数。令nr0代表有多少列含有0个1，nr1代表有多少列含1个1。由于和位置无关。递推方程式：

for i,j:

  [i][j] += [i-2][j+2] * C(i,2)

  [i][j] += [i-1][j-1+1] * C(i,1)*C(j,1)

  [i][j] += [i][j-2] * C(j,2)

最后输出f[0][0]，代表所有填充完成

由于递推方程式不太好在循环中实现，就改为记忆化搜索，代码例如以下：

#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 = 502;

const int MSIZE = 10000;

const int INF = 1 << 30;

typedef long long ll;

ll rec[SIZE][SIZE];

int n, m, mod, x;

ll dp(int nr0, int nr1) {

    if(rec[nr0][nr1] != -1)

        return rec[nr0][nr1];

    if(nr0 == nr1 && nr0 == 0)

        return rec[0][0] = 1;

    ll ans = 0;

    if(nr0 >= 2) {

        ll tmp = dp(nr0 - 2, nr1 + 2) % mod;

        tmp = tmp * ((nr0 * (nr0 - 1)) / 2 % mod) % mod;

        ans = (ans + tmp) % mod;

    }

    if(nr1 >= 2) {

        ll tmp = dp(nr0, nr1 - 2) % mod;

        tmp = tmp * ((nr1 * (nr1 - 1)) / 2 % mod) % mod;

        ans = (ans + tmp) % mod;

    }

    if(nr1 >= 1 && nr0 >= 1) {

        ll tmp = dp(nr0 - 1, nr1);

        tmp = tmp * ((nr0 * nr1) % mod) % mod;

        ans = (ans + tmp) % mod;

    }

    return rec[nr0][nr1] = ans;

}

int main() {

    int col[SIZE];

    while(cin >> n >> m >> mod) {

        Clear(col, 0);

        Clear(rec, -1);

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

            for(int j = 0; j < n; j ++) {

                scanf("%1d", &x);

                col[j] += x;

            }

        int nr0 = 0, nr1 = 0;

        for(int j = 0; j < n; j ++) {

            if(col[j] == 0) nr0 ++;

            else if(col[j] == 1) nr1 ++;

        }

        cout << dp(nr0, nr1) << endl;

    }

}

相关文章