The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

TOPCODER SRM 466 小结

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

posted on 2010-04-04 01:47 abilitytao 阅读(1344) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理