第一题 当成背包瞬秒。
第二题 有个结论 就是只有完全平方数才有奇数个因子, 开始只是觉得能过样例,不一定对。后来展开公式才发现确实是这么一回事
因为 如果 一个数n=a1^k1*a2^k2*a3^k3....就是将它进行素因子分解
那么它的约束个数g(n)=(k1+1)*(k2+1)*(k3+1)*....(kn+1)
如果要为奇数,那么所有括号里的数均为奇数,显然k1 to kn为偶数,该数必为完全平方数!
第三题 想随机化暴搞,估计能过吧,赛后再研究下。。。下午过了,其实和乱搞是一回事,就是枚举所有情况呵。
250
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int dp[6000];
int a[100];

class LotteryTicket


{
public:
string buy(int price, int b1, int b2, int b3, int b4)

{
memset(dp,-1,sizeof(dp));
dp[0]=1;
int i,j;
a[1]=b1;
a[2]=b2;
a[3]=b3;
a[4]=b4;
for(i=1;i<=4;i++)

{
for(j=4000;j>=0;j--)
if(dp[j]==1)
dp[j+a[i]]=1;
}
if(dp[price]==1)

{

string tem="POSSIBLE";
return tem;
}
else

{

string tem="IMPOSSIBLE";
return tem;
}


}
};
500
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

long long a[1000000];

int init()


{

long long i;
long long mm=(long long )1000000*1000000;
for(i=0;i<=1000000;i++)

{
if(i*i>mm)
break;
a[i+1]=i*i;
}
return i;
}

int get(long long n)


{
int i=0;

while(n)
{i++;n/=10;}
return i;
}

int cmp(long long n, string s)


{
int res=0;
int len=s.length();
int i;
for(i=len-1;i>=0;i--)

{
if(n%10!=(s[i]-'0'))
res++;
n/=10;
}
return res;

}

class LotteryCheating


{

public:
int minimalChange(string ID)

{
int res=9999999;
int n;
int len=ID.length();
n=init();
int i;
for(i=1;i<=n;i++)

{
//if(i==2)
// {
// __asm int 3;
// }

if(get(a[i])>len)
break;
int t=cmp(a[i],ID);
if(t<res)
res=t;
}
return res;


}
};


int main()


{

string t="123432";
LotteryCheating a;
a.minimalChange(t);

}


1000
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int n,m;
class MatrixGame


{
public:
vector <string> getMinimal(vector <string> matrix)

{

n=matrix.size();
m=matrix[0].length();
vector<int>x;
int i,j,k;
for(i=0;i<m;i++)
x.push_back(i);

vector <string> t=matrix;
vector <string> res=matrix;
while(true)

{
for(i=0;i<n;i++)
for(j=0;j<m;j++)

{
t[i][j]=matrix[i][x[j]];
}
sort(t.begin(),t.end());
if(t<res)
res=t;
if(next_permutation(x.begin(),x.end())==0)
break;

}
return res;


}
};



恩 1000的小结论是,任意的排列可以由无数次交换得到,证明类似冒泡排序,知道这个结论就好做了。另外就是next_permutation到最后一个排列时如果继续调用返回0.否则是1.
不过我发现我的代码还不够精简,显得比较长,不是很便于阅读。
同时小小地纪念下貌似是第一次成为房间第一,虽然得分不是太高,但是其他人都fail system test 了,呵呵,不过第三题还是没做出来,有些遗憾呢。
一个调试技巧
if(i == 99)


{
__asm int 3

}

int 3 触发一个内部断点 这样调试循环程序时候较为方便。