NFLS-DAY 1

Posted on By 张, 高畅

T0

非常开心和DALAO们一起来集训
就是这个难度……
而且今天遇见了一点点账号密码上的问题，不过问题不大，改变不了的事实

T1

[1000/1000/1000]

高桥决定将 N 个饼干尽可能平均地分配给 K 个用户。 分发所有饼干后，找到用户收到的最大数量的饼干和用户收到的最小数量的饼干之间的最小可能差（绝对） 

#include
using namespace std;
int n,k;
int main()
{
    scanf("%d%d",&n,&k);
    if(!(n%k))printf("0");
    else printf("1");
    return 0;
}

T2

[1200/1200/1200]

小C开始学音乐了!给他一串音符,帮他找到这串音符是C大调还是A小调!
判断方法如下:主音”A”,”D”,”E”属于A小调;主音”C”,”F”,”G”属于C大调.
一串音符有许多小节,用”|”分割,每一小节的第一个字符就代表这一小节的主音,整首曲子的是C,A的哪种就取决于主音属于A小调的多,还是属于C大调的多,如果相等,就看最后一个音符保证最后一个音是”A”或者”C” 

#include
using namespace std;
const int N=105;
int n,A,C;
char s[N];
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    s[0]='|';
    for(int i=0;i<n;i++)
    {
        if(s[i]=='|')
        {
            if(s[i+1]=='A'||s[i+1]=='D'||s[i+1]=='E')A++;
            if(s[i+1]=='C'||s[i+1]=='F'||s[i+1]=='G')C++;
        }
    }
    if(A==C)printf((s[n]=='A')?"A-mol":"C-dur");
    else printf(A<C?"C-dur":"A-mol");
    return 0;
}

T3

[1400/1400/1400]

现在有一个数字按钮界面,按按钮时规定手指只能往右或往下或不动(例如只能按180,49,44,但不能按到98或132等等数字).给定一个整数k,求出能按到的最接近k的数字和k的差值是多少

毫无疑问，在这个数±10以内，一定会有数满足此要求，故直接暴力枚举

#include
using namespace std;
int n,GT[15][15];
int check(int x)
{
    vectorV;
    while(x)
    {
        V.push_back(x%10);
        x/=10;
    }
    reverse(V.begin(),V.end());
    if(V.size()==1)return 1;
    for(int i=0;i<V.size()-1;i++)
    {
        if(!GT[V[i]][V[i+1]])return 0;
    }
    return 1;
}
void work()
{
    scanf("%d",&n);
    for(int d=0;d<=10;d++)
    {
        if(check(n+d)||check(n-d))
        {
            printf("%d\n",d);
            return;
        }
    }
}
int main()
{
    GT[0][0]=1;
    GT[1][0]=GT[1][1]=GT[1][2]=GT[1][3]=GT[1][4]=GT[1][5]=GT[1][6]=GT[1][7]=GT[1][8]=GT[1][9]=1;
    GT[2][0]=GT[2][2]=GT[2][3]=GT[2][5]=GT[2][6]=GT[2][8]=GT[2][9]=1;
    GT[3][3]=GT[3][6]=GT[3][9]=1;
    GT[4][0]=GT[4][4]=GT[4][5]=GT[4][6]=GT[4][7]=GT[4][8]=GT[4][9]=1;
    GT[5][0]=GT[5][5]=GT[5][6]=GT[5][8]=GT[5][9]=1;
    GT[6][6]=GT[6][9]=1;
    GT[7][0]=GT[7][7]=GT[7][8]=GT[7][9]=1;
    GT[8][0]=GT[8][8]=GT[8][9]=1;
    GT[9][9]=1;
    int T;
    scanf("%d",&T);
    while(T--)work();
    return 0;
}

T4

[1530/1700/1700]

有长度为N的数列{A1,A2,…,AN}，这N个数字恰好是1…N的排列。你需要统计有多少个子系列{Ai,Ai+1,…,Aj},满足：i≤j且j-i+1为奇数，序列中位数是B。

