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 阅读(1680) 评论(3)  编辑 收藏 引用

评论

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

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

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

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

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

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


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