首页 > 代码库 > 10.29 下午考试

10.29 下午考试

P74

 

竞赛时间:??????????:??-??:??

题目名称

 

 

 

名称

ha

haha

hahaha

输入

ha.in

haha.in

hahaha.in

输出

ha.out

haha.out

hahaha.out

每个测试点时限

1秒

1.5秒

1.5秒

内存限制

512MB

512MB

512MB

测试点数目

10

10

10

每个测试点分值

10

10

10

是否有部分分

题目类型

传统

传统

传统

注意事项(请务必仔细阅读):

 

 

【问题描述】

祖玛是一款曾经风靡全球的游戏,其玩法是:在一条轨道上初始排列着若干个彩色珠子,其中任意三个相邻的珠子不会完全同色。此后,你可以发射珠子到轨道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻,它们就会立即消失。这类消除现象可能会连锁式发生,其间你将暂时不能发射珠子。

 

开发商最近准备为玩家写一个游戏过程的回放工具。他们已经在游戏内完成了过程记录的功能,而回放功能的实现则委托你来完成。

游戏过程的记录中,首先是轨道上初始的珠子序列,然后是玩家接下来所做的一系列操作。你的任务是,在各次操作之后及时计算出新的珠子序列。

【输入格式】

第一行是一个由大写字母‘A‘~‘Z‘组成的字符串,表示轨道上初始的珠子序列,不同的字母表示不同的颜色。

第二行是一个数字,表示整个回放过程共有次操作。

接下来的行依次对应于各次操作。每次操作由一个数字和一个大写字母描述,以空格分隔。其中,为新珠子的颜色。若插入前共有颗珠子,则表示新珠子嵌入之后(尚未发生消除之前)在轨道上的位序。

【输出格式】

输出共行,依次给出各次操作(及可能随即发生的消除现象)之后轨道上的珠子序列。

如果轨道上已没有珠子,则以“-”表示

【样例输入】

ACCBA

5

1 B

0 A

2 B

4 C

0 A

【样例输出】

ABCCBA

AABCCBA

AABBCCBA

-

A

【样例解释】

你以为山里又有座庙?

【数据规模与约定】

的数据满足

 暂无

【问题描述】

栈是一种强大的数据结构,它的一种特殊功能是对数组进行排序。例如,借助一个栈,依次将数组1,3,2按顺序入栈或出栈,可对其从大到小排序:

1入栈;3入栈;3出栈;2入栈;2出栈;1出栈。

在上面这个例子中,出栈序列是3,2,1,因此实现了对数组的排序。

遗憾的是,有些时候,仅仅借助一个栈,不能实现对数组的完全排序。例如给定数组2,1,3,借助一个栈,能获得的字典序最大的出栈序列是3,1,2

2入栈;1入栈;3入栈;3出栈;1出栈;2出栈。

请你借助一个栈,对一个给定的数组按照出栈顺序进行从大到小排序。当无法完全排序时,请输出字典序最大的出栈序列。

【输入格式】

输入共行。

第一行包含一个整数,表示入栈序列长度。

第二行包含个整数,表示入栈序列。输入数据保证给定的序列是到n的全排列,即不会出现重复数字。

【输出格式】

仅一行,共个整数,表示你计算出的出栈序列。

【样例输入】

3

2 1 3

【样例输出】

3 1 2

【样例解释】

这回山里有座塔。

【数据规模与约定】

对于的数据,。

对于的数据,。

对于的数据,。

 

