2022-04-08美团笔试练题

两个字符串，忽略顺序，是否相同，即是否包含相同的字符，对应字符的数量也相同

"hello"和"olleh"相同。

思路：位运算，0异或0=0，0异或1=1，所以ans初始化为0，任何数和自己异或结果为0，这样用0异或两个字符串的每个字符就可。

O(n)

    bool match(string str1, string str2) {
        int n = str1.size();
        int n2 = str2.size();
        if (n != n2) return false;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans ^= str1[i];
            ans ^= str2[i];
        }
        return ans == 0;
    }

    int main(){
        string str1 = "hello";
        string str2 = "heoll";
        cout << match(str1, str2);
        return 0;
    }

小美斗恶龙

时间限制：3000MS

内存限制：1048576KB

题目描述： 小美得到了一款游戏——斗龙。

小美拥有两个技能，每个技能都能秒杀掉一条龙，但是要付出相应的MP值，第一个技能需要c1点MP值，第二个技能需要c2点MP值。

只要MP足够，小美可以使用无限次技能。

小美即将遇到 n 条龙，如果不使用技能，她和第 i 条龙的战斗结果是T或者F，而如果使用任何一个技能战斗结果都是T。

T表示小美成功打败龙，而F表示小美被龙打败。

如果小美被龙连续打败三次，那小美就会输掉游戏。

请你帮忙计算小美最少需要多少点 MP才能通关。

输入描述：

第一行三个数 n, c1, c2。

(1 ≤ n ≤ 100000，1 ≤ c1, c2 ≤ 1000000000)。

第二行 n 个字符，第 i 个字符 si 代表小美与第 i 场战斗的结果。

si 是 T 代表小美打败龙，si 是 F 代表小美被龙打败。

输出描述：

输出一个数，代表小美最少需要的MP值。

样例输入：

10 7 3
FTFFFTFFFF
样例输出：
6

提示：
小美可以在第3场战斗、第8场战斗中使用第二个技能，需要耗费3×2=6点MP。

    int main(){
        int n;
        long c1, c2;
        cin >> n >> c1 >> c2;
        string s;
        cin >> s;
        long mp = min(c1, c2);
        int n1 = s.size();//本题不需要，在n处会输入决定
        int freq = 0;//连续F次数，遇到T清0，连续第三次F，用技能然后清0
        long mpsum = 0;
        for (int i = 0; i < n1; ++i) {
            if (s[i] == 'T') {
                freq = 0;
                continue;
            }
            else {
                if (freq == 2) {
                    mpsum += mp;
                    freq = 0;
                }
                else {
                    freq += 1;
                }
            }
        }
        cout<<mpsum;
        return 0;
    }

小美中奖啦

持续补充

小美记数字

三、小美记数字
小美的记忆力超级棒，小团决定来考一考小美。

小团给了小美 n 个数，从左到右排成一行，给了1 分钟让小美记住。

然后小团会询问 m 次，每次都问数 x 第一次出现的位置和最后一次出现的位置，若数 x 没出现过，那么回答 0 即可。

小美的记忆力好，但是 1 分钟记住这么多数实在是太难了，请你帮帮小美，完成这次不可能的挑战。

输入描述
第一行两个数 n, m。

(1 ≤ n, m ≤ 50000)。

第二行 n 个数，第 i 个数是 ai。

(1 ≤ ai ≤ 1000000000)。

接下来 m 行，每行一个数 x (1 ≤ x ≤ 1000000000)，代表一次询问。

输出描述
输出 m 行，若数 x 出现过，输出数 x 第一次出现的位置和最后一次出现的位置。

若数 x 没出现过，输出 0。

样例输入
6 4
2 3 1 2 3 3
1
2
3
4
样例输出
3 3
1 4
2 6
0

提示
1 出现的位置有 3，所以答案为 3 3。

2 出现的位置有 1, 4，所以答案为 1 4。

3 出现的位置有 2, 5, 6，所以答案为 2 6。

4 没有出现过，所以答案为 0。

    int main(){
        int m, n;
        cin >> n >> m;
        vector<long> v(n);
        for (int i = 0; i < n; ++i) {
            cin >> v[i];
        }
        unordered_map<long, int> mfirst;//存第一次出现的下标
        unordered_map<long, int> mlast;//存最后一次出现的下标
        for (int i = 0; i < n; ++i) {
            if (mfirst.find(v[i]) == mfirst.end()) {
                mfirst[v[i]] = i+1;//位置是下标+1
                mlast[v[i]] = i+1;
            }
            else mlast[v[i]] = i+1;
        }
        for (int i = 0; i < m; ++i) {
            int q;
            cin >> q;
            if (mfirst.find(q) == mfirst.end()) {
                cout << 0 << endl;
            }
            else {
                cout << mfirst[q] << " " << mlast[q] << endl;
            }
        }
        return 0;
    }

奶茶 值日 流 寻找数字

    int main(){
        string s;
        cin >> s;
        vector<int> v;
        int num = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (isdigit(s[i])) {
                num = num * 10 + int(s[i] - '0');
                if (i == s.size() - 1) {//如果扫到最后一个数，也要存进v
                    v.push_back(num);
                }
            }
            else {//遇到非数字，把已有非0数字存进v
                if (num != 0) {
                    v.push_back(num);
                    num = 0;
                }
                continue;
            }
        }
        sort(v.begin(), v.end());//排序
        for (auto c : v) {
            cout << c << endl;
        }
        return 0;
    }

蚂蚁上树 数数 多重集合