寒假思维训练day13 D. Umka and a Long Flight

2024-01-27 17:14:01
开发
41

寒假思维训练Day13

今天更新一道1700的构造题，附上详细的数学证明和Python、C++代码。

摘要：

题目链接：有需要自取，Problem - 1811D - Codeforces

part1：题意

part2: 题解 (附带数学推导，latex版本)

part3: 代码(py + cpp)

part4: 对构造题的一些总结心得和对应例题。

Part1 题意：Problem - 1811D - Codeforces

1、符号说明：

设 $F[i]$ 为斐波那契数列的第 $i$ 项，满足 $F[0] = F[1] = 1, F[2] = 2, F[n] = F[n - 1] + F[n - 2]$

2、题意：

给定一个 $n$ ，有一个矩形高度为 $F[n]$ ，长度为 $F[n + 1]$ ，要求将其分割成 $n + 1$ 个长度为斐波那契数的正方形，其中还给定一个 $x,y$ ，使得第 $x$ 行和第 $y$ 列必须是一个长度为 $1$ 的正方形，并且要满足相同的正方形个数最多为两个，问最后能否将其分割成 $n + 1$ 个长度为斐波那契数的正方形，能输出"YES",否则输出"NO"。

Part2 题解：

LaTex格式的推导，加上详细的文字说明和相对严谨的语言。

1、已知 $n, x, y$ ，矩形的高为 $F[n]$ ,长为 $F[n + 1]$

2、假设 $x_i$ 为某一项斐波那契数，矩形的长的左边界为 $ys$ ，右边界为 $ye$ ，宽的上边界为 $xs$ ，下边界为 $xe$ ，记成 $xstart,xend,ystart,yend$ 比较清楚, $(x,y)$ 表示此位置上面的长度为1的正方形
3、要将矩形分割成 $n + 1$ 块斐波那契正方形, 可以对面积进行抽象,

对较大项 $i$ 不断进行拆解，使得 $F[i] = F[i - 1] + F[i - 2]$

$F[n] * F[n + 1] = F[n] * (F[n] + F[n - 1]) = F[n]^2 + F[n] * F[n - 1] \\ = F[n]^2 + F[n - 1]^2 + ... + F[2] * F[1] = F[n]^2 + F[n - 1]^2 + ... + F[1]^2 + F[1] * F[0] = F[n]^2 + F[n - 1]^2 + ... + F[1]^2 + F[0]^2$
4、得到结论： $F[n] * F[n + 1] = F[0]^2 + F[1]^2 + ... + F[n]^2$ ，显然满足题目要求的性质，也符合面积的划分性质，我们依此继续往下推导。

5、我们假设从最大的 $F[n]^2$ 开始从大到小划分正方形位置，我们来考虑一下这个划分位置策略的正确性：
假设随意分割好了满足条件的 $n + 1$ 个正方形，那么对于最大的 $F[n]$ ，假如不在两侧，在中间，两边的长度之和为 $F[n - 1]$ 它们单独拿出来一定小于 $F[n - 1]$ ，此时无法构造，矛盾，接下来我们按照这个策略进行讨论。
先考虑最初的矩形，刚开始长边是 $F[n + 1]$ , 高是 $F[n]$ , 所以要么是 $x$ 方向保持不变， $y$ 方向上要么是 $[ys, ye - F[n]] + [ye - F[n] + 1, ye]$ 此处前部分是剩下的，后部分是给 $F[n]$ 正方形的; 要么是 $[ys, ys + F[n] - 1], [ys + F[n], ye]$ ,与前面相反，同时我们应该满足 $(x,y)$ 位置的正方形应该只在一边才行，假设两边都占有 $(x,y)$ 的部分，此时该长度的正方形显然无法分配位置了，如果两种划分方式有一种可以满足条件就选择那种，并且继续往存在 $(x,y)$ 的位置递归，最终如果递归到 $n + 1$ ，按照该策略必然有解，而且能构造出答案。
6、推导完成。

Part3: 代码部分（包含python代码和cpp代码）

代码思路在题解中。

1、Python: 发现了python的一个神奇的地方，python的递归栈是很慢的，在C++代码我写了递归，但是在python这边写一样的方法会TLE, 我改成循环就通过了，这以后将是python编程优化的一个考虑方向。

def dfs(xs, xe, ys, ye, x, y, c, t, n):
    while c < n:
        if ye - ys > xe - xs:
            f1 = x >= xs and x <= xe and y >= ys and y <= ye - fb[t]
            f2 = x >= xs and x <= xe and y >= ys + fb[t] and y <= ye
            if f1 and not f2:
                xe, ye, t, c = xe, ye - fb[t], t - 1, c + 1
            elif not f1 and f2:
                xs, ys, t, c = xs, ys + fb[t], t - 1, c + 1
            else: break
        else:
            f1 = x >= xs and x <= xe - fb[t] and y >= ys and y <= ye
            f2 = x >= xs + fb[t] and x <= xe and y >= ys and y <= ye
            if f1 and not f2:
                xe, ye, t, c = xe - fb[t], ye, t - 1, c + 1
            elif not f1 and f2:
                xs, ys, t, c = xs + fb[t], ys, t - 1, c + 1
            else: break
    return c == n

