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^{\prime },Q^{\prime }$，由于反演点的性质为$r^2=P?P^{\prime }$
所以可以得出两个相似三角形。$PC?bi=P{C}^{\prime },QC?bi=Q{C}^{\prime }$
那么我们可以观察。
当$P^{\prime }{C}^{\prime }$不交圆时，过这条线作垂直平分线交的那个点肯定是最短的。由椭圆的性质可得
当$P^{\prime }{C}^{\prime }$交圆时，$P^{\prime }{C}^{\prime }$连着的直线肯定是最短的。因为两点之间线段最短
好像当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=\underset{i?j}{\max }Aj$
求Bi(2 <= i <= n)
思路：
非常优雅的暴力。sort一下从大到小找到下标不被整除的即可。。

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

#include <bits/stdc++.h>#define MAXN 100005
#define ll long long
#define INF 1000000001using 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$，满足$\sum |a_i?b_{blen?j+1}|<=m$
思路：
orz比赛的时候暴力枚举两个点，逐步向中间逼近，写了个$n^3$的做法。。剪枝还是没怼掉

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

#include <bits/stdc++.h>#define MAXN 5005using 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);}
}