第一题 当成背包瞬秒。
第二题 有个结论 就是只有完全平方数才有奇数个因子， 开始只是觉得能过样例，不一定对。后来展开公式才发现确实是这么一回事
因为 如果 一个数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 触发一个内部断点 这样调试循环程序时候较为方便。