第1題

請選出以下最大的數(shù)（ ）

第2題

操作系統(tǒng)的功能是（ ）

第3題

現(xiàn)有一段 8 分鐘的視頻文件，它的播放速度是每秒 24 幀圖像，每幀圖像是一幅分辨率為 2048×1024 像素的 32 位真彩色圖像。請問要存儲這段原始無壓縮視頻，需要多大的存儲空間？（ ）

第4題

今有一空棧 S，對下列待進棧的數(shù)據(jù)元素序列 a,b,c,d,e,f依次進行：進棧，進棧，出棧，進棧，進棧，出棧的操作，則此操作完成后，棧底元素為（ ）。

第5題

將 (2,7,10,18)分別存儲到某個地址區(qū)間為 0~10 的哈希表中，如果哈希函數(shù) h(x)=（ ），將不會產(chǎn)生沖突，其中 a mod b 表示 a 除以 b 的余數(shù)。

第6題

下列哪些問題不能用貪心法精確求解？（ ）

第7題

具有 n 個定點，e 條邊的圖采用鄰接表存儲結(jié)構(gòu)，進行深度優(yōu)先遍歷運算的時間復(fù)雜度為（ ）。

第8題

二分圖是指能將頂點劃分成兩個部分，每一部分內(nèi)的頂點間沒有邊相連的簡單無向圖。那么，24 個頂點的二分圖至多有（ ）條邊。

第9題

廣度優(yōu)先搜索時，一定需要用到的數(shù)據(jù)結(jié)構(gòu)是（ ）。

第10題

一個班學(xué)生分組做游戲，如果每組三人就多兩人，每組五人就多三人，每組七人就多四人，問這個班的學(xué)生人數(shù) n 在以下哪個區(qū)間？已知 n<60。（ ）

第11題

小明想通過走樓梯來鍛煉身體，假設(shè)從第 1 層走到第 2 層消耗 10 卡熱量，接著從第 2 層走到第 3 層消耗 20 卡熱量，再從第 3 層走到第 4 層消耗 30 卡熱量，依此類推，從第 k 層走到第 k+1 層消耗 10k 卡熱量（k>1）。如果小明想從 1 層開始，通過連續(xù)向上爬樓梯消耗 1000 卡熱量，至少要爬到第幾層樓？（ ）

第12題

表達(dá)式 a*(b+c)-da?(b+c)?d 的后綴表達(dá)形式為（ ）。

第13題

從一個 4×4 的棋盤中選取不在同一行也不在同一列上的兩個方格，共有（ ）種方法。

第14題

對一個 n 個頂點、m 條邊的帶權(quán)有向簡單圖用 Dijkstra 算法計算單源最短路時，如果不使用隊或其他優(yōu)先隊列進行優(yōu)化，則其時間復(fù)雜度為（ ）。

第15題

1948 年，（ ）將熱力學(xué)中的熵引入信息通信領(lǐng)域，標(biāo)志著信息論研究的開端。

第16題

#include <iostream>
using namespace std;

int n;
int d[1000];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    int ans = -1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (d[i] < d[j])
                ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
    cout << ans;
    return 0;
}

假設(shè)輸入的 n 和 d[i] 都是不超過 10000 的正整數(shù)。

1)判斷：n 必須小于 1000，否則程序可能會發(fā)生錯誤。（ ）

第17題

#include <iostream>
using namespace std;

int n;
int d[1000];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    int ans = -1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (d[i] < d[j])
                ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
    cout << ans;
    return 0;
}

假設(shè)輸入的 n 和 d[i] 都是不超過 10000 的正整數(shù)。

2)判斷：輸出一定大于等于 0。（ ）

第18題

#include <iostream>
using namespace std;

int n;
int d[1000];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    int ans = -1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (d[i] < d[j])
                ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
    cout << ans;
    return 0;
}

假設(shè)輸入的 n 和 d[i] 都是不超過 10000 的正整數(shù)。

3)判斷：若將第 13 行的“j = 0”改為“j = i + 1”，程序輸出可能會改變。（ ）

第19題

#include <iostream>
using namespace std;

int n;
int d[1000];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    int ans = -1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (d[i] < d[j])
                ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
    cout << ans;
    return 0;
}

假設(shè)輸入的 n 和 d[i] 都是不超過 10000 的正整數(shù)。

4)判斷：將第 14 行的“d[i] < d[j]”改為“d[i] != d[j]”，程序輸出不會改變。（ ）

第20題

#include <iostream>
using namespace std;

int n;
int d[1000];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    int ans = -1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (d[i] < d[j])
                ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
    cout << ans;
    return 0;
}

假設(shè)輸入的 n 和 d[i] 都是不超過 10000 的正整數(shù)。

5)若輸入的 n 為 100，且輸出為 127，則輸入的 d[i] 中不可能有（ ）

第21題

#include <iostream>
using namespace std;

int n;
int d[1000];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    int ans = -1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (d[i] < d[j])
                ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
    cout << ans;
    return 0;
}

假設(shè)輸入的 n 和 d[i] 都是不超過 10000 的正整數(shù)。

6)若輸出的數(shù)大于 0，則下面說法正確的是（ ）

第22題

#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 1, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

假設(shè)輸入的 n，k 和 d[i] 都是不超過 10000 的正整數(shù)，且 k 不超過 n，并假設(shè) rand() 函數(shù)產(chǎn)生的是均勻的隨機數(shù)。

1）判斷：第 9 行的“x”的數(shù)值范圍是 L+1到 R，即 [L+1, R]。（ ）

第23題

#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 1, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

假設(shè)輸入的 n，k 和 d[i] 都是不超過 10000 的正整數(shù)，且 k 不超過 n，并假設(shè) rand() 函數(shù)產(chǎn)生的是均勻的隨機數(shù)。

2）判斷：將第 19 行的“d[a]”改為“d[b]”，程序不會發(fā)生運行錯誤。（ ）

第24題