这题似乎简单，但需要一些优化。
我们知道，中位数为B，意味着选出集合中，小于B的和大于B的个数是相等的，因此，我们可以重新写出一个数字，大于B的记为1，小于B的记为-1，然后从B的位置开始，分别向两端做前缀/后缀和，将一边结果存入map，并在另一边做加和时判断是否另一边有加和与其是相反数，是则计入答案。
因此，此题时间复杂度O(n log n)，使用unordered_map可获得O(n)的复杂度（当然HASH表初始化也需要时间，不过一般在询问较多的情况下可以忽略不计）

#include
using namespace std;
const int N=100005;
int n,m,pos,res,a[N],s[N];
unordered_mapmp;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;im)a[i]=1;
        else if(a[i]==m)
        {
            a[i]=0;
            pos=i;
        }
        else a[i]=-1;
    }
    for(int i=pos;i;i--)
    {
        if(i<pos)s[i]=s[i+1]+a[i];
        mp[s[i]]++;
    }
    for(int i=pos;ipos)s[i]=s[i-1]+a[i];
        res+=mp[-s[i]];
    }
    printf("%d",res);
    return 0;
}

T5

[1330/1900/1900]

如果一个序列，它的任意两个相邻的元素之差都不超过K，那么这个序列就被称作完美序列。
一个序列的子序列，就是从这个序列中，按照从前往后的顺序，取出任意多个数字（不一定连续）组成的新序列。
一个序列的完美子序列，就是从这个序列中取出一个子序列，且这个子序列是完美序列。
给定一个序列，求这个序列的最长完美子序列。

我好不容易学的DP，你却让我输的这么彻底？？？
毫无疑问，这题与LIS(最长上升子序列)非常的像，因此我们有了如下(1330pts)的代码

#include
using namespace std;
const int N=200005;
int n,k,a[N],f[N],res;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f[i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(abs(a[i]-a[j])<=k)f[i]=max(f[i],f[j]+1);
        }
    }
    for(int i=1;i<=n;i++)res=max(res,f[i]);
    printf("%d",res);
    return 0;
}

非常的简短，非常的有力，非常的好写（bushi
但显然作为T5，出题人肯定要给你一些花活，比如说，数据结构优化。
在LIS里，我们知道，采用的是单调队列优化
但是在这里，我们采用线段树优化，（有写动态开点的）。

#include
using namespace std;
const int N=200005;
int n,k,a[N],b[N],res,tr[N<<2],dp[N];
void pushup(int u){tr[u]=max(tr[u<<1],tr[u1;
    if(y<=mid)update(u<<1,l,mid,x,y);
    else update(u<<1|1,mid+1,r,x,y);
    pushup(u);
}
int query(int u,int l,int r,int L,int R)
{
    if(L1,sum=0;
    if(L<=mid)sum=max(sum,query(u<<1,l,mid,L,R));
    if(mid<R)sum=max(sum,query(u<<1|1,mid+1,r,L,R));
    return sum;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
    {
        int pos1=lower_bound(b+1,b+n+1,a[i]-k)-b;
        int pos2=lower_bound(b+1,b+n+1,a[i])-b;
        int pos3=upper_bound(b+1,b+n+1,a[i]+k)-b-1; 
        dp[i]=query(1,1,n,pos1,pos3)+1;
        update(1,1,n,dp[i],pos2);
        res=max(res,dp[i]); 
    }
    printf("%d",res);
    return 0;
}

T6

[210/2100/2100]

在仓库里有很多商品，你需要检索某一个商品出现的次数

这题考场想到了Trie树，不过因为实现以及细节的原因最后还是选择了暴力。
由于我们查找的东西可能出现在任意位置，而Trie树只能寻找前缀，因此，我们考虑将每一个串的后缀都加入至Trie中，但显然，这样在统计的时候，会重复计数，因此，我们采用类似时间戳一样的设计，如果在一个时间戳内的字串，就不进行计数。
(值得一提的是，Trie树调了快一个半小时，不愧是你Trie树)

#include
using namespace std;
const int N=200005;
struct node
{
    int cnt,val,ne[30];
}tr[N];
int n,m,root,idx=0;
void insert(char *s,int timestamp)
{
    int p=root;
    if(!p)
    {
        p=++idx;
        root=p;
    } 
    for(int i=0;s[i];i++)
    {
        int ch=s[i]-'a';
        if(!tr[p].ne[ch])tr[p].ne[ch]=++idx;
        p=tr[p].ne[ch];
        if(tr[p].val!=timestamp)
        {
            tr[p].val=timestamp;
            tr[p].cnt++;
        }
    }
}
int query(char *s)
{
    int p=root,res=0;
    if(!p)return 0;
    for(int i=0;s[i];i++)
    {
        int ch=s[i]-'a';
        if(!tr[p].ne[ch])return 0;
        p=tr[p].ne[ch];
        res=tr[p].cnt;
    }
    return res;
}
char s[N];
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",s);
        for(int i=0;i<strlen(s);i++)insert(s+i,n+1);
    }
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",s);
        printf("%d\n",query(s));
    }
    return 0;
}