技术分享
/*WA 0分 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 1000010using namespace std;int n,now,top;int a[maxn],f[maxn];int stack[maxn];int init(){    int x=0,f=1;char c=getchar();    while(c<0||c>9){if(c==-)f=-1;c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}    return x*f;}int main(){    freopen("haha.in","r",stdin);    freopen("haha.out","w",stdout);    n=init();now=n;    for(int i=1;i<=n;i++)      a[i]=init();    for(int i=1;i<=n;i++)    {        stack[++top]=a[i];        f[a[i]]=1;        while((top&&stack[top]>=now)||f[now])        {            printf("%d ",stack[top]);            f[stack[top]]=0;            top--;now--;        }    }    return 0;}
View Code
/*刚开始 思路错了造的数据还很简单 没看出来正解 贪心当栈顶元素比后面所有没进队的都大 出栈否则 不断进栈最后全出栈 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 1000010using namespace std;int n,now,top;int a[maxn],s[maxn];int stack[maxn];int init(){    int x=0,f=1;char c=getchar();    while(c<0||c>9){if(c==-)f=-1;c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}    return x*f;}int main(){    freopen("haha.in","r",stdin);    freopen("haha.out","w",stdout);    n=init();now=n;    for(int i=1;i<=n;i++)      a[i]=init();    for(int i=n;i>=1;i--)      s[i]=max(s[i+1],a[i]);    for(int i=1;i<=n;i++)    {        stack[++top]=a[i];        while(top&&stack[top]>=s[i+1])          printf("%d ",stack[top--]);    }    while(top)printf("%d ",stack[top--]);    return 0;}

 

【问题描述】

Q对计算几何有着浓厚的兴趣。他经常对着平面直角坐标系发呆,思考一些有趣的问题。今天,他想到了一个十分有意思的题目:

首先,小Q会在轴正半轴和轴正半轴分别挑选个点。随后,他将轴的点与轴的点一一连接,形成条线段,并保证任意两条线段不相交。小Q确定这种连接方式有且仅有一种。最后,小Q会给出个询问。对于每个询问,将会给定一个点,请回答线段OP与条线段会产生多少个交点?

Q找到了正在钻研数据结构的你,希望你可以帮他解决这道难题。

【输入格式】

第行包含一个正整数,表示线段的数量;

第行包含个正整数,表示小Q在轴选取的点的横坐标;

第行包含个正整数,表示小Q在轴选取的点的纵坐标;

4行包含一个正整数,表示询问数量;

随后行,每行包含两个正整数,表示询问中给定的点的横、纵坐标。

【输出格式】

共行,每行包含一个非负整数,表示你对这条询问给出的答案。

【样例输入】

3

4 5 3

3 5 4

2

1 1

3 3

【样例输出】

0

3

【样例解释】

然后塔里啥都没有。

【数据规模与约定】

对于的数据,。

对于的数据,,坐标范围

技术分享
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 200010using namespace std;int n,m,l,r,a,b,ans;int x[maxn],y[maxn];int init(){    int x=0,f=1;char c=getchar();    while(c<0||c>9){if(c==-)f=-1;c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}    return x*f;}int judge(int t){    return y[t]*a>=x[t]*(y[t]-b);}int main(){    freopen("hahaha.in","r",stdin);    freopen("hahaha.out","w",stdout);    n=init();    for(int i=1;i<=n;i++)      x[i]=init();    for(int i=1;i<=n;i++)      y[i]=init();    sort(x+1,x+n+1);    sort(y+1,y+n+1);    m=init();    while(m--)    {        a=init();b=init();        l=0,r=n;        while(l<=r)        {            int mid=(l+r)/2;            if(judge(mid))            {                ans=mid;                l=mid+1;            }            else               r=mid-1;        }        printf("%d\n",ans);    }    return 0;}
View Code
/*呵呵呵开long long 就过了 不开就0分 ...... 本来用的除法检验 不用来后来不想用除法 移移项 结果呵呵... 全是10的8次方......正解二分判断一下P点是否在二分的线上方就行 */#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define LL long long#define maxn 200010using namespace std;LL n,m,l,r,a,b,ans;LL x[maxn],y[maxn];LL init(){    LL x=0,f=1;char c=getchar();    while(c<0||c>9){if(c==-)f=-1;c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}    return x*f;}LL judge(LL t){    return y[t]*a>=x[t]*(y[t]-b);}int main(){    freopen("hahaha.in","r",stdin);    freopen("hahaha.out","w",stdout);    n=init();    for(LL i=1;i<=n;i++)      x[i]=init();    for(LL i=1;i<=n;i++)      y[i]=init();    sort(x+1,x+n+1);    sort(y+1,y+n+1);    m=init();    while(m--)    {        a=init();b=init();        l=0,r=n;        while(l<=r)        {            LL mid=(l+r)/2;            if(judge(mid))            {                ans=mid;                l=mid+1;            }            else               r=mid-1;        }        printf("%d\n",ans);    }    return 0;}

 

10.29 下午考试