競賽第14期題解

• 第一題
• • 題目描述
  • 題解
  • 復雜度分析
• 第二題
• • 題目描述
  • 題解
  • 復雜度分析
• 第三題
• • 題目描述
  • 題解
  • 復雜度分析
• 第四題
• • 題目描述
  • 題解
  • 復雜度分析

題目不難，但要注意細節(jié)。
ps: 由于考試報告下載bug，本帖代碼為賽后重新編寫。

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：空間域名、網絡空間、營銷軟件、網站建設、尚志網站維護、網站推廣。第一題 題目描述

題目鏈接

題解

本題題目范圍標的是n==x!-1，2<=x<=10，n可以等于0，其實有些矛盾；但只需要注意n=0時返回一個空字符串即可。

#include#include

復雜度分析

時間復雜度為 O ( n ? x ) O(n·x) O(n?x)。
其中n為字符串數(shù)量，x為字符串長度。
因為數(shù)據(jù)范圍較小，所以可以通過。

第二題 題目描述

已知棋盤大小為n*n。 每個位置都有自己的權值q。 該棋盤中有多少對行權值和小于列權值和。
輸入描述：
第一行輸入整數(shù)n。(1<=n<=100)表示棋盤的大小
以下n行每行輸入n個整數(shù)表示棋子的權值。(1<=a<=1000)
輸出描述：
輸出小Q的分值。
輸入樣例：
3
1 2 3
1 2 3
1 2 3
輸出樣例：
3

題解

遍歷求出每行每列的權值和后遍歷比較即可。

#include#includeusing namespace std;
int main() {int n;
    cin >>n;
    vectorrow(n);
    vectorcol(n);
    for (int i = 0; i< n; i++) {for (int j = 0; j< n; j++) {int x;
            cin >>x;
            row[i] += x;
            col[j] += x;
        }
    }
    int ans = 0;
    for (int i = 0; i< n; i++) {for (int j = 0; j< n; j++) {if (row[i]< col[j]) ans++;
        }
    }
    cout<< ans<< endl;
    return 0;
}

復雜度分析

時間復雜度為 O ( n 2 ) O(n^2) O(n2)。
n為棋盤行/列數(shù)。

第三題 題目描述

小Q的檸檬汁做完了。 掏出了自己的數(shù)字卡牌。 想要和別人做數(shù)字游戲。 可是她又不想要輸?shù)粲螒颉?她制定好規(guī)則，每 次每個人只能把這個牌換成它的因子的某個牌。 但是這個因子不能是1或者整數(shù)本身。 現(xiàn)在給出整數(shù)n。 兩個人開始做游 戲，誰無法再給出因子牌則該人勝利，如果該整數(shù)無因子牌直接視為先手勝利，請判斷先手在最優(yōu)策略狀態(tài)下能否必勝。

題解

1. 如果該數(shù)是質數(shù)，則先手勝。
2. 如果該數(shù)（除1和本身外）只有兩個因數(shù)，則后手勝。
3. 如果該數(shù)（除1和本身外）的因數(shù)大于等于三個，易證明，先手總可以制造第二種情況，先手勝。

#include#include#includeusing namespace std;
int main() {int n;
    cin >>n;
    int flag = 0;
    int sq = (int)sqrt((double)n);
    for (int i = 2; i<= sq; i++) {while(n % i == 0) {n /= i;
            flag++;
        }
        if (flag == 2 && n == 1) {cout<< 2<< endl;
            return 0;
        }
    }
    cout<< 1<< endl;
    return 0;
}

復雜度分析

時間復雜度為 O ( n ) O(\sqrt{n}) O(n ?)。

第四題 題目描述

題目鏈接

題解

這道題還是要先讀懂題意，開始誤以為題目要求就是26進制轉換，后來才發(fā)現(xiàn)要求字母按升序排列。并且要注意判斷字符串是否滿足在字母表中這一要求，若不滿足需要輸出0！?。?br />洛谷及各種平臺有很多關于數(shù)位dp及本題其他解法的題解。下面給出一種數(shù)位dp的代碼。

#include#include 
using namespace std;

char arr[10];
long long ans, sum[30][10];
int num;
int main(void)
{scanf("%s",&arr);
    if(strlen(arr) >6){cout<< 0<< endl;
        return 0;
    }
    for(int i = 0; i< strlen(arr); i ++){if(arr[i]< 'a' || arr[i] >'z'){cout<< 0<< endl;
            return 0;
        }
    }
    for(int i = 1; i< strlen(arr); i ++){if(arr[i - 1] >= arr[i]){cout<< 0<< endl;
            return 0;
        }
    }
    for(int i = 1; i<= 26; i ++) sum[i][1] = 1;
    for(int j = 2; j<= 6; j ++){for(int i = 27 - j; i >0; i --){sum[i][j] = sum[i + 1][j - 1] + sum[i + 1][j];
        }
    }
    for(int j = strlen(arr) - 1; j >= 0; j --){num ++;
        for(int i = 1; i<= arr[j] - 'a' + 1; i ++){ans += sum[i][num];
        }
    }
    cout<< ans<< endl;
    return 0;
}

復雜度分析

時間復雜度為 O ( C ? n ) O(C·n) O(C?n)。
其中n為輸出單詞長度。

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

新聞名稱：CSDN競賽第14期題解-創(chuàng)新互聯(lián)
文章路徑：http://weahome.cn/article/csijdp.html