【SinGuLaRiTy-1011】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.
G2019级信息奥赛专项训练
|
题目 |
程序名 |
时间 |
内存 |
测试点 |
|
原子核研究 |
atomic.cpp |
2s |
256MB |
10 |
|
球星 |
star.cpp |
2s |
256MB |
10 |
|
跳跃 |
jump.cpp |
2s |
256MB |
10 |
原子核研究(atomic.cpp)
题目描述
最近物理学家正在研究一些新的原子，称为X族。他们发现该族中的元素非常相近，但是其质量都不相同。质量越接近的越容易相互转化。现在，物理学家已经发明了一种设备，可以对X族的元素来进行以下三种操作：
1.generate M 产生质量为M的一个元素，如果已经存在，则该操作不产生作用。
2.romove M 销掉质量为M的元素，如果不存在质量为M的元素，则该操作不产生作用。
3.query 查询X族中质量最接近的两种元素的质量差的绝对值。如果此时X族中的元素个数小于2，则输出-1.
现在，请你写一个程序来模拟该设备的操作。
输入
输入包含多组测试数据，第一行一个整数t，表示测试数据的组数。对于每一组数据，第一行是一个整数n，表示有n条指令。接下来n行，每行表示一条指令，如上所述。M是一个正整数，不超过100000.
输出
对于每组测试数据，对于其中的每一个查询操作，都要输出一个结果。注意：每一组测试数据后要输出一个空行。
样例数据
|
样例输入 |
样例输出 |
|
1 |
-1 |
STD Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 100000
#define MAXM 100000
#define INF 0x3f3f3f3f
typedef long long int LL;
void Read(int &x)
{
x=;char c=getchar();bool flag=;
while(c<''||''<c){if(c=='-')flag=;c=getchar();}
while(''<=c&&c<=''){x=x*+c-'';c=getchar();}
if(flag)x=-x;
}
int L[MAXM*],R[MAXM*];
int len[MAXM*];
int lval[MAXM*],rval[MAXM*],minval[MAXM*];
int sz;
void updata(int x)
{
lval[x]=lval[x<<];
if(lval[x<<]==len[x<<])
lval[x]+=lval[x<<|];
rval[x]=rval[x<<|];
if(rval[x<<|]==len[x<<|])
rval[x]+=rval[x<<];
minval[x]=min(minval[x<<],minval[x<<|]);
if(rval[x<<]!=len[x<<]&&lval[x<<|]!=len[x<<|])
minval[x]=min(minval[x],rval[x<<]+lval[x<<|]);
}
void build(int l,int r,int x)
{
L[x]=l,R[x]=r;
len[x]=r-l+;
lval[x]=rval[x]=len[x];
minval[x]=INF;
if(L[x]==R[x])
return;
int mid=(l+r)>>;
build(l,mid,x<<);
build(mid+,r,x<<|);
updata(x);
}
void insert(int pos,int x)
{
if(L[x]==R[x])
{
lval[x]=rval[x]=;
minval[x]=INF;
return;
}
int mid=(L[x]+R[x])>>;
if(pos<=mid)
insert(pos,x<<);
else
insert(pos,x<<|);
updata(x);
}
void del(int pos,int x)
{
if(L[x]==R[x])
{
lval[x]=rval[x]=;
minval[x]=INF;
return;
}
int mid=(L[x]+R[x])>>;
if(pos<=mid)
del(pos,x<<);
else
del(pos,x<<|);
updata(x);
}
int query()
{
if(sz<)
return -;
else
return minval[]+;
}
bool has[MAXM+];
int main()
{
int T,n;
Read(T);
while(T--)
{
Read(n);
sz=;
build(,MAXM,);
memset(has,,sizeof(has));
char str[];
int x;
for(int i=;i<=n;++i)
{
scanf("%s",str);
if(str[]=='g')
{
Read(x);
if(!has[x])
{
has[x]=,++sz;
insert(x,);
}
}
else if(str[]=='r')
{
Read(x);
if(has[x])
{
has[x]=;
--sz;
del(x,);
}
}
else
printf("%d\n",query());
}
putchar();
}
return ;
}
题目分析
首先根据题目中涉及查询，插入，删点等操作，就可以大致判断出要用树形存储结构来做。
对于插入与删点这两个操作来说，基本就是"打板",与普通的平衡树没有什么差别。只是题目中提及“可能会删去‘不存在’的元素或插入‘存在’的元素”，最开始我没怎么在意，觉得只要在Delete函数与Insert函数里面修改一下判断条件就行了，后来却始终没有成功，调了足足有40多分钟（也就是这里耽误了太多时间）——后来发现问题在于对树的高度的更新存在问题：只要进行插入或删除操作就会更改平衡树的高度，而这显然是错误的。 后来才“迫不得已”用了一个“蠢办法”，就是设置一个bool型的has数组，去判断一个值是否存储在树中，来规避重复加/删点的问题。（当然，这个方法在最后被证明是正解）
对于查询操作，当时其实并不觉得写起来有多大的困难：在updata函数里面顺带加一个判断去更新minval数组就行了。
球星(star.cpp)
题目描述
给出球星们的能力值、年份、名字，有很多个查询，每个查询给出一个年份的范围，求出这个范围里能力值从高到低排列的前11名球员，如果能力值相同则按年份从低到高排，如果年份仍然相同，则按名字的字典序排。如果不足11个球员，就用XXX代替输出凑够11行。
输入
输入数据：
第一行包含1个整数N（1<=N<=50000）,表示球星的总数，接下来N行，每行描述了1个球星（year,name,ability）。0<=year<=1000000000,name不超过15个字母，0<=ability<=1000000000.
假设没有两个人的名字相同。接下来有一个整数R，表示有R个查询。接下来R行，每行描述了一个产寻，每个查询包含2个整数（x,y）,表示从第x年到第y年。（0<=x<=y<=1000000000）
输出
输出数据：对于每组数据，按上面描述的顺序输出最靠前的11个球员的名字，每个球员占一行。如果不足11行，则用XXX代替，凑够11行。每组数据后都有一个空行。
样例数据
|
样例输入 |
样例输出 |
| 5 1 a 1 2 b 2 2 c 6 5 e 50 5 d 50 2 1 2 5 5 |
c |
STD Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define maxn 50000
using namespace std;
struct node
{
int l,r;
int f[];
}tree[*maxn+];
int f[];
struct d
{
int y,a;
char n[];
bool operator <(const d &b)const
{
if(a==b.a)
{
if(y==b.y)
{
int len=max(strlen(n),strlen(b.n));
for(int i=;i<len;++i)
{
if(n[i]==b.n[i]) continue;
return n[i]>b.n[i];
}
}
return y>b.y;
}
return a<b.a;
}
}p[maxn+];
int n;
bool cmp(const d &a,const d &b)
{
return a.y<b.y;
}
void uptree(int i)
{
int lson=i<<,rson=(i<<)|;
int cl=,cr=,c=;
while((tree[lson].f[cl]||tree[rson].f[cr])&&c<)
{
if(!tree[lson].f[cl])
{
tree[i].f[c]=tree[rson].f[cr];
c++;cr++;
}
else if(!tree[rson].f[cr])
{
tree[i].f[c]=tree[lson].f[cl];
c++;cl++;
}
else if(p[tree[lson].f[cl]]<p[tree[rson].f[cr]])
{
tree[i].f[c]=tree[rson].f[cr];
c++;cr++;
}
else
{
tree[i].f[c]=tree[lson].f[cl];
c++;cl++;
}
}
return;
}
void Build_tree(int i,int l,int r)
{
tree[i].l=l;
tree[i].r=r;
if(l==r)
{
tree[i].f[]=l;
return;
}
int m=(l+r)>>;
Build_tree(i<<,l,m);
Build_tree((i<<)|,m+,r);
uptree(i);
}
void Ask(int i,int l,int r)
{
if(tree[i].l>r||tree[i].r<l) return;
if(l<=tree[i].l&&r>=tree[i].r)
{
int tf[];
memcpy(tf,f,sizeof f);
memset(f,,sizeof f);
int c1=,c2=,c=;
while((tf[c1]||tree[i].f[c2])&&c<)
{
if(!tf[c1])
{
f[c]=tree[i].f[c2];
c++;c2++;
}
else if(!tree[i].f[c2])
{
f[c]=tf[c1];
c++;c1++;
}
else if(p[tf[c1]]<p[tree[i].f[c2]])
{
f[c]=tree[i].f[c2];
c++;c2++;
}
else
{
f[c]=tf[c1];
c++;c1++;
}
}
return;
}
Ask(i<<,l,r);
Ask((i<<)|,l,r);
return;
}
int Find(int i,bool flag)
{
int L=,R=n;
if(!flag)
{
while(L<R)
{
int M=(L+R)>>;
if(p[M].y<i) L=M+;
else R=M;
}
return L;
}
else
{
while(L<R)
{
int M=(L+R+)>>;
if(p[M].y>i) R=M-;
else L=M;
}
return L;
}
}
int main()
{
p[].a=-;
while(cin>>n)
{
for(int i=;i<=n;++i)
scanf("%d%s%d",&p[i].y,p[i].n,&p[i].a);
sort(p+,p+n+,cmp);
Build_tree(,,n);
int q;
cin>>q;
for(int i=;i<=q;++i)
{
int l,r;
scanf("%d%d",&l,&r);
l=Find(l,);
r=Find(r,);
Ask(,l,r);
for(int j=;j<;++j)
{
if(f[j])
printf("%s\n",p[f[j]].n);
else printf("XXX\n");
}
if(i!=q) printf("\n");
memset(f,,sizeof f);
}
memset(tree,,sizeof tree);
}
return ;
}
题目分析
刚看到这道题的时候，唯一的反应就是“EXM？”实在是看不懂应该用那种算法好不好？想了想，觉得既然每个节点包含了那么多种信息，我就写个线段树+Splay好了，于是乎......写到一半发现自己写得思路已经不知所踪，那棵树呀就在转呀转呀......到了考试最后，我绝望的打了一个暴力，安慰自己：”至少，根据经验，至少能水个30分吧......“ 测评时，发现竟只有一个数据点——是的，超级大数据，果断爆零。
下来发现，似乎并没有自己想的那么复杂，用一个线段树+结构体排序，或是一个线段树+优先队列就行了。也就是说，对于线段树中的每一个节点，都塞一个排了序的数组（优先队列也是可以的）进去，维护一下，这道题就可以解决啦。（在上面的代码中我用的是结构体）
跳跃(jump.cpp)
事情出奇的顺利，自从高考研讨会过后，z 同学专心准备 noip2010 。可能是被 z 同学的 潇洒、帅气、阳关所吸引，zn 主动约到了 z 同学，就这样，zn 与 z 同学走到了一起~！那是 一次放假，众所周知，hz 的放假，对于不回家的同学就是能走出封闭的 hz 大门好好玩上3 个小时。Zn 刚与 z 同学吃完 kfc，他们来到了衡水唯一还算比较浪漫的地方(貌似叫什么人 民公园吧，ms 了~~）。
题目描述
公园中有许多木桩，每个木桩都有一个高度，活泼的小 z 同学喜欢从一个木桩跳到另 一个木桩上，zn 说太危险了，于是 z 同学让 zn 算出每一次跳跃的危险系数。小 z 每一次跳 跃的范围是一个 k*k 的矩形，危险系数为这个矩形内最高的木桩高度减去最小的。身为 oier， 你能比学数奥的 zn 算的快吗?
输入
第一行三个整数 n(木桩为 n*n 的矩阵）、k、b（小 zz 准备跳跃的次数） 接下来为 n*n 的矩阵，描述木桩的高度
接下来 b 行；每行两个整数 x,y(表示 z 同学跳跃的范围的左上角为第 x 行第 y 列）， 保证跳跃范围不超过矩阵的范围
样例数据
|
样例输入 |
样例输出 |
|
5 3 1 5 1 2 6 3 1 3 5 2 7 7 2 4 6 1 9 9 8 6 5 0 6 9 3 9 1 2 |
5 |
数据范围
对于30%的数据
0<k<=n<=250 0<b<=100
对于100%的数据
0<k<-n<=250 0<b<=1000 000
STD Code
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int f[][][];
int g[][][];
int N,M,K;
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
int log_2(int n){
int t=;
while (( << (t+))<n) t++;
return t;
}
int main(){
memset(f,,sizeof(f));
memset(g,,sizeof(g));
scanf("%d%d%d",&N,&M,&K);
for (int i=;i<=N;i++){
for (int j=;j<=N;j++){
scanf("%d",&f[i][j][]);
g[i][j][]=f[i][j][];
}
}
int w=log_2(M);
for (int k=;k<=w;k++){
for (int i=;i<=N;i++){
for (int j=;j<=N;j++){
if (i+( << k)-<=N && j+( << k)-<=N){
f[i][j][k]=min(f[i][j][k-],f[i+( << (k-))][j][k-]);
f[i][j][k]=min(f[i][j][k],f[i][j+( << (k-))][k-]);
f[i][j][k]=min(f[i][j][k],f[i+( << (k-))][j+( << (k-))][k-]);
g[i][j][k]=max(g[i][j][k-],g[i+( << (k-))][j][k-]);
g[i][j][k]=max(g[i][j][k],g[i][j+( << (k-))][k-]);
g[i][j][k]=max(g[i][j][k],g[i+( << (k-))][j+( << (k-))][k-]);
}
}
}
}
for (int t=;t<=K;t++){
int i,j;
scanf("%d%d",&i,&j);
int t1=i+M-;
int t2=j+M-;
int mi,ma;
mi=min(f[i][j][w],f[t1-( << w)+][t2-( << w)+][w]);
mi=min(mi,f[i][t2-( << w)+][w]);
mi=min(mi,f[t1-( << w)+][j][w]);
ma=max(g[i][j][w],g[t1-( << w)+][t2-( << w)+][w]);
ma=max(ma,g[i][t2-( << w)+][w]);
ma=max(ma,g[t1-( << w)+][j][w]);
printf("%d\n",ma-mi);
}
return ;
}
题目分析
“最大的”减去“最小的”，这不是一个区间求最值的RMQ问题吗？建一个线段树不就行了？再仔细一看，“n*n的矩阵”，Oh No，这明摆着是要你写一个树套树（矩形树）嘛! 由于此思路的代码非常“绞”，再加上时间不够，最后果断放弃去写第二题的暴力了。
下来后，经过两天的冥思苦想，我终于想出了“还算好写”的矩形树代码，将大矩阵分解成为多个边长为2的小正方形矩阵（即2^k*2^k）,在这些小矩阵中做一个RMQ问题求出最值，在随后的数据中，每输入一个矩形，就进行一次“分割为小矩形”的操作，直接比较求最值，交上去，令人感动的AC!
Time：2017-03-25