2024.2.1 寒假训练记录（15）

今天学了点网络流，vp了个div3，d真是毒瘤啊，晚上写写xcpc真题吧

CF 1921D Very Different Array

题目链接

贪心真是越菜越爱啊，天天贪假

可以想到把大的分给小的，小的分给大的，推广一下就是枚举有多少分给小的有多少分给大的

#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1000010;

void solve()
{
   
	int n, m;
	cin >> n >> m;
	vector<int> a(n), b(m);
	for (int i = 0; i < n; i ++ ) cin >> a[i];
	for (int i = 0; i < m; i ++ ) cin >> b[i];
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	int ans = 0, tmp = 0;
	for (int i = 0; i < n; i ++ ) tmp += llabs(a[i] - b[n - i - 1]), ans = max(ans, tmp);
	for (int i = 0; i < n; i ++ ) tmp = tmp - llabs(a[i] - b[n - i - 1]) + llabs(a[i] - b[m - i - 1]), ans = max(ans, tmp);
	cout << ans << '\n'; 
}

signed main()
{
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t -- )
	{
   
		solve();
	}
}

CF 1921F Sum of Progression

题目链接

这题学到了一个技巧，根号分治，也就是在小数据时暴力计算，大数据先预处理之后使用技巧计算

vp的时候想到了前缀和的应用，但是没能想到根号分治

#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;

const int N = 1000010;

void solve()
{
   
	int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    vector<vector<int>> f(n + 1, vector<int>(350)), prev(n + 1, vector<int>(351));
    for (int j = 1; j <= 350; j ++ )
    {
   
        for (int i = 1; i <= n; i ++ )
        {
   
            if (j <= i)
            {
   
                f[i][j] = f[i - j][j] + ((i - 1) / j + 1) * a[i];
                prev[i][j] = prev[i - j][j] + a[i];
            }
            else
            {
   
                f[i][j] = a[i];
                prev[i][j] = a[i];
            }
        }
    }

    while (q -- )
    {
   
        int s, d, k;
        cin >> s >> d >> k;
        int ans = 0;
        if (d <= 350)
        {
   
            if (s < d) ans = f[s + (k - 1) * d][d];
            else
            {
   
                ans = f[s + (k - 1) * d][d] - f[s - d][d];
                ans -= (s - 1) / d * (prev[s + (k - 1) * d][d] - prev[s - d][d]);
            }
        }
        else
        {
   
            for (int i = s; i <= s + (k - 1) * d; i += d)
            {
   
                ans += ((i - s) / d + 1) * a[i];
            }
        }
        cout << ans << ' ';
    }
    cout << '\n';
}

signed main()
{
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t -- )
	{
   
		solve();
	}
}