720test

Kurumi995 · 2019-07-22 11:10:47 · 个人记录

难得这次的题可以模拟水过而且t3算法还是前一天复习了很久的

【Disk】

Description

有 n 个盘子。盘子被生产出来后，被按照某种顺序摞在一起。初始盘堆中如果一个盘子比所有它上面的盘子都大，那么它是安全的，否则它是危险的。称初始盘堆为 A，另外有一个开始为空的盘堆 B。为了掩盖失误，生产商会对盘子序列做一些“处理”，每次进行以下操作中的一个：(1)将 A 最上面的盘子放到 B 最上面；(2)将 B 最上面的盘子给你。在得到所有 n 个盘子之后，你需要判断初始盘堆里是否有危险的盘子。

Input

接下来 n 个整数，第 i 个整数表示你收到的第 i 个盘子的大小。输入文件包含多组数据（不超过 10 组），每组数据的第一行为一个整数n。

Output

对于每组数据，如果不存在可能的方案使盘子安全，输出”J”，否则输出”Y”。

Sample Input

Sample Output

Y
J

数据范围

20%的数据保证 n<=8。

80%的数据保证 n<=1,000。

100%的数据保证 1<=n<=100,000，0<盘子大小<1,000,000,000 且互不相等。

解析

由于使盘子安全的方案一定是大盘在下小盘在上，所以可以用一个初始栈，让它是安全的，再用一个栈来模拟过程，如果可以满足拿到盘子的顺序，就说明可以是安全的。栈用法详解戳我www

Code

#include<bits/stdc++.h>
#define maxn 100000
using namespace std;
int n;
long long s[maxn+5],t[maxn+5];
stack<long long> a,b;
int main(){
    freopen("disk.in","r",stdin);
    freopen("disk.out","w",stdout);
    while(scanf("%d",&n)!=EOF){
        while(!a.empty())a.pop();
        while(!b.empty())b.pop();
        for(int i=1;i<=n;i++){
            scanf("%lld",&s[i]);
            t[i]=s[i];
        }
        sort(t+1,t+1+n);
        for(int i=n;i>=1;i--)a.push(t[i]);
        int k=1;
        bool ok=1;
        while(k<=n){
            while(b.empty() || b.top()!=s[k]){
                if(a.empty()){
                    ok=0;
                    break;
                }
                long long x=a.top();
                a.pop();
                b.push(x);
            }
            if(!ok)break;
            b.pop();
            k++;
        }
        if(!ok)printf("J\n");
        else if(ok)printf("Y\n");
    } 
    return 0;
}

【Car】

Description

在地图上散落着 n 个车轮，小 J 想用它们造一辆车。要求如下：

1. 一辆车需要四个车轮，且四个车轮构成一个正方形。

2. 车轮不能移动。

你需要计算有多少种造车的方案（两个方案不同当且仅当所用车轮不全相同，坐标相同的两个车轮视为不同车轮）。

Input

第一行一个整数 n。接下来 n 行，每行两个整数 x y，表示在(x,y)处有一个车轮。

Output

一行一个整数，表示方案数

Sample Input

Sample Output

数据范围

30%的数据保证 n ≤ 30。

100%的数据保证 1 ≤ n ≤ 1000; |x|, |y| < 20000。

解析

暴力拿30分是可以的嘻嘻嘻（我考试就是这么做的）。这道题可能要涉及一点点数学知识但是不要慌。我们可以考虑枚举一条对角线（即枚举两个顶点），然后用数学方法算出另外两个点，判断这两个点存不存在，具体可以用map或者hash一下。map用法详解戳我www。以下是做这道题必备数学技能：

已知正方形两个对角坐标 (xi,yi) , (xj,yj) ，求另外两个点的坐标。

对角线中点：((xi+xj)/2,(yi+yj)/2)，简记为(x0,y0)；

根据平面直角坐标系画图可知（自己动手画画吧我是不会发图的www）：

x1-x0=yj-y0 , y1-y0=x0-xj ;

x2-x0=yi-y0 , y2-y0=x0-xi ;

将x0,y0代入可得：

x1=(xi+xj+yj-yi)/2 , y1=(yi+yj+xi-xj)/2 ;

x2=(xi+xj-yj+yi)/2 , y2=(yi+yj-xi+xj)/2 ;

