T1

期望得分:****(没想得几分，有分就行).瞎凑了一个公式..

题目描述

最近公共祖先（Lowest Common Ancestor,LCA）是指在一个树中同时拥有给定的两个点作为后代的最深的节点。
为了学习最近公共祖先，你得到了一个层数为 \(n + 1\) 的满二叉树，其中根节点的深度为 \(0\)，其他
节点的深度为父节点的深度 \(+1\) 。你需要求出二叉树上所有点对 \((i,j)\),（\(i,j\) 可以相等，也可以 \(i > j\)）
的最近公共祖先的深度之和对 \(1e9 + 7\) 取模后的结果。

输入格式

一行一个整数 n 。

输出格式

一行一个整数表示所有点对 (i,j),（i,j 可以相等，也可以 i > j）的最近公共祖先的深度之和对
10 9 + 7 取模后的结果。
____________________________

数据范围

对于\(20\%\)的数据, \(n\leq 10\).
对于\(50\%\)的数据, \(n\leq10^6\).
对于\(100\%\)的数据,\(n\leq10^9\).

解题思路：

在节点i处的子树的节点数是n-i+1,然后因为这两个子树各取一个点的LCA才是当前的i节点.

以LCA为根节点，然后再两个子树中选，那么点的个数就是\(\frac{n-i+1}{2}\ast \frac{n+i+1}{2} \ast 2\).

对于每一个子树来说，子树中的每一个点与LCA本身的LCA也是LCA(有点绕),那么他的贡献就变成了\((2^{n-i+1}-1) \ast i \ast 2\)

因为自己和自己的LCA也要贡献答案,设上边两个贡献的和为\(tmp\),那么贡献就是这样的\((tmp + i) \ast 2^i\)

那么\(ans\)就是：\(\displaystyle \sum^{n}_{i=1}{((\frac{n-i+1}{2}\ast \frac{n+i+1}{2} \ast 2 +(2^{n-i+1}-1) \ast i \ast 2 ) + i) \ast 2 ^ i}\)

把上边这一坨都化简之后就是\(\sum_{i = 1}^{n}{( 2^{2n - i + 1} - 2^i)\ast i}\)

然后我们设
\(p = 2 ^ {2n} - 2^1 + 2 * (2 ^{2n - 1} - 2 ^ 2) + 3 * (2 ^ {2n - 2}- 2 ^ 3) + ...+ n * (2 ^ {n + 1} - 2 ^ n)\)

\(2p = 2 ^ {2n +1} - 2 ^ 2 +2 * (2^{2n} - 2^3) + 3 * (2^{2n - 1} - 2^4) + ... +n*(2^{n + 2} - 2^ {n+ 1})\)

展开之后：
\(p = 2 ^ {2n} - 2^1 + 2 * 2 ^{2n - 1} - 2 * 2 ^ 2 + 3 * 2 ^ {2n - 2}-3* 2 ^ 3 + ...+ n * 2 ^ {n + 1} - n * 2 ^ n\)

\(2p = 2 ^ {2n +1} - 2 ^ 2 +2 * 2^{2n} - 2*2^3 + 3 * 2^{2n - 1} - 3*2^4 + ... +n*2^{n + 2} - n*2^ {n+ 1}\)

\(2p - p = \sum_{i = 1}^ {n}{2^I} + \sum_{i = n +1}^ {2n} 2^i - n * 2 ^ {n + 1}\)

化简之后答案为：

\(ans = 2 ^{2n + 2} + 2^ {n + 1} -(n + 1) * 2^{n + 2} - 2\)

然后就可以用快速幂\(\O(1)\)求了.

code

#include <bits/stdc++.h>
#define N 100010
#define M 1010
#define ll long long

using namespace std;
ll n, sum;
const int mod = 1e9 + 7;

