HDU 5734 Acperience（返虚入浑）

HDU 5734 Acperience（返虚入浑）

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

 

Problem Description - 题目描述

Deep neural networks (DNN) have shown significant improvements in several application domains including computer vision and speech recognition. In computer vision, a particular type of DNN, known as Convolutional Neural Networks (CNN), have demonstrated state-of-the-art results in object recognition and detection.

Convolutional neural networks show reliable results on object recognition and detection that are useful in real world applications. Concurrent to the recent progress in recognition, interesting advancements have been happening in virtual reality (VR by Oculus), augmented reality (AR by HoloLens), and smart wearable devices. Putting these two pieces together, we argue that it is the right time to equip smart portable devices with the power of state-of-the-art recognition systems. However, CNN-based recognition systems need large amounts of memory and computational power. While they perform well on expensive, GPU-based machines, they are often unsuitable for smaller devices like cell phones and embedded electronics.

In order to simplify the networks, Professor Zhang tries to introduce simple, efficient, and accurate approximations to CNNs by binarizing the weights. Professor Zhang needs your help.

 

More specifically, you are given a weighted vector W=(w1,w2,...,wn). Professor Zhang would like to find a binary vector B=(b1,b2,...,bn) (bi∈{+1,−1}) and a scaling factor α≥0 in such a manner that ||W - αB||² is minimum.

 

Note that  denotes the Euclidean norm (i.e., where X=(x1,x2,...,xn)).

深度神经网络（DNN）对诸如计算机视觉与语音识别等领域具有显著的改善作用。DNN在计算机视觉中的特例为卷积神经网络（CNN），这是对象识别与检测的高端成果。

卷积神经网络为对象识别与检测提供可靠结果，在三次元领域十分有用。在识别进步的同时，虚拟现实(VR by Oculus)，增强现实(AR by HoloLens)，与智能穿戴设备也出现了有趣的进展。合而观之，是时候为智能穿戴搭载尖端识别系统了。然而基于CNN的识别系统需要大量的内存与高超的计算性能。虽然他们在基于GPU的昂贵机器上表现良好，但在例如手机与嵌入式之类的小设备上就坑爹了。

为了简化网络，张教授尝试通过简明扼要的二进制权重估计CNN的精确近似值。教授需要你的帮助。

简而言之，先给你一个加权向量W=(w1,w2,...,wn)。张教授想找出一个二进制向量B=(b1,b2,...,bn) (bi∈{+1,−1})与一个缩放系数α≥0使得||W - αB||^2最小。

注意||·||表示欧几里德范数（即||X||^2 = (x1^2 + ... xn^2)，其中X=(x1,x2,...,xn)）。

Input - 输入

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case: 

The first line contains an integers n (1≤n≤100000) -- the length of the vector. The next line contains n integers: w1,w2,...,wn (−10000≤wi≤10000).

多组测试用例。输入的第一行为一个整数T，表示测试用例的数量。对于每个测试用例：

第一行为一个整数n (1≤n≤100000)——向量的长度。下一行有n个整数w1,w2,...,wn (−10000≤wi≤10000)。

 

Output - 输出

For each test case, output the minimum value of ||W - αB||² as an irreducible fraction "p/q" where p, q are integers, q>0.

对于每组测试用例，输出以不可约分数"p/q"的表示||W - αB||^2最小值，此处p与q为整数，q>0。

Sample Input - 输入样例

3
4
1 2 3 4
4
2 2 2 2
5
5 6 2 3 4

Sample Output - 输出样例

5/1
0/1
10/1

 

题解

 　　一般的公式推倒

　　此时已基本是一元二次不等式，设

 

　　带入，得

　　因为opt>=0，所以要使opt最小，则b最大。

即

代码 C++

#include <cstdio>
#include <cstdlib>
#define mx 100005
__int64 GCD(__int64 a, __int64 b){
    __int64 c;
    while (c = a%b) a = b, b = c;
    return b;
}
int main(){
    __int64 t, n, i, tmp, c, b;
    for (scanf("%I64d", &t); t; --t){
        c = b = tmp = 0;
        for (i = scanf("%I64d", &n); i <= n; ++i){
            scanf("%I64d", &tmp);
            c += tmp * tmp;
            b += abs(tmp);
        }
        c = c*n - b*b;
        tmp = GCD(c, n);
        printf("%I64d/%I64d
", c / tmp, n / tmp);
    }
    return 0;
}