程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ Monthly, June 2014 月賽BCDEFGH題題解

ZOJ Monthly, June 2014 月賽BCDEFGH題題解

編輯：C++入門知識

比賽鏈接：點擊打開鏈接

上來先搞了f、c，，然後發現狀態不對，一下午都是腦洞大開，，

無腦wa，無腦ce。。。一樣的錯犯2次。。

硬著頭皮搞了幾發，最後20分鐘碼了一下G，不知道為什麼把1直接當成不能加油的站就會wa。。太弱。。

唔···太懶第二天才發題解。。

B:Gears

並查集

題解：點擊打開鏈接

C:Consecutive Blocks

離散化一下然後模擬

題解：點擊打開鏈接

D:An Easy Game

設dp[i][j]為前i個位置已經匹配了j個位置的方法數。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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\n", ans);
    }
    return 0;
}

E:Romantic Value

簡單最小割。

題解：點擊打開鏈接

F:First Digit

屌絲題。。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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

縮點拓撲序下求最長鏈

題解：點擊打開鏈接