2016 Multi-University Training Contest 2题解报告
A - Acperience
题意：
给你一个加权向量,需要我们找到一个二进制向量和一个比例因子α,使得|W-αB|的平方最小，而B的取值为+1，-1，我们首先可以想到α为输入数据的平均值，考虑到是平方和，然后化简表达式，可以得到一个化简的式子，用n通分，可以做到没有除法，然后分子分母化简到互质。
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return a % b == 0 ? b : gcd(b, a%b);
}
int main()
{
ll n;
int kase;
ll sum, sum2;
while (~scanf("%d", &kase))
{
while (kase--)
{
scanf("%lld", &n);
sum = 0;
sum2 = 0;
int num;
for (int i = 0; i < n; i++) {
scanf("%d", &num);
sum += abs(num);
sum2 += num * num;
}
ll a = n * sum2 - sum*sum;
ll ans = gcd(a, n);
//cout << a / ans << " " << n / ans << endl;
printf("%lld/%lld\n", a/ans,n/ans);
}
}
return 0;
}E - Eureka
题意：
由题目中的不等式可以分析得到，对于共线的点可以在一个集合中，于是这个问题转化为在全集中划分共线的点的集合，最后用组合数学求数量。这样就可以解决这个问题。
接下来的问题是如果求得在一个点的集合数量，可以从一个点出发，处理其他啊全部的点，下一次去掉这个点，O（n*n）处理，这样考虑这个点与其它点的向量关系，可以用map保存每种向量的数量，这里特殊处理一下，在点的重载减法里面处理。即在这条直线上的点的数目，对于重复的点也需要保存一下，组合数计数加进去。
这个题还有一点处理：对这种方法，从一点个出发，我在计数时候一定取这个点，这样虽然处理的直线会有重复，但是我的计数没有重复，所以这个的处理并不是一次计算一条线段上面的全部集合数量。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
typedef long long ll;
using namespace std;
struct node
{
int x, y;
bool operator<(const node& p)const {
if (x != p.x)return x < p.x;
return y < p.y;
}
bool operator== (const node& p)const {
if (x == p.x&&y == p.y)return true;
return false;
}
};
int gcd(int x, int y)
{
if (x == 0)return y;
else return gcd(y%x, x);
}
node operator-(node a, node b) {
node temp;
temp.x = a.x - b.x; temp.y = a.y - b.y;
if (temp.x != 0 || temp.y != 0) {
int ans = gcd(temp.x, temp.y);
if (ans != 0) { temp.x /= ans; temp.y /= ans; }
}
if (temp.x == 0)temp.y = abs(temp.y);
else if (temp.x < 0) {
temp.x = -temp.x;
temp.y = -temp.y;
}
return temp;
}
const int maxn = 1001;
node no[maxn];
map<node, int>::iterator it;
typedef long long ll;
const int mod = 1e9 + 7;
ll num[maxn];
ll ans;
int main() {
int T;
num[0] = 1;
for (int i = 1; i<maxn; i++)
{
num[i] = num[i - 1] * 2;
num[i] %= mod;
}
scanf("%d", &T);
while (T--) {
int n;
ans = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &no[i].x, &no[i].y);
}
for (int i = 0; i < n; i++) {
map<node, int>p;
int len = 1;
for (int j = i + 1; j < n; j++) {
if (no[i] == no[j]) {
len++;
continue;
}
node temp = no[i] - no[j];
p[temp]++;
}
//len-1是保证处理的这个点加入集合
if (len > 1)
{
ans += num[len - 1] - 1;
ans %= mod;
}
for (it = p.begin(); it != p.end(); it++) {
int m = it->second;
//num[n]-1是保证在外面至少取一个点。
ans = ans+((ll)num[len - 1])*((ll)num[m] - 1);
ans = ans % mod;
}
}
printf("%I64d\n", ans);
}
}I - It's All In The Mind
题意：
求一个分式的最大值，即保存前两个最大（a1,a2），后面最小(a3 a4 a5....)，可以保证题目最优答案。由于非递增型，对第一第二的数据特殊处理，a3及其以后，保证ak前面的等于ak即可，这样保证最小。
队友的这种处理，还是很方便a2 = min(a1, a2);，不需要特殊处理，写出来就AC了。
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
int gcd(int a, int b)
{
return a % b == 0 ? b : gcd(b, a % b);
}
int main()
{
ll n,m;
int kase;
ll sum, sum2;
int num;
while (~scanf("%d", &kase))
{
int x, y;
int a1,a2, b;
while (kase--)
{
a1 =100,a2=100;
b = 0;
scanf("%lld%lld", &n,&m);
int j = 1;
bool flag = 0;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
if (x == 1) {
a1 = y;
}
else if (x == 2) {
a2 = y;
}
else {
if (j < 3)j = 3;
for (j; j <= x; j++)
b += y;
}
}
a2 = min(a1, a2);
b += (a1+a2);
int ans = gcd(a1+a2, b);
cout << (a1+a2)/ ans << "/" << b / ans << endl;
}
}
return 0;
}K - Keep On Movin
题意：
maximize the length of the shortest palindromic string
保证的是每一个字符串都是回文的，对于偶数的字母类型，可以保证，加入任何回文串，对于奇数的字母类型，可以把其中的偶数的个数减掉，最后保留的是1，其它的看成偶数的字母类型，加入到偶数的类型中。
一个技巧，把每两个字母看成一个组，这个不需要考虑字母的组数，直接用除法平均分配就好了。
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
int gcd(int a, int b)
{
return a % b == 0 ? b : gcd(b, a % b);
}
int main()
{
ll n;
int kase;
ll sum, sum2;
int num;
while (~scanf("%d", &kase))
{
while (kase--)
{
sum = 0;
int k = 0;
scanf("%lld", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &num);
if(num & 1)
{k++;
sum += num - 1;
}
else sum += num;
}
sum = sum / 2;
if(k>0)cout << sum/k*2+1<<endl;
else cout << sum*2 << endl;
}
}
return 0;
}L - La Vie en rose
HDU - 5745
题解连接
DP还不行，嘤嘤嘤......
