2020牛客寒假算法基礎訓練營4題解

eg：題目難度感覺是升序的啊，又是一場七題（然後又沒打完，跑去和同學英雄聯盟了），沒想到I題隻是個小貪心，H題樹狀數組和J題确實不太會，簡單的記錄一下通過的前七道題，最後三道題如果補了的話會更新的。

A-歐幾裡得

題意：輾轉相除法進行了n次，求最小的a+b且a>b。

題解：随意觀察了一下，可以發現是個斐波那契數列從 0 , 1 , 2 , 3 , 5 , 8 … … 0,1,2,3,5,8…… 0,1,2,3,5,8……若n為0則是0+1，若n為1則是1+2，類推。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
ll f[100];
int main(){
    f[0]=0;f[1]=1;f[2]=2;
    for(int i=3;i<=81;i++)f[i]=f[i-1]+f[i-2];
    int T;
    scanf("%d",&T);
    while(T--){
        int i;
        scanf("%d",&i);
        printf("%lld\n",f[i]+f[i+1]);
    }
    return 0;
}

B-括号序列

題意：括号序列判斷是否合法。

題解：棧的基礎應用，似乎會爆系統棧（或者我系統棧寫萎了）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
char s[maxn];
char q[maxn];
int cnt;
int main(){
    scanf("%s",&s);
    int len=strlen(s),flag=0;
    for(int i=0;i<len;i++){
        if(s[i]=='(' || s[i]=='[' || s[i]=='{')q[++cnt]=s[i];
        else{
            if(s[i]==')'){
                if(q[cnt]=='(')cnt--;
                else flag=1;
            }
            if(s[i]==']'){
                if(q[cnt]=='[')cnt--;
                else flag=1;
            }
            if(s[i]=='}'){
                if(q[cnt]=='{')cnt--;
                else flag=1;
            }
        }
    }
    if(cnt!=0)flag=1;
    if(!flag)puts("Yes");
    else puts("No");
    return 0;
}

C-子段乘積

題意：長度為n的數組，求連續k個數的乘積的最大值。

題解：線段樹維護區間乘法。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
const int mod=998244353;
const int INF=0x3f3f3f3f;
ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int n,k,a[maxn];
ll s[maxn*4];
void pushup(int node){
    s[node]=s[node<<1]*s[node<<1|1]%mod;
}
void build(int node,int l,int r){
    if(l==r){
        s[node]=1ll*a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    pushup(node);
}
ll query(int L,int R,int l,int r,int node){
    if(L<=l && r<=R)return s[node];
    int mid=(l+r)>>1;
    ll ans=1;
    if(L<=mid)ans=ans*query(L,R,l,mid,node<<1)%mod;
    if(R>mid)ans=ans*query(L,R,mid+1,r,node<<1|1)%mod;
    return ans;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    int l=1,r=k;
    ll ans=0;
    while(r<=n){
        ans=max(ans,query(l,r,1,n,1));
        l++;r++;
    }
    printf("%lld\n",ans);
    return 0;
}

D-子段異或

題意：長度為n的數組，求區間異或和為0的數量。

題解：維護區間字首異或和，如果兩個異或和的值相等說明這個區間異或和為0。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
const int mod=998244353;
const int INF=0x3f3f3f3f;
ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int n,a[maxn],f[maxn];
map<int,int>mmap;
ll ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)f[i]=f[i-1]^a[i];
    for(int i=0;i<=n;i++)
        ans+=1ll*mmap[f[i]],mmap[f[i]]++;
    printf("%lld\n",ans);
    return 0;
}

E-最小表達式

題意：給出若幹個1～9還有+号，問如何排列組合使得可以排列出一個合法的加法算式且結果最小。

題解：貪心，盡可能均勻配置設定數字即可。注意需要用到高精度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int a[11],k,num;
char s[maxn];
string A[maxn],ans,v;
string add(string a,string b){
    v.clear();
    int tmp=0,t=0;
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    while(a.size()!=b.size()){
        if(a.size()>b.size())b.push_back('0');
        else a.push_back('0');
    }
    for(int i=0;i<a.size();i++){
        tmp=a[i]+b[i]-'0'*2+t;
        t=tmp/10;
        v.push_back(tmp%10+'0');
    }
    if(t>0)v.push_back(t+'0');
    reverse(v.begin(),v.end());
    return v;
}
int main(){
    scanf("%s",&s);
    int len=strlen(s);
    for(int i=0;i<len;i++)
        if(s[i]=='+')k++;
        else a[s[i]-'0']++,num++;
    if(k==0){
        sort(s,s+len);
        printf("%s\n",s);
    }
    else{
        int l=1;
        for(int i=1;i<=9;i++){
            for(int j=1;j<=a[i];j++){
                A[l].push_back(i+'0');
                l++;
                if(l>k+1)l=1;
            }
        }
        for(int i=1;i<=k+1;i++)
            ans=add(A[i],ans);
        cout<<ans<<endl;
    }
    return 0;
}

