A

分析

统计前缀个数,一想到字符串的前缀,我们就应该想到字典树,这个和字典一样的前缀树.
这道题目是字典树模板的略微改动,我们发现这道题目和一般字典树的查询不一样,字典树一般查询是看这个字符串是否出现,而这道题目这是统计这个字符串出现的次数.

AC代码

#include<iostream>
using namespace std;
const int N=1000010;
int n,m,idx;
int son[N][26],cnt[N];
char str[N];
// 插入一个字符串
void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query()
{
    int p = 0,res=0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) break;
        p = son[p][u];
        res+=cnt[p];
    }
    return res;
}

int main()
{
   
    cin>>n>>m;
    while(n--)
    {
        cin>>str;
        insert();
    }
    while(m--)
    {
        cin>>str;
        cout<<query()<<endl;
    }
return 0;
    
}

C

分析

对字符串S自己匹配求出next数组,然后根据定义,对于每一个i,s[i-next[i]+1~i]与s[1~next[i]]是相等的,而且不存在更大的next值满足条件.具体证明可以看李煜东金牌爷的<<算法竞赛进阶指南>>
既然如此的话,那么我们发现当i-next[i]能够整除i时候,那么s[1~i-next[i]]就是s[i-1]的最小循环元,至于次数那么也就是i/(i-next[i]).

AC代码

#include<iostream>
using namespace std;
const int N=1e6+10;
int ne[N],n,m,i,j,len,cnt;
char a[N];
void calc_ne()
{
    ne[1]=0;
    for(int i=2,j=0;i<=n;i++)
    {
        while(j>0 && a[i]!=a[j+1])
            j=ne[j];
        if (a[j+1]==a[i])
            j++;
        ne[i]=j;
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF && n)
    {
        cin>>(a+1);//读到下标从一开始的位置
        printf("Test case #%d\n",++cnt);
        calc_ne();
        for(int i=2;i<=n;i++)
            if (i%(i-ne[i])==0 && i/(i-ne[i])>1)
                printf("%d %d\n",i,i/(i-ne[i]));
        puts("");
    }
return 0;
}

 

D

分析

我们发现这道题目,要求我们算出哈夫曼编码,也就是最短不重叠前缀的编码,那么我们就可以用上trie字典树的性质配合哈夫曼树进行处理.
哈夫曼树,就是满足权值*路径长度最短的树,因此我们这道题目直接可以开哈夫曼树处理即可,代码很清晰.

AC代码

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define pll pair<long long,long long>
const int N=101000;
long long n,m,i,j,k,ans,x;
priority_queue<pll,vector<pll>,greater<pll> > p;
int main()
{
    cin.tie(0);
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        p.push(make_pair(x,0));
    }
    while((p.size()-1)%(k-1)!=0) 
        p.push(pll(0,0));
    while(p.size()>=k)
    {
        long long deep=-1,temp=0;
        for(j=1;j<=k;j++)
        {
            pll dx=p.top();
            p.pop();
            temp+=dx.first;
            deep=max(deep,dx.second);
        }
        p.push(make_pair(temp,deep+1));
        ans+=temp;
    }
    cout<<ans<<endl<<p.top().second;
    return 0;
}

 

E

分析

经典哈夫曼树的模型，每次合并重量最小的两堆果子即可。使用小根堆维护所有果子，每次弹出堆顶的两堆果子，并将其合并，合并之后将两堆重量之和再次插入小根堆中。

AC代码

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int main()
{
    int n;  
    cin>>n;
    priority_queue<int ,vector<int>,greater<int>>heap;//小根堆
    while(n--)
    {
        int x;
        cin>>x;
        heap.push(x);
    }
    int res=0;
    while(heap.size()>1)
    {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);
        
    }
    cout<<res<<endl;
    
return 0;
}

 

F

分析

首先我们观察这道题目其实和之前的E题Largest Rectangle in a Histogram,十分相似,但是之前这道题的水平面是已经确定好了,

那么这道题目是不是也可以这么做呢?我们可以枚举水平面,看每一个平面上的最大值即可.

AC代码

#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int s[N][N],l[N],r[N];   
int q[N];                  
int work(int h[])          
{
    h[0]=h[m+1]=-1;     
    int tt=0;             
    q[0]=0;
    for (int i=1;i<=m;i++)
    {
        while(h[q[tt]]>=h[i]) tt--;
        l[i]=q[tt];    
        q[++tt]=i;  
    }
    tt=0;
    q[0]=m+1;
    for(int i=m;i;i--)
    {
        while(h[q[tt]]>=h[i]) tt--;
        r[i]=q[tt];
        q[++tt]=i;
    }

    int res=0;
    for(int i=1;i<=m;i++)
        res=max(res,h[i]*(r[i]-l[i]-1));

    return res;
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            char c;
            cin>>c;
            if(c=='F') s[i][j]=s[i-1][j]+1;        
        }

    int res=0;
    for(int i=1;i<=n;i++) res=max(res,work(s[i]));

    cout<<res*3<<endl;

    return 0;
}

 

G

分析

Trie数组相关应用：
1.每次先把号码一个一个存进str数组，每个数字位都++
2.判断如果一个号码每一位出现次数均大于1，说明其为前缀，输出”NO”

AC代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    string s[100005];
    char p[12];
    int t,flag=0,n,i,j;
    cin>>t;
    while(t--)
    {
        flag=0;
        cin>>n;
        for(int i=0;i<n;i++)
        {
           cin>>p;
           s[i]=p;
        }
        sort(s,s+n);
        for(int i=1;i<n;i++)
        {
            if(s[i].size()>=s[i-1].size())
            {
                for(j=0;j<s[i-1].size();j++)
                   if(s[i][j]!=s[i-1][j])   break;
                      
                 if(j>=s[i-1].size())
                      flag=1; 
            }
        }
        if(flag) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;

}

 H

分析

向这样的动态求第k小的值，并且k的变化要么+1 要么-1 要么不变的话，就可以用对顶堆数据结构。

当加入一个数x的话判断如果大根堆为空或者x >= 小根堆堆顶的话直接加入小根堆中
反之加入到大根堆中，并且把大根堆堆顶的数添加到小根堆中，并把大根堆堆顶删除
当来到一次get操作

AC代码

#include<iostream>
#include<queue>
using namespace std;
const int N=3e4+10;
priority_queue<int> q;
priority_queue<int, vector<int> ,greater<int> > q2;
int num[N],n,m,x;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>num[i];
    int k=1;
    for(int i=1;i<=m;i++)
    {
        cin>>x;
        while(k<=x)
        {
            q2.push(num[k]);
            if(!q.empty()&&q.top()>q2.top())
            {
                int t=q.top();
                q.pop();
                q2.push(t);
                t=q2.top();
                q2.pop();
                q.push(t);
            }
            k++;
        }
        cout<<q2.top()<<endl;
        int t=q2.top();
        q2.pop();
        q.push(t);
    }
    return 0;
}