2017 Multi-University Training Contest - Team 6

orz还有四场。坚持
hdu 6096 6097 6098 6099 6100 6101 6102 6103 6104 6105 6106 6107

Mindis

题意：有两个圆内有两点，P，Q与圆心距离都相等，现在求圆上一点C使得PC+QC最小

思路：明显答案不全是PQ的垂直平分线呀。
听说暴力黄金三分可以过。没见识过orz

先做P和Q点的反演点 P′,Q′ ，由于反演点的性质为 r2=P∗P′
所以可以得出两个相似三角形。 PC∗bi=PC′,QC∗bi=QC′
那么我们可以观察。
当 P′C′ 不交圆时，过这条线作垂直平分线交的那个点肯定是最短的。由椭圆的性质可得
当 P′C′ 交圆时， P′C′ 连着的直线肯定是最短的。因为两点之间线段最短
好像当P、C在圆心上时精度会不够。特判一下。

#include <bits/stdc++.h>

#define print(name) printf("name : x = %lf y = %lf\n", name.x, name.y)

using namespace std;

struct point {
    double x, y;    
};

double getPointDis(point a, point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double getDis(double a, double b) {
    return sqrt(a * a + b * b);
}

point getF(double r, point p) {
    double dis = getPointDis(p, (point){0, 0});
    double l = r * r / dis;
    double bi = l / dis;
    point ans;
    ans.x = p.x * bi;
    ans.y = p.y * bi;
    return ans;
}

point getMid(point p, point q) {
    point ans;
    ans.x = (p.x + q.x) / 2;
    ans.y = (p.y + q.y) / 2;
    return ans;
}

int main() {
    int T;
    point p, q, fp, fq, mid;
    double dis, d1, d2, ans, fpdis, pdis, bi, r;
    scanf("%d", &T);
    while (T--) {
        scanf("%lf", &r);
        scanf("%lf %lf", &p.x, &p.y);
        scanf("%lf %lf", &q.x, &q.y);
        if (p.x == 0 && p.y == 0) {
            printf("%.7lf\n", 2 * r);
            continue;
        }
        fp = getF(r, p);
        fq = getF(r, q);
        mid = getMid(fp, fq);
        dis = getPointDis(mid, (point){0, 0});
        fpdis = getPointDis(fp, (point){0, 0});
        pdis = getPointDis(p, (point){0, 0});
        bi = fpdis / r;
        if (dis > r) {
            d1 = dis - r;
            d2 = getPointDis(mid, fp);
            ans = 2 * getDis(d1, d2) / bi;
        } else {
            ans = getPointDis(fp, fq) / bi;
        }
        printf("%.7lf\n", ans);
    }
} 

Inversion

题意：对于每一个大与2的i有 Bi=maxi∤jAj
求Bi(2 <= i <= n)
思路：
非常优雅的暴力。sort一下从大到小找到下标不被整除的即可。。

比赛时傻逼的感觉时间不够，还离散化处理出来了个类似 O(n∗logn∗logn) 的东西
怀疑人生的时候单纯的学弟说暴力过了orz。。。

#include <bits/stdc++.h>

#define MAXN 100005
#define ll long long
#define INF 1000000001

using namespace std;

struct node {
    ll idx, num;
} num[MAXN];

ll a[MAXN];

int cmp(node a, node b) {
    return a.num < b.num;
}

int main() {
    ll T, n;
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld", &n);
        for (ll i = 1; i <= n; i++) {
            scanf("%lld", &num[i].num);
            num[i].idx = i;
        }
        sort(num + 1, num + 1 + n, cmp);
        for (ll i = 2; i <= n; i++) {
            if (i != 2) {
                printf(" ");
            }
            for (ll j = n; j >= 1; j--) {
                if (num[j].idx % i) {
                    printf("%lld", num[j].num);
                    break;
                }
            }
        }
        printf("\n");
    }
}

Kirinriki

真的是怎么暴力都暴力不过去。最后还交了发MLE
题意：
给一个串，要求找到两个不重叠且长度相同的子串 a,b ，满足 ∑|ai−bblen−j+1|<=m
思路：
orz比赛的时候暴力枚举两个点，逐步向中间逼近，写了个 n3 的做法。。剪枝还是没怼掉

其实我们每次只需要枚举一个点，他向他两边做一次 ai−bblen−j+1 的统计，然后从那个点开始，作尺取法，两个指针维护，看每次可以量出来最长多长且和不超过m的串即为所需要的答案。
这样的做法。每次只需要枚举n个点。对于每个点计算最多n / 2次。然后再计算最多n / 2次。时间复杂度为 O(n2)
要注意的是，枚举点的时候，有两种情况，一种是枚举的点也是需要用的，一种是枚举的点不需要用到，只需要用他两边的点。

#include <bits/stdc++.h>

#define MAXN 5005

using namespace std;

int tmp[MAXN];
int T, m, ans;

void getAns(int cnt) {
    int tot = 0;
    int j = 0;
    for (int i = 0; i < cnt; i++) {
        while (tot + tmp[j] <= m && j < cnt) {
            tot += tmp[j++];
        }
        ans = max(j - i, ans);
        if (i == j) {
            j++;
        } else {
            tot -= tmp[i];
        }
    }
}

int main(){
    char ch[MAXN];
    scanf("%d", &T);
    while (T--) {
        ans = 0;
        scanf("%d", &m);
        scanf("%s", ch + 1);
        int len = strlen(ch + 1);
        for (int i = 1; i <= len; i++) {
            int x1 = i - 1, x2 = i + 1;
            int cnt = 0;
            while (x1 > 0 && x2 <= len) {
                tmp[cnt++] = abs(ch[x1--] - ch[x2++]);
            }
            getAns(cnt);
        }
        for (int i = 1; i <= len; i++) {
            int x1 = i - 1, x2 = i;
            int cnt = 0;
            while (x1 > 0 && x2 <= len) {
                tmp[cnt++] = abs(ch[x1--] - ch[x2++]);
            }
            getAns(cnt);
        }
        printf("%d\n", ans);
    }
}

/* 100 2 abcd */

Classes

题意：
给n个教室，保证他们一定有一个是正确的。
这个教室有m个同学，他们有a,b,c,d,e,f,g个同学分别报了A,B,C,AB,BC,AC,ABC班。
现在问某个正确的教室最多多少个同学。
思路：
就是个3元组的容斥，满足每一块都大于0即可。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int A, B, C, AB, BC, AC, ABC, T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d %d %d %d %d", &A, &B, &C, &AB, &BC, &AC, &ABC);
            if (A + B + C - AB - BC - AC + ABC >= 0 && AB + BC + AC - 2 * ABC >= 0) {
                if (A >= AB && A >= AC && B >= BC && B >= AB && C >= BC && C >= AC) {
                    if (AB >= ABC && AC >= ABC && BC >= ABC) {
                        if (A >= AB + AC - ABC && B >= AB + BC - ABC && C >= AC + BC - ABC) {
                            ans = max(A + B + C - AB - BC - AC + ABC, ans);
                        }
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
}