首页 > 软件开发 > 软件开发

C. Celex Update (思维)

admin 软件开发 2021-05-25 09:26:40
后台-系统设置-扩展变量-手机广告位-内容正文底部

题意
题目链接
给你一个这样的图形,只能向右向下走,问你从(x1,y1)走到(x2,y2),对经过的数字进行求和,问你求得的和有多少种。
在这里插入图片描述
思路
我们可以找一组数两组数进行枚举找一下规律。
在这里插入图片描述
假如我们从(1,1)到(3,3),我们可以求出每种情况的和。
1+2+4+8+13=28
1+2+5+8+13=29
1+2+5+9+13=30
1+3+5+9+13=31
1+3+6+9+13=32
我们可以从这些数中看出规律,情况数就是路径的最大值减去路径的最小值+1。
然后我们再解决如何求最大值减去最小值的差,如果直接算肯定是不行的,我们需要再找一些规律。
我们设短边为x,则最差值就是。
我们假设两种路径形成的矩形的较小边长是x,较大边长是y,我们就会发现,就是求0+1+2+…+x+x+x…+x+x-1+x-2+…+2+1+0,这就是最大值和最小值的差(对应路径中每一步,获得的差值。)然而中间的x有多少个呢?我们发现总共的步数有(y+x+1)步,前后两个(0+1+2+…+x-1),花费了2 * x步,所以有(y-x+1)个x,所以最后差值就是(y-x+1) * x+x * (x-1) ,也就是y * x 。所以最小值和最大值之间就有y *x+1个数,答案就是y * x+1。
代码

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll dp[100010];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<abs(x1-x2)*abs(y1-y2)+1<<endl;
    }
    return 0;
}

总结
这一题的关键就是善于找到规律。

文章来源:https://blog.csdn.net/qq_45719639/article/details/117195132

后台-系统设置-扩展变量-手机广告位-内容正文底部
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。
本文地址:https://www.jcdi.cn/ruanjiankaifa/30821.html

留言与评论(共有 0 条评论)
   
验证码:
后台-系统设置-扩展变量-手机广告位-评论底部广告位

教程弟

https://www.jcdi.cn/

统计代码 | 京ICP1234567-2号

Powered By 教程弟 教程弟

使用手机软件扫描微信二维码