#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 1, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

假設(shè)輸入的 n，k 和 d[i] 都是不超過 10000 的正整數(shù)，且 k 不超過 n，并假設(shè) rand() 函數(shù)產(chǎn)生的是均勻的隨機數(shù)。

3）當(dāng)輸入的 d[i] 是嚴(yán)格單調(diào)遞增序列時，第 17 行的“swap”的平均執(zhí)行次數(shù)是（ ）

第25題

#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 1, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

假設(shè)輸入的 n，k 和 d[i] 都是不超過 10000 的正整數(shù)，且 k 不超過 n，并假設(shè) rand() 函數(shù)產(chǎn)生的是均勻的隨機數(shù)。

4）當(dāng)輸入的 d[i] 是嚴(yán)格單調(diào)遞減序列時，第 17 行的“swap”平均執(zhí)行次數(shù)是（ ）

第26題

#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 1, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

假設(shè)輸入的 n，k 和 d[i] 都是不超過 10000 的正整數(shù)，且 k 不超過 n，并假設(shè) rand() 函數(shù)產(chǎn)生的是均勻的隨機數(shù)。

5）若輸入的 d[i] 為 i，此程序①平均的時間復(fù)雜度和②最壞情況下的時間復(fù)雜度分別是（ ）

第27題

#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 1, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

假設(shè)輸入的 n，k 和 d[i] 都是不超過 10000 的正整數(shù)，且 k 不超過 n，并假設(shè) rand() 函數(shù)產(chǎn)生的是均勻的隨機數(shù)。

6）若輸入的 d[i] 都為同一個數(shù)，此程序的平均時間復(fù)雜度是（ ）

第28題

#include <iostream>
#include <queue>
using namespace std;

const int maxl = 2000000000;

class Map {
    struct item {
        string key; int value;
    } d[maxl];
    int cnt;
public:
    int find(string x) {
        for (int i = 0; i < cnt; i++)
            if (d[i].key == x)
                return d[i].value;
        return -1;
    }
    static int end() { return -1; }
    void insert(string k, int v) {
        d[cnt].key = k; d[cnt++].value = v;
    }
} s[2];

class Queue {
    string q[maxl];
    int head, tail;
public:
    void pop() { ++head; }
    string front() { return q[head + 1]; }
    bool empty() { return head == tail; }
    void push(string x) { q[++tail] = x; }
} q[2];

string st0, st1;
int m;

string LtoR(string s, int L, int R) {
    string t = s;
    char tmp = t[L];
    for (int i = L; i < R; ++i)
        t[i] = t[i + 1];
    t[R] = tmp;
    return t;
}

string RtoL(string s, int L, int R) {
    string t = s;
    char tmp = t[R];
    for (int i = R; i > L; --i)
        t[i] = t[i - 1];
    t[L] = tmp;
    return t;
}

bool check(string st, int p, int step) {
    if (s[p].find(st) != s[p].end())
        return false;
    ++step;
    if (s[p ^ 1].find(st) == s[p].end()) {
        s[p].insert(st, step);
        q[p].push(st);
        return false;
    }
    cout << s[p ^ 1].find(st) + step << endl;
    return true;
}

int main() {
    cin >> st0 >> st1;
    int len = st0.length();
    if (len != st1.length()) {
        cout << -1 << endl;
        return 0;
    }
    if (st0 == st1) {
        cout << 0 << endl;
        return 0;
    }
    cin >> m;
    s[0].insert(st0, 0); s[1].insert(st1, 0);
    q[0].push(st0); q[1].push(st1);
    for (int p = 0;
         !(q[0].empty() && q[1].empty());
         p ^= 1) {
        string st = q[p].front(); q[p].pop();
        int step = s[p].find(st);
        if ((p == 0 &&
              (check(LtoR(st, m, len - 1), p, step) ||
               check(RtoL(st, 0, m), p, step)))
                  ||
            (p == 1 &&
              (check(LtoR(st, 0, m), p, step) ||
               check(RtoL(st, m, len - 1), p, step))))
            return 0;
    }
    cout << -1 << endl;
    return 0;
}

1)判斷：輸出可能為 0。（ ）

第29題

#include <iostream>
#include <queue>
using namespace std;
 
const int maxl = 2000000000;
 
class Map {
    struct item {
        string key; int value;
    } d[maxl];
    int cnt;
public:
    int find(string x) {
        for (int i = 0; i < cnt; i++)
            if (d[i].key == x)
                return d[i].value;
        return -1;
    }
    static int end() { return -1; }
    void insert(string k, int v) {
        d[cnt].key = k; d[cnt++].value = v;
    }
} s[2];
 
class Queue {
    string q[maxl];
    int head, tail;
public:
    void pop() { ++head; }
    string front() { return q[head + 1]; }
    bool empty() { return head == tail; }
    void push(string x) { q[++tail] = x; }
} q[2];
 
string st0, st1;
int m;
 
string LtoR(string s, int L, int R) {
    string t = s;
    char tmp = t[L];
    for (int i = L; i < R; ++i)
        t[i] = t[i + 1];
    t[R] = tmp;
    return t;
}
 
string RtoL(string s, int L, int R) {
    string t = s;
    char tmp = t[R];
    for (int i = R; i > L; --i)
        t[i] = t[i - 1];
    t[L] = tmp;
    return t;
}
 
bool check(string st, int p, int step) {
    if (s[p].find(st) != s[p].end())
        return false;
    ++step;
    if (s[p ^ 1].find(st) == s[p].end()) {
        s[p].insert(st, step);
        q[p].push(st);
        return false;
    }
    cout << s[p ^ 1].find(st) + step << endl;
    return true;
}
 
