2021牛客寒假演算法基礎集訓營3

A：模數的世界

B：內卷

C：重力墜擊（列舉）

??題目大意是給定 n ( 1 ≤ n ≤ 10 ) n(1\le n\le 10) n(1≤n≤10)個敵人的坐標 ( 0 ≤ ∣ x i ∣ , ∣ y i ∣ ≤ 7 ) (0\le|x_i|,|y_i|\le7) (0≤∣xi?∣,∣yi?∣≤7)，每個敵人都有一個被消滅的范圍 r i ( 1 ≤ r i ≤ 7 ) r_i(1\le r_i\le7) ri?(1≤ri?≤7)；然后給定攻擊者的攻擊范圍 R ( 1 ≤ R ≤ 7 ) R(1\le R \le7) R(1≤R≤7)以及攻擊輪數 k ( 1 ≤ k ≤ 3 ) k(1\le k\le3) k(1≤k≤3)，要求確定攻擊者的坐標位置（必須是整數），問消滅最多的敵人數，
??坐標范圍很小，很明顯考慮列舉，因為每一次的列舉數到了 15 ? 15 = 225 15*15=225 15?15=225，所以不適合用0/1位列舉，直接DFS即可，血淚教訓：不要用sqrt()函式太多次，庫函式速度慢，會導致TLE，

#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
struct Enermy{
    int x,y,r;
}e[15];
int n,k,R,maxnum=0;
int vis[15],mp[20][20],dx[5],dy[5];
inline int Distance(int x1,int y1,int x2,int y2){return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}
inline void cal()
{
    int ans=0;
    for(int i=1;i<=n;++i) vis[i]=0;
    for(int num=1;num<=k;++num)
        for(int i=1;i<=n;++i)
        {
            if(vis[i] || Distance(dx[num],dy[num],e[i].x,e[i].y)>(R+e[i].r)*(R+e[i].r)) continue;
            else vis[i]=1,ans++;
        }
    if(ans>maxnum) maxnum=ans;
}
inline void DFS(int deep)
{
    if(deep>k) {cal();return;}
    else{
        for(int i=-7;i<=7;++i)
            for(int j=-7;j<=7;++j)
                if(mp[i+7][j+7]==0){
                    mp[i+7][j+7]=1;dx[deep]=i,dy[deep]=j;
                    DFS(deep+1);
                    mp[i+7][j+7]=0;
                }
    }
}
int main()
{
    scanf("%d%d%d",&n,&k,&R);
    for(int i=1;i<=n;++i) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].r);
    DFS(1);
    printf("%d",maxnum);
}

D：Happy New Year！（C語言入門題）

#include<bits/stdc++.h>
using namespace std;
int get_num(int x)
{
    int ans=0;
    while(x) ans+=x%10,x/=10;
    return ans;
}
int main()
{
    int n,cur_sum,next,next_sum;cin>>n;
    cur_sum=get_num(n);next=n+1;
    while(1)
    {
        next_sum=get_num(next);
        if(next_sum==cur_sum) {cout<<next;break;}
        next++;
    }
}

E：買禮物（鏈表，線段樹）

??題目大意是 n n n個箱子放了 n n n個禮物，有兩種操作：①從第 i i i個箱子中取出禮物；②詢問 [ x , y ] [x,y] [x,y]中是否有兩個相同種類的禮物，
??很明顯的單點修改和區間查詢的問題，但關鍵問題是如何做到區間查詢得到是否有不同種類的禮物，這里是首先采用鏈表的思想，用 l a s t [ i ] last[i] last[i]表示和第 i i i個禮物種類相同的上一個禮物的位置（沒有則為0）， n e x [ i ] nex[i] nex[i]表示和第 i i i個禮物種類相同的下一個禮物的位置（沒有則為INF），然后一個禮物的取走，就相當于鏈表的洗掉操作： l a s t [ n e x [ i ] ] = l a s t [ i ] , n e x [ l a s t [ i ] ] = n e x [ i ] last[nex[i]]=last[i],nex[last[i]]=nex[i] last[nex[i]]=last[i],nex[last[i]]=nex[i]，我們用 n e x [ ] nex[] nex[]陣列建立線段樹（區間最小值），很明顯一個區間的最小值如果小于區間右端點，就說明存在兩個種類相同的禮物，

