Hello 2019题解

题解 CF1097A 【Gennady and a Card Game】

map大法好qwq

枚举每一个的第\(1,2\)位判是否与给定的重复即可

# include <bits/stdc++.h>

std::map<char, int> m1, m2;

int main()

{

    std::string s[6], str;

    std::cin >> str;

    for(int i = 1; i <= 5; i++)

        std::cin >> s[i], m1[s[i][0]] = 1, m2[s[i][1]] = 1;

    if(m1[str[0]] || m2[str[1]])

        return printf("YES\n") * 0;

    printf("NO\n");

    return 0;

}

题解 CF1097B 【Petr and a Combination Lock】

\(dfs\)入门题，下一个

枚举每一个是正还是负，最后判能不能被\(360\)整除即可

时间复杂度\(O(2^n)\)



# include <bits/stdc++.h>

int n, flag, a[20], used[20];

inline void check()

{

    int sum = 0;

    for(int i = 1; i <= n; i++)

        sum += a[i] * (used[i] ? (-1) : 1);

    if(sum % 360 == 0)

        flag = 1;

}

void dfs(int x)

{

    if(x == n + 1)

        return (void) (check());

    dfs(x + 1);

    used[x] = 1;

    dfs(x + 1);

    used[x] = 0;

}

int main()

{

    scanf("%d", &n);

    for(int i = 1; i <= n; i++)

        scanf("%d", &a[i]);

    dfs(1);

    printf(flag ? "YES" : "NO");

    return 0;

}

题解 CF1097C 【Yuhao and a Parenthesis】

说起Yuhao,我就不得不提@BlueCat,想起了他旋转**的情景，明年，中美，两开花，关注

对于每个括号序列，我们都用栈预处理出它不能配对的部分

等等？什么叫不能配对的部分？

比如说序列\()())\),\())\)就是它不能配对的部分

然后把这个部分取反

就得到了如果要把这个序列弄成正确的需要的最简序列\(x_i\)

显然这个部分要放在当前串的前面或后面

但是我们有些时候发现这东西是假的

比如这个序列\())))((((\),它的匹配序列是\((((())))\),很明显放前或后都不行，那么这个串就废了

如果这个串没废，就把\(x_i\)的计数累加\(1\)

然后我们枚举每一个\(x_i\)，将\(ans\)累加上\(\min{x_i,x_i取反}\)(取反只把一个括号序列中'('变成')'，反之亦然)

注意这里有一个特判，如果有一个串本来就是好的，那么统计答案时，由于空串的反串还是空串，所以答案会算两次

所以要特判出好串的个数\(cnt\)

最后输出\(ans/2+cnt/2\)即可(下取整)

#include <bits/stdc++.h>

const int MaxN = 100010, MaxM = 500010;

std::string s[MaxN], str[MaxN];

std::map<std::string, int> m;

inline std::string change(std::string s)

{

    int len = s.length();

    std::string tmp = "";

    for (int i = 0; i < len; i++)

        tmp += ((s[i] == '(') ? ')' : '(');

    return tmp;

}

inline int check1(std::string s)

{

    std::stack<char> st;

    int len = s.length();

    for (int i = 0; i < len; i++)

    {

        if (s[i] == '(')

            st.push('(');

        else if (s[i] == ')' && st.empty())

            return 0;

        else

            st.pop();

    }

    return 1;

}

inline void check(int x, std::string s)

{

    std::vector<char> st;

    int len = s.length();

    for (int i = 0; i < len; i++)

    {

        if (st.empty())

        {

            st.push_back(s[i]);

            continue;

        }

        if (s[i] == '(')

            st.push_back('(');

        else if (s[i] == ')' && st.back() == '(')

            st.pop_back();

        else if (s[i] == ')' && st.back() == ')')

            st.push_back(')');

    }

    std::string tmp = "";

    for (int i = 0; i < st.size(); i++)

        tmp += ((st[i] == '(') ? ')' : '(');

    if (check1(tmp + s) || check1(s + tmp))

        ++m[tmp];

    //  std::cout << " " << s << " " << tmp << "\n";

}

int main()

{

    int n, ans = 0;

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)

        std::cin >> s[i], check(i, s[i]);

    for (std::map<std::string, int>::iterator it = m.begin(); it != m.end(); ++it)

    {

        if (it->first == "")

            continue;

        ans += std::min(it->second, m[change(it->first)]);

    }

    printf("%d\n", (ans / 2) + (m[""] / 2));

    return 0;

}

巴特西

Hello 2019题解

Hello 2019题解

题解 CF1097A 【Gennady and a Card Game】

题解 CF1097B 【Petr and a Combination Lock】

题解 CF1097C 【Yuhao and a Parenthesis】

最新文章

热门文章