T7

[576/2400/2400]
终于过了，调了一个晚上+一个中午
很难说这题的难度，但是思维量确实也比较大
考虑正解：若枚举Ai是等差数列的中间的数，则说明，Ai-d与Ai+d分布在Ai的异侧
因此，若Ai不是中间数，则证明，Ai-d,Ai+d都在Ai左侧
但是我们需要能够快速判断此事的工具，而这个工具就是——hash
有了hash还不够，我们考虑线段树优化整个过程，让取出与查找hash值都是log(n)的。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+5;
const LL base=131LL,mod=1LL*(1e9+7);
int n,a[N];
LL power[N];
struct segment_tree
{

    int tr[N<<2][2];
    inline int lson(int u){return u<<1;}
    inline int rson(int u){return u<<1|1;}  
    void update(int u,int l,int r,int x)
    {
        if(l==r)
        {
            tr[u][0]=tr[u][1]=1;
            return;
        }
        int mid=l+r>>1;
        if(x<=mid)update(lson(u),l,mid,x);
        else update(rson(u),mid+1,r,x);
        tr[u][0]=((LL)tr[lson(u)][0]*(LL)power[r-mid]%mod+(LL)tr[rson(u)][0])%mod;
        tr[u][1]=((LL)tr[rson(u)][1]*(LL)power[mid-l+1]%mod+(LL)tr[lson(u)][1])%mod;
    }
    int query(int u,int l,int r,int L,int R,int x)
    {
        if(L<=l&&r<=R)return tr[u][x];
        int mid=l+r>>1;
        if(L<=mid&&mid<R)
        {
            int lres=query(lson(u),l,mid,L,R,x),rres=query(rson(u),mid+1,r,L,R,x);
            int posl=max(L,l),posr=min(R,r);
            if(!x)return ((LL)lres*(LL)power[posr-mid]%mod+(LL)rres)%mod;
            else return((LL)rres*(LL)power[mid-posl+1]%mod+(LL)lres)%mod;
        }
        else if(L<=mid)return query(lson(u),l,mid,L,R,x)%mod;
        else return query(rson(u),mid+1,r,L,R,x)%mod;
    }
}tree;
void work()
{
    scanf("%d",&n);
    memset(tree.tr,0,sizeof tree.tr);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        int len=min(a[i]-1,n-a[i]);
        int lres=!len?-1:tree.query(1,1,n,a[i]-len,a[i]-1,0); 
        int rres=!len?-1:tree.query(1,1,n,a[i]+1,a[i]+len,1);
        tree.update(1,1,n,a[i]);
        if(lres!=rres)
        {
            puts("Y");
            return;
        }
    }
    puts("N");
}
int main()
{
    power[0]=1;
    for(int i=1;i<N;i++)power[i]=(LL)power[i-1]*base%mod;
    int T;
    scanf("%d",&T);
    while(T--)work();
    return 0;
}
训练日志