是不是超级简单！！！

Code

#include<bits/stdc++.h> 
#define maxn 20000
using namespace std;
int n;
long long cnt=0;
struct tyre{
    int x,y;
}t[maxn+5];
map<long long,int> p; 
int main(){
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);  
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&t[i].x,&t[i].y);
        p.insert(pair<long long,int>(t[i].x*maxn+t[i].y,1)); 
    }
    double x1,x2,y1,y2;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(t[i].x==t[j].x && t[i].y==t[j].y)continue;
            x1=(t[i].x+t[j].x+t[j].y-t[i].y)*1.0/2;
            y1=(t[i].y+t[j].y+t[i].x-t[j].x)*1.0/2;
            x2=(t[i].x+t[j].x-t[j].y+t[i].y)*1.0/2;
            y2=(t[i].y+t[j].y-t[i].x+t[j].x)*1.0/2;
            if(p[x1*maxn+y1]!=1 || p[x2*maxn+y2]!=1)continue;
            cnt++;
        }
    }
    printf("%lld\n",cnt/2);
    return 0;
}

【rollcall】

Description

在J班的体育课上，同学们常常会迟到几分钟，但体育老师的点名却一直很准时。老师只关心同学的身高，他会依次询问当前最高的身高，次高的身高，第三高的身高，等等。在询问的过程中，会不时地有人插进队伍里。你需要回答老师每次的询问。

Input

第一行两个整数 n m，表示先后有 n 个人进队，老师询问了 m 次。

第二行 n 个整数，第 i 个数 Ai 表示第 i 个进入队伍的同学的身高为 Ai。

第三行 m 个整数，第 j 个数 Bj 表示老师在第 Bj 个同学进入队伍后有一次询问。

Output

m 行，每行一个整数，依次表示老师每次询问的答案。数据保证合法。

Sample Input

7 4
9 7 2 8 14 1 8
1 2 6 6

Sample Output

数据范围

40%的数据保证 n ≤ 100。

100%的数据保证 1 ≤ m ≤ n ≤ 30000; 0 ≤ Ai < 2^32。

解析

一个标标准准漂漂亮亮可可爱爱精精致致的平衡树模板题。无旋Treap平衡树戳我www

但是据说这道题解法千变万化，可以用两个优先队列维护，甚至还有直接lowerbound并AC的dalao。

#include<bits/stdc++.h>
#define maxn 30000
using namespace std;
long long n,m,newp=0,root=0;
long long val[maxn+5];
long long siz[maxn+5],rnd[maxn+5],lc[maxn+5],rc[maxn+5]; 
long long a[maxn+5];
void upload(long long p){
    siz[p]=siz[lc[p]]+siz[rc[p]]+1;
}
long long newadd(long long v){
    newp++;
    siz[newp]=1;
    val[newp]=v;
    rnd[newp]=rand();
    return newp;
}
long long merge(long long x,long long y){
    if(!x || !y)return x+y;
    if(rnd[x]<rnd[y]){
        rc[x]=merge(rc[x],y);
        upload(x);
        return x;
    }
    else{
        lc[y]=merge(x,lc[y]);
        upload(y);
        return y;
    }
}
void split(long long p,long long k,long long &x,long long &y){
    if(!p){
        x=y=0;
        return ;
    }
    if(val[p]<=k){
        x=p;
        split(rc[p],k,rc[p],y);
    }
    else{
        y=p;
        split(lc[p],k,x,lc[p]);
    }
    upload(p);
}
void doInsert(long long v){
    long long x,y;
    split(root,v-1,x,y);
    root=merge(merge(x,newadd(v)),y);
} 
long long kth(long long p,long long k){
    if(siz[lc[p]]>=k)return kth(lc[p],k);
    if(siz[lc[p]]+1==k)return val[p];
    return kth(rc[p],k-(siz[lc[p]]+1));
}
int main(){
    freopen("rollcall.in","r",stdin);
    freopen("rollcall.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=n;i++){
        scanf("%lld",&a[i]);        
    }
    long long q,cnt=0,num=0;
    while(m--){
        num++;
        scanf("%lld",&q);
        while(q!=cnt){
            cnt++;
            doInsert(a[cnt]);
        }
        printf("%lld\n",kth(root,num));
    }
    return 0;
}