The Fourth Dimension Space

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

暑假第一次大练习赛总结

 

     难度感觉还好吧,最后一题那么简单居然没过有点后悔,而且做RSA浪费了大量时间导致后来没有时间看别的题,这一点要注意下。不然有很多能过的题过不了,这就比较遗憾了。

A. 剩下的士兵 就是对n不断地除以m,直到比m小为止,同时记录除了几次,然后将剩下的数字乘以mN次即可得到答案。
#include
<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;
int n,m;

int get(int n,int d)
{
    
int res=n;
    
for(int i=1;i<=d;i++)
    
{
        res
*=m;
    }

    
return res;
}


int main()
{
    
    
while(scanf("%d%d",&n,&m)!=EOF)
    
{
        
if(n==0&&m==0)
            
break;
        
int cnt=0;
        
while(n)
        
{
            
if(n<m)
                
break;
            n
/=m;
            cnt
++;
        }

        printf(
"%d\n",n);
        
for(int i=1;i<n;i++)
            printf(
"%d ",get(i,cnt));
        printf(
"%d\n",get(n,cnt));

    }

    
return 0;
}

    
B base64编码,貌似有道上才做过的,可是我依然选择了数组模拟。 怎么就不会用位运算呢。。。这题可以再研究下
#include
<iostream>
#include
<cmath>
#include
<algorithm>
#include
<map>
using namespace std;
map
<int,char>mm;

/**//*
int main()
{

    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    int a;
    char s[10];
    while(scanf("%d%s",&a,s)!=EOF)
    {

        printf("mm[%d]='%s';\n",a,s);


    }
    return 0;
}
*/


int two[]={32,16,8,4,2,1};
char s[1000];
int t[1000];
int lastpos;
void add(int i,int a)//将字符串的asc码附加到i号地址的后面
{    
    
int tt=a;
    
for(int j=i+8-1;j>=i;j--)
    
{

        t[j]
=tt%2;
        tt
/=2;
    }

}


int get(int i)
{

    
int res=0;
    
for(int j=0;j<6;j++)
    
{
        res
+=t[i+j]*two[j];
    }

    
return res;
}




int main()
{
    mm[
0]='A';
    mm[
17]='R';
    mm[
34]='i';
    mm[
51]='z';
    mm[
1]='B';
    mm[
18]='S';
    mm[
35]='j';
    mm[
52]='0';
    mm[
2]='C';
    mm[
19]='T';
    mm[
36]='k';
    mm[
53]='1';
    mm[
3]='D';
    mm[
20]='U';
    mm[
37]='l';
    mm[
54]='2';
    mm[
4]='E';
    mm[
21]='V';
    mm[
38]='m';
    mm[
55]='3';
    mm[
5]='F';
    mm[
22]='W';
    mm[
39]='n';
    mm[
56]='4';
    mm[
6]='G';
    mm[
23]='X';
    mm[
40]='o';
    mm[
57]='5';
    mm[
7]='H';
    mm[
24]='Y';
    mm[
41]='p';
    mm[
58]='6';
    mm[
8]='I';
    mm[
25]='Z';
    mm[
42]='q';
    mm[
59]='7';
    mm[
9]='J';
    mm[
26]='a';
    mm[
43]='r';
    mm[
60]='8';
    mm[
10]='K';
    mm[
27]='b';
    mm[
44]='s';
    mm[
61]='9';
    mm[
11]='L';
    mm[
28]='c';
    mm[
45]='t';
    mm[
62]='+';
    mm[
12]='M';
    mm[
29]='d';
    mm[
46]='u';
    mm[
63]='/';
    mm[
13]='N';
    mm[
30]='e';
    mm[
47]='v';
    mm[
14]='O';
    mm[
31]='f';
    mm[
48]='w';
    mm[
15]='P';
    mm[
32]='g';
    mm[
49]='x';
    mm[
16]='Q';
    mm[
33]='h';
    mm[
50]='y';
    
int ca;
    scanf(
"%d",&ca);
    cin.ignore();
    
while(ca--)
    
{
        
        memset(t,
0,sizeof(t));
        gets(s);
        
int len=strlen(s);
        lastpos
=len*8-1;
        
for(int i=0;i<len;i++)
        
{
            add(i
*8,(int)s[i]);
        }

        
if(len*8%6!=0)
        
{
            
for(int i=0;i<=len*8/6;i++)
            
{

                
int ans=get(i*6);
                printf(
"%c",mm[ans]);
            }

        }

        
else
        
{
            
for(int i=0;i<len*8/6;i++)
            
{

                
int ans=get(i*6);
                printf(
"%c",mm[ans]);
            }

        }


        
if(len%3==0)
        
{
            printf(
"\n");
            
continue;
        }

        
else if(len%3==1)
        
{
            printf(
"==\n");
        }

        
else if(len%3==2)
        
{

            printf(
"=\n");
        }

        
    }

    
return 0;

}



