娱乐 每 日 算 法 挑 战 【第9期·周末特辑】

[Mr.K 018]

又到周末啦。这次为大家带来的是2018年BIT校赛的B题。

召唤阵：

@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵

B 魔道中人

 

搬运工注：以下提及的“本人”均指出题人，与本搬运工无关2333

 

公主：我好想找个对象，能不能在校赛题面里帮我宣传一下。

本人：没问题，要什么样的？

公主：没太多要求，只希望她可以稍微弥补下我的短板。

本人：比如？

公主：我数学不好，总喜欢浪。

本人：找个老实的数学系的？

公主：太片面。

本人：那你说全面。

公主：我假期研究了很久恋爱先生里的分析方法，把我的要求用一个题目总结出来了，我可以从女生解答这个题目的过程中看出我想看到的品质。

本人：你怕不是个魔道中人！

公主：帮我这次吧，事成重八牛府共饮此杯。

本人：我这种正直出题人不会被诱惑的！

公主：多加两份自制牛丸。

本人：说题。

公主：给四个正整数，她如果能求出使得可以作为三角形的三边长，，的整数三元组的个数，那她就是我心目中的完美女神。

本人：行，比赛的时候在后台等着收女朋友吧。

 

各位同学们，现在公主已经在后台等着了，只要你们可以解决这个问题，一个娇小可爱无敌呆萌都不沾边的公主就可以带回家了。搬运工注：醒醒，今年是2020年，而且咱连后台都没有上哪找公主去啊

 

输入

第一行一整数T表示用例组数，每组用例输入四个整数

 

输出

对于每组用例，输出满足条件的三元组个数

样例输入

  
  1
  1 1 1 2

 

样例输出

  
  4

 

样例解释

满足条件的三元组有

 

四月 18, 2020，由Mr.K 018修改

[ZERC]

召唤阵：

@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵

更新：版主，别砍我，这个回复是在主楼更新之前回的，我回的时候召唤阵还不在...

四月 18, 2020，由ZERC修改

[yhz012]

等下咱没看懂题……

aa是什么意思？比如a是10，那么aa是1010的意思吗？

[Mr.K 018]

33 分钟前, yhz012 说道:

等下咱没看懂题……

aa是什么意思？比如a是10，那么aa是1010的意思吗？

aa和a应该是没关系的，其他同理

等下，我好像少粘进来一个条件

已修改，补上了

四月 18, 2020，由Mr.K 018修改

[yhz012]

8 分钟前, Mr.K 018 说道:

aa和a应该是没关系的，其他同理

等下，我好像少粘进来一个条件

已修改，补上了

所以我可以理解为aa就是x，bb是y，cc是z，和abc本身一点关系没有是吧

那最暴力的方法就是3个for（逃（

[NianRuoshui]

1 分钟前, yhz012 说道:

所以我可以理解为aa就是x，bb是y，cc是z，和abc本身一点关系没有是吧

那最暴力的方法就是3个for（逃（

 IF加FOR 生死难料

[Mr.K 018]

21 分钟前, NianRuoshui 说道:

 IF加FOR 生死难料

生死难料×

一去不回√

[yhz012]

19 分钟前, NianRuoshui 说道:

 IF加FOR 生死难料

不过感觉这问题本质整数规划……还是NPC的问题，加速估计也加速不了多少

我在想先线性规划拿到区域之后去逐个整数点判断或许能好一点……

[摸鱼奇才咖啡喵]

6 小时前, Mr.K 018 说道:

多加两份自制牛丸。

肚几饿了www

[Mr.K 018]

1 分钟前, 摸鱼奇才咖啡喵 说道:

肚几饿了www

重八牛府共饮此杯（确信

[yyh]

这考虑到三角形的约束貌似无脑莽就行了，不需要特殊技巧也不会TLE

[ppzt]

题目说给定4个整数 所以未知数应该只有abcd才对 那aa应该就是叠字形式的a？

[Mr.K 018]

1 分钟前, ppzt 说道:

题目说给定4个整数 所以未知数应该只有abcd才对 那aa应该就是叠字形式的a？

不是的，aa跟a没关系的，其他同理。

这里写的aa等等，是因为原题如此

[ppzt]

2 分钟前, Mr.K 018 说道:

不是的，aa跟a没关系的，其他同理。

这里写的aa等等，是因为原题如此

那就不止4个整数了啊……我现在打不开你付的图 是我理解错了什么？

[Mr.K 018]

刚刚, ppzt 说道:

那就不止4个整数了啊……我现在打不开你付的图 是我理解错了什么？

你是说那些公式么？

公式我没有用图床，直接上传到STM里来的

[ppzt]

1 分钟前, Mr.K 018 说道:

你是说那些公式么？

公式我没有用图床，直接上传到STM里来的

我知道 原题不是说

引用

给四个正整数，她如果能求出使得可以作为三角形的三边长，，的整数三元组的个数

所以给定的不是只有4个正整数么？ 如果a b c aa bb cc d都是未知数的话 这就7个了啊……

[Mr.K 018]

刚刚, ppzt 说道:

我知道 原题不是说

所以给定的不是只有4个正整数么？ 如果a b c aa bb cc d都是未知数的话 这就7个了啊……

a b c d四个数是输入，是已知的，aa,bb,cc和a,b,c是无关的，只有他们三个是未知数

[ppzt]

1 分钟前, Mr.K 018 说道:

a b c d四个数是输入，是已知的，aa,bb,cc和a,b,c是无关的，只有他们三个是未知数

ok 懂了 那就brute force吧 我也想不出什么优化的解法了……