Codeforces Round #340 (Div. 2)

题目链接：https://codeforces.com/contest/617

A - Elephant

事到如今这种三行签到是真的送的真诚。

B - Chocolate

题意：要把一块巧克力长条分成若干段，让每段都恰有1颗榛子，求方案数。

题解：每段被1包围的0，提供其数量+1的方案数。dp解法的话好像要分几种情况写的。

C - Watering Flowers

题意：有n<=2000个点，每个点表示一盆花。给花浇水，每盆花至少要1号喷头或者2号喷头其中之一喷到（指在圆内）。最小化喷头的圆的总面积。

题解：数据量小，直接暴力，枚举一个点是1号喷头的边界点，剩下的喷不到的就是2号喷头的。（这样会漏掉全部都由2号喷头来喷的情况！）

ll x[2005], y[2005];
 
void test_case() {
    int n;
    ll x1, y1, x2, y2;
    cin >> n >> x1 >> y1 >> x2 >> y2;
    for(int i = 1; i <= n; ++i)
        cin >> x[i] >> y[i];
    ll ans = LINF;
    for(int i = 1; i <= n; ++i) {
        ll R1 = (x[i] - x1) * (x[i] - x1) + (y[i] - y1) * (y[i] - y1);
        ll maxR2 = 0;
        for(int j = 1; j <= n; ++j) {
            ll dis1 = (x[j] - x1) * (x[j] - x1) + (y[j] - y1) * (y[j] - y1);
            if(dis1 > R1) {
                ll dis2 = (x[j] - x2) * (x[j] - x2) + (y[j] - y2) * (y[j] - y2);
                maxR2 = max(maxR2, dis2);
            }
        }
        ans = min(ans, R1 + maxR2);
    }
    ll maxR2 = 0;
    for(int j = 1; j <= n; ++j) {
        ll dis2 = (x[j] - x2) * (x[j] - x2) + (y[j] - y2) * (y[j] - y2);
        maxR2 = max(maxR2, dis2);
    }
    ans = min(ans, maxR2);
    cout << ans << endl;
}

Codeforces Round #340 (Div. 2)

原文：https://www.cnblogs.com/KisekiPurin2019/p/12287950.html