首页 > 代码库 > 10.27 noip模拟试题(afternoon)(跪在游戏玩少了2333)
10.27 noip模拟试题(afternoon)(跪在游戏玩少了2333)
【问题描述】
祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。
开发商最近准备为玩家写一个游戏过程的回放工具。他们已经在游戏内完成了过程记录的功能，而回放功能的实现则委托你来完成。
游戏过程的记录中，首先是轨道上初始的珠子序列，然后是玩家接下来所做的一系列操作。你的任务是，在各次操作之后及时计算出新的珠子序列。
【输入格式】
第一行是一个由大写字母‘A‘~‘Z‘组成的字符串，表示轨道上初始的珠子序列，不同的字母表示不同的颜色。
第二行是一个数字?，表示整个回放过程共有?次操作。
接下来的?行依次对应于各次操作。每次操作由一个数字?和一个大写字母?描述，以空格分隔。其中，?为新珠子的颜色。若插入前共有?颗珠子，则? ∈ [0,?] 表示新珠子嵌入之后（尚未发生消除之前）在轨道上的位序。
【输出格式】
输出共?行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上
第 2 页 共 6 页
P74
的珠子序列。
如果轨道上已没有珠子，则以“-”表示。
【样例输入】
ACCBA 5
1 B
0 A
2 B
4 C
0 A
【样例输出】
ABCCBA
AABCCBA
AABBCCBA
-
A
【样例解释】
你以为山里又有座庙？
游戏玩少了23333 规则想错了
wa成sb2333 错的就不粘了 巨丑2333
代码没写完2333
【问题描述】
栈是一种强大的数据结构，它的一种特殊功能是对数组进行排序。例如，借助一个栈，依次将数组 1,3,2 按顺序入栈或出栈，可对其从大到小排序：
1 入栈；3 入栈；3 出栈；2 入栈；2 出栈；1 出栈。
在上面这个例子中，出栈序列是 3,2,1，因此实现了对数组的排序。
遗憾的是，有些时候，仅仅借助一个栈，不能实现对数组的完全排序。例如给定数组 2,1,3，借助一个栈，能获得的字典序最大的出栈序列是 3,1,2：
2 入栈；1 入栈；3 入栈；3 出栈；1 出栈；2 出栈。
请你借助一个栈，对一个给定的数组按照出栈顺序进行从大到小排序。当无法完全排序时，请输出字典序最大的出栈序列。
【输入格式】
输入共2行。
第一行包含一个整数?，表示入栈序列长度。
第二行包含?个整数，表示入栈序列。输入数据保证给定的序列是1到 n 的全排列，即不会出现重复数字。
【输出格式】
仅一行，共?个整数，表示你计算出的出栈序列。
【样例输入】
3
2 1 3
【样例输出】
3 1 2
【样例解释】
这回山里有座塔。
【数据规模与约定】
简单贪心 闲的写了ST表后缀就好了23333
#include<cstdio>#define maxn 2000010using namespace std;int n,a[maxn],s[maxn],top,now,f[maxn][25],P[maxn];int init(){ int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}int max(int x,int y){ return x>y?x:y;}void Get(){ for(int i=1;i<=n;i++)f[i][0]=a[i]; for(int j=1;j<=20;j++) for(int i=1;i+(1<<j)-1<=n;i++) f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]); for(int i=1;i<=n;i++) for(int j=0;j<=20;j++) if((1<<j)>i){ P[i]=j-1;break; }}int Query(int l,int r){ int k=P[r-l+1]; return max(f[l][k],f[r-(1<<k)+1][k]);}int main(){ freopen("haha.in","r",stdin); freopen("haha.out","w",stdout); n=init(); for(int i=1;i<=n;i++) a[i]=init(); now=n;Get(); for(int i=1;i<=n;i++){ s[++top]=a[i]; while(s[top]==now&&top){ printf("%d ",s[top]); top--;now--; } while(1){ int mx=Query(i+1,n); if(mx<s[top]){ printf("%d ",s[top]);top--; } else break; } } while(top){ printf("%d ",s[top]);top--; } return 0;}
【问题描述】
小 Q 对计算几何有着浓厚的兴趣。他经常对着平面直角坐标系发呆，思考一些有趣的问题。今天，他想到了一个十分有意思的题目：
首先，小 Q 会在?轴正半轴和?轴正半轴分别挑选?个点。随后，他将?轴的点与?轴的点一一连接，形成?条线段，并保证任意两条线段不相交。小 Q 确定这种连接方式有且仅有一种。最后，小 Q 会给出?个询问。对于每个询问，将会
给定一个点?(?? ,??)，请回答线段 OP 与?条线段会产生多少个交点？
小 Q 找到了正在钻研数据结构的你，希望你可以帮他解决这道难题。
【输入格式】
第1行包含一个正整数?，表示线段的数量；第2行包含?个正整数，表示小 Q 在?轴选取的点的横坐标；
第3行包含?个正整数，表示小 Q 在?轴选取的点的纵坐标；第 4 行包含一个正整数?，表示询问数量；
随后?行，每行包含两个正整数?? ,??，表示询问中给定的点的横、纵坐标。
【输出格式】
共?行，每行包含一个非负整数，表示你对这条询问给出的答案。
【样例输入】
3
4 5 3
3 5 4
2
1 1
3 3
【样例输出】
0
3
【样例解释】
然后塔里啥都没有。
裸二分+数学只是判断
#include<cstdio>#include<cstring>#include<algorithm>#define inf 1e9#define maxn 200010using namespace std;int n,m,a[maxn],b[maxn];struct node{ int x,y;}p[maxn];int init(){ int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}bool Judge(int i,int x,int y){ double Y=(double)p[i].y-(double)x*(double)p[i].y/(double)p[i].x; return Y<=y;}int main(){ freopen("hahaha.in","r",stdin); freopen("hahaha.out","w",stdout); n=init(); for(int i=1;i<=n;i++) a[i]=init(); for(int i=1;i<=n;i++) b[i]=init(); sort(a+1,a+1+n);sort(b+1,b+1+n); for(int i=1;i<=n;i++){ p[i].x=a[i];p[i].y=b[i]; } n++;p[n].x=inf;p[n].y=inf; m=init();int x,y; while(m--){ x=init();y=init(); int l=0,r=n,pos=0; while(l<=r){ int mid=l+r>>1; if(Judge(mid,x,y)){ l=mid+1;pos=max(pos,mid); } else r=mid-1; } printf("%d\n",pos); } return 0;}
10.27 noip模拟试题(afternoon)(跪在游戏玩少了2333)