首页 > 代码库 > 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;}
/*刚开始 思路错了造的数据还很简单 没看出来正解 贪心当栈顶元素比后面所有没进队的都大 出栈否则 不断进栈最后全出栈 */#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;}
/*呵呵呵开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 下午考试