PAT甲級問題分類アセンブリ——その他

本文はPAT甲級分類アセンブリシリーズの文章である.
 
集合、ハッシュ、数学、アルゴリズム、これらの問題は比較的少ないので、一緒に話します.
タイトル番号
見出し
スコア
大意
を選択します.
1063
Set Similarity
25
集合類似度
しゅうごう
1067
Sort with Swap(0, i)
25
0番の要素と交換してソート
数学
1068
Find More Coins
30
サブセットと問題
アルゴリズム#アルゴリズム#
1070
Mooncake
25
リュックサックの問題
アルゴリズム#アルゴリズム#
1078
Hashing
25
ハッシュ＃ハッシュ＃
ハッシュ＃ハッシュ＃
1085
Perfect Sequence
25
制約に合致する最大数列の長さ
しゅうごう
1092
To Buy or Not to Buy
20
判定サブセット
しゅうごう
1093
Count PAT's
25
すうじれつ
数学
1063はstd::setの使用で、1092はもっと水で、この2つはしません.
 
集合-1085:
集合,表現方法は多種多様で,簡単な配列で表される並列調査集合,複雑なのは赤黒樹に基づくstd::setである.
しかし、私もその時整理している間にどのようにこの問題を集合に分けたのか分かりませんが、この問題がどのように分類されたのかは言いにくいです.問題は,入力データから最大のサブカラム(連続とは限らない)が最大値が最小値を超えない所定の倍数を満たすことを要求する.
実装方法は比較的簡単で,まずソートし,次いで各数について,その倍数を超える最初の数を見つけ,反復器を減算すると長さである.検索は2点で線形を使用できないため、タイムアウトします.

 1 #include 
 2 #include 
 3 #include 
 4 
 5 int main()
 6 {
 7     long num, para;
 8     std::cin >> num >> para;
 9     std::vector<long> data(num);
10     for (auto& i : data)
11         std::cin >> i;
12     std::sort(data.begin(), data.end());
13     int max = 0;
14     for (int i = 0; i != num; ++i)
15     {
16         if (i == 0 || data[i] != data[i - 1])
17         {
18             auto left = data.begin() + i;
19             auto right = data.end();
20             while (left < right)
21             {
22                 auto mid = left + (right - left) / 2;
23                 if (*mid > data[i] * para)
24                     right = mid;
25                 else
26                     left = mid + 1;
27             }
28             int length = right - data.begin() - i;
29             if (length > max)
30                 max = length;
31             if (right == data.end())
32                 break;
33         }
34     }
35     std::cout << max;
36 }

 
ハッシュ-1078:
ハッシュ知識を純粋に理論的に考察し,衝突を一方向二乗プローブ法で処理した.何も言うことはありませんが、標準的なハッシュです.データ構造の問題集にはhard versionがありますが、それは本当に難しいです.

 1 #include 
 2 #include 
 3 #include 
 4 
 5 bool is_prime(int _num)
 6 {
 7     if (_num == 1)
 8         return false;
 9     if (_num > 2 && _num % 2 == 0)
10         return false;
11     int end = std::sqrt(_num);
12     for (int i = 3; i <= end; i += 2)
13         if (_num % i == 0)
14             return false;
15     return true;
16 }
17 
18 int main(int argc, char const *argv[])
19 {
20     int m;
21     std::cin >> m;
22     while (!is_prime(m))
23         ++m;
24     std::vector<bool> hash(m);
25     int n;
26     std::cin >> n;
27     for (int i = 0; i != n; ++i)
28     {
29         try
30         {
31             int t;
32             std::cin >> t;
33             for (int j = 0; j != m; ++j)
34             {
35                 int h = (t + j * j) % m;
36                 if (hash[h] == 0)
37                 {
38                     hash[h] = 1;
39                     if (i > 0)
40                         std::cout << ' ';
41                     std::cout << h;
42                     throw 0;
43                 }
44             }
45             if (i > 0)
46                 std::cout << ' ';
47             std::cout << '-';
48         }
49         catch (...)
50         {
51             ;
52         }
53     }
54     return 0;
55 }

 
数学-1067:
一見、全く考えがない.普通のソートでこんなことをしたの?明らかに、この問題はソートを試験しないで、少し数学の知識が問題を転化する必要があります.
1つのシーケンスについて、値が位置の集合と等しい場合、必ずいくつかのリングを形成することができる.この問題で考慮しなければならないのは、一元環、すなわち、あるべき位置にある要素と、0がどのような環にあるかである.
自分でいくつかのデータを作ってみると、交換が必要な回数は次のとおりです.
0が0番の位置にある場合、シーケンス長+多重ループ個数-1元ループ個数(0を含む).
0番位置が0でない場合、シーケンス長+多重ループ個数-一元ループ個数-2.

 1 #include 
 2 #include 
 3 
 4 int main(int argc, char const *argv[])
 5 {
 6     int n;
 7     std::cin >> n;
 8     std::pair<int, bool> data[n];
 9     int loop = 0;
10     int single = 0;
11     for (auto& i : data)
12         std::cin >> i.first;
13     for (int i = 0; i != n; ++i)
14     {
15         if (data[i].second)
16             continue;
17         data[i].second = 1;
18         if (data[i].first == i)
19             ++single;
20         else
21         {
22             ++loop;
23             int t = data[i].first;
24             while (!data[t].second)
25                 data[t].second = 1, t = data[t].first;
26         }
27     }
28     if (data[0].first == 0)
29         std::cout << n + loop - single;
30     else
31         std::cout << n + loop - single - 2;
32 
33     return 0;
34 }

 
数学-1093:
要求数「PAT」の個数.一つ一つ数えるとタイムアウトになるに違いないが、さすがに問題では数が多いから型を取ると言っている.
正常なアルゴリズムも面倒ではありません.まず左から右へ遍歴し、「P」の数を数え、「A」に出会ったときに記録する.さらに右から左に遍歴し、「T」の数を数え、「A」に出会ったときに記録する.最後に遍歴して,'A'ごとに先ほど記録した数の積を計算して加算する.

