1921(920div3)

A. Square

给出四个坐标，算出正方形的面积

int _,x[5],y[5];
void solve()
{
    for (int i = 1; i <= 4;i++)
        cin >> x[i] >> y[i];
    sort(x + 1, x + 5);
    sort(y + 1, y + 5);
    cout << (x[4] - x[1]) * (y[4] - y[1]) << '\n';
}

B . Arranging Cats

科学家们有 $n$ 个箱子，猫可以坐在里面，也可以不坐在里面。
盒子的当前状态用序列 $b_{1}, \dots, b_{n}$ 表示：如果 $i$ 号盒子里有猫，则为 $b_{i} = 1$ ，否则为 $b_{i} = 0$ 。

幸运的是，猫可以无限量生产，因此科学家们可以在一天内完成以下操作之一：

取一只新猫并将其放入盒子中（对于 $i$ 中的 $b_{i} = 0$ ，指定 $b_{i} = 1$ ）。
从盒子中取出一只猫，让它退休（对于 $i$ 中的 $b_{i} = 1$ ，指定 $b_{i} = 0$ ）。
将一只猫从一个盒子移到另一个盒子（对于 $i, j$ 中的 $b_{i} = 1, b_{j} = 0$ ，指定 $b_{i} = 0, b_{j} = 1$ ）。

我们还发现，有些盒子里马上就装满了猫。因此，科学家们知道猫在盒子中的初始位置 $s_{1}, \dots, s_{n}$ 和期望位置 $f_{1}, \dots, f_{n}$ 。

指出检验假设所需的最少天数。

对于每组数据:
$\begin{matrix} n \\ s (s t r i n g) \\ f (s t r i n g) \end{matrix}$

Solution

实际上，一对 $(0, 1) (1, 0)$ 可以相互抵消掉，则答案就是 可以抵消掉的对数 加上 不能抵消掉的对数
可以抵消的个数为 $c n t = min (c n t_{1}, c n t_{2})$ ,没有抵消掉的个数为 $m a x (c n t_{1}, c n t_{2}) - c n t$
总数即为 $m a x (c n t_{1}, c n t_{2})$

string s, f;
void solve()
{
    int n;
    cin >> n;
    cin >> s >> f;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n;i++)
    {
        if(s[i]=='0'&&f[i]=='1')
            cnt1++;
        if(s[i]=='1'&&f[i]=='0')
            cnt2++;
    }
    int cnt = min(cnt1, cnt2);
    cout << cnt + (max(cnt1, cnt2) - cnt) << '\n';//cout<<max(cnt1,cnt2)<<'\n';
    //ans = the pair of <1,0>and <0,1>+the differences numbers
}

C . Sending Messages

需要在 $m_{1}, m_{2}, \dots m_{n}$ ( $m_{i} < m_{i + 1}$ ) 时刻发送 $n$ 条信息。
在 $0$ 时刻，他的手机只剩下 $f$ 单位的电量。在 $0$ 时刻，手机处于开机状态。

每开机一个单位，手机就会损失 $a$ 个单位的电量。
此外，斯捷潘可以随时关闭手机，稍后再打开。这一操作每次消耗 $b$ 个单位的能量。
考虑到开机和关机是瞬时的，因此您可以在 $x$ 时刻开机，并在同一时刻发送信息，反之亦然，在 $x$ 时刻发送信息，并在同一时刻关闭手机。

如果在任何时刻电量降至 $0$ （变为 $\leq 0$ ），则无法在该时刻发送信息。

由于所有信息对斯捷潘都非常重要，他想知道是否可以在不给手机充电的情况下发送所有信息。

给出 需要发送的信息数量、手机初始电量、单位时间电量消耗 以及 依次关机和开机时的电量消耗。
判断是否能够发送所有信息。
对于每组数据:
$\begin{matrix} n & f & a & b \\ m_{1} & m_{2} & m_{3} & \dots & m_{n} \end{matrix}$

Solution

