Wannafly模拟赛4 A,B,D解题报告

A.LapTop

题目描述

FST是一名可怜的小朋友，他很强，但是经常fst，所以rating一直低迷。
但是重点在于，他非常适合ACM！并在最近的区域赛中获得了不错的成绩。
拿到奖金后FST决定买一台新笔记本，但是FST发现，在价格能承受的范围内，笔记本的内存和速度是不可兼得的。
可是，有一些笔记本是被另外一些“完虐”的，也就是内存和速度都不高于另外某一个笔记本，现在FST想统计一下有多少笔记本被“完虐”。

输入描述:

第一行一个正整数n，
表示笔记本的数量。接下来n行，每行两个正整数Mi，Si表示这款笔记本的内存和速度。
n≤105,Mi,Si≤109

输出描述:

一行，一个正整数，表示被完虐的笔记本数。

输入

4

100 700

200 500

50 100

300 400

输出

1

大致思路：

对于每一个笔记本都有两个值，先对于任意一个值进行排序。

然后建立线段树，统计区间另一个最大值。

然后从后往前扫，每次扫描当前位置到最后一个的区间之内有没有比另一个值大的，如果有ans++

代码：

#include<bits/stdc++.h>
using namespace std;
const int INF=1<<30;
const int maxn=1e5+7;
struct Node{
    int m,s;
}node[maxn];
int tree[maxn<<2];
void build(int l,int r,int k)
{
    //cout<<k<<endl;
    if(l>r)
        return ;
    if(l==r){
        tree[k]=node[l].s;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,k<<1);
    build(mid+1,r,k<<1|1);
    tree[k]=max(tree[k<<1],tree[k<<1|1]);
}
int query(int l,int r,int ql,int qr,int k)
{
    if(l>r||ql>r||qr<l)
        return -INF;
    if(ql<=l&&qr>=r)
        return tree[k];
    int mid=(l+r)>>1;
    return max(query(l,mid,ql,qr,k<<1),query(mid+1,r,ql,qr,k<<1|1));
}
bool cmp(Node a,Node b)
{
    return a.m<b.m;
}
int main()
{
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    memset(tree,0,sizeof(tree));
    int n,ans=0;
    cin>>n;
    for(int i=0;i<n;++i)
        cin>>node[i].m>>node[i].s;
    sort(node,node+n,cmp);
    build(0,n-1,1);
    for(int i=n-2;i>=0;--i){
        int x=query(0,n-1,i,n-1,1);//区间查询
        //cout<<x<<" "<<i<<endl;
        if(x>node[i].s)
            ans++;
    }
    cout<<ans<<endl;
    return 0;
}

B.Distance

题目描述

FST作为小朋友，经常会遇到和距离有关的问题，但是他已经厌倦了曼哈顿距离和欧几里德距离，所以FST就定义了一种FST距离。
这种距离并不用于空间或平面中，而运用于FST发明的一些神奇的算法中（唔... ...）。
设i号元素的特征值为Ai，则i和j的FST距离是 |i2 - j2|+|Ai2 - Aj2|。
为了实现某新的数据结构，FST想在一大堆元素中找出距离最大的一对元素，他不关心是哪一对元素，只想求出最大距离。

输入描述:
第一行，一个正整数n，为元素个数。
第二行，n个正整数Ai为这n个元素的特征值。

输出描述:
一行，一个正整数表示最大距离。long long请用lld

输入

2
4 3
输出

10
备注:

n≤1e5,Ai≤1e9

大致思路：

对于原式，很容易地分类讨论出两种情况，从而将绝对值号去掉

从而分别统计Ai^2+i^2的最大最小值和Ai^2-i^2的最大最小值

分别将最大最小值相减，取一个abs，再在两个情况中取一个max，就是答案

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
const long long INF=1e20;
struct Node{
    ll a,id;
    ll m1,m2;
}node[maxn];
int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.txt","r",stdin);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>node[i].a;
        node[i].id=i;
        node[i].m1=1ll*i*i+node[i].a*node[i].a;//记得乘1ll
        node[i].m2=1ll*i*i-node[i].a*node[i].a;
    }
    ll min1=INF,min2=INF,max1=-INF,max2=-INF;
    for(int i=1;i<=n;++i){
        max1=max(max1,node[i].m1);
        min1=min(min1,node[i].m1);
        max2=max(max2,node[i].m2);
        min2=min(min2,node[i].m2);
    }
    ll ans1=abs(max1-min1),ans2=abs(max2-min2);
    cout<<max(ans1,ans2)<<endl;
    return 0;
}

D.Fancy Signal Translate

题目描述

FST是一名可怜的小朋友，他很强，但是经常fst，所以rating一直低迷。
但是重点在于，他真的很强！他发明了一种奇特的加密方式，这种加密方式只有OIer才能破解。
这种加密方式是这样的：对于一个01串，他会构造另一个01串，使得原串是在新串中没有出现过的最短的串。
现在FST已经加密好了一个串，但是他的加密方式有些BUG，导致没出现过的最短的串不止一个，他感觉非常懊恼，所以他希望计算出没出现过的最短的串的长度。

输入描述:

一行，一个01串。长度≤105
输出描述:

一行，一个正整数，表示没有出现过的最短串的长度。
输入

100010110011101

输出

4

大致思路:

 因为字符串的长度最长不超过1e5，所以01串的长度时很小的，最多大概在13。

所以就可以以字符串的每一位开始，建立长度不超过13的字典树。

然后对于字典树进行BFS，找到第一个没有完整子节点的节点为止，答案就是那个节点的深度

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
typedef pair<int,int> pii;
struct Tree{
    struct Node{
        int next[2];
    }node[maxn<<2];
    int size;
    void init()
    {
        for(int i=0;i<maxn<<2;++i){
            memset(node[i].next,0,sizeof(node[i].next));
        }
        size=1;
    }
    void insert(char *s)
    {
        int now=0;
        for(int i=0;i<13;++i){
            if(s[i]=='')
                return ;
            int x=s[i]-'0';
            if(!node[now].next[x])
                node[now].next[x]=size++;
            now=node[now].next[x];
        }
    }
    int sear()
    {
        queue<pii> q;
        q.push(make_pair(0,1));
        while(!q.empty())
        {
            pii u=q.front();
            int x=u.first;
            int k=u.second;
            q.pop();
            for(int i=0;i<2;++i){
                if(node[x].next[i])
                    q.push(make_pair(node[x].next[i],k+1));
                else
                    return k;
            }
        }
        return 13;
    }
}Tree;
char str[maxn];
int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.txt","r",stdin);
    Tree.init();
    cin>>str;
    int len=strlen(str);
    for(int i=0;i<len;++i)
        Tree.insert(str+i);
    cout<<Tree.sear()<<endl;
    return 0;
}