Day 1

P8772

1. 双重循环

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

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> v(n + 2);
    for (int i = 1; i <=n; ++i){
        cin >> v[i];
    }
    long long ans = 0;
    for(int i = 1;i<=n;i++){
        for(int j = i + 1;j <= n;j++){
            ans += v[i] * v[j];
        }
    }
    cout << ans;
    return 0;
}

2. 优化乘法

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

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> v(n + 2);
    for (int i = 1; i <=n; ++i){
        cin >> v[i];
    }
    long long ans = 0;
    for(int i = 1;i<=n;i++){
        int temp = 0;
        for(int j = i+1;j<=n;j++){
            temp += v[j];
        }
        ans += temp * v[i];
    }
    cout << ans;
    return 0;
}

3. 前缀和

$$su{m}_i=su{m}_{i-1}+nu{m}_i$$

前缀和数组的第 $i$ 项 = 原数组的 0 到 $i-1$ 项的和 + 原数组的第 $i$ 项。 对于 $a_1,a_2\dots ,a_n$，要求 $\sum _{i=j}^k{a}_i$，只要计算 $su{m}_k-su{m}_{j-1}$ 即可。

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

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> v(n + 2);
    for (int i = 1; i <=n; ++i){
        cin >> v[i];
    }
    long long ans = 0;

    vector<long long> sum(n + 2,0);
    for(int i = 1;i<=n;i++){
        sum[i] = sum[i-1]+v[i];
    }

    for(int i = 1;i<=n;i++){
        ans += v[i] * (sum[n] - sum[i]);
    }
    cout << ans;
    return 0;
}

P9231

$$x=y^2-z^2=(y+z)(y-z)$$$$\{\begin{array}{l}y+z=a\\ y-z=b\end{array}\Rightarrow 2y=a+b$$

偶+偶=偶，偶+奇=奇，奇+奇=偶 偶-偶=偶，偶-奇=奇，奇-奇=偶 因此，$a,b$ 奇偶性相同，也就是 $x$ 可以拆成两个奇偶性相同的数的乘积。

• 奇数拆成 $1$ 和本身：

$$\{\begin{array}{l}y+z=1\\ y-z=x\end{array}$$

• 偶数拆成两个偶数乘积，每个偶数都有因子 $2$，因此 $x$ 含有因子 $4$

$$\{\begin{array}{l}y+z=2k\\ y-z=2k\end{array}$$

P8781

剪一轮来回下来灌木高度一定会归零，和剪多少天没有关系，只要讨论一轮来回修剪中什么时候最高即可。 显然要么是比较修剪之前的阶段和修剪之后的阶段：

$$n_i=2\times max(n-i,i-1)$$

Day 2

P9240

由题意，$V=\frac{A}{B}$ 给定数据中，要求 $V$ 满足输出 $A\to B$ 的转化情况：

• 上界：$A\to B,V_{max}=\lfloor \frac{a}{b}\rfloor$，此时 $A$ 完全转化为 $B$ 。
• 下界：$A\to B+1,V_{min}=\lfloor \frac{a}{b+1}\rfloor +1$，此时可以转化 $B+1$ 个（也就是 $B+1$ 的上界），再向上扩大转化所需的 $A$ 使之不能转化到 $B+1$ 个，所以 $+1$；

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

const int inf=0x3f3f3f3f;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	int mn=0,mx=inf;
	while(n--)
	{
		int a,b;
		cin>>a>>b;
		mn=max(mn,a/(b+1)+1);
		mx=min(mx,a/b);
	}
	cout<<mn<<' '<<mx<<'\n';
	return 0;
}

P10387

每行包含两个整数 $p_i$ 和 $c_i$ ​，表示第 $i$ 名士兵进行一次训练的金币成本和要成为顶尖战士所需的训练次数。 贪心的度：所有士兵使用组团训练的成本低于单独训练的成本，则使用组团训练。

• $cn{t}_{c_i}$，训练 $i$ 次的士兵的训练成本（的索引）
• $now$，所有士兵训练一次的成本，训练一次的成本
• $sum$，所有士兵单独训练所需成本，训练所有次的成本 对于第 $i$ 次组合训练:
• 如果 $now\ge S$ ，则说明还需要组合训练，$ans$ 加上 $S$, $Sum$ 减去$now$，$now$ 减去 $cn{t}_i$。
• 如果 $now<S$ ，跳出循环，答案即为 $ans+Sum$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
//#define N 1e6 + 10
//const int N = 1e6 + 10;
constexpr int N = 1e6 + 10;
LL n, s, p[N], c[N], cnt[N], Sum, now, ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> s;
    for (int i = 1; i <= n; i++)
        cin >> p[i] >> c[i], cnt[c[i]] += p[i], now += p[i], Sum += p[i] * c[i];
    for (int i = 1; i <= 1e6; i++) // 1e6，训练次数，每次解决的是第i次训练，循环内都使用组团训练
    {
        if (now < s)
            break;
        ans += s;     // 确定的费用增加
        Sum -= now;   // 所有士兵单独训练成本
        now -= cnt[i];// 减去训练i次士兵的成本（如果i>=cnt[i]，这些士兵不需要再训练，成本减掉）
    }
    cout << ans + Sum;
    return 0;
}

P10424

模拟。 注意顺序是反的

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

bool isGoodNum(int n)
{
    if(n == 1) return true;
    string s = to_string(n);
    reverse(s.begin(), s.end());
    int len = s.size();
    for (int i = 1; i <= len; i++)
    {
        if ((i % 2 == 0) && (s[i - 1] - '0') % 2 == 0)
        {
            continue;
        }
        if (i % 2 != 0 && (s[i - 1] - '0') % 2 != 0)
        {
            continue;
        }
        return false;
    }
    return true;
}

int main(int argc, char const *argv[])
{
    //cout << isGoodNum(10) << endl;
    int N;
    cin >> N;
    int sum = 0;
    for (int i = 1; i <= N; i++)
    {
        if (isGoodNum(i))
        {
            sum += 1;
            //cout << i << " ";
        }
    }
    cout << sum;
    return 0;
}

P10898

先用 $2\times 2$ 的正方形最大化边长：

$$w=2\lfloor \sqrt{7385137888721}\rfloor =5435122$$

检查 $1\times 1$ 小正方形，发现不能使边长 $+1$：

$$10470245=4x+4,x=\frac{10470241}{4}=2617560.25<5435122$$

所以最大就是 $5435122$。

P10899

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

int main(int argc, char const *argv[])
{
    char a,b;
    unsigned long long int now_time,last_time = 0;
    int sum = 0;
    int max_sum = 0;
        while(cin >> a >> b >> now_time){
        if(a == b && now_time - last_time <= 1000){
            sum++;
        }else{
            max_sum = max(max_sum, sum);
            sum = 1;// 从1开始，因为是满足now_time - last_time <= 1000才能++sum，此时上一个操作是要计算在内的，也就是一次正确的操作算是1连击
        }
        last_time = now_time;
    }
    cout << max_sum;
    return 0;
}

数据太弱 hhh

a a 1000
b b 2000
c c 3000

unsigned

P10900

$$a_i=\frac{(n+m)\times (m-n+1)}{2},2a_i=(n+m)\times (m-n+1)$$

右边一定是一个奇数乘以一个偶数，因此只要左边是 $2^n$ 就不能被表示，判断求指数就行了。