#define int long long//注意要开ll
int m[200010];
void solve()
{
    int n, f, a, b;
    cin >> n >> f >> a >> b;
    for (int i = 1; i <= n;i++)
        cin >> m[i];
    sort(m + 1, m + 1 + n);
    for (int i = 1; i <= n;i++)
    {
        if(a*(m[i]-m[i-1])>b)
            f -= b;
        else
            f -= a*(m[i]-m[i-1]);
    }
    if(f>0)//在这里f>=0?题目似乎没给清楚
        cout << "yes\n";
    else
        cout << "no\n";
}

D . Very Different Array

给出 $a, b$ 数组，分别有 $n, m 个整数 (m \geq n)$ ，在 $b$ 数组中选出 $n$ 个数组成一个长度为 $n$ 的新数组使得:
$D = \sum_{i = 1}^{n} ∣ a_{i} - c_{i} ∣$ 最大并输出 $max (D)$

对于每组数据:

\begin{matrix} n & m \\ a_{1} & a_{2} & \dots & a_{n} \\ b_{1} & b_{2} & \dots & b_{m} \end{matrix}

Solution

我的想法是最大减去对应的最小的，但是是错误的

Hack 数据

2 6
7 9
8 1 10 6 3 9

按照我的思路：

$a : 7, 9$
$b : 10, 9, 8, 6, 3, 1$
大的减去对应小的: $D = (10 - 7) + (9 - 1) = 11 \neq 12$ $W A$

expect 12 BUT found 11

一个正确的思路和我的很像却也不同：

当选定 $n$ 个数的时候，只需要大的减去对应小的依次相加即可
一般中间的不取，只取前面 $i$ 个和后面 $n - i$ 个即可，(我做的时候是按照前面和后面均分来的，但是是错误的)

因此做法是：

确定一个界限 $i$ ，先按照对应（大对应小）来计算 ans，后面只需要计算变化量即可。

可以枚举每一种情况

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

    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1, greater<int>());

    long long ans = 0, tmp = 0;
    for (int i = 1; i <= n; i++)
        tmp += abs(a[i] - b[i]);
    ans = tmp;

    for (int i = 0; i < n; i++)
        tmp += abs(a[n - i] - b[m - i]) - abs(a[n - i] - b[n - i]),ans = max(ans, tmp);

    cout << ans << '\n';
}

E. Eat the Chip

Alice(白) 和 Bob(黑)能走的方向如图。双方都以最佳状态下棋，结果是？

对于每个样例：

\begin{matrix} h & w & x_{a} & x_{b} & y_{a} & y_{b} \end{matrix}

Solution

如果有一方发现自己会输，就会想办法平局，分类讨论，较为麻烦

先算出两人见面之前 $y$ 的范围，进攻方 $[l_{1}, r_{1}]$ ,防守方 $[l_{2}, r_{2}]$ ,满足： $l_{1} \leq l_{2} + 1, r_{1} \geq r_{2} - 1$ ,满足则可以 win，否则 Draw

void solve()
{
    int xs, ys, xa, ya, xb, yb;
    cin >> xs >> ys >> xa >> ya >> xb >> yb;
    if (xa >= xb)
    {
        cout << "Draw\n";
        return;
    }
    int x = xb - xa; //可达范围
    if (x % 2)
    {
        int la = max(1, ya - x / 2), ra = min(ys, ya + x / 2);
        int lb = max(1, yb - x / 2), rb = min(ys, yb + x / 2);
        if (la <= lb + 1 && ra >= rb - 1)
            cout << "Alice\n";
        else
            cout << "Draw\n";
    }
    else
    {
        int la = max(1, ya - x / 2), ra = min(ys, ya + x / 2);
        int lb = max(1, yb - (x - 1) / 2), rb = min(ys, yb + (x - 1) / 2);
        if (lb <= la + 1 && rb >= ra - 1)
            cout << "Bob\n";
        else
            cout << "Draw\n";
    }
}

F. Sum of Progression

给你一个由 $n$ 个数字组成的数组 $a$ 。还有 $q$ 个形式为 $s, d, k$ 的查询。

