[数据结构与算法] 【acwing】2003. 找到牛(思维）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【acwing】2003. 找到牛(思维） -> 正文阅读

[数据结构与算法]【acwing】2003. 找到牛(思维）

穿越隧道
在这里插入图片描述

O(n)

只扫一遍，后腿数量加上之前前腿出现的位置，就是牛出现的位置的总情况。
参见大佬思路

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 10;
map<pair<pii,pii>,int> mp;
int ans,cnt;
string s;
int main(){
    cin >> s;
    int len = s.size();
    // cout <<"len = " << len << endl;
    for(int i = 0,j = len - 1; i < len; i++){
        
        if(i < len - 1 && s[i] == '(' && s[i + 1] =='('){
            cnt++;//后腿数量增加
        }
        if(i < len - 1 && s[i] == ')' && s[i + 1] == ')'){
            ans+=cnt;//前腿数量ans
            //ans也为牛的位置数量
        }
    }
    // pair<pii,pii> aaa;
    // int bbb = 0;
    // map<pair<pii,pii>,int>::iterator it;
    // for(it = mp.begin(); it!=mp.end(); it++){
    //     aaa = it->first;
    //     bbb = it->second;
    //     cout << aaa.first.first <<" " << aaa.first.second << " || " << aaa.second.first <<" " << aaa.second.second << bbb  << endl;
    // }
    cout << ans << endl;
    return 0;
}

TLE版(5/10)

只能过一半样例
数据范围： $5e^4$

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 10;
map<pair<pii,pii>,int> mp;
string s;
int main(){
    cin >> s;
    int len = s.size();
    // cout <<"len = " << len << endl;
    for(int i = 0,j = len - 1; i < len; i++){
        if(i < len - 1 && s[i] == '(' && s[i + 1] =='('){
            while(j >= 1 && j > i + 1){
                if(s[j] == ')' && s[j - 1] == ')'){
                    mp[{{i,i+1},{j,j-1}}]++;
                }
                j--;
            }
            j = len - 1;
            // cout <<" i = " << i << endl;
        }
    }
    // pair<pii,pii> aaa;
    // int bbb = 0;
    // map<pair<pii,pii>,int>::iterator it;
    // for(it = mp.begin(); it!=mp.end(); it++){
    //     aaa = it->first;
    //     bbb = it->second;
    //     cout << aaa.first.first <<" " << aaa.first.second << " || " << aaa.second.first <<" " << aaa.second.second << bbb  << endl;
    // }
    cout << mp.size() << endl;
    return 0;
}