int main() {
    cin >> st0 >> st1;
    int len = st0.length();
    if (len != st1.length()) {
        cout << -1 << endl;
        return 0;
    }
    if (st0 == st1) {
        cout << 0 << endl;
        return 0;
    }
    cin >> m;
    s[0].insert(st0, 0); s[1].insert(st1, 0);
    q[0].push(st0); q[1].push(st1);
    for (int p = 0;
         !(q[0].empty() && q[1].empty());
         p ^= 1) {
        string st = q[p].front(); q[p].pop();
        int step = s[p].find(st);
        if ((p == 0 &&
              (check(LtoR(st, m, len - 1), p, step) ||
               check(RtoL(st, 0, m), p, step)))
                  ||
            (p == 1 &&
              (check(LtoR(st, 0, m), p, step) ||
               check(RtoL(st, m, len - 1), p, step))))
            return 0;
    }
    cout << -1 << endl;
    return 0;
}

2）判斷：若輸入的兩個字符串長度均為 101 時，則 m=0 時的輸出與 m=100 時的輸出是一樣的。（ ）

第30題

#include <iostream>
#include <queue>
using namespace std;
 
const int maxl = 2000000000;
 
class Map {
    struct item {
        string key; int value;
    } d[maxl];
    int cnt;
public:
    int find(string x) {
        for (int i = 0; i < cnt; i++)
            if (d[i].key == x)
                return d[i].value;
        return -1;
    }
    static int end() { return -1; }
    void insert(string k, int v) {
        d[cnt].key = k; d[cnt++].value = v;
    }
} s[2];
 
class Queue {
    string q[maxl];
    int head, tail;
public:
    void pop() { ++head; }
    string front() { return q[head + 1]; }
    bool empty() { return head == tail; }
    void push(string x) { q[++tail] = x; }
} q[2];
 
string st0, st1;
int m;
 
string LtoR(string s, int L, int R) {
    string t = s;
    char tmp = t[L];
    for (int i = L; i < R; ++i)
        t[i] = t[i + 1];
    t[R] = tmp;
    return t;
}
 
string RtoL(string s, int L, int R) {
    string t = s;
    char tmp = t[R];
    for (int i = R; i > L; --i)
        t[i] = t[i - 1];
    t[L] = tmp;
    return t;
}
 
bool check(string st, int p, int step) {
    if (s[p].find(st) != s[p].end())
        return false;
    ++step;
    if (s[p ^ 1].find(st) == s[p].end()) {
        s[p].insert(st, step);
        q[p].push(st);
        return false;
    }
    cout << s[p ^ 1].find(st) + step << endl;
    return true;
}
 
int main() {
    cin >> st0 >> st1;
    int len = st0.length();
    if (len != st1.length()) {
        cout << -1 << endl;
        return 0;
    }
    if (st0 == st1) {
        cout << 0 << endl;
        return 0;
    }
    cin >> m;
    s[0].insert(st0, 0); s[1].insert(st1, 0);
    q[0].push(st0); q[1].push(st1);
    for (int p = 0;
         !(q[0].empty() && q[1].empty());
         p ^= 1) {
        string st = q[p].front(); q[p].pop();
        int step = s[p].find(st);
        if ((p == 0 &&
              (check(LtoR(st, m, len - 1), p, step) ||
               check(RtoL(st, 0, m), p, step)))
                  ||
            (p == 1 &&
              (check(LtoR(st, 0, m), p, step) ||
               check(RtoL(st, m, len - 1), p, step))))
            return 0;
    }
    cout << -1 << endl;
    return 0;
}

3）判斷：若兩個字符串的長度均為 n，則最壞情況下，此程序的時間復(fù)雜度為 Θ(n!)。（ ）

第31題

#include <iostream>
#include <queue>
using namespace std;
 
const int maxl = 2000000000;
 
class Map {
    struct item {
        string key; int value;
    } d[maxl];
    int cnt;
public:
    int find(string x) {
        for (int i = 0; i < cnt; i++)
            if (d[i].key == x)
                return d[i].value;
        return -1;
    }
    static int end() { return -1; }
    void insert(string k, int v) {
        d[cnt].key = k; d[cnt++].value = v;
    }
} s[2];
 
class Queue {
    string q[maxl];
    int head, tail;
public:
    void pop() { ++head; }
    string front() { return q[head + 1]; }
    bool empty() { return head == tail; }
    void push(string x) { q[++tail] = x; }
} q[2];
 
string st0, st1;
int m;
 
string LtoR(string s, int L, int R) {
    string t = s;
    char tmp = t[L];
    for (int i = L; i < R; ++i)
        t[i] = t[i + 1];
    t[R] = tmp;
    return t;
}
 
string RtoL(string s, int L, int R) {
    string t = s;
    char tmp = t[R];
    for (int i = R; i > L; --i)
        t[i] = t[i - 1];
    t[L] = tmp;
    return t;
}
 
bool check(string st, int p, int step) {
    if (s[p].find(st) != s[p].end())
        return false;
    ++step;
    if (s[p ^ 1].find(st) == s[p].end()) {
        s[p].insert(st, step);
        q[p].push(st);
        return false;
    }
    cout << s[p ^ 1].find(st) + step << endl;
    return true;
}
 
int main() {
    cin >> st0 >> st1;
    int len = st0.length();
    if (len != st1.length()) {
        cout << -1 << endl;
        return 0;
    }
    if (st0 == st1) {
        cout << 0 << endl;
        return 0;
    }
    cin >> m;
    s[0].insert(st0, 0); s[1].insert(st1, 0);
    q[0].push(st0); q[1].push(st1);
    for (int p = 0;
         !(q[0].empty() && q[1].empty());
         p ^= 1) {
        string st = q[p].front(); q[p].pop();
        int step = s[p].find(st);
        if ((p == 0 &&
              (check(LtoR(st, m, len - 1), p, step) ||
               check(RtoL(st, 0, m), p, step)))
                  ||
            (p == 1 &&
              (check(LtoR(st, 0, m), p, step) ||
               check(RtoL(st, m, len - 1), p, step))))
            return 0;
    }
    cout << -1 << endl;
    return 0;
}