对于每个查询 $q$ ，求 $a_{s} + a_{s + d} \cdot 2 + \dots + a_{s + d \cdot (k - 1)} \cdot k$ 即：

\sum_{i = 1}^{k} a_{s + d (i - 1)} \times i

对于每个测试用例： $\begin{matrix} n & q \\ a_{1} & a_{2} & \dots & a_{n} \\ s_{1} & d_{1} & k_{1} \\ s_{2} & d_{2} & k_{2} \\ ⋮ & (q query) \\ s_{q} & d_{q} & k_{q} \end{matrix}$

Solution

根号分治
设置一个阈值: $$w=\sqrt{ n }$$

当 $d > w$ ,直接暴力做(因为这时的运算次数很少了)

当 $d \leq w$ ，开数组算前缀和. ( $s, d 分别代表 i, j$ )

$f$ 数组来记录 $⌊ \frac{s}{d} ⌋ \times a_{s + λ \times d}$ 前缀和，记录的是 $a_{s} \times ⌊ \frac{s}{d} ⌋ + s_{s + d} \times ⌊ \frac{s + d}{d} ⌋ + \dots$
$g$ 数组记录的是 $a_{s + λ \times d}$ 的前缀和，记录的是 $a_{s} + s_{s + d} + \dots$
差距 $(\frac{s}{d} - 1) g = a_{s} \times (\frac{s}{d} - 1) + a_{s + d} \times (\frac{s}{d} - 2) + \dots$
$\leftrightarrow$ $ans = f - (\frac{s}{d} - 1) g = a_{s} \times 1 + a_{s + d} \times 2 + \dots + a_{s + (k - 1) d} \times k = target$
$\leftrightarrow ans= f [s + d \times (k - 1)] [d] - f [s - d] [d] - (g [s + d \times (k - 1)] [d] - g [s - d] [d]) \times (\frac{s}{d} - 1)$

处理方式可能不止一种...

int n,q,a[100010];
ll f[100010][350],g[100010][350];//序号 步长d 
sync_with_stdio(false), cin.tie(nullptr);//必须关闭同步流，不然会超时
void solve()
{
    cin >> n >> q;
	int value = sqrt(n);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int d = 1; d <= value; d++){
        for (int i = 1; i <= n; i++){
            f[i][d] = ((i - d > 0) ? f[i - d][d] : 0ll) + 1ll * a[i] *(i / d); //((i - 1) / d + 1);灰色的另一种也可以
            g[i][d] = ((i - d > 0) ? g[i - d][d] : 0ll) + a[i];
        }
    }
    ll ans;
    while (q--){
        cin >> s >> d >> k;
        ans = 0;
        if (d > value){
            for (int i = 0; i < k; i++)
                ans += 1ll * a[s + i * d] * (i + 1);
        }
        else{
            ans = f[s + d * (k - 1)][d] - ((s - d > 0) ? f[s - d][d] : 0);
            ans -= (g[s + d * (k - 1)][d] - ((s - d > 0) ? g[s - d][d] : 0)) * (s / d - 1); //((s - 1) / d);
        }
        cout << ans << '\n';
    }
}

G. Mischievous Shooter

谢尔只带了一把幸运猎枪，他可以朝四个方向之一射击：右下、左下、左上或右上。射击时，霰弹枪会击中所选方向上的所有目标，这些目标的曼哈顿距离不会超过一个固定常数 $k$ .

每个测试用例：

$\begin{matrix} n & m & k \\ s t r (m_{1}) \\ s t r (m_{2}) \\ ⋮ \\ s t r (m_{n}) \end{matrix}$
其中字符". "表示单元格为空，字符 "#"表示存在目标.

输出一个整数，该整数等于一次射击击中目标的最大可能数目。

输入样例

4
3 3 1
.#.
###
.#.

2 5 3
###..
...##

4 4 2
..##
###.
#..#
####

2 1 3
#
#

输出样例

Notes：

Solution

(待更...)