[toc]

A题

题意

给出一个点(x,y)，求从(0,0)走到该点的最小次数
每次只能走到一个直线距离是整数的点上,可以走多次

分析

分为三种情况
- (0,0) 不需要走,0次
- (x,y) xx+yy=整数,走的距离为整数,走一次
- (x,y) xx+yy!=整数,需要走两次(0,x)–>(x,y)

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
const int N = 2e5 + 10;

void solve()
{
    int x, y;
    cin >> x >> y;
    int t = sqrt(x * x + y * y);
    int cnt = 0;
    if (t * t == x * x + y * y)
        cnt = 1;
    else
        cnt = 2;
    if (!x && !y)
        cnt--;
    cout << cnt << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
}

B题

题意

每次可以对ai做两个操作
- ai=ai-1 + x
- ai=ai-1 - y

求所有ai的值都不超过B,的最大数列和

分析

贪心的想,可以一直加,知道ai的值要超过B，这需要不加x,而是选择-y

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll a[N];
void solve()
{
    ll n, B, x, y;
    cin >> n >> B >> x >> y;
    ll last = 0;
    for (int i = 1;i <= n;i++)
    {
        if (last + x > B)
            a[i] = last - y;
        else a[i] = last + x;
        last = a[i];
    }

    ll sum = 0;

    for (int i = 1;i <= n;i++)
        sum += a[i];
    cout << sum << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
}

C题

题意

每次可以删除的要求
- 长度>=2的回文串
- 正则括号序列

每次选择一个字符串中 最短的，满足要求的 前缀子串,进行删除,知道不能删除为止。求操作的次数和 最后字符串中剩下的字符数量

分析

我们可以发现:
如果前缀第一个字符是‘(’
- 第二个字符是’)’,是正则括号,可以删除
- 第二个字符是’(‘,是回文串,可以删除

如果前缀第一个字符是’)’
此时只能是回文串的形式才能删除

• 第二个字符串是’(‘,不是回文串,继续往下找
• 第二个字符串是’)’,是回文串,可以删除

代码

由于最后清空时,l的位置是在n+1,所以问题2的答案是 == n+1-i

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
const int N = 5e5 + 10;
typedef long long ll;
ll a[N];
void solve()
{
    int n;
    string s;
    cin >> n >> s;
    s = " " + s;
    int cnt = 0;
    int l = 1;
    while (l < n)
    {
        if (s[l] == '(')
            l += 2;
        else {
            int r = l+1;
            while (r <= n && s[r] != ')')
                r++;
            if (r > n) break;
            l = r + 1;
        }
        cnt++;
    }
    cout << cnt << ' ' << n - l + 1<< endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
}

D题*

前缀最值,二分,数学,桶,贪心

题意

有n个种类的伙伴和金币,每个伙伴都有伤害值,血量,和招募所需的金币
每次可以选择一个种类的伙伴,但招募的数量不能超过金币。
现在要招募伙伴去攻击一个怪兽,怪兽也有伤害和血量,会同时攻击所有伙伴,求打败怪兽所需的最小的金币数,如果不能打败该怪兽,就输出-1

注意：每个怪兽战斗的过程是独立的,因为我们每个过程招募的伙伴种类可以不同,金币永远一样都是C

分析

假设伙伴的伤害为x,血量为y,怪兽伤害d,血量为h
首先,由于一个伙伴都不能死,所以打败一个怪兽的条件是：
- h/x < y/d –> h*d < x*y

由于有m个怪兽,范围是1~1e6,因此可以想到O(nlogn)或者O(n)的时间复杂度做法。
有注意到要找到最小的金币数,那么大概率是一个二分。
由于我们知道二分的前提条件是单调性,由于要满足单调性,就必须使得数组是单调递增的。

注意到金币数量C的范围是1~1e6,而我们要求的是最小金币数,因为二分枚举的就是C,可以把1~C作为数组下标,数组存储的是当前伙伴造成的最大 x*y

染色倍数

由于一个类型的伙伴可以召唤无穷个,只要金额不超过C
那么可以用类似求约数个数的思想,去用当前数组枚举一遍所有的倍数

for (int i = 1;i <= k;i++)
        for (int j = i;j <= k;j += i)
            a[j] = max(a[j], a[i] * (j / i));

前缀最值

因为我们要使得数组保持单调性,那么可以用前缀最值思想,使得数组具有单调性

for (int i = 1;i <= k;i++)
        a[i] = max(a[i], a[i - 1]);

最后 由于 x*y==d*h是不合法的,二分找到第一个>d*h的就可以了

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;
typedef long long ll;
typedef pair<ll, ll> PII;
ll a[N];
PII b[N];
ll n, m, k;

int binary_search(ll x)
{
    int l = 1, r = k + 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] > x)
            r = mid;
        else if (a[mid] == x)
            l = mid + 1;
        else l = mid + 1;
    }
    return l;
}

int main()
{
    cin >> n >> k;
    for (int i = 1;i <= n;i++)
    {
        int c, d, h;
        cin >> c >> d >> h;
        a[c] = max(a[c], 1ll * d * h);
    }
    //染色倍数
    for (int i = 1;i <= k;i++)
        for (int j = i;j <= k;j += i)
            a[j] = max(a[j], a[i] * (j / i));

    for (int i = 1;i <= k;i++)
        a[i] = max(a[i], a[i - 1]);
    cin >> m;
    for (int i = 1;i <= m;i++)
        cin >> b[i].first >> b[i].second;

    for (int i = 1;i <= m;i++)
    {
        ll d = b[i].first;
        ll h = b[i].second;
        ll t = d * h;
        int pos = binary_search(t);

        if (pos == k + 1)
            cout << -1 << ' ';
        else cout << pos << ' ';
    }
    return 0;
}