F-樹上博弈

題意：給出一棵樹，每次隻能選擇朝葉子結點或者父親結點移動，如果不能移動則對方獲勝。問先手獲勝的雙方起始狀态數量。

題解：觀察到，如果雙方距離為偶數時先手必勝。那麼轉換成樹上求距離為偶數的點對。樹上dp入門題。考慮 d p [ u ] [ 0 ] dp[u][0] dp[u][0]為到u結點的偶數結點數， d p [ u ] [ 1 ] dp[u][1] dp[u][1]為到u結點的奇數結點數，周遊這棵樹，to表示可到達的結點，每個結點的答案就是 d p [ u ] [ 0 ] ∗ d p [ t o ] [ 1 ] + d p [ u ] [ 1 ] ∗ d p [ t o ] [ 0 ] dp[u][0]*dp[to][1]+d p[u][1]*dp[to][0] dp[u][0]∗dp[to][1]+dp[u][1]∗dp[to][0]，每次還需要更新 d p [ u ] [ 0 ] dp[u][0] dp[u][0]和 d p [ u ] [ 1 ] dp[u][1] dp[u][1]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int n;
ll dp[maxn][2],ans;
vector<int>G[maxn];
inline void dfs(int u,int fa){
    dp[u][0]=1ll;dp[u][1]=0ll;
    for(int i=0;i<G[u].size();i++){
        int to=G[u][i];
        if(to==fa)continue;
        dfs(to,u);
        ans+=dp[u][0]*dp[to][1];
        ans+=dp[u][1]*dp[to][0];
        dp[u][0]+=dp[to][1];
        dp[u][1]+=dp[to][0];
    }
}
int main(){
    n=read();
    for(int i=2;i<=n;i++){
        int x;
        x=read();
        G[x].push_back(i);
        G[i].push_back(x);
    }
    ans=0;
    dfs(1,-1);
    printf("%lld\n",ans*2ll);
    return 0;
}

G-音樂鑒賞

題意：不怎麼好說，看題了解吧。

題解：二分答案，二分這個期末占比。check僅需保證每個人的平均分乘上平均分占比加上81*期末占比大于90即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int n;
double ans,a[maxn];
bool check(double x){
    if(ans*(1.0-x)+81*x>90)return true;
    else return false;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf",&a[i]),ans+=a[i];
    ans/=n;
    double l=0.0,r=1.0,mid,f;
    while(fabs(l-r)>=eps){
        mid=(l+r)/2;
        if(check(mid))l=mid,f=l;
        else r=mid;
    }
    f*=100;
    printf("%.2lf%%\n",f);
    return 0;
}

剛剛補了道I題前來更新

I-比對星星

題意：給出了n個星星，每個星星有橫縱坐标還有一個價值z，如果 x i < x j , y i < y j , z i < z j x_i<x_j ,y_i<y_j,z_i<z_j xi<xj,yi<yj,zi<zj那麼就能比對，要盡可能多的比對。求數量。

題解：z的取值是0和1，是以題目就成了一道水題。先按照x坐标排序如果z為0就加入待比對序列，為1就開始比對，找到一個滿足題意的盡可能大的y即可。用muliset維護（STL大出彩）。

#include "stdio.h"
#include "string.h"
#include "iostream"
#include "algorithm"
#include "stack"
#include "set"
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const ll mod=1e9+7;
const int INF=0x3f3f3f3f;
int n,ans;
struct arr{
    int x,y,z;
}p[maxn];
multiset<int>s;
multiset<int>::iterator it;
bool cmp(arr a,arr b){
    return a.x<b.x;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
    sort(p+1,p+1+n,cmp);
    for(int i=1;i<=n;i++){
        if(p[i].z==0)s.insert(p[i].y);
        else{
            it=s.lower_bound(p[i].y);
            if(it!=s.begin()){
                it--;
                s.erase(it);ans++;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

2020牛客寒假算法基礎訓練營4題解

A-歐幾裡得

B-括号序列

C-子段乘積

D-子段異或

E-最小表達式

F-樹上博弈

G-音樂鑒賞

I-比對星星

繼續閱讀

HDU Reorder the Books

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

hdu 4741 Save Labman No.004（計算幾何） Save Labman No.004

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希