def solve():
    n, x, y = map(int, input().strip().split())
    h, k = fb[n], fb[n + 1]
    if dfs(1, h, 1, k, x, y, 0, n, n):
        print("YES")
    else:
        print("NO")

ts = int(input())
fb = [0] * 50
fb[0] = fb[1] = 1
for i in range(2, 46):
    fb[i] = fb[i - 1] + fb[i - 2]

for _ in range(ts):
    solve()

1、CPP: 递归

#include <bits/stdc++.h>
#define int long long 
using namespace std;
using PII = pair<int, int>; 
constexpr int N = 100; 
constexpr int inf = 0x3f3f3f3f; 
int n, m; 
int fb[N]; 
bool flag; 
void dfs(int xs, int xe, int ys, int ye, int x, int y, int c, int t) {
    if(c == n) {
        flag = true;
        return;
    }  
    if(flag) return; 
    if(ye - ys > xe - xs) { // 列 > 行 
        if(flag) return;
        bool f1 = x >= xs && x <= xe && y >= ys && y <= ye - fb[t], 
        f2 = x >= xs && x <= xe && y >= ys + fb[t] && y <= ye;
        if(f1 && !f2) dfs(xs, xe, ys, ye - fb[t], x, y, c + 1, t - 1);
        else if(!f1 && f2) dfs(xs, xe, ys + fb[t], ye, x, y, c + 1, t - 1); 
    }
    else {
        if(flag) return;
        bool f1 = x >= xs && x <= xe - fb[t] && y >= ys && y <= ye, 
        f2 = x >= xs + fb[t] && x <= xe && y >= ys && y <= ye; 
        if(f1 && !f2) dfs(xs, xe - fb[t], ys, ye, x, y, c + 1, t - 1); 
        else if(!f1 && f2) dfs(xs + fb[t], xe, ys, ye, x, y, c + 1, t - 1); 
    }
} 

void solve() {
    flag = 0; 
    int x, y; 
    cin >> n >> x >> y; 
    int h = fb[n], k = fb[n + 1];
    dfs(1, h, 1, k, x, y, 0, n);
    if(flag) puts("YES"); 
    else puts("NO"); 
    
}
signed main() {
    fb[0] = fb[1] = 1;
    for(int i = 2; i <= 45; i ++ ) fb[i] = fb[i - 1] + fb[i - 2];  
    int ts; 
    cin >> ts; 
    while(ts --) solve(); 
    return 0; 
}

Part4: 对构造题的一些总结心得和对应例题。

1、前后缀贪心模型，比如说观察前后缀的sum，去看以后怎么考虑最好。Problem - 1903C - Codeforces

2、双指针贪心模型，考虑两端相消或者相互作用，还有就是考虑左右边界。 Problem - 1891C - Codeforces

Problem - 1907D - Codeforces

3、转换观察法模型，有些关系可以抽象成图，观察图的某些性质去总结规律。也可以抽象成一个集合，两个集合相等可以说明有解可构造。Problem - 1891C - Codeforces

4、打表找规律模型，一般没什么规律可循即可打表找规律，一般和数论有关的很喜欢考，acm也喜欢考，属于人类智慧题。Problem - 1916D - Codeforces

5、公式推导演算模型，常见的分为公式的等价变形、公式的化简（这个常考，一般需要先证明某些性质，可以直接抵消，一般如果原公式处理起来很复杂时就可以考虑）。Problem - 1889B - Codeforces

6、考虑奇偶数去简化问题或者分类问题模型，从其中的一些运算性质入手，因为奇数偶数的加减以及%运算（这个结论很重要）的结果的奇偶性是固定的，Problem - 1898C - Codeforces

7、根据性质构造模型，看看能不能分成几个块，几个不同的集合，再选择算法去解决。Problem - 1873G - Codeforces

8、考虑从小到大处理模型，或者是从大到小处理，有时候先处理小的对大的不会有影响，或者反过来，这样的处理顺序是最完美的。Problem - 1904D2 - Codeforces

9、边界贪心法模型，一般要在问题的最边界处考虑，有时候这样做结果是最优的，或者考虑边界上的影响，假如让影响最小，就使得影响<= 固定值。 Problem - E - Codeforces and Problem - 1903C - Codeforces

Problem - D - Codeforces

上面的题目用到了9、边界贪心法模型。

感谢观看！会持续更新。

原文地址:https://blog.csdn.net/m0_74847145/article/details/135839249 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1751171691100377088.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部