Codeforces #418(Div 2)

C. An impassioned circulation of affection

预处理$n|\Sigma|$种询问，每次用双指针查找。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1505;
int n, q;
char str[MAXN];
int A[MAXN][26];
int pos[MAXN], top = 0;
void init()
{
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 26; j++) {
            top = 0;
            memset(pos, 0, sizeof pos);
            for (register int k = 1; k <= n; k++)
                if (str[k]-'a' == j)
                    pos[k] = 1;
            int l = 1, len = 0, t = 0, ans = 0;
            for (register int k = 1; k <= n; k++) {
                len += 1-pos[k], t++;
                while (len > i) len -= 1-pos[l], t--, l++;
                ans = max(ans, t);
            }
            A[i][j] = ans;
        }
    }
}
int main()
{
    scanf("%d", &n);
    scanf("%s", str+1);
    init();
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        int u; char c;
        scanf("%d %c", &u, &c);
        printf("%d\n", A[u][c-'a']);
    }
    return 0;
}

D. An overnight dance in discotheque

大力贪心，不会证明。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const double eps = 1e-9;
struct circ {
    int x, y, r;
    friend bool operator < (const circ &a, const circ &b)
    { return a.r > b.r; }
} c[MAXN], A[MAXN], B[MAXN];
int n;
int ta = 0, tb = 0;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        scanf("%d%d%d", &c[i].x, &c[i].y, &c[i].r);
    sort(c+1, c+n+1);
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int tmsa = 0, tmsb = 0;
        for (int j = 1; j <= ta; j++)
            if ((long long)(A[j].x-c[i].x)*(A[j].x-c[i].x)+(long long)(A[j].y-c[i].y)*(A[j].y-c[i].y) <= (long long)(A[j].r-c[i].r)*(A[j].r-c[i].r)) tmsa++;
        for (int j = 1; j <= tb; j++)
            if ((long long)(B[j].x-c[i].x)*(B[j].x-c[i].x)+(long long)(B[j].y-c[i].y)*(B[j].y-c[i].y) <= (long long)(B[j].r-c[i].r)*(B[j].r-c[i].r)) tmsb++;
        if ((tmsa&1)==0) A[++ta] = c[i], ans += (long long)c[i].r*c[i].r;
        else if ((tmsb&1)==0) B[++tb] = c[i], ans += (long long)c[i].r*c[i].r;
        else A[++ta] = c[i], ans -= (long long)c[i].r*c[i].r;
    }
    printf("%.10f\n", ans*M_PI);
    return 0;
}