TopCoder HigSchool 2010 Round 1

这是第一次比赛。。本来是海选出500个人的。。结果总共都没有500个人囧。。
由于明天就要上学了。。本来不想参加的。。但是根本没有睡意。。于是就上了。。
第一题这个太水了。。怎么做都可以。。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class TheSequencesLevelOne {
public:
vector <int> find(vector <int>);
};

vector <int> TheSequencesLevelOne::find(vector <int> s) {
vector<int> ans;
for(int i=0;i<s.size();i++)
{
int a;
for(int t=0;t<=7;t++)
{
int x=s[i];
x-=t;
if(x%4==0||x%7==0)
{
a=x;break;
}
x+=2*t;
if(x%4==0||x%7==0)
{
a=x;break;
}
}
ans.push_back(a);
}
return ans;
}

//Powered by [KawigiEdit] 2.0!
第二题找规律啊。。奇数位放当前最小的,放了后删掉,偶数位放当前第二小的,放了后删掉,
最后一位特判一下就可以了。。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class TheSequencesLevelTwo {
public:
vector <int> find(vector <int>);
};

vector <int> TheSequencesLevelTwo::find(vector <int> s) {
set<int> S(s.begin(),s.end());
vector<int> Ans;
for(int i=0;i<s.size()-1;i++)
{
if(i%2==0)
{
Ans.push_back(*S.begin());
S.erase(S.begin());
}
else
{
Ans.push_back(*(++S.begin()));
S.erase(++S.begin());
}
}
Ans.push_back(*S.begin());
return Ans;
}

//Powered by [KawigiEdit] 2.0!
第三题的题目可以转化成分成有序的两堆不包括最大数,两堆中相邻元素差不超过K。那么从小到大一个个考虑元素,每个堆有意义的只有大小和最上面的数。。同时一定有一个堆最上面是当前最大的数,所以只要记录3个值就可以了。。然后递推。。算出所有的结果。。然后判断一下最大数就可以了。。
我也不知道为什么我非常WS的用了动态申请。。
dp[i][j][k]当前左边堆有i个,右边堆有j最大的那个在左边堆的最上面,k是右边堆最上面数的编号
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class TheSequencesLevelThree {
public:
int find(vector <int>, int);
};
const int mod=1234567891;
int TheSequencesLevelThree::find(vector <int> s, int K) {
sort(s.begin(),s.end());
long long***dp;
int n=s.size();if(n<3) return 0;
dp=new long long**[n+1];
for(int i=0;i<=n;i++)
{
dp[i]=new long long*[n+1];
for(int j=0;j<=n;j++)
{
dp[i][j]=new long long[n+1];
for(int k=0;k<=n;k++)
dp[i][j][k]=0;
}
}
dp[0][0][0]=1;int t;
for(int l=0;l<n;l++)
for(int i=0;i<=l;i++)
{
int j=l-i;
for(int k=0;k<n;k++)
if(t=dp[i][j][k])
{
int now=i+j;
if(i==0||s[now]-s[now-1]<=K)
dp[i+1][j][k]+=t,dp[i+1][j][k]%=mod;
if(j==0||s[now]-s[k]<=K)
dp[j+1][i][now-1]+=t,dp[j+1][i][now-1]%=mod;
}
}
long long ans=0;
for(int l=1;l<n-1;l++)
{
int r=n-l-1;
for(int k=0;k<n;k++)
{
int x=dp[l][r][k];
if(s[n-1]-s[k]<=K&&s[n-1]-s[n-2]<=K)
ans+=x,ans%=mod;
}
}
ans*=2;ans%=mod;
return ans;
}

//Powered by [KawigiEdit] 2.0!我还Cha掉了一个人的程序。。算法不知道对不对。一看他的特判就知道他判错了。。处女Cha啊。。
我的Coding的速度真是慢死了。。分低的要命。。囧
PS.那个人算法真是对的。。

这么大的随机数据都过了。。反而被我这个Cha掉囧。。

2 thoughts on “TopCoder HigSchool 2010 Round 1

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>