Codeforces 50B 選擇符號配對

難易度 : 1500

英文原文如下

There is a given string S consisting of N symbols. Your task is to find the number of ordered pairs of integers i and j such that

1. 1 ≤ i, j ≤ N

2. S[i] = S[j], that is the i-th symbol of string S is equal to the j-th.

中文翻譯

有一個給予的字串 S 由 N個符號所組成。你的任務就是要找到整數 i 以及 j 的配對數量

1. 1 ≤ i, j ≤ N

2. S[i] = S[j], 索引 i 的符號與索引 j 的是相同的。

輸入

The single input line contains S, consisting of lowercase Latin letters and digits. It is guaranteed that string S in not empty and its length does not exceed 10⁵.

輸入的一行包含S, 由小寫拉丁字母以及數字所組成。字串 S 保證不是空的而且其長度會超過 10⁵ 。

輸出

Print a single number which represents the number of pairs i and j with the needed property. Pairs (x, y) and (y, x) should be considered different, i.e. the ordered pairs count.

印出一個單獨的數字代表了要求的 i 跟 j 配對的數量。配對(x,y) 以及 (y,x) 是被視為不同的。

範例

因為沒有說 i 不能與 j 相同，故所有符號都不一樣的狀況下，長度就是他的答案

也就是每個索引對應到的都是自己(與自己組成一對)

[0,0],[1,1],[2,2],[3,3],[0,0],[5,5],[6,6]

每個符號都一致，故排列組合等於 10*10=100

解題思路

在我第一個想法中，想要用的是兩個 for 迴圈

就各自 for 到 length的長度去跑，但隨後就被自己否決了，這樣的時間複雜度 O(n²) 在 Codeforces 中絕對是會超時的。

C#解決方案

方案1

string txt = Console.ReadLine();

Dictionary<char,int> dict =   new Dictionary<char,int>();

foreach(var a in txt)
{
    if (!dict.ContainsKey(a))
    {
        dict.Add(a, 1);
    }
    else
    {
        dict[a] = dict[a]+1;
    }
}

double res = 0;
foreach(var item in dict)
{
    res+= Math.Pow(item.Value,2);
}

Console.Write((long)res);

最後的解決方案是用一個字典來儲存每個字元出現的次數，然後各自平方並加總

例如 : aabbb，字典就會是 { ‘a’:2, ‘b’:3 }，答案會是 2²+3² =13

整體概念就是將單字拆開成一小一小段的

畢竟這次的找配對是要完全一致，故可以很簡單的用這個概念區分

另外，用 double來做是因為用 int 時在某些案例中不夠了…

結論

這一題難的應該算是概念吧，想通就結束了

不然傻傻的用兩個for loop也不是不行啦，只是很可能會不通過而已

這一題出自於比賽 – Dashboard – Codeforces Beta Round 47 – Codeforces

然後這裡看這一系列的其他題目

• Codeforces 50A 骨牌堆疊 – 翻譯與解答

🧡如果文章有幫上你的忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Problem – 50B – Codeforces

一些其他的Codeforces文章