G Add Number 
这题用贪心 但是感觉有点诡异,我也没法给出这种方法的证明。恩 再琢磨琢磨 #include
<iostream>
#include
<algorithm>
using namespace std;

int const maxn=50;
int t;
int a[maxn];
int n,m,k;

void input()
{
    scanf(
"%d%d%d",&n,&m,&k);
    
for(int i=1;i<=m;i++)
        scanf(
"%d",&a[i]);
}


int main()
{
    scanf(
"%d",&t);
    
while(t--)
    
{

        input();
        
int cnt=0;
        
int tmax=0;
        
int pos=1;
        
//while(tmax<a[pos]-1)
        
//{
        
//    cnt++;
        
//    tmax=2*tmax+1;
        
//}
        
        
for(pos=1;pos<=m;pos++)
        
{

            
while(tmax<a[pos]-1)
            
{
                cnt
++;
                tmax
=2*tmax+1;
            }

            tmax
+=a[pos];
        }

        
while(tmax<n)
        
{
            tmax
=2*tmax+1;
            cnt
++;
        }

        
if(cnt<=k)
            printf(
"YES\n");
        
else
            printf(
"NO\n");
    }

    
return 0;
}
谢谢 Glory 神牛提示

H Route
做BFS,果如到达某个点的概率大于初始值就更新它,由于是BFS,所以每条路径都会测试到。
#include
<iostream>
#include
<algorithm>
#include
<memory.h>
using namespace std;

int const maxn=1010;
int mm[1010][1010];
int t;
int n;
//int v[maxn];
double p[maxn];//1到n-2 注意
double realp[maxn];
struct node
{
    
int t;
    node 
*next;
}
pool[maxn*maxn];

struct node2
{
    
int t;
    
double gailv;

}
q[maxn*maxn];
node hash[maxn];
int pcnt=0;
node 
*newnode()
{
    node 
*p=&pool[pcnt++];
    
return p;
}

void add(int a,int b)
{
    node 
*p=newnode();
    p
->next=hash[a].next;
    p
->t=b;
    hash[a].next
=p;
}

void init()
{
    
    
for(int i=0;i<n;i++)
        realp[i]
=0;//记住这个100
    pcnt=0;
    
for(int i=0;i<=n;i++)
    
{
        hash[i].next
=NULL;
        hash[i].t
=-1;
    }

}


void input()
{
    init();
    
int i,j;
    
for(i=0;i<n;i++)
        
for(j=0;j<n;j++)
        
{

            
int t;
            scanf(
"%d",&t);
            
if(t==1)
                add(i,j);
        }

}


