https://codeforces.com/contest/1646

A. Square Counting

这题我理解为 $n^2$ 在 s 中出现的次数，s / ($n^2$) 就a掉了。

#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second

using namespace std;

const int N = 1200 + 10;
typedef pair<int, int> PII;

ll t, n, s;

int main()
{
    scanf("%lld", &t);
    while(t --)
    {
        scanf("%lld%lld", &n, &s);
        printf("%lld\n", s / (n * n));

    }

    return 0;
}

B. Quality vs Quantity

贪心 + 双指针

贪心策略：大的数优先染成红色，小的数优先染成蓝色，所以先排序。染色的方法用双指针，先染红色再染蓝色，当出现满足条件的方案，说明找到了一组解，返回true，若两指针碰头都没有满足条件的方案，说明这组数据无解，返回false。

#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second

using namespace std;

const int N = 2e5 + 10;
typedef pair<int, int> PII;

ll t, n, s;
ll q[N];

bool work()
{
    ll Sred, Cred, Sblue, Cblue;
    Sred = Cred = Sblue = Cblue = 0;
    int i = 0, j = n + 1;
    while(i < -- j)
    {
        Sred += q[j]; Cred ++;
        while(Sblue < Sred && ++ i < j)
        {
            Sblue += q[i]; Cblue ++;
            if(Sred > Sblue && Cblue > Cred)
                return true;
        }
    }

    return false;
}

int main()
{
    scanf("%lld", &t);
    while(t --)
    {
        scanf("%lld", &n);
        for(int i = 1; i <= n; i ++)
            scanf("%lld", &q[i]);
        sort(q + 1, q + 1 + n);
        if(work()) puts("Yes");
        else puts("No");
    }


    return 0;
}

C. Factorials and Powers of Two

搜索 + 剪枝

这题的意思是用小于 1e12 的 $2^d$ 和 $d!$ 的所有数中选择出组合相加等于n的最小个数，若没有组合方案输出 -1。比赛时将所有 $2^d$ 和 $d!$ 都纳入了搜索范围，一共 55 个数，复杂度为 $2^{55}$，直接爆炸。后来补题发现 $2^d$ 就可以组合出所有数，根本不存在无解的方案。
我真傻，真的(
我用的正解是在上述搜索的基础上剪掉 $2^d$，对剩下 15 个阶乘数进行搜索，考虑选择当前阶乘数dfs(u + 1, x - power[u], cnt + 1) 或者不选dfs(u + 1, x, cnt)，当不能再选择时取出 x 在二进制表示中的 1 来表示 $2^d$ 的个数 while(x) x -= x & -x , t ++;，与选择的阶乘数相加再取最小值即可。最大计算量为$2^{15} * 12$ < 4e5，能过。

#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second

using namespace std;

const int N = 2e5 + 10;
typedef pair<int, int> PII;

ll t, n, minn;
vector<ll> power;

void getpower()
{
    ll t = 1;
    for(ll i = 1; t <= 1e12; i ++)
    {
        t *= i;
        power.push_back(t);
    }
}

void dfs(ll u, ll x, ll cnt)
{
    if(x < 0 || u >= power.size()) return;
    if(power[u] > x)
    {
        ll t = 0;
        while(x) x -= x & -x , t ++;
        minn = min(minn, t + cnt);
        return;
    }

    dfs(u + 1, x - power[u], cnt + 1);
    dfs(u + 1, x, cnt);
}

int main()
{
    cin >> t;
    getpower();

    while(t --)
    {
        cin >> n;

        minn = 0x3f3f3f3f;
        dfs(0, n, 0);

        cout << minn << endl;
    }

    return 0;
}

基础课还没学完，能力有限，比赛时只a掉两题，后面的题就不涉足了。≡ω≡