#include 
#include <string>
#include 

int main()
{
    std::string str;
    std::cin >> str;
    std::vector<int> count_p(str.size());
    std::vector<int> count_t(str.size());
    long count = 0;
    for (int i = 0; i != str.size(); ++i)
        if (str[i] == 'P')
            ++count;
        else if (str[i] == 'A')
            count_p[i] = count;
    count = 0;
    for (int i = str.size() - 1; i >= 0; --i)
        if (str[i] == 'T')
            ++count;
        else if (str[i] == 'A')
            count_t[i] = count;
    count = 0;
    for (int i = 0; i != str.size(); ++i)
        if (str[i] == 'A')
            count += count_p[i] * count_t[i];
    count %= 1000000007;
    std::cout << count;
}

 
アルゴリズム-1070:
欲張りアルゴリズムは,データ構造のDijkstraに一言言及されたが,システムでは述べられていない.しかし、この問題のアルゴリズムはかなり明らかで、月餅ごとの単価を並べ替えて、高いから低いまで選択すればいい.

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 
 7 struct Mooncake
 8 {
 9     double weight;
10     double price;
11 };
12 
13 int main()
14 {
15     int num;
16     double demand;
17     std::cin >> num >> demand;
18     std::vector product(num);
19     for (auto& p : product)
20         std::cin >> p.weight;
21     for (auto& p : product)
22         std::cin >> p.price;
23     std::sort(product.begin(), product.end(), [](const Mooncake& lhs, const Mooncake& rhs) {
24         return lhs.price / lhs.weight > rhs.price / rhs.weight;
25     });
26     double total = 0;
27     double profit = 0;
28     for (const auto& p : product)
29     {
30         double weight = p.weight > demand - total ? demand - total : p.weight;
31         total += weight;
32         profit += weight / p.weight * p.price;
33         if (std::abs(total - demand) < 0.001)
34             break;
35     }
36     std::cout.setf(std::ios::fixed);
37     std::cout << std::setprecision(2) << profit;
38 }

 
アルゴリズム-1068:
この問題は私にはできないから、圧巻だ.
できないから、でたらめを書きます.まず、関数を再帰的に呼び出す各コインの数を列挙する再帰実装を書きます.要求に合致する組み合わせがある場合は異常を投げ出し,硬貨の組み合わせを異常パラメータとする.結果は2つの例がいずれも過ぎたが,提出された結果は4つのaccept,1つのwrong,2つのtimeoutであった.結局再帰的で、時間の複雑さは指数級で、タイムアウトしないのがおかしいですね.
もっと良いアルゴリズムが思いつかず、答えを調べた.この問題は01リュックサックの問題で、動的計画アルゴリズムに属して、私はまだ学んでいないので、できないのも無理はありません.しかもこの問題は01リュックの問題の特殊版で、サブセットと問題で、重量と価値はすべて数の大きさです.似たようなのは有名な2数と、3数と、4数となどです.
コアアルゴリズムは、このブログからコピーされています.

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 
 6 int main()
 7 {
 8     int num, target;
 9     std::cin >> num >> target;
10     std::vector<int> coin(num);
11     for (auto& i : coin)
12         std::cin >> i;
13     std::sort(coin.begin(), coin.end(), std::greater<int>());
14     std::vector<:vector style="color: #0000ff;">bool>> select(num);
15     for (auto& v : select)
16         v.resize(target + 1);
17     std::vector<int> total(target + 1);
18     for (int i = 0; i != num; ++i)
19         for (int j = target; j >= coin[i]; --j)
20             if (total[j] <= total[j - coin[i]] + coin[i])
21             {
22                 select[i][j] = true;
23                 total[j] = total[j - coin[i]] + coin[i];
24             }
25     if (total[target] != target)
26     {
27         std::cout << "No Solution";
28         return 0;
29     }
30     int price = target;
31     int which = num - 1;
32     std::vector<int> found;
33     while (price)
34     {
35         if (select[which][price])
36         {
37             found.push_back(coin[which]);
38             price -= coin[which];
39         }
40         --which;
41     }
42     int count = 0;
43     for (int i : found)
44     {
45         if (count++)
46             std::cout << ' ';
47         std::cout << i;
48     }
49 }

最後に、Evaはもう大きな子供です.自分で問題を解決することを学ばなければなりません.いつもアルゴリズムを書かせないでください.肝心な問題は君がいつも私に難題を出していることだ.