牛客（NC）廣西大學第三屆程式設計競賽（同步賽）

賽題鏈接：牛客（NC）廣西大學第三屆程式設計競賽（同步賽） 點擊傳送

A題 A++++++++++++++++++（簽到題）

簽到題，給n個字串，其中national和international為一組，求其中有多少組；
資料小直接暴力沒啥好說的

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
int main()
{
    int t;
    scanf("%d",&t);
    int n;
    string s
    while(t--){
        scanf("%d",&n);
        int ans=0,cnt=0;
        for(int i=0;i<n;i++){//記錄輸入的資料中有多少個national和international；
            cin>>s;//輸入字串s，可以用字符陣列代替
            if(s=="national")ans++;
            else cnt++;
        }
        printf("A");
        for(int i=0;i<min(ans,cnt);i++)printf("+");//輸出A后面的‘+’的個數為ans和cnt中最短的那個；
        printf("\n");
    }
    return 0;
}

B題 GDP Carry（博弈）

博弈：博弈是資訊學和數學試題中常會出現的一種型別，演算法靈活多變是其最大特點， 尋找必敗態即為針對此類試題給出一種解題思路，

注：題解中Antinomy稱為小A；

B題給出一個序列，小A每次從序列中取出一段非空連續的數（取走后剩余的序列視為連續），它們的和為奇數，小西每次從序列中取出一段非空連續數，和為偶數，小A先手，輪到誰無法操作即為輸，

對于輸入的序列，無論數值大小，都可以看作為一組01串（因為題目只看奇偶，奇數為1，偶數為0）；
對于每一種01串都可分為三種情況：
①1的數量為奇數個（即有奇數個奇數）
②1的數量為偶數個（即有偶數個奇數）
③序列中沒有1（即為偶數序列）
對于情況①小A先手，取連續元素和為奇數的序列，可直接取完整個序列，小西無法進行操作，情況①小A必勝；

對于情況②小A先手，取連續元素和為奇數的序列，可取至序列僅剩一個奇數，此時若序列中還有偶數，小西取一個偶數序列（無法取完整個序列），之后小A可取完剩余的整個序列，小西無法操作，小A勝；若序列中沒有其他偶數，小西無法操作，小A勝；情況②小A必勝

對于情況③，偶數序列，小A先手無法取數，小西必勝；情況③小西必勝

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);
    int ans=0,a;
    for(int i=0;i<n;i++){
        scanf("%d",&a);
        if(a%2!=0)ans++;
    }
    if(ans==0) printf("XiJam");
    else printf("Antinomy");
    return 0;
}

C題 Interpretability（思維題）

對于題意給出的這些邊，求這些邊最多能構成多少個三角形；
思維題，也可理解為一種貪心；

首先這題n的范圍n較大，直接存邊大小存不下；
關于這題的三角形構造，每條邊都是2的整數次方（即2，4，8，16……），即三條長度不同的邊無法構成三角形，腰比底小的也無法構成三角形；
構成三角形只有兩種：1、等邊三角形；2、等腰三角形（腰長比底長大），

一開始我的想法是存邊數，即存陣列f，先對于每個fi，除以三取出所有的等邊三角形，取完后%3取余數，此時f陣列中只有0，1，2三種數字，之后，對于f陣列從后往前遍歷（因為腰要比底長），構造等腰三角形，先將陣列中的2與在2前面的1組合，之后對于剩下的2，組合剩下的三角形；

	int n;
    scanf("%d",&n);
    long long ans=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&f[i]);
        ans+=f[i]/3;
        f[i]%=3;
    }
    long long x=0;
    for(int i=n;i>=1;i--){
        if(f[i]==2)x++;
        else if(f[i]==1&&x){
            ans++;
            if(x>0)x--;
        }
    }
    ans+=(x*2)/3;
    cout<<ans<<endl;
    return 0;

簡單來說就是先貪心等邊三角形，再組合等腰三角形；
但是這種思維是錯誤的；就很榮幸的WA了；
例如：對于樣例：3 4 4 4；用上述方法得出3個三角形；若是先貪等腰三角形，可得4個三角形