#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
const int maxn=5e5+100;
const int INF=0x3f3f3f3f;
vector<int> v[maxn*2];
int n,q,a[maxn],last[maxn],nex[maxn],tree[maxn*4];
void build(int l=1,int r=n,int p=1)
{
    if(l==r) tree[p]=nex[l];
    else{
        int mid=(l+r)/2;
        build(l,mid,p*2);build(mid+1,r,p*2+1);
        tree[p]=min(tree[p*2],tree[p*2+1]);
    }
}
void update(int l,int r,int num,int cl=1,int cr=n,int p=1)
{
    if(cr<l || cl>r) return;
    if(cl==cr) tree[p]=num;
    else{
        int mid=(cl+cr)/2;
        update(l,r,num,cl,mid,p*2);
        update(l,r,num,mid+1,cr,p*2+1);
        tree[p]=min(tree[p*2],tree[p*2+1]);
    }
}
int query(int l,int r,int cl=1,int cr=n,int p=1)
{
    if(cr<l || cl>r) return INF;
    if(cl>=l && cr<=r) return tree[p];
    else{
        int mid=(cl+cr)/2;
        return min(query(l,r,cl,mid,p*2),query(l,r,mid+1,cr,p*2+1));
    }
}
int main()
{
    close;cin>>n>>q;
    for(int i=1;i<=1e6;++i) v[i].push_back(0);
    for(int i=1;i<=n;++i) cin>>a[i],v[a[i]].push_back(i);
    for(int i=1;i<=1e6;++i)
    {
        int size=v[i].size();
        if(size==1) continue;
        v[i].push_back(INF);
        for(int j=1;j<size;++j) last[v[i][j]]=v[i][j-1],nex[v[i][j]]=v[i][j+1];
    }
    build();
    while(q--)
    {
        int op;cin>>op;
        if(op==1){
            int pos;cin>>pos;
            if(nex[pos]!=INF) last[nex[pos]]=last[pos];//注意這個地方要特判，否則會造成越界
            nex[last[pos]]=nex[pos];
            update(pos,pos,INF);
            update(last[pos],last[pos],nex[pos]);
            last[pos]=0;nex[pos]=INF;
        }
        else{
            int x,y;cin>>x>>y;
            if(query(x,y)<=y) cout<<"1\n";
            else cout<<"0\n";
        }
    }
}

F：匹配串（思維）

??題目大意是給定 n n n個匹配串，僅由小寫字母或者’#‘組成，’#‘代表能夠匹配任意長度的序列，同時保證了每個匹配串中至少含有一個’#’，問能不能找到字串和這 n n n個匹配串都匹配，如果不能則輸出0，有無窮多個則輸出-1，否則輸出個數，
??簡單的貪心題，只要每個匹配串的第一個’#‘前的前綴串和最后一個’#'后的后綴串能夠能夠匹配（不一定長度一樣，但是沒有出現不一致），就能夠構造出無窮多個，否則輸出-1.

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+100;
string s[maxn],before="",after="";bool ok=true;
void solve(int n)
{
    for(int i=0;i<s[1].length();++i) {if(s[1][i]!='#') before+=s[1][i];else break;}
    for(int i=s[1].length()-1;i>=0;--i){if(s[1][i]!='#') after+=s[1][i];else break;}
    int lenb=before.length(),lena=after.length();
    for(int i=2;i<=n;++i)
    {
        int p=0;
        for(int j=0;j<s[i].length();++j)
        {
            if(s[i][j]!='#'){
                if(p<lenb){if(before[p]!=s[i][j]) {ok=false;return;}p++;}
                else before+=s[i][j],p=++lenb;
            }
            else break;
        }
        p=0;
        for(int j=s[i].length()-1;j>=0;--j)
        {
            if(s[i][j]!='#'){
                if(p<lena){if(after[p]!=s[i][j]) {ok=false;return;}p++;}
                else after+=s[i][j],p=++lena;
            }
            else break;
        }
    } 
}
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;++i) cin>>s[i];
    solve(n);
    if(ok) cout<<-1;else cout<<0;
}

G：糖果（連通塊）

??題目大意是給 n n n個小朋友分糖，他們有 m m m對朋友關系，要同時滿足①不能低于 a i a_i ai?；②分的躺不能比他朋友分的少，
??可以轉化成圖，有朋友關系就是有一條邊相連，每個小朋友分的糖果數就是其所在的連通塊中最大的 a i a_i ai?.所以DFS跑一遍圖，找到圖中的各個連通塊的大小以及連通塊中 m a x ( a i ) max(a_i) max(ai?)即可，

