Codeforces Round #773 (Div. 2) A~C 个人题解

封面：56525842

大致题意：一个三角形的三个顶点坐标都是非负整数， 计算它的“不安全”的边的长度

（“安全”的边： 轴出发的直线段能直接接触到且不穿过三角形的边）

思路：简单求一下在x轴上方的与x轴平行的边的长度即可，注意此时另一个点在这段平行线下方（打比赛时因为这个WA了）

附上代码：

#include
#include

using namespace std;

void solve()
{
    int x1, x2, x3, y1, y2, y3, res = 0;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

    if (y1 == y2 && y3 < y1) res = abs(x2 - x1);
    else if (y2 == y3 && y1 < y2) res = abs(x2 - x3);
    else if (y1 == y3 && y2 < y1) res = abs(x1 - x3);

    cout << res << 'n';

    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--)
        solve();

    return 0;
}   

大致题意：对于给定的个数字分为  ~  组，求最大的“能量”和

（组的“能量”定义为：该组有多少个不同的数字）

 思路：用map先存下各个数字的出现次数，此时map.size()就是不同数字的种类， 记作。

显然，只有1组时，能量值为k；有n组时，能量值为n。（比赛时到这里就卡了233333）

若此时有组，分出第组时：

①原组的数存在重复，分出去一组后数的的种类没有减少，能量值不变，新增一组，总能量值增加1

②原组的数不存在重复，分出去一组后数的的种类减少， 能量值减1，新增一组，总能量值不变

只需先进行操作②再进行操作①即可，且分为组时，总能量值不会超过，不会小于。

所以只需要用max()函数即可

附上代码：

#include
#include
#include

大致题意：给定n个数的一串序列以及一个数字x，使满足每一对数都在这一序列中，求最少要往序列中添加多少个数字。

思路：刚看到题目的时候觉得可以暴力循环两编解决，然后发现必然会TLE，于是想到如何优化复杂度。

这里采用双指针（之前先用sort()排序）

a[n] 存已有元素，f[n]存是否被使用

用指针 i 遍历所有元素，指针 j

①指向大于 x * a[i] 的第一个数

②j--，此时 j 指向不大于a[i] 的最后一个数

③如果此时a[j]没被使用，就标记f[j]被使用过；如果被使用了，说明所需添加的数 + 1

④j--，此时 j 指向不大于a[i] 的最后第二个数

⑤循环

（PS：int会爆，要开long long）

附上代码：

#include
#include
#include

using namespace std;

void solve()
{
    long long n, x;
    cin >> n >> x;

    vectora(n);
    vectorf(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a.begin(), a.end());

    int j = 0, q = 0, res = 0;
    for (int i = 0; i < n; i++)
    {
        if (f[i])
            continue;
        if (a[j] < a[i] * x)
        {
            while (a[j] <= a[i] * x && j < n) j++;
            q = --j;
        }
        if (i < q && a[q] == a[i] * x)
            f[q--] = 1;
        else res++;
    }

    cout << res << 'n';

    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--)
        solve();

    return 0;
}