4）若輸入的第一個字符串長度由 100 個不同的字符構(gòu)成，第二個字符串是第一個字符串的倒序，輸入的 m 為 0，則輸出為（ ）。

第32題

#include <iostream>
#include <queue>
using namespace std;
 
const int maxl = 2000000000;
 
class Map {
    struct item {
        string key; int value;
    } d[maxl];
    int cnt;
public:
    int find(string x) {
        for (int i = 0; i < cnt; i++)
            if (d[i].key == x)
                return d[i].value;
        return -1;
    }
    static int end() { return -1; }
    void insert(string k, int v) {
        d[cnt].key = k; d[cnt++].value = v;
    }
} s[2];
 
class Queue {
    string q[maxl];
    int head, tail;
public:
    void pop() { ++head; }
    string front() { return q[head + 1]; }
    bool empty() { return head == tail; }
    void push(string x) { q[++tail] = x; }
} q[2];
 
string st0, st1;
int m;
 
string LtoR(string s, int L, int R) {
    string t = s;
    char tmp = t[L];
    for (int i = L; i < R; ++i)
        t[i] = t[i + 1];
    t[R] = tmp;
    return t;
}
 
string RtoL(string s, int L, int R) {
    string t = s;
    char tmp = t[R];
    for (int i = R; i > L; --i)
        t[i] = t[i - 1];
    t[L] = tmp;
    return t;
}
 
bool check(string st, int p, int step) {
    if (s[p].find(st) != s[p].end())
        return false;
    ++step;
    if (s[p ^ 1].find(st) == s[p].end()) {
        s[p].insert(st, step);
        q[p].push(st);
        return false;
    }
    cout << s[p ^ 1].find(st) + step << endl;
    return true;
}
 
int main() {
    cin >> st0 >> st1;
    int len = st0.length();
    if (len != st1.length()) {
        cout << -1 << endl;
        return 0;
    }
    if (st0 == st1) {
        cout << 0 << endl;
        return 0;
    }
    cin >> m;
    s[0].insert(st0, 0); s[1].insert(st1, 0);
    q[0].push(st0); q[1].push(st1);
    for (int p = 0;
         !(q[0].empty() && q[1].empty());
         p ^= 1) {
        string st = q[p].front(); q[p].pop();
        int step = s[p].find(st);
        if ((p == 0 &&
              (check(LtoR(st, m, len - 1), p, step) ||
               check(RtoL(st, 0, m), p, step)))
                  ||
            (p == 1 &&
              (check(LtoR(st, 0, m), p, step) ||
               check(RtoL(st, m, len - 1), p, step))))
            return 0;
    }
    cout << -1 << endl;
    return 0;
}

5）已知當(dāng)輸入為

0123

3210

1

時輸出為 4，當(dāng)輸入為

012345

543210

1

時輸出為 14，當(dāng)輸入為

01234567

76543210

1

時輸出為 28，則當(dāng)輸入為

0123456789ab

ba9876543210

1

輸出為（ ）。

第33題

#include <iostream>
#include <queue>
using namespace std;
 
const int maxl = 2000000000;
 
class Map {
    struct item {
        string key; int value;
    } d[maxl];
    int cnt;
public:
    int find(string x) {
        for (int i = 0; i < cnt; i++)
            if (d[i].key == x)
                return d[i].value;
        return -1;
    }
    static int end() { return -1; }
    void insert(string k, int v) {
        d[cnt].key = k; d[cnt++].value = v;
    }
} s[2];
 
class Queue {
    string q[maxl];
    int head, tail;
public:
    void pop() { ++head; }
    string front() { return q[head + 1]; }
    bool empty() { return head == tail; }
    void push(string x) { q[++tail] = x; }
} q[2];
 
string st0, st1;
int m;
 
string LtoR(string s, int L, int R) {
    string t = s;
    char tmp = t[L];
    for (int i = L; i < R; ++i)
        t[i] = t[i + 1];
    t[R] = tmp;
    return t;
}
 
string RtoL(string s, int L, int R) {
    string t = s;
    char tmp = t[R];
    for (int i = R; i > L; --i)
        t[i] = t[i - 1];
    t[L] = tmp;
    return t;
}
 
bool check(string st, int p, int step) {
    if (s[p].find(st) != s[p].end())
        return false;
    ++step;
    if (s[p ^ 1].find(st) == s[p].end()) {
        s[p].insert(st, step);
        q[p].push(st);
        return false;
    }
    cout << s[p ^ 1].find(st) + step << endl;
    return true;
}
 
int main() {
    cin >> st0 >> st1;
    int len = st0.length();
    if (len != st1.length()) {
        cout << -1 << endl;
        return 0;
    }
    if (st0 == st1) {
        cout << 0 << endl;
        return 0;
    }
    cin >> m;
    s[0].insert(st0, 0); s[1].insert(st1, 0);
    q[0].push(st0); q[1].push(st1);
    for (int p = 0;
         !(q[0].empty() && q[1].empty());
         p ^= 1) {
        string st = q[p].front(); q[p].pop();
        int step = s[p].find(st);
        if ((p == 0 &&
              (check(LtoR(st, m, len - 1), p, step) ||
               check(RtoL(st, 0, m), p, step)))
                  ||
            (p == 1 &&
              (check(LtoR(st, 0, m), p, step) ||
               check(RtoL(st, m, len - 1), p, step))))
            return 0;
    }
    cout << -1 << endl;
    return 0;
}

6）若兩個字符串的長度均為 n，且 0<m<n?1，且兩個字符串的構(gòu)成相同（即任何一個字符在兩個字符串中出現(xiàn)的次數(shù)均相同），則下列說法正確的是（ ）。提示：考慮輸入與輸出有多少對字符前后順序不一樣。

第34題

