[已解决]梦想星际舰队第24关 && FCOI #9 第五题格子题解【原创】

zhangjinxuan

梦想星际舰队第24关 && FCOI #9 题解

第五题：格子

题目描述
有一种在网格图内的由 0 1 依次交错组成的网格图 G（如下图）。

010101010101
110101010101
000101010101
111101010101
000001010101 ...
111111010101
000000010101
111111110101
000000000101
111111111101
000000000001
111111111111
   
   .
   .
   .

这个是向右向下无限延伸的。

写一个程序，对于给定的一个矩形区域，计算区域内有多少个 1。

形式化地说，给定 (x1,y1),(x2,y2)，你需要求出 ∑_(i=x1)^(x2) [∑_(j=y1)^(y2)[G i,j=1]]。

请注意，关于坐标的描述就是先行后列，(2, 3) 表示 2 行 3 列。

输入格式
四个整数 x1,y1,x2,y2。

输出格式
一个整数表示答案。

输入输出样例
输入 #1

2 2 4 6

输出 #1

9

输入 #2

1 1 1000000000 1000000000

输出 #2

500000000500000000

数据范围
1≤x1<x2≤10^9 ,1≤y1<y2≤10^9

其他说明
本题目为 zhangjinxuan 原创题目。
测试链接：https://www.luogu.com.cn/problem/U330662

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-8-25 19:14:04

让我重新拿回满分

