江苏理工 - 题目详情 - JNACMer Online Judge这一道题让我们找到一些线段满足条件这道题有两种思路吧我觉得第一种是找到所有能作为中点的点然后看他有几种情况的中点假设点i,j可以作为中点那么(i-x,j-y)和ix,jy这两个点如果存在就对最终结果但是这样写的话看看复杂度m*n*(m*n)大概是这样吧差不多要10的12次方所以需要优化我的想法是因为取中点的缘故这个矩形是对称的。那么我只需要在x或y中取i和n-i中小的那个因为如果取大的那个会使得点超过边界这样我可以把以这个点为中点的所有的可能的x和y提示(i-x,j-y)和ix,jy有多少种得到dx和dy配对,也就是把这两个统计的结果乘起来但是-dx和-dy和dx,dy得到的线段是同一个所以需要除二还有一点dx_cnt * dy_cnt 为什么要减一因为这两个乘起来会出现dx等于0dy也等于0的情况但是要求线段长度不为0另外为什么这个式子不会除出来小数因为这两个是奇数奇数乘奇数还是奇数再减一就变成偶数了把这个答案加到总的答案里面就可以了就这样遍历下一个可能作为中点的点。这样的话复杂度是n*m#include bits/stdc.husing namespace std;typedef long long ll;int main() {int n, m;cin n m;ll ans 0;for (int i 0; i n; i) {int A min(i, n - i); // dx 的最大绝对值int dx_cnt 2 * A 1; // dx 的可取个数for (int j 0; j m; j) {int B min(j, m - j); // dy 的最大绝对值int dy_cnt 2 * B 1; // dy 的可取个数ans ((ll)dx_cnt * dy_cnt - 1) / 2;}}cout ans endl;return 0;}//不要直接复制代码可能有不可见的文字第二个思路的话中点公式x1x2/2,y1y2/2那么x1x2一定为偶数y1y1也一样那么x1,x2一定奇偶性相同y也一样。那么x是偶数的点有多少种算出来y是偶数的有多少种算出来x是奇数的有多少种y是奇数的有多少种算出来。然后把x(奇数)*y(奇数x偶数*y偶数x(偶数)*y奇数y(偶数)*x奇数这四种情况是所有端点的可能性在每个情况里面取两个点用到组合数算出所有可能把这四种情况的所以可能都加起来这样就得到了所有线段数。#include bits/stdc.husing namespace std;typedef long long ll;int main() {int n, m;cin n m;ll a n / 2 1;ll b (n 1) - a;ll c m / 2 1;ll d (m 1) - c;ll ac a * c;ll ad a * d;ll bc b * c;ll bd b * d;ll ans (ac*(ac-1) ad*(ad-1) bc*(bc-1) bd*(bd-1)) / 2;cout ans endl;return 0;}//不要直接复制代码可能有不可见的文字