（分?jǐn)?shù)背包）小 S 有 n 塊蛋糕，編號從 1 到 n。第 i 塊蛋糕的價值是 wi，體積是 vi。他有一個大小為 B 的盒子來裝這些蛋糕，也就是說裝入盒子的蛋糕的體積總和不能超過 B。

他打算選擇一些蛋糕裝入盒子，他希望盒子里裝的蛋糕的價值之和盡量大。

為了使盒子里的蛋糕價值之和更大，他可以任意切割蛋糕。具體來說，他可以選擇一個 α(0<α<1)，并將一塊價值是 w，體積為 v 的蛋糕切割成兩塊，其中一塊的價值是 αw，體積是 αv，另一塊的價值是 (1?α)w，體積是 (1?α)v。他可以重復(fù)無限次切割操作。

現(xiàn)要求編程輸出最大可能的價值，以分?jǐn)?shù)的形式輸出。

比如 n=3，B=8，三塊蛋糕的價值分別是 4、4、2，體積分別是 5、3、2。

那么最優(yōu)的方法就是將體積為 5 的蛋糕切成兩份，一份體積是 3，價值是 2.4，另一份體積是 2，價值是 1.61，然后把體積是 3 的那部分和后兩塊蛋糕打包進盒子。最優(yōu)的價值之和是 8.4，故程序輸出 42/5。

輸入的數(shù)據(jù)范圍為：1≤n≤1000，1≤B≤105，1≤wi,vi≤100。

提示：將所有的蛋糕按照性價比 wi/vi 從大到小排序后進行貪心選擇。

試補全程序。

#include <cstdio>
using namespace std;

const int maxn = 1005;

int n, B, w[maxn], v[maxn];

int gcd(int u, int v) {
    if (v == 0)
        return u;
    return gcd(v, u % v);
}

void print(int w, int v) {
    int d = gcd(w, v);
    w = w / d;
    v = v / d;
    if (v == 1)
        printf("%d\n", w);
    else
        printf("%d/%d\n", w, v);
}

void swap(int &x, int &y) {
    int t = x; x = y; y = t;
}

int main() {
    scanf("%d %d", &n, &B);
    for (int i = 1; i <= n; i ++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (int i = 1; i < n; i ++)
        for (int j = 1; j < n; j ++)
            if ( ① ) {
                swap(w[j], w[j + 1]);
                swap(v[j], v[j + 1]);
            }
    int curV, curW;
    if ( ② ) {
        ③
    } else {
        print(B * w[1], v[1]);
        return 0;
    }

    for (int i = 2; i <= n; i ++)
        if (curV + v[i] <= B) {
            curV += v[i];
            curW += w[i];
        } else {
            print( ④ );
            return 0;
        }
    print( ⑤ );
    return 0;
}

① 處應(yīng)填（ ）

第35題

（分?jǐn)?shù)背包）小 S 有 n 塊蛋糕，編號從 1 到 n。第 i 塊蛋糕的價值是 wi，體積是 vi。他有一個大小為 B 的盒子來裝這些蛋糕，也就是說裝入盒子的蛋糕的體積總和不能超過 B。

他打算選擇一些蛋糕裝入盒子，他希望盒子里裝的蛋糕的價值之和盡量大。

為了使盒子里的蛋糕價值之和更大，他可以任意切割蛋糕。具體來說，他可以選擇一個 α(0<α<1)，并將一塊價值是 w，體積為 v 的蛋糕切割成兩塊，其中一塊的價值是 αw，體積是 αv，另一塊的價值是 (1?α)w，體積是 (1?α)v。他可以重復(fù)無限次切割操作。

現(xiàn)要求編程輸出最大可能的價值，以分?jǐn)?shù)的形式輸出。

比如 n=3，B=8，三塊蛋糕的價值分別是 4、4、2，體積分別是 5、3、2。

那么最優(yōu)的方法就是將體積為 5 的蛋糕切成兩份，一份體積是 3，價值是 2.4，另一份體積是 2，價值是 1.61，然后把體積是 3 的那部分和后兩塊蛋糕打包進盒子。最優(yōu)的價值之和是 8.4，故程序輸出 42/5。

輸入的數(shù)據(jù)范圍為：1≤n≤1000，1≤B≤105，1≤wi,vi≤100。

提示：將所有的蛋糕按照性價比 wi/vi 從大到小排序后進行貪心選擇。

試補全程序。

#include <cstdio>
using namespace std;

const int maxn = 1005;

int n, B, w[maxn], v[maxn];

int gcd(int u, int v) {
    if (v == 0)
        return u;
    return gcd(v, u % v);
}

void print(int w, int v) {
    int d = gcd(w, v);
    w = w / d;
    v = v / d;
    if (v == 1)
        printf("%d\n", w);
    else
        printf("%d/%d\n", w, v);
}

void swap(int &x, int &y) {
    int t = x; x = y; y = t;
}

int main() {
    scanf("%d %d", &n, &B);
    for (int i = 1; i <= n; i ++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (int i = 1; i < n; i ++)
        for (int j = 1; j < n; j ++)
            if ( ① ) {
                swap(w[j], w[j + 1]);
                swap(v[j], v[j + 1]);
            }
    int curV, curW;
    if ( ② ) {
        ③
    } else {
        print(B * w[1], v[1]);
        return 0;
    }

    for (int i = 2; i <= n; i ++)
        if (curV + v[i] <= B) {
            curV += v[i];
            curW += w[i];
        } else {
            print( ④ );
            return 0;
        }
    print( ⑤ );
    return 0;
}

② 處應(yīng)填（ ）

第36題

（分?jǐn)?shù)背包）小 S 有 n 塊蛋糕，編號從 1 到 n。第 i 塊蛋糕的價值是 wi，體積是 vi。他有一個大小為 B 的盒子來裝這些蛋糕，也就是說裝入盒子的蛋糕的體積總和不能超過 B。

他打算選擇一些蛋糕裝入盒子，他希望盒子里裝的蛋糕的價值之和盡量大。

