ACWING周赛52题解

前阵子太忙了，好久没c++了。

大家如果超过三周没看见我更新，可以催更（

原本打算昨天打周赛的，结果忘了。。。。于是今天就补一下，然后更新题解。

T1

rt，这个是枚举。T1基本语法题。

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int sum = 0;
    for(int i = 1; i <= 1010; i ++)
    {
        sum += i * (i + 1) / 2;
        if(sum > n) 
        {
            cout << i - 1 << endl;
            return 0;
        }
    }
}

T2

其实就是看离 $i$ 最近的一个0在哪里。

注意数据范围，是不能纯枚举的，要二分。（ $O(N log N)$ ）

这里的二分可能有同学不理解了。这不是无序的吗？为什么二分？

把所有 0 的下标放进一个数组里，然后二分即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int n;
int a[N];
vector<int> pos;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) 
    {
        cin >> a[i];
        if(!a[i]) pos.push_back(i);
    }
    for(int i = 1; i <= n; i ++)
    {
        int l = 0, r = pos.size() - 1;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(pos[mid] >= i) r = mid;
            else l = mid + 1;
        }
        int ans = abs(i - pos[l]);
        l = 0, r = pos.size() - 1;
        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            if(pos[mid] <= i) l = mid;
            else r = mid - 1;
        }
        ans = min(ans, abs(i - pos[l]));
        cout << ans << ' ';
    }
    return 0;
}

T3

这个一看就是数学题，没想到这次T3这么水（

说白了感觉就是解二元二次。

以下内容感谢@垫底抽风 的 Latex教程

题目就是要求解如下的二元二次方程组。

$\displaystyle \left\\{ \begin{aligned} & x + y = d \\\ & xy = d \\\ \end{aligned} \right.$

先消元，我瞎消了一个 $x$ 。

得到

$\displaystyle y(d - y) = d$

去括号并把所有项移到左边。

$\displaystyle -{y}^2 + dy - d = 0$

然后套用二元一次方程求根公式

$\displaystyle x = \frac{-b \pm \sqrt {{b} ^ 2 - 4ac}}{2a}$

发现在这里 $a = -1$ , $b = d$ , $c = -d$

代入，得

$\displaystyle y = \frac{-d \pm \sqrt {{d} ^ 2 - 4d}}{-2}$

所以，当 $\displaystyle {d} ^ 2 - 4d < 0$ 时，无解。

其他的时候算出来即可。

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
double get(int x)
{
    int p = x * x - 4 * x;
    double t = sqrt(p) - x;
    return t / (-2) * 1.0;
}
int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int x;
        cin >> x;
        if(x * x - 4 * x < 0) cout << "N\n";
        else
        {
            cout << "Y ";
            double ans = get(x);
            printf("%.10lf %.10lf\n", ans, x - ans);
        }
    }
    return 0;
}