2022级综合训练

• 本次训练三道题目都为codeforces上原题。

1.Binary Decimal

• 题解:多尝试几组数据不难看出题目所求为,所有位数上最大的一个值.

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
void slove()
{
    string s;
    cin >> s;
    int maxn = 0;
    for (int i = 0; i < s.length(); i++)
    {
        maxn = max(maxn, s[i] - '0');
    }
    cout << maxn << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(15);
    int __ = 1;
    cin >> __;
    while (__--)
    {
        slove();
    }
    return 0;
}

2.New Year Transportation

• 题解: mp[i]=true代表 小贝能到达i位置.如果能到 i 位置就一定能到 i+a[i] 位置.以此类推.最后我们判断 mp[t] 是否为true,如果mp[t]=false,说明不能到达t.

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
int a[N];
bool mp[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(15);
    int n, m;
    cin >> n >> m;
    int i = 1;
    mp[1] = 1;
    for (int i = 1; i <= n - 1; i++)
    {
        cin >> a[i];
    }
    while (i < n)
    {
        i += a[i];
        mp[i] = 1;
    }
    if (mp[m])
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}

3.Pursuit

• 题解: 如果想多进行最少的回合数让A的分数超过B,那么我们可以让增加的回合中A的分数都等于100,B的分数都等于0.我们发现如果增加x回合能让A的分数超过B,那么进行x+k (k>=0)个回合一定能使A的分数超过B,如果增加y回合不能让A的分数超过B,那么增加y-k (k>=0) 个回合一定不能让A>=B.所以我们可以用二分答案来解决这个问题.

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
int a[N];
int b[N];
int n, m;
bool check(int x)
{
    int cnt = n + x - (n + x) / 4;
    int nd = min(x, cnt);
    int ans1 = 0;
    int ans2 = 0;
    for (int i = 1; i <= cnt - nd; i++)
        ans1 += a[i];
    for (int i = 1; i <= cnt; i++)
    {
        if (i <= n)
            ans2 += b[i];
        else
            break;
    }
    ans1 += (nd * 100);
    return ans1 >= ans2;
}
void slove()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    sort(a + 1, a + n + 1, greater<int>()); //从大到小
    sort(b + 1, b + n + 1, greater<int>());
    int l = 0, r = 4 * n;
    int ans = 0;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(15);
    int __ = 1;
    cin >> __;
    while (__--)
    {
        slove();
    }
    return 0;
}