為了使盒子里的蛋糕價值之和更大，他可以任意切割蛋糕。具體來說，他可以選擇一個 α(0<α<1)，并將一塊價值是 w，體積為 v 的蛋糕切割成兩塊，其中一塊的價值是 αw，體積是 αv，另一塊的價值是 (1?α)w，體積是 (1?α)v。他可以重復(fù)無限次切割操作。

現(xiàn)要求編程輸出最大可能的價值，以分?jǐn)?shù)的形式輸出。

比如 n=3，B=8，三塊蛋糕的價值分別是 4、4、2，體積分別是 5、3、2。

那么最優(yōu)的方法就是將體積為 5 的蛋糕切成兩份，一份體積是 3，價值是 2.4，另一份體積是 2，價值是 1.61，然后把體積是 3 的那部分和后兩塊蛋糕打包進盒子。最優(yōu)的價值之和是 8.4，故程序輸出 42/5。

輸入的數(shù)據(jù)范圍為：1≤n≤1000，1≤B≤105，1≤wi,vi≤100。

提示：將所有的蛋糕按照性價比 wi/vi 從大到小排序后進行貪心選擇。

試補全程序。

#include <cstdio>
using namespace std;
const int maxn = 1005;
int n, B, w[maxn], v[maxn];
int gcd(int u, int v) {
    if (v == 0)
        return u;
    return gcd(v, u % v);
}
void print(int w, int v) {
    int d = gcd(w, v);
    w = w / d;
    v = v / d;
    if (v == 1)
        printf("%d\n", w);
    else
        printf("%d/%d\n", w, v);
}
void swap(int &x, int &y) {
    int t = x; x = y; y = t;
}
int main() {
    scanf("%d %d", &n, &B);
    for (int i = 1; i <= n; i ++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (int i = 1; i < n; i ++)
        for (int j = 1; j < n; j ++)
            if ( ① ) {
                swap(w[j], w[j + 1]);
                swap(v[j], v[j + 1]);
            }
    int curV, curW;
    if ( ② ) {
        ③
    } else {
        print(B * w[1], v[1]);
        return 0;
    }
    for (int i = 2; i <= n; i ++)
        if (curV + v[i] <= B) {
            curV += v[i];
            curW += w[i];
        } else {
            print( ④ );
            return 0;
        }
    print( ⑤ );
    return 0;
}

③ 處應(yīng)填（ ）

第37題

（分?jǐn)?shù)背包）小 S 有 n 塊蛋糕，編號從 1 到 n。第 i 塊蛋糕的價值是 wi，體積是 vi。他有一個大小為 B 的盒子來裝這些蛋糕，也就是說裝入盒子的蛋糕的體積總和不能超過 B。

他打算選擇一些蛋糕裝入盒子，他希望盒子里裝的蛋糕的價值之和盡量大。

為了使盒子里的蛋糕價值之和更大，他可以任意切割蛋糕。具體來說，他可以選擇一個 α(0<α<1)，并將一塊價值是 w，體積為 v 的蛋糕切割成兩塊，其中一塊的價值是 αw，體積是 αv，另一塊的價值是 (1?α)w，體積是 (1?α)v。他可以重復(fù)無限次切割操作。

現(xiàn)要求編程輸出最大可能的價值，以分?jǐn)?shù)的形式輸出。

比如 n=3，B=8，三塊蛋糕的價值分別是 4、4、2，體積分別是 5、3、2。

那么最優(yōu)的方法就是將體積為 5 的蛋糕切成兩份，一份體積是 3，價值是 2.4，另一份體積是 2，價值是 1.61，然后把體積是 3 的那部分和后兩塊蛋糕打包進盒子。最優(yōu)的價值之和是 8.4，故程序輸出 42/5。

輸入的數(shù)據(jù)范圍為：1≤n≤1000，1≤B≤105，1≤wi,vi≤100。

提示：將所有的蛋糕按照性價比 wi/vi 從大到小排序后進行貪心選擇。

試補全程序。

#include <cstdio>
using namespace std;
const int maxn = 1005;
int n, B, w[maxn], v[maxn];
int gcd(int u, int v) {
    if (v == 0)
        return u;
    return gcd(v, u % v);
}
void print(int w, int v) {
    int d = gcd(w, v);
    w = w / d;
    v = v / d;
    if (v == 1)
        printf("%d\n", w);
    else
        printf("%d/%d\n", w, v);
}
void swap(int &x, int &y) {
    int t = x; x = y; y = t;
}
int main() {
    scanf("%d %d", &n, &B);
    for (int i = 1; i <= n; i ++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (int i = 1; i < n; i ++)
        for (int j = 1; j < n; j ++)
            if ( ① ) {
                swap(w[j], w[j + 1]);
                swap(v[j], v[j + 1]);
            }
    int curV, curW;
    if ( ② ) {
        ③
    } else {
        print(B * w[1], v[1]);
        return 0;
    }
    for (int i = 2; i <= n; i ++)
        if (curV + v[i] <= B) {
            curV += v[i];
            curW += w[i];
        } else {
            print( ④ );
            return 0;
        }
    print( ⑤ );
    return 0;
}

④ 處應(yīng)填（ ）

第38題

（分?jǐn)?shù)背包）小 S 有 n 塊蛋糕，編號從 1 到 n。第 i 塊蛋糕的價值是 wi，體積是 vi。他有一個大小為 B 的盒子來裝這些蛋糕，也就是說裝入盒子的蛋糕的體積總和不能超過 B。

他打算選擇一些蛋糕裝入盒子，他希望盒子里裝的蛋糕的價值之和盡量大。

為了使盒子里的蛋糕價值之和更大，他可以任意切割蛋糕。具體來說，他可以選擇一個 α(0<α<1)，并將一塊價值是 w，體積為 v 的蛋糕切割成兩塊，其中一塊的價值是 αw，體積是 αv，另一塊的價值是 (1?α)w，體積是 (1?α)v。他可以重復(fù)無限次切割操作。