int main()
{

    scanf(
"%d",&t);
    
while(t--)
    
{
        scanf(
"%d",&n);
        input();
        
        
for(int i=1;i<n-1;i++)
            scanf(
"%lf",&realp[i]);
        memset(p,
0,sizeof(p));
        realp[n
-1]=1;
        realp[
0]=1;
            

        
int l,r;
        q[
1].gailv=1;
        q[
1].t=0;
        l
=r=1;
        
while(l<=r)
        
{
            
for(node *pp=hash[q[l].t].next;pp;pp=pp->next)
            
{
                
if(realp[pp->t]*q[l].gailv>p[pp->t])
                
{
                    p[pp
->t]=realp[pp->t]*q[l].gailv;
                    r
++;
                    q[r].gailv
=p[pp->t];
                        q[r].t
=pp->t;

                }

            }

            l
++;
        }

        
if(p[n-1]>0.00001)
            printf(
"%.4lf\n",p[n-1]);
        
else
            printf(
"Cannot reach!\n");
    }

    
return 0;
}

J RSA签名 数论大综合题,这次居然是卡在学校的OJ不能用long 
long 上,我囧啊 浪费我近2个小时时间,这两个小时至少可以出两题吧。。。具体分析见这篇文章
    http://www.cppblog.com/abilitytao/archive/2010/05/22/116089.html



K.纯暴力。。。开始的时候还以为先得猜出4个数再暴力。。。没想到是直接从0暴力到9999。。。我汗
#include
<iostream>
#include
<algorithm>
using namespace std;
int const maxn=100;
int n;

struct node
{
    
int a[4];
    
int A,B;
    
bool operator<(node other)const
    
{
        
return B<other.B;
    }


}
re[maxn];

bool OK(int p[])
{

    
int v[10];
    memset(v,
0,sizeof(v));
    
for(int j=0;j<4;j++)
    
{
        
if(v[p[j]]==1)
            
return false;
        v[p[j]]
=1;
    }

    
return true;
}



bool check(int num)
{
    
int v[10];
    
int p[4];
    
int nn=num;
    
for(int j=3;j>=0;j--)
    
{
        p[j]
=nn%10;
        nn
/=10;
    }

    
if(!OK(p))
        
return false;
    
for(int i=0;i<n;i++)
    
{
        memset(v,
0,sizeof(v));
        
int cnt1=0;
        
int cnt2=0;
        
for(int j=0;j<4;j++)
        
{
            
if(p[j]==re[i].a[j])
                cnt1
++;
        }

        
if(cnt1!=re[i].A)
            
return false;
        
for(int j=0;j<4;j++)
        
{
            v[re[i].a[j]]
=1;
        }

        
for(int j=0;j<4;j++)
        
{
            
if(v[p[j]]==1)
                cnt2
++;
        }

        
if(cnt2!=re[i].B)
            
return false;
    }

    
return true;
}



int main()
{

    
while(scanf("%d",&n))
    
{
        
if(n<=0)
            
break;
        
for(int i=0;i<n;i++)
        
{
            scanf(
"%1d%1d%1d%1d %1dA%1dB",&re[i].a[0],&re[i].a[1],&re[i].a[2],&re[i].a[3],&re[i].A,&re[i].B);
        }

        
for(int i=100;i<=9999;i++)
        
{
            
if(i==2134)
                
int tt=1234;
            
int p[4];
            
if(check(i))
            
{
                
int nn=i;
                
for(int j=3;j>=0;j--)
                
{
                    p[j]
=nn%10;
                    nn
/=10;
                }

                
for(int j=0;j<4;j++)
                    printf(
"%d",p[j]);
                printf(
"\n");
                
break;
            }


        }


        
    }

    
return 0;
}

   

posted on 2010-07-08 22:29 abilitytao 阅读(1664) 评论(3)  编辑 收藏 引用

评论

# re: 暑假第一次大练习赛总结 2010-07-09 13:32 飞鸽传书

知识是很基本的,不过看你写得很好,赞!  回复  更多评论   

# re: 暑假第一次大练习赛总结 2010-07-10 08:54 treeboy

弱弱地问下:怎么把文章放在首页,我是新用户  回复  更多评论   

# re: 暑假第一次大练习赛总结[未登录] 2010-07-30 00:46 abilitytao

@treeboy
写完之后选择首页原创精华区  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理