牛客算法周周练17题解(ABCDE)

A.生成树

思路：贪心。

一开始用写了个假算法，发现数据太弱了。
以第一棵树为基准，我们用记录每条边，规定，这样方便去重。

然后我们只需在第二课树找到第一棵树中不存在的边即可，因为第二棵树少的边和多的边数肯定相等的，不然边数和不可能为，所以根据贪心我们只需统计少的边即可，这样用就很方便了，此时的大小是：，是相重的个数，

我们需要的答案是，所以答案是：。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
set<PII>s;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(u>v) swap(u,v);
        s.insert(make_pair(u,v));
    }
    int ans=0;
    for(int i=1;i<n;i++){
         int u,v;
        scanf("%d%d",&u,&v);
       if(u>v) swap(u,v);
        s.insert(make_pair(u,v));
    }
    printf("%d\n",s.size()-(n-1));
    return 0;
}

B.七彩线段

思路：状态压缩。

看到最大只有，可以想到用一个数的二进制表示状态。

我们可以设前个线段为状态的最大长度。

当不用第个线段时，显然有状态转移：。

当用第个线段时，我们需要找到最后一个小于的线段，这一步可以排序后二分查找。

令找到的位置为。

令新状态：

然后求中的个数为个的最大值即可。

对于求二进制中的1可以递推求。

.

意思是删掉最右边的1.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int dp[N][130];
struct line{
    int l,r,c;
    bool operator<(const line&l)const{
        return r<l.r;
    }
}a[N];
int b[N],n,m,cnt[130];
void pre(int n){
    cnt[0]=0;
    for(int i=1;i<=n;i++) cnt[i]=cnt[i&(i-1)]+1;
}
int solve(){
    int ans=-1;
    memset(dp,-1,sizeof dp);
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<128;j++){
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
            int p=lower_bound(b+1,b+n+1,a[i].l)-b-1;
            if(~dp[p][j]){
            dp[i][j|(1<<(a[i].c-1))]=max(dp[i][j|(1<<(a[i].c-1))],dp[p][j]+a[i].r-a[i].l);
            //printf("dp[%d][%d]=%d\n",p,j,dp[p][j]);
            //printf("i=%d,j|x=%d\n",i,j|(1<<(a[i].c-1)));
            }
            if(cnt[j]==m) 
            ans=max(ans,dp[i][j]);
        }
    return ans; 
}
int main(){
    pre(128);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].c);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) b[i]=a[i].r;
    printf("%d\n",solve());
    return 0;
}

C.成绩分析

思路：签到题，对于平均值，我们只需将所有数求和，然后除以即可，对于中位数，我们需要特判一下，如果是奇数，我们直接取中间的一个数，如果是偶数，就取中间的两个数的平均值，最后再将中位数和平均数，求绝对值差即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int a[N];
int main(){
    int n,b=0;
    cin>>n;
    for(int i=0;i<n;i++){
       cin>>a[i];
       b+=a[i];
    }
    b/=n;
    int x;
    if(n&1) x=a[n/2];
    else x=(a[n/2-1]+a[n/2])/2;
    printf("%d\n",abs(b-x));
    return 0;
}

D.刺客信条

思路：优先队列。

考虑：以到达时间较短的方格优先进入队列，然后从起点开始，把起点丢入队列，开始跑一遍，因为我们是以时间较短优先，所以最先到达终点的就是用时最少的了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
char a[N][N];
int n,m,d[4][2]={0,1,0,-1,1,0,-1,0},vis[N][N],b[N][N];
int sx,sy,ex,ey;
struct node{
    int x,y,d;
    bool operator <(const node& no)const{
        return d>no.d;
    }
}now;
int bfs(int x,int y){
    priority_queue<node>q;
    q.push({x,y});
    vis[x][y]=1;
    while(!q.empty()){
         now=q.top();q.pop();
         //printf("(%d,%d)=%d\n",now.x,now.y,now.d);
         if(now.x==ex&&now.y==ey) return now.d;
         for(int i=0;i<4;i++){
              int nx=now.x+d[i][0],ny=now.y+d[i][1];
             if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]){
                  int h=now.d+b[nx][ny];
                  vis[nx][ny]=1;
                 q.push({nx,ny,h});
             }
         }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++){
           scanf("\n%c",&a[i][j]);
           if(a[i][j]=='S') sx=i,sy=j;
           else if(a[i][j]=='E') ex=i,ey=j;
           else if(a[i][j]=='A'||a[i][j]=='B'||a[i][j]=='C') b[i][j]=100;
           else b[i][j]=a[i][j]-'0';
       }
    printf("%d\n",bfs(sx,sy));
    return 0;
}

E.我不爱她

思路：。

才发现是多校里的题目，之前太菜了不会，发现只需要代码改动一下就行了。

还是一样，考虑预处理所有字符串的后缀，用存起来，然后每个字符串作为前缀时的贡献，因为要满足最长的后缀也即最长的前缀，所以对于较短的重复的前缀我们要删去一些贡献，比如。

对于来说，后缀的个数为，但是实际上只有第一个字符串能与其匹配。

所以中的要减去较长的出现的前缀，即的个数为。

所以的贡献实际上为个。

这一步可以用实现，因为中的数组就代表的最长前后缀的长度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=998244353;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define ull unsigned long long
#define IOS ios::sync_with_stdio(false),cin.tie(0)
string s[N];
int nt[N];
unordered_map<ull,int>mp;
int ans[N],base=233;
void kmp(string s){
    nt[0]=0;
    for(int i=1,j=0;i<s.size();i++){
        while(j&&s[i]!=s[j]) j=nt[j-1];
        if(s[i]==s[j]) j++;
        nt[i]=j;
    }     
}
void Hash(string s)    
{
    ull t=0,p=1;
    for(int i=s.size()-1;i>=0;i--){
        t+=p*(s[i]-'a'+1);
        p*=base;
        mp[t]++;
    }
}
int n;
int main(){
    IOS;
    int t;
    cin>>t;
    while(t--){
    cin>>n;
    mp.clear(),mst(ans);
    ll res=0;
    for(reg int i=0;i<n;i++)  cin>>s[i],Hash(s[i]);
    for(reg int i=0;i<n;i++){
        ull t=0;
        for(reg int j=0;j<s[i].size();j++){
            t=t*base+s[i][j]-'a'+1;
            ans[j]=mp[t];
        }
        kmp(s[i]);
        for(reg int j=0;j<s[i].size();j++){
             if(nt[j]) ans[nt[j]-1]-=ans[j];
        }
        for(reg int j=0;j<s[i].size();j++)
            res+=1LL*ans[j]*(j+1);
    }
    cout<<res<<endl; 
    }
    return 0;
}