x1, y1, x2, y2 = map(int, input().split())
ans = 0
ans += (min(x2, y2) // 2) * (min(x2, y2) // 2 * 4 + 2) // 2
ans += (max(x2, y2) - min(x2, y2) // 2 * 2) // 2 * min(x2, y2)
if y1 > 1:
    ans -= (min(x2, y1 - 1) // 2) * (min(x2, y1 - 1) // 2 * 4 + 2) // 2
    ans -= (max(x2, y1 - 1) - min(x2, y1 - 1) // 2 * 2) // 2 * min(x2, y1 - 1)
if x1 > 1:
    ans -= (min(x1 - 1, y2) // 2) * (min(x1 - 1, y2) // 2 * 4 + 2) // 2
    ans -= (max(x1 - 1, y2) - min(x1 - 1, y2) // 2 * 2) // 2 * min(x1 - 1, y2)
if x1 > 1 and y1 > 1:
    ans += (min(x1 - 1, y1 - 1) // 2) * (min(x1 - 1, y1 - 1) // 2 * 4 + 2) // 2
    ans += (max(x1 - 1, y1 - 1) - min(x1 - 1, y1 - 1) // 2 * 2) // 2 * min(x1 - 1, y1 - 1)
print(ans)

真.照着写

跳转到最佳答案楼层

zhangjinxuan

@额外减小 @sfqxx @Ewan-Ahiouy

Mike_python小

梦想星际舰队第24关 && FCOI #9 第五题格子题解

这道题目是关于一个由0和1组成的网格图的计算问题。题目要求计算给定矩形区域内的1的个数。

根据题目描述，我们可以发现该网格图的规律是：每隔一列的数字是0、1、0、1...交替出现，并且每隔两行整体向上或向下平移一位。

解题思路如下：

首先，我们可以观察到每个矩形区域的左上角坐标都在每隔两行整体平移后的某个位置上，而每个矩形区域的右下角坐标则是相对于该位置的偏移量。

由于矩形区域的大小可能非常大，直接遍历矩形区域内的每个格子来统计1的个数是不可行的。因此，我们需要寻找一种更高效的方法。

观察到网格图整体向上或向下平移一位，我们可以发现在每隔两行平移之后，矩形区域内1的个数也会重复出现。

假设每隔两行平移后的位置为(x', y')，其中x'和y'分别表示平移后位置的行号和列号。那么我们可以通过计算[x2/2] - [(x1-1)/2]来得到平移后位置的行号x'，其中[]表示取整操作。

接下来，我们需要计算矩形区域内每一列中1的个数。观察到每隔一列出现的数字是0、1、0、1...交替出现，我们可以发现每隔两列1的个数是相同的。

假设每隔两列1的个数为count，那么我们可以通过计算[count * (y2-y1+1)/2]来得到矩形区域内每隔两列1的个数，其中y2-y1+1表示矩形区域的列数。

最后，我们需要计算矩形区域右侧剩余的一列中1的个数。我们可以观察到这一列的1的个数与矩形区域的行数相关，具体计算方法为将矩形区域的行数mod 2，再与每隔两行平移后的位置的行号x'进行比较，如果小于等于x'，则该列中的1的个数为矩形区域的行数mod 2，否则为矩形区域的行数mod 2 - 1。

综上所述，我们可以按照上述步骤计算出矩形区域内的1的个数。

希望以上解析能对您有所帮助！如果还有其他问题，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！

isdkz

根据题目描述，我们需要计算给定矩形区域内的1的个数。题目中给出了一个由0和1交错组成的无限延伸的网格图G。

我们可以观察到，网格图G中的每一行的1的个数都是相同的，且每一个1的位置都是连续的。所以我们可以通过计算每一行中1的个数，再将其乘以区域的行数，就可以得到区域内1的总个数。

首先，我们需要计算给定区域的起始行和结束行分别对应的1的个数。假设每一行中1的个数为count，起始行为x1，结束行为x2，那么起始行对应的1的个数为count * (y2 - y1 + 1)，结束行对应的1的个数为count * (y2 - y1 + 1)。因为起始行和结束行之间的行数为x2 - x1 + 1，所以我们还需要加上这个区间内每一行的1的个数，即count * (x2 - x1 + 1)。

综上所述，我们可以得到区域内1的总个数为count * (y2 - y1 + 1) + count * (x2 - x1 + 1)。

接下来，我们需要计算每一行中1的个数count。观察题目给出的网格图G，我们可以发现每一行中1的个数是以2为周期重复出现的。即第一行和第三行的1的个数相同，第二行和第四行的1的个数相同，以此类推。

所以我们可以将给定的区域的起始行和结束行分别对2取模，得到一个余数。如果余数为0，则说明起始行和结束行在同一个周期内，即count为(y2 - y1 + 1) / 2。如果余数为1，则说明起始行和结束行在不同的周期内，即count为(y2 - y1 + 1) / 2 + 1。

综上所述，我们可以得到每一行中1的个数count为(y2 - y1 + 1) / 2 或 (y2 - y1 + 1) / 2 + 1。

最后，我们将count代入前面的公式，即可得到区域内1的总个数。

以下是具体的代码实现：

def calculate_ones(x1, y1, x2, y2):
    count = (y2 - y1 + 1) // 2 if (x1 % 2 == 0) else (y2 - y1 + 1) // 2 + 1
    total_ones = count * (y2 - y1 + 1) + count * (x2 - x1 + 1)
    return total_ones

x1, y1, x2, y2 = map(int, input().split())
result = calculate_ones(x1, y1, x2, y2)
print(result)

希望能对你有帮助！

sfqxx

我要看看为什么我这道题寄了

奋斗中的鱼

看错抱歉

zhangjinxuan

奋斗中的鱼 发表于 2023-8-25 19:06
都……23关了？我是不是太lazy了？
不对吼，我好像都不会
sorry！

so，你是梦想护卫舰的成员吗

陈尚涵

看看

陈尚涵

我就知道，用数学，但是根本想不到

sfqxx

让我重新拿回满分

x1, y1, x2, y2 = map(int, input().split())
ans = 0
ans += (min(x2, y2) // 2) * (min(x2, y2) // 2 * 4 + 2) // 2
ans += (max(x2, y2) - min(x2, y2) // 2 * 2) // 2 * min(x2, y2)
if y1 > 1:
    ans -= (min(x2, y1 - 1) // 2) * (min(x2, y1 - 1) // 2 * 4 + 2) // 2
    ans -= (max(x2, y1 - 1) - min(x2, y1 - 1) // 2 * 2) // 2 * min(x2, y1 - 1)
if x1 > 1:
    ans -= (min(x1 - 1, y2) // 2) * (min(x1 - 1, y2) // 2 * 4 + 2) // 2
    ans -= (max(x1 - 1, y2) - min(x1 - 1, y2) // 2 * 2) // 2 * min(x1 - 1, y2)
if x1 > 1 and y1 > 1:
    ans += (min(x1 - 1, y1 - 1) // 2) * (min(x1 - 1, y1 - 1) // 2 * 4 + 2) // 2
    ans += (max(x1 - 1, y1 - 1) - min(x1 - 1, y1 - 1) // 2 * 2) // 2 * min(x1 - 1, y1 - 1)
print(ans)

真.照着写

liuhongrun2022

这个程序是用来计算给定矩形区域内有多少个1的。我会对代码进行解释：

def calculate_ones(x1, y1, x2, y2):    count = (y2 - y1 + 1) // 2 if (x1 % 2 == 0) else (y2 - y1 + 1) // 2 + 1    total_ones = count * (y2 - y1 + 1) + count * (x2 - x1 + 1)    return total_onesx1, y1, x2, y2 = map(int, input().split())result = calculate_ones(x1, y1, x2, y2)print(result)

这部分代码定义了一个`calculate_ones`函数，用来计算给定矩形区域内的1的数量。函数接受四个参数：`x1`、`y1`、`x2`、`y2`，表示矩形区域的坐标范围。函数通过判断`x1`的奇偶性来确定起始位置，然后根据矩形的宽度和高度计算出1的数量，并返回结果。

接下来，代码从输入中读取四个整数`x1`、`y1`、`x2`、`y2`，然后调用`calculate_ones`函数计算结果，并将结果打印输出。

x1, y1, x2, y2 = map(int, input().split())ans = 0ans += (min(x2, y2) // 2) * (min(x2, y2) // 2 * 4 + 2) // 2ans += (max(x2, y2) - min(x2, y2) // 2 * 2) // 2 * min(x2, y2)if y1 > 1:    ans -= (min(x2, y1 - 1) // 2) * (min(x2, y1 - 1) // 2 * 4 + 2) // 2    ans -= (max(x2, y1 - 1) - min(x2, y1 - 1) // 2 * 2) // 2 * min(x2, y1 - 1)if x1 > 1:    ans -= (min(x1 - 1, y2) // 2) * (min(x1 - 1, y2) // 2 * 4 + 2) // 2    ans -= (max(x1 - 1, y2) - min(x1 - 1, y2) // 2 * 2) // 2 * min(x1 - 1, y2)if x1 > 1 and y1 > 1:    ans += (min(x1 - 1, y1 - 1) // 2) * (min(x1 - 1, y1 - 1) // 2 * 4 + 2) // 2    ans += (max(x1 - 1, y1 - 1) - min(x1 - 1, y1 - 1) // 2 * 2) // 2 * min(x1 - 1, y1 - 1)print(ans)

这部分代码使用数学公式来计算矩形区域内的1的数量。首先，根据最小值和最大值计算出矩形的宽度和高度。然后按照不同情况计算出1的数量，并将结果累加到变量`ans`中。

最后，根据矩形区域的起始坐标，对`ans`进行调整。如果起始y坐标大于1，则减去前面的部分；如果起始x坐标大于1，则减去上方的部分；如果起始x和y坐标同时大于1，则加上左上角部分。

最后，将调整后的`ans`打印输出。

希望这个解答能够帮助到您！如果还有其他问题，请随时提问。

此内容为ChatGPT回答，如果对你有帮助，请设置一个最佳答案！

zhangjinxuan

liuhongrun2022 发表于 2023-8-25 19:17
这个程序是用来计算给定矩形区域内有多少个1的。我会对代码进行解释：

有点慢了

额外减小

啊啊啊，如果我犯了低级错误的话就太令人悲伤了。

额外减小

我这个代码错哪了？我是不是没有特判？@sfqxx @Ewan-Ahiouy @zhangjinxuan

#include <cstdio>
#include <algorithm>
using namespace std;
//膜拜@zhangjinxuan dalao %%%orz 

inline int is_0_or_1(int x,int y)
{
        if(y>x)swap(x,y);
        return !(x%2);
}


int main()
{
        int x1,x2,y1,y2;
        unsigned long long ans=0;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        if(x2<y2)
        {
                swap(x1,y1);
                swap(x2,y2);
        }//保证直线部分在右边不在下边 
        //part 1 有棱角
        
        long long j1,j2;
        j1=x1>y1?x1:y1;
        if(j1%2)j1++;
        j2=x2>y2?y2:x2;
        if(j2%2)j2--;
        long long sx=j1*2-x1-y1+1,mx=j2*2-x1-y1+1;
        ans+=(sx+mx)*((j2-j1)/2+1)/2;
        
        
        //part 2 直线
        long long zs=j2+2,zw=x2%2?x2-1:x2;
        ans+=((zw-zs)/2+1)*(y2-y1+1);
        printf("%llu\n",ans);
         
        
}

额外减小

额外减小 发表于 2023-8-25 19:29
我这个代码错哪了？我是不是没有特判？@sfqxx @Ewan-Ahiouy @zhangjinxuan

我的思路就是没那么麻烦，直接分两部分，一部分也是等差数列但首项不为1，另一部分也是直线，就3个点挖了，死活看不出错

zhangjinxuan

额外减小 发表于 2023-8-25 19:29
我这个代码错哪了？我是不是没有特判？@sfqxx @Ewan-Ahiouy @zhangjinxuan

我去。

额外减小

zhangjinxuan 发表于 2023-8-25 19:30
我去。

？

zhangjinxuan

额外减小 发表于 2023-8-25 19:30
？

看着有点脑瓜疼……我分析一下

额外减小

zhangjinxuan 发表于 2023-8-25 19:30
看着有点脑瓜疼……我分析一下

我的思路：由于图形关于y=x的对称性，可以通过交换x,y来使直线部分都在右边。

01 01010101
11 01010101
    --------------
00|01010101|
11|11010101|
00|00010101|
11|11110101|
     --------------
00 00000101
11 11111101
00 00000001
11 11111111

然后就是分成棱角和直线两部分。
其中，j1,j2表示区域内边缘的两个拐点的坐标（x=y），通过等差数列判断折线总长度（相邻两项差4）
然后j2+2就是直线部分开始的横坐标，zw就是直线部分结束的最后一个横坐标。求和一下就是直线的总长度

Ewan-Ahiouy

额外减小 发表于 2023-8-25 19:29
我这个代码错哪了？我是不是没有特判？@sfqxx @Ewan-Ahiouy @zhangjinxuan

别问我，我不会