ll read() {
    int s = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

ll q_pow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

signed main() {
//  freopen("commonants.in", "r", stdin);
//  freopen("commonants.out", "w", stdout);
    n = read();
    ll q = q_pow(2, 2 * n + 2), w = q_pow(2, n);
    w = (w * (4 * n + 2) % mod) % mod;
    sum = q - w - 2;
    cout << (sum + mod) % mod;
}

T2 即时战略 (rts.c/cpp/pas)

期望得分：40

实际得分：40（暴力求解）

题目描述

\(LKP\)在玩一个即时战略 (Real Time Strategy) 游戏。与大多数同类游戏类似，这个游戏的地图是平面的，并且玩家都有一个基地。
\(LKP\) 的对手杰哥的基地是一个 \(w \ast h\) 的矩形。其中矩形的每个格子都有一个建筑，每个建筑都有一个重要度。其中第 \(i\) 行第 \(j\) 列的格子中的建筑的重要度为 \(w_{ij}\) 。
\(LKP\)决定轰炸杰哥的基地。他可以选择杰哥基地的任何一个格子释放一个能量为 \(p\) 的炸弹。释放以后，这个格子的建筑会受到 \(p\) 的摧毁度。炸弹产生的冲击波可以向四个方向扩散，每扩散一格能量值会减少 \(1\) 。即释放位置相邻的 \(4\) 个格子会受到 \(p − 1\) 的摧毁度，再向外的 \(8\) 个格子会受到 \(p − 2\)的摧毁度 ... 直到能量值减为 \(0\) ，形式化的讲，如果在第 \(x\) 行第 \(y\) 列释放炸弹，那么第 \(i\) 行第 \(j\) 列的格子受到的摧毁度 \(d_{ij} = max(0,p − (| x − i | + | y − j |))\) 。
对于每个的格子，杰哥受到的损失即为这个格子的重要度与受到的摧毁度的乘积，即 \(w_{ij} \ast d_[ij]\) 。
HLY 想知道，对于每一种投放炸弹的方案，杰哥受到的最小总损失和最大总损失各为多少，形式化的讲，即为
\(\sum_{i = 1}^{w} \sum_{j = 1}^{h} {w_{ij} \ast d_{ij}}\)
的最小值与最大值。

输入格式

第 \(1\) 行三个整数 \(w,h,p\) 。
接下来 $w $行，每行 \(h\) 个整数。从第 \(2\) 行开始第 \(i\) 行第 \(j\) 个整数表示 \(w_{ij}\) 。

输出格式

一行两个数，表示杰哥受到的最小总损失和最大总损失，用空格隔开。

数据范围

对于 \(100\%\) 的数据，\(1 ≤ n,m ≤ 400\),\(1 ≤ p ≤ 200\),\(0 ≤ w_{ij} ≤ 10 ^5\) 。
子任务 1 （\(10\) 分） ：满足 \(p = 1\) 。
子任务 2 （\(30\) 分） ：满足 \(1 ≤ n,m ≤ 40\) 。
子任务 3 （\(60\) 分） ：没有特殊限制。

解题思路：

把这个东西翻转45°看成一个斜着的矩形，然后中间的那一部分类似菱形的东西就变成了矩形
然后就能用前缀和做了，做的时候一层一层的加上.从最外层开始，
最外边加一，往里一次加2.3.4然后枚举每个点做上述操作，然后就做完了.

code

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
const int maxn = 1010;

int g[maxn][maxn], trans[maxn][maxn];
long long s[maxn][maxn];

int main() {
//  freopen("rts.in", "r", stdin);
//  freopen("rts.out", "w", stdout);
    int n, m, p;
    long long mx = 0x8000000000000000ll, mn = 0x7fffffffffffffffll;
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= m; ++j) 
            scanf("%d", g[m + i - j] + i + j - 1);
    for (int i = 1; i < n + m; ++i) 
        for (int j = 1; j < n + m; ++j) 
            s[i][j] = g[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= m; ++j) {
            int x = m + i - j, y = i + j - 1;
            long long ans = 0;
            for (int k = 0; k < p; ++k) {
                int x1 = std::max(x - k, 1), y1 = std::max(y - k, 1);
                int x2 = std::min(x + k, n + m - 1), y2 = std::min(y + k, n + m - 1);
                ans += s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
            }
            mx = std::max(mx, ans), mn = std::min(mn, ans);
        }
    std::cout << mn << " " << mx << std::endl;
    return 0;
}