#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
vector<int> v[maxn];int vis[maxn],a[maxn];
ll ans=0,num=0,maxnum=0;
void DFS(int root,int fa)
{
    int size=v[root].size();
    num++;vis[root]=1;if(a[root]>maxnum) maxnum=a[root];
    for(int i=0;i<size;++i)
    {
        if(v[root][i]==fa || vis[v[root][i]]) continue;
        DFS(v[root][i],root);
    }
}
int main()
{
    close;int n,m;cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=m;++i){
        int x,y;cin>>x>>y;
        v[x].push_back(y);v[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
        if(!vis[i]) num=maxnum=0,DFS(i,0),ans+=num*maxnum;
    cout<<ans;
}

H：數字串（構造）

??題目大意是給出一個只包括小寫字母的字串S，并假定’a’=1,‘b’=2…,‘z’=26.你需要找出另一個字串T，滿足按照上述規則轉換出來的數字串和S轉換出來的數字串保持一致，多種方案輸出一種即可，不存在則輸出-1.
??①拆分：存在一個字母對應的數字比10大，同時不等于20時，我們將個位和十位拆開，分別轉換成一個字母即可；②合并：如果兩個字母對應的數字都是一位數，同時組合起來是一個不超過26的合法數字，那么就直接組合轉換成一個字母，
??如果上述兩種方式都做不到，說明沒有合法的字串，輸出-1.

#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false);
using namespace std;
bool ok=false;
int main()
{
    string T,S="";cin>>T;
    int len=T.length();
    for(int i=0;i<len;++i)
    {
        int num=T[i]-'a'+1;
        if(num>10 && num!=20){
            S+=(char)((num/10)-1+'a');S+=(char)((num%10)-1+'a');
            for(int j=i+1;j<len;++j) S+=T[j];
            ok=true;
            break;
        }
        else if(num<=2){
            if(i+1<len && (T[i+1]-'a'+1)<10 && num*10+(T[i+1]-'a'+1)<=26)
            {
                S+=(char)('a'+num*10+(T[i+1]-'a'));
                for(int j=i+2;j<len;++j) S+=T[j];
                ok=true;
                break;
            } 
        }
        S+=T[i];
    }
    if(ok) cout<<S;else cout<<-1;
}

I：序列的美觀度（貪心/DP）

??題目大意是一個字串的美觀度是整數 i i i的數量，整數 i ( 1 ≤ i ≤ n ) i(1\le i\le n) i(1≤i≤n)要滿足 S i = S i + 1 S_i=S_{i+1} Si?=Si+1?.問對于給定的字串S來說，他的所有子序列（不一定連續）中最大的美觀度是多少，
??解法一：貪心的思想，找最近的兩個相同數字拼接在當前序列末尾是最優的，設 x , y x,y x,y是當前最近的兩個相同數字，那么在 x , y x,y x,y之間一定找不到任何相同的兩個數字；假定 z z z是中間的某一個數，那么即使他和 y y y后面的某個數配對，貢獻也不會超過當前的選擇（都是1），

#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
const int maxn=1e6+100;
int loc[maxn],a[maxn];
map<int,int> mp;
int main()
{
    close;int n,x;cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        if(mp[a[i]]!=0) loc[i]=mp[a[i]];
        mp[a[i]]=i;
    }
    int lastpos=1,num=0;
    for(int i=1;i<=n;++i)
        if(loc[i]>=lastpos) lastpos=i,num++;
    cout<<num;
}

??賽后看到了題解中的一種做法，解法二：DP，我們令 d p [ i ] dp[i] dp[i]表示以 a [ i ] a[i] a[i]結尾的子序列的最大美觀度，很容易得到轉移方程是： d p [ i ] = m a x { d p [ j ] + 1 } ( j < i & & a [ i ] = a [ j ] ) dp[i]=max\{dp[j]+1\}(j<i\ \&\&\ a[i]=a[j]) dp[i]=max{dp[j]+1}(j<i && a[i]=a[j]) d p [ i ] = m a x { d p [ j ] } ( j < i & & a [ i ] ≠ a [ j ] ) dp[i]=max\{dp[j]\}(j<i\ \&\&\ a[i]\ne a[j]) dp[i]=max{dp[j]}(j<i && a[i]?=a[j])如果直接這樣寫的時間復雜度是 O ( n 2 ) O(n^2) O(n2)，但我們可以再第一個式子中就記錄最近一個相等的位置，第二個式子直接對前 i ? 1 i-1 i?1項記錄最大值，然后二者區最大即可，

J：加法和乘法（博弈）

??題目大意是給定 n n n個數，每次可以選擇其中的兩個數，將他們進行加法或乘法運算，然后僅保留運算后的結果，最后剩下一個數時，如果是奇數，則牛牛贏；否則牛妹贏，
??如果 n = 1 n=1 n=1，直接判斷結果； n = 2 n=2 n=2時，兩個數都是偶數時，牛妹贏，否則都是牛牛贏； n ≥ 3 n\ge 3 n≥3時，①如果偶數的個數多余1個，一定是牛妹贏：我們發現牛牛每次操作最多減少一個偶數，但牛妹可以減少兩個奇數同時帶來一個偶數，不管牛牛怎么操作，每一輪牛妹都選擇兩個奇數相加就可以維持偶數個數最少不改變，兩個偶數朝上和一個奇數的局面一定是牛妹贏，②如果只有一個偶數，那就相當于牛妹先手，③奇數個奇數時，誰后手誰贏；④偶數個奇數時，誰先手誰贏，

#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
const int maxn=1e6+100;
int a[maxn];
int main()
{
    close;int n,num_even=0,num_odd=0;cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i],(a[i]&1)?num_odd++:num_even++;
    if(n==1){if(num_odd==1) cout<<"NiuNiu";else cout<<"NiuMei";}
    else if(n==2){if(num_even==2) cout<<"NiuMei";else cout<<"NiuNiu";}
    else{
    	if(num_even>=2) cout<<"NiuMei";
        else if(num_even==1){if(num_odd&1) cout<<"NiuNiu";else cout<<"NiuMei";}
        else{if(num_odd&1) cout<<"NiuMei";else cout<<"NiuNiu";}
    }
}