現(xiàn)要求編程輸出最大可能的價值，以分?jǐn)?shù)的形式輸出。

比如 n=3，B=8，三塊蛋糕的價值分別是 4、4、2，體積分別是 5、3、2。

那么最優(yōu)的方法就是將體積為 5 的蛋糕切成兩份，一份體積是 3，價值是 2.4，另一份體積是 2，價值是 1.61，然后把體積是 3 的那部分和后兩塊蛋糕打包進盒子。最優(yōu)的價值之和是 8.4，故程序輸出 42/5。

輸入的數(shù)據(jù)范圍為：1≤n≤1000，1≤B≤105，1≤wi,vi≤100。

提示：將所有的蛋糕按照性價比 wi/vi 從大到小排序后進行貪心選擇。

試補全程序。

#include <cstdio>
using namespace std;

const int maxn = 1005;

int n, B, w[maxn], v[maxn];

int gcd(int u, int v) {
    if (v == 0)
        return u;
    return gcd(v, u % v);
}

void print(int w, int v) {
    int d = gcd(w, v);
    w = w / d;
    v = v / d;
    if (v == 1)
        printf("%d\n", w);
    else
        printf("%d/%d\n", w, v);
}

void swap(int &x, int &y) {
    int t = x; x = y; y = t;
}

int main() {
    scanf("%d %d", &n, &B);
    for (int i = 1; i <= n; i ++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (int i = 1; i < n; i ++)
        for (int j = 1; j < n; j ++)
            if ( ① ) {
                swap(w[j], w[j + 1]);
                swap(v[j], v[j + 1]);
            }
    int curV, curW;
    if ( ② ) {
        ③
    } else {
        print(B * w[1], v[1]);
        return 0;
    }

    for (int i = 2; i <= n; i ++)
        if (curV + v[i] <= B) {
            curV += v[i];
            curW += w[i];
        } else {
            print( ④ );
            return 0;
        }
    print( ⑤ );
    return 0;
}

⑤處應(yīng)填（ ）

第39題

（最優(yōu)子序列）取 m = 16，給出長度為 n 的整數(shù)序列 a1,a2,…,an(0≤ai≤2m)。對于一個二進制數(shù) x，定義其分值 w(x) 為x+popcnt(x)，其中 popcnt(x) 表示 x 二進制表示中 1 的個數(shù)。對于一個子序列 b1,b2,…,bk，定義其子序列分值 S 為 w(b1?b2)+w(b2?b3)+w(b3?b4)+…w(bk?1?bk)。其中? 表示按位異或。對于空子序列，規(guī)定其子序列分值為 0。求一個子序列似的其子序列的分值最大，輸出這個最大值。

輸入第一行包含一個整數(shù) n(1≤n≤40000)。接下來一行包含 n 個整數(shù)a1,a2,…,an。

提示：考慮優(yōu)化樸素的動態(tài)規(guī)劃算法，將前 m/2 位和后m /2位分開計算。

Max[x][y] 表示當(dāng)前的子序列下一個位置的高 8 位是 x、最后一個位置的低 8 位是 y 時的最大價值。

試補全程序。

#include <iostream>

using namespace std;

typedef long long LL;

const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];

int w(int x)
{
    int s = x;
    while (x)
    {
        ①;
        s++;
    }
    return s;
}

void to_max(LL &x, LL y)
{
    if (x < y)
        x = y;
}

int main()
{
    int n;
    LL ans = 0;
    cin >> n;
    for (int x = 0; x <= MS; x++)
        for (int y = 0; y <= MS; y++)
            Max[x][y] = -INF;
    for (int i = 1; i <= n; i++)
    {
        LL a;
        cin >> a;
        int x = ②, y = a & MS;
        LL v = ③;
        for (int z = 0; z <= MS; z++)
            to_max(v, ④);
        for (int z = 0; z <= MS; z++)
            ⑤;
        to_max(ans, v);
    }
    cout << ans << endl;
    return 0;
}

① 處應(yīng)填（ ）

第40題

（最優(yōu)子序列）取 m = 16，給出長度為 n 的整數(shù)序列 a1,a2,…,an(0≤ai≤2m)。對于一個二進制數(shù) x，定義其分值 w(x) 為x+popcnt(x)，其中 popcnt(x) 表示 x 二進制表示中 1 的個數(shù)。對于一個子序列 b1,b2,…,bk，定義其子序列分值 S 為 w(b1?b2)+w(b2?b3)+w(b3?b4)+…w(bk?1?bk)。其中? 表示按位異或。對于空子序列，規(guī)定其子序列分值為 0。求一個子序列似的其子序列的分值最大，輸出這個最大值。

輸入第一行包含一個整數(shù) n(1≤n≤40000)。接下來一行包含 n 個整數(shù)a1,a2,…,an。

提示：考慮優(yōu)化樸素的動態(tài)規(guī)劃算法，將前 m/2 位和后m /2位分開計算。

Max[x][y] 表示當(dāng)前的子序列下一個位置的高 8 位是 x、最后一個位置的低 8 位是 y 時的最大價值。

試補全程序。

#include <iostream>

using namespace std;

typedef long long LL;

const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];

int w(int x)
{
    int s = x;
    while (x)
    {
        ①;
        s++;
    }
    return s;
}

void to_max(LL &x, LL y)
{
    if (x < y)
        x = y;
}

int main()
{
    int n;
    LL ans = 0;
    cin >> n;
    for (int x = 0; x <= MS; x++)
        for (int y = 0; y <= MS; y++)
            Max[x][y] = -INF;
    for (int i = 1; i <= n; i++)
    {
        LL a;
        cin >> a;
        int x = ②, y = a & MS;
        LL v = ③;
        for (int z = 0; z <= MS; z++)
            to_max(v, ④);
        for (int z = 0; z <= MS; z++)
            ⑤;
        to_max(ans, v);
    }
    cout << ans << endl;
    return 0;
}

