昨天下午查看邮箱，看到了topcoder的SRM比赛通知和cf的比赛通知，当时什么也不想做，心里空荡荡的，忽然就想参加一下，试试看。吃完晚饭回来一看，就剩十几分钟了，匆忙把平台下了，就开始等待比赛开始了。话说这是第一次在topcoder比赛，以前一直都不想的，认为自己水平不够，参加比赛也是找虐，想把水平提高一下再比赛，可是...直到现在还是菜鸟一只...汗颜... 以前也在tc上练习过了，貌似做了一道题...不过后来重装系统了，所有插件、配置都没了，等到比赛开始，我就有点傻了，写类写方法...?好像有点印象，就试着写了第一题，在不能编译、不能调试的情况下（当时忘了有编译和调试功能），竟然提交成功了，哈哈，运气还不错。
Problem 1：给一个含有n个数的序列，从中找出k个数，使这k个数的和第二小。排序然后处理就可以了。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std; class LittleElephantAndBooks
{
public:
int getNumber(vector<int> pages, int number)
{
sort(pages.begin(), pages.end());
int sum = ;
for (int i = ; i < number-; i++)
sum += pages[i];
sum += pages[number];
return sum;
}
};
Problem 1
Problem 2: 给两个正整数N和K，A和B是[1...N]的两个排列，定义magic(A, B) = sum (max(A[i], B[i])), 1 <= i <= N。找出magic(A, B) >= K 的个数。
当时第一感觉就是暴力，时间有点紧，一时也没想到什么好的解决办法，就暴力枚举了，时间复杂度O((n!)2)...不过还是提交了，结果被challenge了...（challenge时找了好长时间才知道怎么做，然后就看人家challenge，完全打酱油了...），今天看别人代码才发现了O(n!)的解法，当A不变B变化时，将A和B对应数对进行排列，magic值不变，共有有n!种排列。
#include <string>
#include <vector>
#include <algorithm>
using namespace std; class LittleElephantAndPermutationDiv2
{
public:
long long getNumber(int N, int K)
{
long long fact[];
fact[] = ;
for (int i = ; i <= N; i++)
fact[i] = i * fact[i-]; vector<int> a, b;
for (int i = ; i <= N; i++)
{
a.push_back(i);
b.push_back(i);
}
long long cnt = ;
do
{
int sum = ;
for (int i = ; i <= N; i++)
sum += max(a[i], b[i]);
if (sum >= K) cnt += fact[N];
} while (next_permutation(b.begin(), b.end()));
return cnt;
}
};
Problem 2
Problem 3: 给一个[A, A+N]的序列，通过擦除数的数字使得系列变成一个非递减序列，问共有多少种方法？
看完后没什么思路，想了一会儿还是没法写，就坐那发呆等着结束了...-_-||，今天准备看别人代码，扫了一眼，我...还是算了，以后再说吧...
第一次tc比赛就这样了，结果rating 875，感觉还算不错吧，其实也没我想的那么重要，不一定非要有一个好的开始，勇于开始也是不错的选择。
PS：吐槽一下这网络，比赛的时候掉了好几次，今天感觉一半的时间都是浪费在登陆上了...