1 水题。。。非常松的限制条件,如果都去掉的话,或许会成为challenge的一道好题
2 非常恶心的问题,一个trick把我给绕进去了。。不能线序的遍历一遍,需要不断设置,不断扩充未完成的集合,并附设标记位
3 又是一道恶心的题目。。。这种1000分的题目,一定不要放弃,不断思考,一定会有结果的。。
This problem can be solved greedily with the following powerful observation.
Let X1, X2, X3, ..., XN be the numbers. We must allocate them in the encrypted string in some order. Suppose that Xi is the last number allocated number in this order. Then, it is optimal to allocate the rest of the numbers starting from the smallest one and in increasing order. That is, if Xi is the last number allocated, then the smallest possible length of the encrypted string is partialsolution(sortascending(X1,X2,...,X(i-1),X(i+1),...,XN) + Xi).
We'll see that this is true by contradiction. Suppose there exist j and k (both are not equal to i), j Xk and the representative of Xj is to the left of the representative of Xk. The proof will be complete if we show that we can swap the locations of the representatives of these two numbers, since we can then apply this until all numbers except Xi are sorted. We suppose that Xj is allocated at position 2^Pj and Xk is allocated at position 2^Pk. Since Xk
解答,代码写的真的是非常的漂亮!!
// END CUT HERE
#line 5 "SignalIntelligence.cpp"
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
// BEGIN CUT HERE
//Begin Sosi TopCoder
//const double EPS=1e-11;
//const double PI=acos(-1.0);
//const short INF=32767,NF= -32768;
//const int INF=2147483647,NF= -2147483648;
//const long long INF=9223372036854775807,NF=-9223372036854775808;
//const long double INF=99999999.99999999;
//Numberic Functions
//template //template //template // {vector
// i++;if (i>n/i) i=n;}if (n>1) R.push_back(make_pair(n,1));return R;} //template // {if(n //template // {vector
//Translator //template //int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;}//NOTES:toInt( //long long toInt64(string s){long long r=0;istringstream sin(s);sin>>r;return r;} //double toDouble(string s){double r=0;istringstream sin(s);sin>>r;return r;}//NOTES:toDouble( //template //template //template //template //template //template //Fraction //template //template //template //template //template //template //template //STL //bool comp(T A,T B){return A //do{ } while(next_permutation(T.begin(), T.end())); //int dirx[]={1,0,-1,0}; //int diry[]={0,-1,0,1}; //clockwise //int dirx[]={1, 1, 0,-1,-1,-1,0,1}; //int diry[]={0,-1,-1,-1, 0, 1,1,1}; //clockwise //End Sosi TopCoder // END CUT HERE class SignalIntelligence //$CARETPOSITION$ // BEGIN CUT HERE // END CUT HERE }; // BEGIN CUT HERE 做题的时候,summer在旁边晃来晃去。。。心烦。。。不过看到最后的代码的实现,的确是非常优美啊!
{
public:
long long encrypt(vector
{
int n = numbers.size();
long long best = -1;
for (int i=0;i
//printf("try %d as last one/n", numbers[i]);
vector
for (int j=0;j
sort(numbers2.begin(),numbers2.end());
//printf("numbers left:");
//for (int j=0;j
long long pos = 1, npos = pos;
for (int j=0;j
//printf("set %d at pos %d/n", numbers2[j], pos);
npos = pos;
while (pos + numbers2[j] >= npos) npos *= 2;
pos = npos;
}
//printf("would be %d long/n/n",pos + numbers[i]-1);
if (best == -1 || npos + numbers[i]-1 }
return best;
}
public:
void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); }
private:
template
void test_case_1() { int Arr0[] = {4,4,2,2}; vector
void test_case_2() { int Arr0[] = {1000000000,1000000000,1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,1000000000,1000000000}; vector
int main()
{
SignalIntelligence ___test;
___test.run_test(-1);
return 0;
}