USACO測試賽2

D2ege. 奶牛唱歌

問題描述

一個鮮為人知的事實是，奶牛擁有自己的文字：「牛文」。牛文由 26 個字母 'a' 到 'z' 組成，但是當(dāng)奶牛說牛文時，可能與我們所熟悉的 'abcdefghijklmnopqrstuvwxyz' 不同，她會按某種特定的順序排列字母。

為了打發(fā)時間，奶牛 Bessie 在反復(fù)哼唱牛文字母歌，而 Farmer John 好奇她唱了多少遍。

給定一個小寫字母組成的字符串，為 Farmer John 聽到 Bessie 唱的字母，計算 Bessie 至少唱了幾遍完整的牛文字母歌，使得 Farmer John 能夠聽到給定的字符串。Farmer John 并不始終注意 Bessie 所唱的內(nèi)容，所以他可能會漏聽 Bessie 唱過的一些字母。給定的字符串僅包含他記得他所聽到的字母。

輸入格式

輸入的第一行包含 26 個小寫字母 'a' 到 'z' 的牛文字母表順序。下一行包含一個小寫字母組成的字符串，為 Farmer John 聽到 Bessie 唱的字母。字符串的長度不小于 1 且不大于 1000。

輸出格式

輸出 Bessie 所唱的完整的牛文字母歌的最小次數(shù)。

輸入樣例

abcdefghijklmnopqrstuvwxyz
mood

輸出樣例

3

樣例說明

在這個樣例中，牛文字母表與日常的字母表的排列一致。

Bessie 至少唱了三遍牛文字母歌。有可能 Bessie 只唱了三遍牛文字母歌，而 Farmer John 聽到了以下被標(biāo)記為大寫的字母。
abcdefghijklMnOpqrstuvwxyz
abcdefghijklmnOpqrstuvwxyz
abcDefghijklmnopqrstuvwxyz

測試點性質(zhì)

測試點 2-5 中，牛文字母表與日常的字母表相同。
測試點 6-10 沒有額外限制。

題解

判斷字母順序即可。

#include <bits/stdc++.h>
using namespace std;

int vhash[200];

int main()
{
    freopen("herd.in" , "r" , stdin);
    freopen("herd.out" , "w" , stdout);

    string dct;
    string res;
    cin >> dct >> res;

    for(int i = 0 ; i < dct.length() ; i ++)
        vhash[dct[i]] = i + 1;
    
    int cnt = 1 , pre = -1;

    for(int i = 0 ; i < res.length() ; i ++)
    {
        if(vhash[res[i]] > pre)
            pre = vhash[res[i]]; 
        else
            cnt ++ , pre = vhash[res[i]];
    }

    cout << cnt << endl;
    return 0;
}

D5b69. 照片分組

問題描述

Farmer John 正再一次嘗試給他的 N 頭奶牛拍照（2≤N≤1000）。

每頭奶牛有一個范圍在 1…100 之內(nèi)的整數(shù)的「品種編號」。Farmer John 對他的照片有一個十分古怪的構(gòu)思：他希望將所有的奶牛分為不相交的若干組（換句話說，將每頭奶牛分到恰好一組中）并將這些組排成一行，使得第一組的奶牛的品種編號之和為偶數(shù)，第二組的編號之和為奇數(shù)，以此類推，奇偶交替。

Farmer John 可以分成的最大組數(shù)是多少？

輸入格式

輸入的第一行包含 N。下一行包含 N 個空格分隔的整數(shù)，為 N 頭奶牛的品種編號。

輸出格式

輸出 Farmer John 的照片中的最大組數(shù)。可以證明，至少存在一種符合要求的分組方案。

輸入樣例

7
1 3 5 7 9 11 13

輸出樣例

3

樣例說明

在這個樣例中，以下是一種分成最大組數(shù)三組的方案。將 1 和 3 分在第一組，5、7 和 9 分在第二組，11 和 13 分在第三組。

輸入樣例

7
11 2 17 13 1 15 3

輸出樣例

5

樣例說明

在這個樣例中，以下是一種分成最大組數(shù)五組的方案。將 2 分在第一組，11 分在第二組，13 和 1 分在第三組，15 分在第四組，17 和 3 分在第五組。

題解

奇數(shù) + 奇數(shù) = 偶數(shù)
偶數(shù) + 偶數(shù) = 偶數(shù)

所以只要使得奇數(shù)偶數(shù)的數(shù)量相近，然后再構(gòu)成奇數(shù)和偶數(shù)即可。

#include <bits/stdc++.h>
using namespace std;

int cnt_a , cnt_b;

int main()
{
    // freopen("group.in" , "r" , stdin);
    // freopen("group.out" , "w" , stdout);

    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i ++)   
    {
        int tmp;
        cin >> tmp;
        if(tmp % 2 == 0)
            cnt_a ++;
        else 
            cnt_b ++;
    }

    while(cnt_b > cnt_a)
    {
        cnt_b -= 2;
        cnt_a ++;
    }

    if(cnt_a == cnt_b)
        cout << cnt_a + cnt_b;
    else
        cout << cnt_b * 2 + 1;

    return 0;
}

Dg9s3. 牛舍安排

問題描述

Farmer John 有 N 頭奶牛（1≤N≤20），高度為 a1…aN。他的牛欄有 N 個牛棚，高度限制分別為 b1…bN（例如，如果 b5=17，那么一頭高度不超過 17 的奶牛可以住在牛棚 5 里）。Farmer John 有多少種不同的方式安排他的奶牛，使得每頭奶牛均住在不同的牛棚里，并且使得每個牛棚的高度限制均得到滿足？

輸入格式

輸入的第一行包含 N。

第二行包含 N 個空格分隔的整數(shù) a1,a2,…,aN。

第三行包含 N 個空格分隔的整數(shù) b1,b2,…,bN。所有的高度和高度限制均在范圍
內(nèi)。

輸出格式

輸出 Farmer John 可以將每頭奶牛安排到不同的牛棚里，使得每個牛棚的高度限制均得到滿足的方法數(shù)。注意輸出的數(shù)量可能需要使用 64 位整數(shù)型，例如 C++ 中的 long long。

輸入樣例

4
1 2 3 4
2 4 3 4

輸出樣例

8

樣例說明

在這個例子中，我們不能將第三頭奶牛安排到第一個牛棚里，因為 3=a3>b1=2。類似地，我們不能將第四頭奶牛安排到第一或第三個牛棚里。一種符合高度限制的安排方式為將奶牛 1 安排到牛棚 1，奶牛 2 安排到牛棚 2，奶牛 3 安排到牛棚 3，奶牛 4 安排到牛棚 4。

測試點性質(zhì)

測試點 1-5 滿足 N≤8。
測試點 6-12 沒有額外限制。

題解

排列組合。
記錄合法的數(shù)量，再排除不合法的數(shù)量(用排序可以降低復(fù)雜度)。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 30;

int a[MAXN];
int b[MAXN];

int n , ans = 1;

signed main()
{
    freopen("stalling.in" , "r" , stdin);
    freopen("stalling.out" , "w" , stdout);

    cin >> n;
    for(int i = 1 ; i <= n ; i ++)  
        cin >> a[i];
    for(int i = 1 ; i <= n ; i ++)
        cin >> b[i];

    sort(a + 1 , a + 1 + n);

    for(int i = n ; i >= 1 ; i --)
    {
        int cnt = 0;

        for(int j = 1 ; j <= n ; j ++)
            if(b[j] >= a[i])
                cnt ++;
        
        cnt -= (n - i); //不合法排列數(shù)
        ans *= cnt;
    }

    cout << ans << endl;

    return 0;
}