ZOJ Monthly, June 2014 月赛BCDEFGH题题解

比赛链接：点击打开链接

上来先搞了f、c，，然后发现状态不正确，一下午都是脑洞大开，，

无脑wa，无脑ce。。。一样的错犯2次。。

硬着头皮搞了几发，最后20分钟码了一下G，不知道为什么把1直接当成不能加油的站就会wa。。太弱。。

唔···太懒第二天才发题解。。

B:Gears

并查集

题解：点击打开链接

C:Consecutive Blocks

离散化一下然后模拟

题解：点击打开链接

D:An Easy Game

设dp[i][j]为前i个位置已经匹配了j个位置的方法数。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <queue>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>

using namespace std;

#define ll long long
#define mod 1000000009
#define N 105

int n, K, m;
int dp[N][N];
int C[N][N];
string s1;
string s2;

int dfs(int differ, int left) {
    if (left == 0) {
        return differ == 0;
    }
    else {
        if (~dp[differ][left]) {
            return dp[differ][left];
        }
        int &ans = dp[differ][left];
        ans = 0;
        int a = differ;
        int b = n - differ;
        for (int i = 0; i <= differ && i <= m; ++i) {
            if (b >= m - i) {
                ans += (int)((ll)C[b][m - i] * C[a][i] % mod * dfs(differ - i + (m - i), left - 1) % mod);
                ans %= mod;
            }
        }
        return ans;
    }
}

int main(){
    for (int i = 0; i < N; ++i) {
        C[i][i] = 1;
        for (int j = 0; j < i; ++j) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            C[i][j] %= mod;
        }
    }
    while (cin >> n >> K >> m){
        cin >> s1 >> s2;
        int nSum = 0;
        int nLen = s1.length();
        for (int i = 0; i < nLen; ++i) {
            if (s1[i] != s2[i]) {
                ++nSum;
            }
        }
        memset(dp, -1, sizeof(dp));
        int ans = dfs(nSum, K);
        printf("%d
", ans);
    }
    return 0;
}

E:Romantic Value

简单最小割。

题解：点击打开链接

F:First Digit

屌丝题。。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
int main()
{
    int T ,m,u,v,w; scanf("%d",&T);
    while(T--){ scanf("%d%d",&u,&v);puts("1"); }
    return 0;
}

G:Greedy Driver

spfa2次，，

题解：点击打开链接

H:Grouping

缩点拓扑序下求最长链

题解：点击打开链接