[bzoj3505][CQOI2014]数三角形_组合数学
2024-08-31 15:10:59
数三角形 bzoj-3505 CQOI-2014
题目大意:给你一个n*m的网格图,问你从中选取三个点,能构成三角形的个数。
注释:$1\le n,m\le 1000$。
想法:本来是想着等中考完了之后花上一周的时间把之前欠的blog都更掉,然后做了这道题发现网上的题解让我匪夷所思(他们写着任何人都能看懂的代码,说着只有自己才能听懂的话)。其实是这样的,求三角形个数就等价于求有多少种选取的方案使得三点共线。显然竖着的和横着的都是可以O(1)的,我们只需要计算斜着的就行了。那么,我们枚举什么才能使得在O(能过)的情况下出解?我们对于一个网格图(0,0)到(a,b),对角线上的点显然可以用gcd来求。我们已经知道了对角线上的点,然后算一下这些点所有的三点共线的方案数?算完了之后发现后面没法进行了,所以对于每一个这样的矩形我们不能直接计算。我们对于每一个a*b的网格矩形只计算这样的三点共线:这三个共线的点中外边两个点之间线段是我们枚举网格矩阵的对角线。换言之,我们对于一个已经求好了对角线上有多少整点的方格矩形,它对答案的共线就是gcd。这样计算是不会重复的,对于每一种三点共线的选取方案,只会在端点是当前枚举矩形的对角线端点是才会被计算,所以这样是不重不漏的。我们这样枚举贴在(0,0)上的矩形,紧接着算一下整个n*m的方格图里有多少这样的矩形,然后直接累计答案即可。总时间复杂度O(n*n*(gcd的log))。
最后,附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,m;
ll ans;
ll C(int x)
{
return (ll)x*(x-1)*(x-2)/6;
}
int main()
{
scanf("%d%d",&n,&m);
n++;m++;
ans=C(n*m)-(ll)n*C(m)-(ll)m*C(n);
for (int i=1;i<n;i++)
for (int j=1;j<m;j++)
{
int num=__gcd(i,j)-1;
if (num>=1) ans-=(ll)(n-i)*(m-j)*num*2;
}
printf("%lld\n",ans);
return 0;
}
小结:好题。枚举的方式决定了解决问题的难易程度。
最新文章
- EasyPR--开发详解(8)文字定位
- java中获取路径的几种基本的方法
- 《Effective Java》—— 读后总结
- 关于全站https必要性http流量劫持、dns劫持等相关技术
- php获取从百度搜索进入网站的关键词
- 为什么需要auto_ptr_ref
- 《算法导论》习题解答 Chapter 22.1-6(求universal sink 通用汇点)
- [转]T4模版引擎之生成数据库实体类
- postgresql的/d命令
- Android 中使用 html 作布局文件
- 初步swift语言学习笔记2(可选类型?和隐式可选类型!)
- Reverse Words in a String | LeetCode OJ | C++
- C语言之printf函数
- 解决UnicodeDecodeError: ‘ascii’ codec can’t decode byte 0xe5 in position 108: ordinal not in range(128
- tensorflow softsign函数应用
- javascript的加减乘除结果会有误差,在两个浮点数相加的时候会比较明显。以下函数返回较为精确的计算结果
- T-SQL:SQL语句处理顺序的坑(四)
- java的MVC与C#
- Linux中系统检测工具top命令
- TJU Problem 2548 Celebrity jeopardy