slove  3/10

rank  308

补题   8/10

--------------------------------------------------------

A、Equivalent Prefixes

https://ac.nowcoder.com/acm/contest/881/A

题解：笛卡尔树

https://blog.csdn.net/qq_41608020/article/details/96462051

B、Integration

https://ac.nowcoder.com/acm/contest/881/B

题解：积分

https://blog.csdn.net/qq_41608020/article/details/96475673

C、Euclidean Distance

https://ac.nowcoder.com/acm/contest/881/C

题解：贪心

https://blog.csdn.net/qq_41608020/article/details/96704241

E、ABBA

https://ac.nowcoder.com/acm/contest/881/E

题解：枚举下一个位置是A还是B。然后判断是否存在没有使用的A或者B，如果存在就转移。

Code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
ll dp[2005][2005];
int main()
{
	int n, m;
	while (scanf("%d%d", &n, &m) > 0)
	{
		int len = n + m;
		for (int i = 0; i <= len; i++)
			for (int j = 0; j <= len; j++)
				dp[i][j] = 0;
		dp[0][0] = 1;
		for (int i = 0; i <= len; i++)
		{
			for (int j = 0; j <= len; j++)
			{
				if (j + 1 <= i + m)//B
					dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % mod;
				if (i + 1 <= j + n)//A
					dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
			}
		}
		printf("%lld\n", dp[len][len]);
	}
}

F、Random Point in Triangle

https://ac.nowcoder.com/acm/contest/881/F

题意：在三角形中任选一点，与三条边连起来，构成三个三角形，求这三个三角形的面积的最大值的期望（撒点)

撒点代码

#include <bits/stdc++.h>
const double eps = 1e-6;
const double PI = acos(-1.0); // PI = 180°= 3.14 
using namespace std;
//判断符号
int sign(double x)
{
	if (fabs(x) < eps)
		return 0;
	return x > 0 ? 1 : -1;
}

struct point
{
	double x;
	double y;
	point operator + (const point& other) { return point{ x + other.x, y + other.y }; }
	point operator - (const point& other) { return point{ x - other.x, y - other.y }; }
	point operator * (double k) { return point{ x * k, y * k }; }
	point operator / (double k) { return point{ x / k, y / k }; }
	bool operator == (const point& other)
	{
		return sign(x - other.x) == 0 && sign(y - other.y) == 0;
	}
	bool operator < (const point& other)
	{
		if (fabs(x - other.x) < eps)
			return y < other.y;
		return x < other.x;
	}
	void scan() { scanf("%lf%lf", &x, &y); }
	void print() { printf("%.2lf %.2lf\n", x, y); }
};
double cross(point a, point b)
{
	return a.x * b.y - b.x * a.y;
}
double getarea(point a, point b, point c)
{
	double res = 0;
	res += cross(a, b);
	res += cross(b, c);
	res += cross(c, a);
	return fabs(res / 2);
}
int main()
{
	int len = 1000;//长度  构造 (0,0),(len,0),(0,len)三角形
	int times = 10000;//次数
	point a, b, c;
	a = point{ 0,0 };
	b = point{ (double)len,0 };
	c = point{ 0,(double)len };
	srand(time(NULL));
	double ans = 0;
	int T = times;
	while (times--)//撒点
	{
		qwe:;
		int x = rand() % (len + 1);
		int y = rand() % (len + 1);
		if (x  + y > len)
			goto qwe;
		point p = { x,y };//计算最大面积
		ans += max({ getarea(a,b,p), getarea(b, c, p), getarea(c,a,p) });
	}
	ans /= T;//总面积除以次数*36
	ans *= 36;
	double S = (double)len * len / 2;//原三角形面积
	printf("%.2lf\n", S);
	printf("%.2lf\n", ans);
	printf("%.2lf\n", ans / S);
}

Code :

#include <bits/stdc++.h>
#define ll long long
using namespace std;
//判断符号
struct point
{
	ll x;
	ll y;
};
ll cross(point a, point b)
{
	return a.x * b.y - b.x * a.y;
}
ll getarea(vector<point> sol)
{
	ll ans = 0;
	sol.push_back(sol[0]);
	for (int i = 0; i < sol.size() - 1; i++)
		ans += cross(sol[i], sol[i + 1]);
	return abs(ans * 11);
}
point a, b, c;
int main()
{
	while (scanf("%lld", &a.x) > 0)
	{
		scanf("%lld", &a.y);
		scanf("%lld%lld%lld%lld", &b.x, &b.y, &c.x, &c.y);
		vector<point>v = { a,b,c };
		ll ans = getarea(v);
		printf("%lld\n", ans);
	}
}

H、XOR

https://ac.nowcoder.com/acm/contest/881/H

题解：

https://blog.csdn.net/qq_41608020/article/details/96885563

I、Points Division

https://ac.nowcoder.com/acm/contest/881/I

题解：

https://blog.csdn.net/qq_41608020/article/details/96738923

J、Fraction Comparision

https://ac.nowcoder.com/acm/contest/881/J

java暴力真香

Code：

import java.math.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        //更改的是返回值，不是原值
        BigInteger x,y,a,b;
        while (input.hasNextBigInteger()){
            x=input.nextBigInteger();
            a=input.nextBigInteger();
            y=input.nextBigInteger();
            b=input.nextBigInteger();
            x=x.multiply(b);
            y=y.multiply(a);
            if (x.compareTo(y)==0){
                System.out.println("=");
            }
            else if (x.compareTo(y)>0){
                System.out.println(">");
            }
            else
            {
                System.out.println("<");
            }
        }

    }
}