[数据结构与算法]Codeforces Round #770 (Div. 2) (A-D题解)

源代码:ACM/OpenjudgeNow/Codeforces at master · abmcar/ACM (github.com)

A. Reverse and Concatenate

题目大意:

思路:

我们发现对于任意的字符串s,s+rev(s)为一个回文串,而对于一个回文串t,t+rev(t) = rev(t) + t

因此我们只需要判断字符串是否为回文串即可

代码:

void work()
{
    string s;
    cin >> n >> m;
    cin >> s;
    string rs = s;
    reverse(rs.begin(), rs.end());
    if (m == 0 || rs + s == s + rs)
    {
        cout << 1 << endl;
        return;
    }
    cout << 2 << endl;
}

B. Fortune Telling

题目大意:

思路:

题目看上去有点难,但如果我们继续观察,可以发现+和xor的位运算在最后一位上结果是相同的

因此,我们根据数组的xor出的最后一位跟x和x+3对比

答案的最后一位和数组xor和的最后一位相同

代码:

void dfs(int nowNum, int nowPos, int nowAns)
{
    if (ok)
        return;
    if (nowPos == n + 1)
    {
        if (nowNum == y)
            ok = true;
        return;
    }
    if (nowNum + nowAns < y)
        return;
    dfs(nowNum + nums[nowPos], nowPos + 1, nowAns - nums[nowPos]);
    dfs(nowNum xor nums[nowPos], nowPos + 1, nowAns - nums[nowPos]);
}

void work()
{
    ok = false;
    cin >> n >> x >> y;
    nums.resize(n + 1);
    int totAns = 0;
    for (int i = 1; i <= n; i++)
        cin >> nums[i];
    totAns = x % 2 ;
    for (int i = 1; i <= n; i++)
        totAns = totAns xor (nums[i] % 2);
    if (y % 2 == totAns)
        cout << "Alice" << endl;
    else
        cout << "Bob" << endl;
}
     

C. OKEA

题目大意:

思路:

我们知道如果两个平均数为整数的区间的平均数为整数

那么我们可以选择尽可能让22区间的平均数为整数

另外,奇数+奇数 = 偶数 , 偶数+偶数=偶数

可以让奇数列为 1 3 5 7

偶数列为 2 4 6 8这种形式

可以证明这种情况最优

代码:

void work()
{
    cin >> n >> m;
    vector<vector<int>> ans(n + 1, vector<int>(m + 1));
    bool ok = true;
    int nowNum = 1;
    for (int i = 1; i <= n; i += 2)
    {
        for (int j = 1; j <= m; j++)
        {
            if (nowNum > n * m)
                ok = false;
            ans[i][j] = nowNum;
            nowNum += 2;
        }
    }
    nowNum = 2;
    for (int i = 2; i <= n; i += 2)
    {
        for (int j = 1; j <= m; j++)
        {
            if (nowNum > n * m)
                ok = false;
            ans[i][j] = nowNum;
            nowNum += 2;
        }
    }
    if (!ok)
    {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cout << ans[i][j] << " \n"[j == m];
}

D. Finding Zero

题目大意:

思路:

我觉得我写的没有官方好,就直接放官方的了

代码:

int query(int i, int j, int k)
{
    cout << "? " << i << " " << j << " " << k << endl;
    cin >> lastAns;
    return lastAns;
}

void answer(int i, int j)
{
    cout << "! " << i << " " << j << endl;
}

void solve(vector<int> &nowNum)
{
    vector<pair<int, int>> nowAns(4);
    vector<int> newNum;
    nowAns[0] = {query(nowNum[1], nowNum[2], nowNum[3]), nowNum[0]};
    nowAns[1] = {query(nowNum[0], nowNum[2], nowNum[3]), nowNum[1]};
    nowAns[2] = {query(nowNum[1], nowNum[0], nowNum[3]), nowNum[2]};
    nowAns[3] = {query(nowNum[1], nowNum[2], nowNum[0]), nowNum[3]};
    sort(nowAns.begin(), nowAns.end());
    for (int i = 0; i < 4; i++)
        if (nowAns[0].second == nowNum[i] || nowAns[1].second == nowNum[i])
            newNum.push_back(nowNum[i]);
        else
            lastOut = nowNum[i];
    nowNum = newNum;
}

void work()
{
    used.clear();
    cin >> n;
    vector<int> nowNum;
    nowNum.push_back(1);
    nowNum.push_back(2);
    nowNum.push_back(3);
    nowNum.push_back(4);
    solve(nowNum);
    for (int i = 5; i <= n; i++)
    {
        nowNum.push_back(i);
        if (nowNum.size() == 4)
            solve(nowNum);
    }
    if (nowNum.size() == 3)
    {
        nowNum.push_back(lastOut);
        solve(nowNum);
    }
    // for (auto it : nowNum)
    //     cout << it << " ";
    // cout << endl;
    answer(nowNum[0], nowNum[1]);
}