学步园

 Minimum Scalar Product

You are given two vectors v₁=(x₁,x₂,...,x_n) and v₂=(y₁,y₂,...,y_n). The scalar product of these vectors is a single
number, calculated as x₁y₁+x₂y₂+...+x_ny_n.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum
scalar product.

Input

The first line of the input file contains integer number T - the number
of test cases. For each test case, the first line contains integer number n. The next two lines contain nintegers
each, giving the coordinates of v₁ and v₂ respectively.

T = 10
100 ≤ n ≤ 800
-100000 ≤ x_i, y_i ≤ 100000

Sample

分析：

贪心法之田鸡赛马，对于任意一个vector，拿自己现有的最小的和对方最大的进行乘。　

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
typedef long long int ll;
using namespace std;
int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int m;scanf("%d",&m);
		vector<int> a,b;
		for(int j=0;j<m;j++){
			int s; scanf("%d",&s); a.push_back(s);
		}
		for(int j=0;j<m;j++){
			int s; scanf("%d",&s); b.push_back(s);
		}
		sort(a.begin(),a.end());
		sort(b.begin(),b.end(),greater<int>());

		ll mt=0;
		for(int j=0;j<m;j++){
			mt+=(ll)a[j]*b[j];
		}
		printf("Case #%d: %lld\n",i,mt);
	}
	return 0;
}

All Your Base

In A.D. 2100, aliens came to Earth. They wrote a message in a cryptic language, and next to it they wrote a series of symbols. We've come to the conclusion that the symbols indicate a number: the number
of seconds before war begins!

Unfortunately we have no idea what each symbol means. We've decided that each symbol indicates one digit, but we aren't sure what each digit means or what base the aliens are using. For example, if they
wrote "ab2ac999", they could have meant "31536000" in base 10 -- exactly one year -- or they could have meant "12314555" in base 6 -- 398951 seconds, or about four and a half days. We are sure of three things: the number is positive; like us, the aliens will
never start a number with a zero; and they aren't using unary (base 1).

Your job is to determine the minimum possible number of seconds before war begins.

Input

The first line of input contains a single integer, T. T test cases follow. Each test case is a string on a line by itself. The line will contain only characters in the 'a' to 'z' and '0' to '9' ranges
(with no spaces and no punctuation), representing the message the aliens left us. The test cases are independent, and can be in different bases with the symbols meaning different things.

1 ≤ T ≤ 100
The answer will never exceed 10¹⁸

1 ≤ the length of each line < 61

Sample

分析：

贪心法，最高位安排１，往下依次安排０，２，３，.... t,

　　　　进制越小越好，lst=max(2,t+1)

#include <iostream>
#include <stdio.h>
#include <unistd.h>
#include <map>
using namespace std;

typedef long long int ll;

ll getMin(string s){
	int buf[70];
	map<char,int> m;
	int lst=0;
	for(int i=0;i<s.length();i++){
		char c=s[i];
		if(m.find(c)!=m.end()){
			buf[i]=m[c];
		}
		else{
			if(i==0) buf[i]=1,m[c]=1;
			else{
				buf[i]=lst++,m[c]=buf[i];
			   	if(lst==1) lst=2;//jump 1
			}
		}
	}
	lst=(lst==0)?2:lst;
	ll t=0;
	for(int i=0;i<s.length();i++){
		t*=lst;
		t+=buf[i];
	}
	return t;
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		char buf[70];
		scanf("%s",buf);
		printf("Case #%d: %lld\n",i+1,getMin(string(buf)));
	}
	return 0;
}