情况

时间：2024年7月3日星期三 16:25

题解

Educational Codeforces Round 167 (Rated for Div. 2)_哔哩哔哩_bilibili
mod jiangly

A - Catch the Coin

题意

人在中心点四面八方都能走，走一步，硬币y轴–。

思路

比赛时，还用数学算了一下,满足：
$y+|x|>=|x|-1$
能接住。
然后发现，这不就是
$y>=-1$

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100000;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>> t;
    while(t--){
        int x, y;
        cin >> x >> y;
        if (y+abs(x)>=abs(x)-1)
            cout << "YES" << endl;
            else
                cout << "NO" << endl;
    }
    return 0;
}

B - Substring and Subsequence

题意

子字符串：连续的包含在一个字符串
子序列：从一个字符串中删去一些字符（可能不删）。
给出一个子字符串和子序列，找到最短的满足条件的字符串。
a必须连续出现，b是删去某些得到的结果。

问题

这题急了没贪出来，没忍住cheat了。后来发现，思路反了
b的最长的子串是a的子序列 —-jiangly（没听懂）（后来听懂了）

但是贪心的思路就是，遍历b，找到b中，某个最长子串（连着）是在a中子序列（不需连续）
我当时怎么想着从最后一个开始对齐，真服了。回过头来看绝对蠢死。

代码

by jiangly

void solve()
{
    string a, b;
    cin >> a >> b;
    int add = b.size();
    for (int i = 0; i < b.size();i++)   
    {
        int k = i;
        for (int j = 0; j < a.size();j++){
            if(k<b.size()&&a[j]==b[k]){
                k++;
            }
        }
        ans = min(ans, i + (int)(b.size()) - k); // b的最长的子串是a的子序列
    }
    cout << add +a.size()<< '\n';
}

C - Two Movies

题意

两个电影。若干人，一人对每个电影都有一个评价（1,0,-1），你选择一个电影评价，两个电影的得分的最小值为最终评分。找出最终评分的最大值。

思路

比赛时候：贪心，全用if写，过用例就算成功。结果喜闻乐见：wa on test 2
jiangly：谁大加谁
如果一样，如果是1，有一个加1的机会。如果是-1，先都减1，再增加一个加一的机会。
输出A+C，B+C，A+B+C >>1的最小值（为什么这是对的？）（因为思想就是要在这两个一样的时候，是二者最小值的最大值，向下取整，取更小的那一个）
右移1位相当于除以2，这个只有正数适用，而负数不适用。重要！涉及到取整问题。负奇数除二是向上取整！
[CSDN相关文章]http://t.csdnimg.cn/vaJDN

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 2 * 10e5 + 1;
int a[N], b[N];
void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int A = 0, B = 0, C = 0;
    for (int i = 0; i < n; i++)
    {
      
        cin >> b[i];
        if (a[i] > b[i])
        {
            A += a[i];
        }
        else if (a[i] < b[i])
        {
            B += b[i];
        }
        else if (a[i] == 1)
        {
            C++;
        }
        else if (a[i] == -1)
        {
            C++;
            A--;
            B--;
        }
    }


    int ans = min(A + C, min(B + C, (A + B + C) >>1));//右移1位相当于除以2，这个只有正数适用，而负数不适用。重要！
    cout << ans << endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}