“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛Part1（BCEFHJ）
“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛Part1（BCEFHJ）
太菜了先写写签到题，按做题顺序的
C.面积（签到题）
题意：
求正方形周围接四个半圆的图形的面积。
思路：
推一下公式就可以了。假设正方形边长是x，π为PI。则
化简就是
注意PI=3.14。
代码：
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43862364
H.直线(公式+大数)
题意：
n条直线在平面上最多存在多少交点 。
思路：
公式是
其实也很好理解，两条非平行直线有且只有一个交点，其中一条直线与其他直线都有n-1个交点，那么n条直线之间的交点就是n *(n-1).这样的话，每个交点都计算了两次，所以答案要再/2.
因为n的范围是1e15，所有要用大数，也可以用python,JAVA……
代码：
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43863149
E.赛马（贪心）
题意：
每匹马都有一个战力值，战力值大的获胜，问小明最多可以赢多少场。
思路：
证明有点麻烦但是不是很难想的贪心思路。
网上有一篇证明很详细的博客，可以参考一下
先说思路：我们肯定是想尽可能的赢得比赛，所以对于对方的战力值小的马，都要尽可能的战胜，不然后面的战力值大的马取胜更加困难。
所以可以设两个指针i,j，分别表示用自己的第i匹马和对方的第j匹马比赛，如果当前这场比赛可以赢的话，就i++,j++,res++;否则，就用自己战斗力更大的马来比，即i++;
代码：
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43867206
B.减成1（差分）
题意：
存在n个数，每次操作可以任选一个区间使得区间内的所有数字减一。问最少多少次操作，可以让所有数都变成1。
思路：
用每一个都跟前一个比较，如果后者比前者大的话，就计算进答案。
因为要求最后都变为1，所以可以在输入时就全部-1，这样按照题目的要求就相当于是都变为0.
代码：
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43873512
J.最大值(二分)
题意：
有一个字符串s，对于字符串中一个非前缀子串恰好为字符串的前缀我们称之为ac串。
请问给出一个字符串他的ac串最大长度为多少
思路：
二分最大长度，对于每一个长度，看非前缀的子串里是否有与前缀相等的字符串，如果有，说明该长度符合题意，接下来可以试试更长的；反之，接下来就只能试更短的。
代码：
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43875020
F.三角形（思维+斐波那契）
题意：
把一个数分为若干个数，使得从中任意取三个都不能构成三角形，求最多可以分成多少个数。
思路：
按照斐波那契数列来分一定是最优的，斐波那契的前几项为1，1，2，3，5
比如5的话，就可以分为1，1，3。
题意就转化为了找斐波那契的前res项，使得这些项的和<=a;
要注意求和的过程会爆ll，要用ull.
代码：
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43880755
