A. Square Counting

Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t; cin >> t;
    for(int i = 0; i < t; i++)
    {
        long long n, s; 
        cin >> n >> s;
        cout << s / (n * n) << "\n";
    }
    return 0;
}

B. Quality vs Quantity

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010;

ll n, a[N];

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++)	cin >> a[i];
        
    sort(a, a + n);

    ll j = n - 1, i = 1;
    ll t1 = a[0], t2 = 0;
    	
    while (i < j)
    {
        t1 += a[i]; i++;
        t2 += a[j]; j--;
        if (t2 > t1)
        {
            puts("YES");
            return;
        }
    } 
        puts("NO");
    return;
} 

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

C. Factorials and Powers of Two (二进制枚举)

题目大意

题意：将一个自然数 $n$（ $n \le 10^{12}$）分成满足以下条件的数之和：

• 这个数是某个自然数的阶乘（ $a=x!$ ）
• 这个数是 2 的整数幂次。（ $a=2^x$ ）

且拆分方案中，每个数仅能出现一次。
设共分为 $k$ 个数，求 $k$ 的最小值。

解题思路

思路参考这里
对不超过 $10^{{12}$ 范围的数字中，最多有15个阶乘
我们可以对每一个阶乘选或不选一共2个选择， 共$2}15$个状态
对这些状态进行二进制枚举
处理完后再处理$2^x$, 可以发现这里处理次数即剩余的每一位数值为1的个数，可以直接用count()得出
例如(15)2 = 1111 = 8 + 4 + 2 + 1 = 2^3 + 2^2 + 2^1 + 2^0共4位为1,也即处理次数
OS: bitset<长度>b(数字/01字符串) 可以直接转为二进制
TIPS: 对于涉及数字2的一类题目，可以考虑用二进制做

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll fact[15], n;

void solve()
{
    int ans = 60;
    cin >> n;
    for (int i = 0; i < 1 << 15 ; i++)  // 对每一种状态进行二进制枚举， 选或不选一共2^15种
    {
        bitset<15> b1(i);
        ll t = n;
        for (int j = 0; j < 15; j++) t -= b1[j] * fact[j];  // 该为是0就不选，减去0， 是1就减去这个阶乘
              
        if (t >= 0)  // 处理完阶乘后再看t中有几个‘1’;
        {
            bitset<45> b2(t);  // 直接通过bitset<> 可以将数字转换为二进制
            ans = min(ans, (int)(b1.count() + b2.count()));
        }	
    }
    cout << ans << '\n';
    return; 
}

int main()
{
    ll temp = 1;
    // 预处理好阶乘数组（下标从0开始）， 并且只要到15！即可，因为15!就已经超过10^12了
    for (int i = 1; i <= 15; i++)	temp *= i, fact[i - 1] = temp; 
        
    int t;	cin >> t;
    while(t--) solve();
    return 0;		
} 

D. Repetitions Decoding(树上dp)

以后补

E. Power Board(数学/枚举)

题目大意

解题思路

严格鸽的题解把这题的思路讲的特别详细
做法就是枚举每一个数的幂次行，并且记录它们的的幂次有多少个不同的数即可
TIPS:因为2^20 > n，也就是说，2的幂次行的个数也就20个，那么3的幂次行，5的幂次行的个数肯定小于20。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000020;

int n, m, mp[25]; // mp[i] 表示为，如果有i个幂次行的话，一共有mp[i]个不同的幂次
bool vis[N], st[20 * N];

int qmi(int a, int k){int res = 1;while (k){if (k & 1) res = res * a;a = a * a;k >>= 1;}return res;}

signed main()
{
    cin >> n >> m;
    
    int cnt = 0;
    for (int i = 1; i <= 20; i++)  // 预处理个数
    {
        for (int j = 1; j <= m; j++)
        {
            if (!st[i * j]) cnt++;
            st[i * j] = true;
        }
        mp[i] = cnt;
    }
        
    int res = 1;  // 第一行就一个数
    for (int i = 2; i <= n; i++)
    {
        if (vis[i]) continue;
        int j = 1;
        while (qmi(i, j) <= n)  // 找到某一个数的幂次的最大值的j
        {
            vis[qmi(i, j)] = true;
            j++;
        }
        j--;
        res += mp[j];
    }

    cout << res << '\n';
    return 0;
}