校赛决赛题解

题解

补题第一题 切pizza：
思路：
赛上没有想到二分，用了线段树，可惜代码没有跑出来，当然，线段树其实是行不通的，因为是面积，除非二维线段树（2333，不知道有没有。后来，wj菊苣讲题解的时候说二分，因为美味度是随坐标单调增加的唉，然后又就没有听啦，当时太饿了。
然后，自己写的二分wa了十几遍过不了，很悲伤，是脑子除了问题，所以问了好人mz学长。
此题暴露出来的问题有：
1.二分判浮点精度的时候不能自己手写精度，一般这种要求精度的题用循环就可以了。
2.very important，m和n的范围是在1e5的范围内，所以相乘的话有可能会爆int，就是没想到，所以n*m的时候就直接乘在了1.0前面，后面读题时，第一是一定能要预判所有数据的最大范围，第二就是直接用long long或者double之类的就好了。mark一下，仔细一点。
代码：

#include <stdio.h>
#include <string.h>
#include <math.h>
const double pi = acos(-1.0);
struct node
{
    double cen;
    double deg;
    double r;
}node[100005];
int n,m,k;
double mm(double g)
{
    double sum = 0;
    for (int i = 0;i < k;i++)
    {
        if (node[i].cen + node[i].r <= g)
        {
            sum += pi * node[i].r * node[i].r * node[i].deg;
        }
        else if (node[i].cen < g && node[i].cen + node[i].r > g)
        {
            double x = g - node[i].cen;
            double w = 2 * (acos(x / node[i].r));
            double area = pi * node[i].r * node[i].r - (1.0 / 2 * w * node[i].r * node[i].r - 1.0 / 2 * node[i].r * node[i].r * sin(w));
            sum += area * node[i].deg;
        }
        else if (node[i].cen - node[i].r < g && node[i].cen > g)
        {
            double x = node[i].cen - g;
            double w = 2 * (acos(x / node[i].r));
            double area = 1.0 / 2 * w * node[i].r * node[i].r - 1.0 / 2 * node[i].r * node[i].r * sin(w);
            sum += area * node[i].deg;
        }
        else if (node[i].cen == g)
            sum += 1.0 / 2 * pi * node[i].r * node[i].r;
    }
    return sum + m * g;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        double sum = 0;
        scanf("%d%d%d",&n,&m,&k);
        for (int i = 0;i < k;i++)
        {
            double t1;
            scanf("%lf%lf%lf%lf",&node[i].cen,&t1,&node[i].r,&node[i].deg);
            sum += pi * node[i].r * node[i].r * node[i].deg;
        }
        sum += 1.0 * n * m;
        double l = 0,h = n,mid;
        for (int i = 0;i < 100;i++)
        {
            mid = (l + h) / 2;
            if (mm(mid) >= sum / 2) h = mid;
            else l = mid;
            //printf("%f*****\n",mid);
        }
        printf("%.4f\n",mid);
    }
    return 0;
}

补题第二题 24game：
这题在赛上写爆搜，兰儿wa了二十几发。赛下来写，我不是用的dfs。
第一种想法是枚举所有数字与符号的全排列，但是后来经过mzjj的验证有些情况是过不了的，并不能涵盖所有括号的情况，遂重新写。
后来去网上查了资料，发现了后缀表达式与表达式树，经过两节高数了的深思熟虑（滑稽，想出来了全排列与表达式树相结合的方法，1A了。
表达式树有三种：
1.（x op y）op(z op w);
2.(x op y) op z op w
3.x op y op (z op w)
主要是从 8 8 3 3这个想出来的

代码：

#include <stdio.h>
#include <math.h>
#include <string.h>
int a[4];
bool v[4];
int p[4];
char b[1000][3];
int cnt = 0;
bool flag = 0;
double cal(double x,int op,double y)
{
    double ans;
    if (op == 0)
        ans = x + y;
    if (op == 1)
        ans = x - y;
    if (op == 2)
        ans = x * y;
    if (op == 3)
    {
        if (y == 0)
            ans = 100000000000;
        else
            ans = x / y;
    }
    return ans;
}
void dfs(void)
{
    double c[4];
    for (int i = 0;i < 4;i++)
        c[i] = a[p[i]];
    for (int i = 0;i < cnt;i++)
    {
        if (flag) break;
        double ans;
        double x = cal(c[0],b[i][0],c[1]);
        double y = cal(c[2],b[i][2],c[3]);
        ans = cal(x,b[i][1],y);
        if (fabs(ans - 24) < 1e-8)
            flag = 1;
        ans  = cal(c[0],b[i][0],c[1]);
        ans  = cal(ans,b[i][1],c[2]);
        ans = cal(ans,b[i][2],c[3]);
        if (fabs(ans - 24) < 1e-8)
            flag = 1;
        ans  = cal(c[0],b[i][0],c[1]);
        ans  = cal(c[2],b[i][1],ans);
        ans = cal(c[3],b[i][2],ans);
        if (fabs(ans - 24) < 1e-8)
            flag = 1;
    }
}
void fun(int k)
{
    if (flag) return;
    if (k == 4)
        dfs();
    for (int i = 0;i < 4;i++)
    {
        if (!v[i])
        {
            v[i] = 1;
            p[k] = i;
            fun(k+1);
            v[i] = 0;
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    for (int i = 0;i < 4;i++)
        for (int j = 0;j < 4;j++)
            for (int k = 0;k < 4;k++)
    {
        b[cnt][0] = i;
        b[cnt][1] = j;
        b[cnt][2] = k;
        cnt++;
    }
    while (t--)
    {
        flag = 0;
        memset(v,0,sizeof(v));
        memset(p,0,sizeof(p));
        for (int i = 0;i < 4;i++)
            scanf("%d",&a[i]);
        fun(0);
        if (flag)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

第三题 马（无敌js
思路：首先可以推出马可以到达的坐标，横纵坐标之和必须是3的倍数，其次，此坐标必须满足杨辉三角，即abs(n-m) <= (n + m) / 3。之后，就是大组合数取模的问题了。
求解这个问题，主要用到了几个定理。
第一，Lucas定理：

C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p

mark 一下
第二 费马小定理：
a的逆元就是a的p-2次方
第三：
依据费马小定理，计算逆元时需要用到快速幂算法。

这题主要是学习新姿势。

代码：

#include <stdio.h>
typedef long long ll;
const ll p = 1000003;
int abs(int x)
{
    if (x < 0)
        return -x;
    else
        return x;
}
ll quick_mod(ll a,ll b)
{
    if (b == 0) return 1;
    ll x = quick_mod(a,b / 2);
    ll ans = x * x % p;
    if (b % 2) ans = ans * a % p;
    return ans;
}
ll C(ll n, ll m)
{
    if (m > n) return 0;
    ll ans = 1;
    for (int i = 1;i <= m;i++)
    {
        ll a = n - m + i;
        ll b = i;
        ans = ans * (a * quick_mod(b,(p - 2)) % p) % p;
    }
    return ans;
}
ll Lucas(ll n,ll m)
{
    if (m == 0)
        return 1;
    else
        return C(n % p,m % p) * Lucas(n / p,m / p) % p;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        n--;m--;
        if ((m + n) % 3 == 0)
        {
            if (abs(n-m) > (n + m) / 3)
                printf("0\n");
            else
                printf("%lld\n",Lucas((n + m) / 3,m - (n + m) / 3));
        }
        else
            printf("0\n");
    }
    return 0;
}