AC思路：先貪等腰三角形；
對于f陣列，從前往后遍歷，f1無法構造等腰三角形，構造等邊三角形，對于后面每個fi，若是前面有剩余的邊給它當底邊，構造等腰三角形，剩余的邊構造等邊三角形，再剩余的邊做底邊與后面的邊構造；（這樣都不用存陣列）

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

int main()
{
    ll n;
    scanf("%lld",&n);
    ll a,t,ans=0;//t用來存前方有多少條邊做底邊,ans存構造多少個三角形，資料較大int會爆，用long long存
    for(int i=0;i<n;i++){
        scanf("%lld",&a);
        if(t!=0){//前面有邊做底邊，貪等腰
            int un=a/2;//對于每個底邊要兩條腰構造三角形
            if(un>=t){
                a-=2*t;
                ans+=t;
                t=0;
            }
            else{
                a-=2*un;
                ans+=un;
                t-=un;
            }
        }
        ans+=a/3;//剩余的構造等邊三角形
        t+=a%3;
    }
    printf("%lld\n",ans);
    return 0;
}

E題 Antinomy與黑風海（圖論模板題）

一看到這題，就想到了圖論，仔細看求最少需要的時間，就想到了最小生成樹和最短路，再看一眼，單向邊，我就用最短路寫了，

看一下資料范圍1e6，普通的最短路演算法存不下，就用堆優化的Dijkstra演算法，
注：不熟悉Djk的可以看我的另一篇博客————>最短路徑———Dijkstra演算法（點擊傳送）

這題的難點是，每到一個點還要回到原點再到下一個點，開始的確有點懵（單向邊），后來仔細想；
單向邊，從s（默認為1）開始，我正著Djk一次，反著Djk一次，這兩次不同的是把單向邊的方向翻轉，
得出的資料為s到其他點的最短距離和其他點到s的最短距離將兩個dis陣列加起來即為題目所求；

貼個代碼：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
struct lq{
    int x,d;
};
 
struct xb{
    int x,d;
     bool operator <(const xb &a) const{
        return x>a.x;
    }
};
 
priority_queue<xb> q;
int dis[1000005];
int ans[1000005];
vector<lq> a[1000005];
vector<lq> b[1000005];
void Djk(int n,int s){
    for(int i=1;i<=n;i++) dis[i]=INF;
    xb e;
    e.x=s;
    e.d=0;
    dis[s]=0;
    q.push(e);
    while(!q.empty()){
        e=q.top();
        q.pop();
        int v=e.x;
        int u=e.d;
        if(dis[v]<u) continue;
        int len=a[v].size();
        for(int i=0;i<len;i++){
            lq g=a[v][i];
            if(dis[v]+g.d<dis[g.x]){
                dis[g.x]=dis[v]+g.d;
                e.x=g.x;
                e.d=dis[g.x];
                q.push(e);
            }
        }
    }
}
void DJK(int n,int s){
    for(int i=1;i<=n;i++) ans[i]=INF;
    xb e;
    e.x=s;
    e.d=0;
    ans[s]=0;
    q.push(e);
    while(!q.empty()){
        e=q.top();
        q.pop();
        int v=e.x;
        int u=e.d;
        if(ans[v]<u) continue;
        int len=b[v].size();
        for(int i=0;i<len;i++){
            lq g=b[v][i];
            if(ans[v]+g.d<ans[g.x]){
                ans[g.x]=ans[v]+g.d;
                e.x=g.x;
                e.d=ans[g.x];
                q.push(e);
            }
        }
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        lq e;
        e.x=y;
        e.d=z;
        a[x].push_back(e);
        e.x = x;
        b[y].push_back(e);
    }
    Djk(n,1);
    DJK(n,1);
    long long sum=0;
    for(int i=1;i<=n;i++){
        sum+=dis[i];
        sum+=ans[i];
    }
    printf("%lld",sum);
    return 0;
}

好了，小菜雞的我只會這些題目，題解有問題歡迎各位大佬指正(≧?≦)ﾉ