这天的题目没有名字，就以 A，B，C 分别代表 T1，T2，T3 吧。

A

题意

平面上给出 n(n\leq 200) 个圆环，求这些圆环的面积并。

思路

参照 BZOJ2178 ，将横坐标看作自变量，直线 x=a 交圆环的长度为 f(a) ，那么我们要求的就是函数 f 再横坐标范围内的定积分。用 Simpson 积分拟合这个函数即可求出答案。 （不知道有没有纯几何解法）

代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN=220;
const int INF=1E7;
const double EPS=5E-4;
struct Ring
{
    int x, y, R, r;
} a[MAXN];
struct Range
{
    double l, r;
    Range() {}
    Range(double a, double b): l(a), r(b) {}
    bool operator < (const Range& rhs) const
    {
        return l<rhs.l;
    }
} b[2*MAXN];
int n;
inline double f(double x)
{
    int m=0;
    for (int i=1; i<=n; i++)
    {
        double d=fabs(x-a[i].x);
        if (a[i].r<=d&&d<=a[i].R)
        {
            double q=sqrt(a[i].R*a[i].R-d*d);
            b[++m]=Range(a[i].y-q, a[i].y+q);
        }
        else if (d<=a[i].r)
        {
            double p=sqrt(a[i].r*a[i].r-d*d);
            double q=sqrt(a[i].R*a[i].R-d*d);
            b[++m]=Range(a[i].y-q, a[i].y-p);
            b[++m]=Range(a[i].y+p, a[i].y+q);
        }
    }
    sort(b+1, b+m+1);
    double L=-INF, R=-INF, s=0;
    for (int i=1; i<=m; i++)
    {
        if (b[i].l>R) s+=R-L, L=b[i].l;
        R=max(R, b[i].r);
    }
    s+=R-L;
    return s;
}
inline double simpson(double l, double r)
{
    double mid=(l+r)/2;
    return (f(l)+4*f(mid)+f(r))*(r-l)/6;
}
double asr(double l, double r, double eps, double ans)
{
    double mid=(l+r)/2;
    double L=simpson(l, mid), R=simpson(mid, r);
    if (fabs(L+R-ans)<=15*eps) return L+R+(L+R-ans)/15;
    return asr(l, mid, eps/2, L)+asr(mid, r, eps/2, R);
}
int main()
{
//  freopen("A.in", "r", stdin);
//  freopen("A.out", "w", stdout);
    scanf("%d", &n);
    double L=INF, R=-INF;
    for (int i=1; i<=n; i++)
    {
        scanf("%d%d%d%d", &a[i].x, &a[i].y, &a[i].R, &a[i].r);
        L=min(L, (double)a[i].x-a[i].R); R=max(R, (double)a[i].x+a[i].R);
    }
    printf("%.3lf\n", asr(L, R, EPS, simpson(L, R)));
    return 0;
}

B

题意

在平面上由原点 (0,0) 出发，每一次行进可以选择向上、下、左、右四个方向走一格，求行进 r(r\leq 10^6) 次后走到 (x,y) 的方案数。

思路

应该可以推组合的式子，可是我并不会，所以我选择找规律。 暴力 DP 打表后得出规律，答案为 \binom{r}{\frac{r-x-y}{2}}\binom{r}{\frac{r+x-y}{2}} 。题目里没给 x,y 的范围，如果明显走不到就判掉即可。

代码

#include <cstdio>
const int MAXN=1100000;
const int N=1000000;
const int MOD=998244353;
int fac[MAXN];
void exgcd(int a, int b, int& x, int& y)
{
    if (b==0) x=1, y=0;
    else exgcd(b, a%b, y, x), y-=a/b*x;
}
inline int inv(int a)
{
    int x, y;
    exgcd(a, MOD, x, y);
    return (x%MOD+MOD)%MOD;
}
inline int C(int n, int m)
{
    return 1ll*fac[n]*inv(1ll*fac[m]*fac[n-m]%MOD)%MOD;
}
inline int calc(int x, int y, int n)
{
    if (x<-n||x>n||y<-n||y>n||(n-x-y)%2==1) return 0;
    return 1ll*C(n, (n-x-y)/2)*C(n, (n+x-y)/2)%MOD;
}
int main()
{
//  freopen("B.in", "r", stdin);
//  freopen("B.out", "w", stdout);
    int T;
    scanf("%d", &T);
    fac[0]=1;
    for (int i=1; i<=N; i++) fac[i]=1ll*fac[i-1]*i%MOD;
    while (T--)
    {
        int x, y, r;
        scanf("%d%d%d", &x, &y, &r);
        printf("%d\n", calc(x, y, r));
    }
    return 0;
}

C

题意

有 n(n\leq 10^5) 堆金币，每堆 a_i 个，每次可以选择两堆编号相差 k 的金币全部拿走。不限取金币的次数，求最多能取多少金币。

思路

考虑 1~n 模 k 意义下的同余类，显然两个不在一类的金币堆之间不互相影响。再观察同一类的金币堆，发现若堆数为偶数则可以全部取完，否则至少会剩下一个在这一类中编号为奇数的堆。那么让这一堆的金币数最少即可。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=110000;
const int INF=0X3F3F3F3F;
int a[MAXN];
int main()
{
//  freopen("C.in", "r", stdin);
//  freopen("C.out", "w", stdout);
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    long long ans=0;
    for (int i=1; i<=n; i++) ans+=a[i];
    for (int i=1; i<=k; i++)
    {
        int cnt=0, mn=INF;
        for (int j=i; j<=n; j+=k)
            if (++cnt&1) mn=min(mn, a[j]);
        if (cnt&1) ans-=mn;
    }
    printf("%lld\n", ans);
    return 0;
}