② 處應(yīng)填（ ）

第41題

（最優(yōu)子序列）取 m = 16，給出長度為 n 的整數(shù)序列 a1,a2,…,an(0≤ai≤2m)。對于一個二進制數(shù) x，定義其分值 w(x) 為x+popcnt(x)，其中 popcnt(x) 表示 x 二進制表示中 1 的個數(shù)。對于一個子序列 b1,b2,…,bk，定義其子序列分值 S 為 w(b1?b2)+w(b2?b3)+w(b3?b4)+…w(bk?1?bk)。其中? 表示按位異或。對于空子序列，規(guī)定其子序列分值為 0。求一個子序列似的其子序列的分值最大，輸出這個最大值。

輸入第一行包含一個整數(shù) n(1≤n≤40000)。接下來一行包含 n 個整數(shù)a1,a2,…,an。

提示：考慮優(yōu)化樸素的動態(tài)規(guī)劃算法，將前 m/2 位和后m /2位分開計算。

Max[x][y] 表示當(dāng)前的子序列下一個位置的高 8 位是 x、最后一個位置的低 8 位是 y 時的最大價值。

試補全程序。

#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];
int w(int x)
{
    int s = x;
    while (x)
    {
        ①;
        s++;
    }
    return s;
}
void to_max(LL &x, LL y)
{
    if (x < y)
        x = y;
}
int main()
{
    int n;
    LL ans = 0;
    cin >> n;
    for (int x = 0; x <= MS; x++)
        for (int y = 0; y <= MS; y++)
            Max[x][y] = -INF;
    for (int i = 1; i <= n; i++)
    {
        LL a;
        cin >> a;
        int x = ②, y = a & MS;
        LL v = ③;
        for (int z = 0; z <= MS; z++)
            to_max(v, ④);
        for (int z = 0; z <= MS; z++)
            ⑤;
        to_max(ans, v);
    }
    cout << ans << endl;
    return 0;
}

③ 處應(yīng)填（ ）

第42題

（最優(yōu)子序列）取 m = 16，給出長度為 n 的整數(shù)序列 a1,a2,…,an(0≤ai≤2m)。對于一個二進制數(shù) x，定義其分值 w(x) 為x+popcnt(x)，其中 popcnt(x) 表示 x 二進制表示中 1 的個數(shù)。對于一個子序列 b1,b2,…,bk，定義其子序列分值 S 為 w(b1?b2)+w(b2?b3)+w(b3?b4)+…w(bk?1?bk)。其中? 表示按位異或。對于空子序列，規(guī)定其子序列分值為 0。求一個子序列似的其子序列的分值最大，輸出這個最大值。

輸入第一行包含一個整數(shù) n(1≤n≤40000)。接下來一行包含 n 個整數(shù)a1,a2,…,an。

提示：考慮優(yōu)化樸素的動態(tài)規(guī)劃算法，將前 m/2 位和后m /2位分開計算。

Max[x][y] 表示當(dāng)前的子序列下一個位置的高 8 位是 x、最后一個位置的低 8 位是 y 時的最大價值。

試補全程序。

#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];
int w(int x)
{
    int s = x;
    while (x)
    {
        ①;
        s++;
    }
    return s;
}
void to_max(LL &x, LL y)
{
    if (x < y)
        x = y;
}
int main()
{
    int n;
    LL ans = 0;
    cin >> n;
    for (int x = 0; x <= MS; x++)
        for (int y = 0; y <= MS; y++)
            Max[x][y] = -INF;
    for (int i = 1; i <= n; i++)
    {
        LL a;
        cin >> a;
        int x = ②, y = a & MS;
        LL v = ③;
        for (int z = 0; z <= MS; z++)
            to_max(v, ④);
        for (int z = 0; z <= MS; z++)
            ⑤;
        to_max(ans, v);
    }
    cout << ans << endl;
    return 0;
}

④ 處應(yīng)填（ ）

第43題

（最優(yōu)子序列）取 m = 16，給出長度為 n 的整數(shù)序列 a1,a2,…,an(0≤ai≤2m)。對于一個二進制數(shù) x，定義其分值 w(x) 為x+popcnt(x)，其中 popcnt(x) 表示 x 二進制表示中 1 的個數(shù)。對于一個子序列 b1,b2,…,bk，定義其子序列分值 S 為 w(b1?b2)+w(b2?b3)+w(b3?b4)+…w(bk?1?bk)。其中? 表示按位異或。對于空子序列，規(guī)定其子序列分值為 0。求一個子序列似的其子序列的分值最大，輸出這個最大值。

輸入第一行包含一個整數(shù) n(1≤n≤40000)。接下來一行包含 n 個整數(shù)a1,a2,…,an。

提示：考慮優(yōu)化樸素的動態(tài)規(guī)劃算法，將前 m/2 位和后m /2位分開計算。

Max[x][y] 表示當(dāng)前的子序列下一個位置的高 8 位是 x、最后一個位置的低 8 位是 y 時的最大價值。

試補全程序。

#include <iostream>

using namespace std;

typedef long long LL;

const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];

int w(int x)
{
    int s = x;
    while (x)
    {
        ①;
        s++;
    }
    return s;
}

void to_max(LL &x, LL y)
{
    if (x < y)
        x = y;
}

int main()
{
    int n;
    LL ans = 0;
    cin >> n;
    for (int x = 0; x <= MS; x++)
        for (int y = 0; y <= MS; y++)
            Max[x][y] = -INF;
    for (int i = 1; i <= n; i++)
    {
        LL a;
        cin >> a;
        int x = ②, y = a & MS;
        LL v = ③;
        for (int z = 0; z <= MS; z++)
            to_max(v, ④);
        for (int z = 0; z <= MS; z++)
            ⑤;
        to_max(ans, v);
    }
    cout << ans << endl;
    return 0;
}

⑤處應(yīng)填（ ）