第1題

若有定義 int a = 7, float x = 2.5, y = 4.7;，則表達(dá)式 x + a % 3 * (int) (x + y) % 2 的值是（ ）

第2題

下列屬于圖像文件格式的（ ）

第3題

下面哪個(gè)選項(xiàng)是11 1011 1001 0111 和 01 0110 1110 1011進(jìn)行邏輯或運(yùn)算的結(jié)果( )。

第4題

編譯器的作用是 ( )。

第5題

設(shè)變量 x 為 float 型且已賦值，下列哪條語(yǔ)句能將 x 中的數(shù)值保留到小數(shù)點(diǎn)后兩位，并將第三位四舍五入 ( )。

第6題

由數(shù)字 1, 1, 2, 4, 8, 8組成的不同的 4 位數(shù)的個(gè)數(shù)是 ( )。

第7題

排序的算法很多，若按排序的穩(wěn)定性和不穩(wěn)定性分裂，下面算法中 ( ) 是不穩(wěn)定排序。

第8題

G 是一個(gè)非連通無(wú)向圖（沒(méi)有重邊和自環(huán)），共有 28 條邊，則該圖至少有 ( )。

第9題

一些數(shù)字可以顛倒過(guò)來(lái)看，例如 0、1、8 顛倒過(guò)來(lái)還是本身，6 顛倒過(guò)來(lái)是 9，9 顛倒過(guò)來(lái)看還是 6，其他數(shù)字顛倒過(guò)來(lái)都不構(gòu)成數(shù)字。類似的，一些多位數(shù)也可以顛倒過(guò)來(lái)看，比如 106 顛倒過(guò)來(lái)是 901。假設(shè)某個(gè)城市的車牌只由 5 位數(shù)字組成，每一位都可以取 0 到 9。請(qǐng)問(wèn)這個(gè)城市最多有多少個(gè)車牌倒過(guò)來(lái)恰好還是原來(lái)的車牌，并且車牌上的 5 位數(shù)能被 3 整除 ( )。

第10題

一次期末考試，某班有 15 人數(shù)學(xué)得滿分，有 12 人語(yǔ)文得滿分，共有 4 人語(yǔ)文、數(shù)學(xué)都是滿分，那么這個(gè)班至少有一門滿分的同學(xué)有多少人 ( )。

第11題

設(shè) A 和 B 是兩個(gè)長(zhǎng)為 n 的有序數(shù)組，現(xiàn)在需要將 A 和 B 合并成一個(gè)排好序的數(shù)組，請(qǐng)問(wèn)在歸并算法中，在最壞情況下至少要做多少次比較( )。

第12題

以下哪個(gè)結(jié)構(gòu)可以用來(lái)存圖 ( )。

第13題

以下哪些算法不屬于貪心算法 ( )。

第14題

有一個(gè)等比數(shù)列，共有奇數(shù)項(xiàng)，其中第一項(xiàng)和最后一項(xiàng)分別是 2 和 118098，中間一項(xiàng)是 486，請(qǐng)問(wèn)以下那個(gè)數(shù)是可能的公比 ( )。

第15題

由正實(shí)數(shù)構(gòu)成的數(shù)字三角形排列如圖所示，第一行為數(shù)字 a_1,1，第二行的數(shù)從左到右依次為 a_2,1、 a_2,2，第 n 行的數(shù)為 a_n,1、a_n,2...a_n,n。從 a_1,1 開(kāi)始，每一行的數(shù)a_i,j 只有兩條邊可以分別通向下一行的兩個(gè)數(shù) a_i+1,j 和 a_i+1,j+1。用動(dòng)態(tài)規(guī)劃算法找出一條從 a_1,1 向下通到 a_n,1、 a_n,2...a_n,n 中的某個(gè)路徑，是的該路徑上的數(shù)之和最大。

令 C[i][j]是從 a_1,1 到 a_i,j 的路徑上的數(shù)值，并且 C[i][0] = C[0][j] = 0，則 C[i][j] = ( )

第16題

#include <cstdio>
using namespace std;
int n;
int a[100];

int main() {
   scanf("%d", &n);
   for (int i = 1; i <= n; ++i)
       scanf("%d", &a[i]);
   int ans = 1;
   for (int i = 1; i <= n; ++i) {
       if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d
", ans);
   }
   return 0;
}

1）第 16 行輸出 ans 時(shí)，ans 的值一定大于 i。

第17題

#include <cstdio>
using namespace std;
int n;
int a[100];

int main() {
   scanf("%d", &n);
   for (int i = 1; i <= n; ++i)
       scanf("%d", &a[i]);
   int ans = 1;
   for (int i = 1; i <= n; ++i) {
       if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d
", ans);
   }
   return 0;
}

2）程序輸出的 ans 小于等于 n。

第18題

#include <cstdio>
using namespace std;
int n;
int a[100];

int main() {
   scanf("%d", &n);
   for (int i = 1; i <= n; ++i)
       scanf("%d", &a[i]);
   int ans = 1;
   for (int i = 1; i <= n; ++i) {
       if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d
", ans);
   }
   return 0;
}

3）若將第 12 行的 “<” 改為 “!=” 程序輸出的結(jié)果不會(huì)改變。

第19題

#include <cstdio>
using namespace std;
int n;
int a[100];

int main() {
   scanf("%d", &n);
   for (int i = 1; i <= n; ++i)
       scanf("%d", &a[i]);
   int ans = 1;
   for (int i = 1; i <= n; ++i) {
       if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d
", ans);
   }
   return 0;
}

4）當(dāng)程序執(zhí)行到第 16 行時(shí)，若 ans - i > 2，則 a[i+1]≤a[i]。

第20題

#include <cstdio>
using namespace std;
int n;
int a[100];

int main() {
   scanf("%d", &n);
   for (int i = 1; i <= n; ++i)
       scanf("%d", &a[i]);
   int ans = 1;
   for (int i = 1; i <= n; ++i) {
       if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d
", ans);
   }
   return 0;
}

5）若輸入的 a 數(shù)組是一個(gè)嚴(yán)格單調(diào)遞增的數(shù)列，此程序的時(shí)間復(fù)雜度是

第21題

#include <cstdio>
using namespace std;
int n;
int a[100];

int main() {
   scanf("%d", &n);
   for (int i = 1; i <= n; ++i)
       scanf("%d", &a[i]);
   int ans = 1;
   for (int i = 1; i <= n; ++i) {
       if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d
", ans);
   }
   return 0;
}

6)最壞情況下，此程序的時(shí)間復(fù)雜度為：

第22題

#include <iostream>
using namespace std;
const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];

int getRoot(int v) {
    if (fa[v] == v) return v;
    return getRoot(fa[v]);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        fa[i] = i;
        cnt[i] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, x, y;
        cin >> a >> b;
        x = getRoot(a);
        y = getRoot(b);
        ans += cnt[x] * cnt[y];
        fa[x] = y;
        cnt[y] += cnt[x];
    }
    cout << ans << endl;
    return 0;
}

1)輸入的 a 和 b 的值應(yīng)在 [0,n?1] 的范圍內(nèi)

第23題

#include <iostream>
using namespace std;
const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];

int getRoot(int v) {
    if (fa[v] == v) return v;
    return getRoot(fa[v]);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        fa[i] = i;
        cnt[i] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, x, y;
        cin >> a >> b;
        x = getRoot(a);
        y = getRoot(b);
        ans += cnt[x] * cnt[y];
        fa[x] = y;
        cnt[y] += cnt[x];
    }
    cout << ans << endl;
    return 0;
}
1)輸入的 a

2)第 16 行改成 fa[i]=0;，不影響程序運(yùn)行結(jié)果

第24題

#include <iostream>
using namespace std;
const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];

int getRoot(int v) {
    if (fa[v] == v) return v;
    return getRoot(fa[v]);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        fa[i] = i;
        cnt[i] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, x, y;
        cin >> a >> b;
        x = getRoot(a);
        y = getRoot(b);
        ans += cnt[x] * cnt[y];
        fa[x] = y;
        cnt[y] += cnt[x];
    }
    cout << ans << endl;
    return 0;
}

3)若輸入的 a 和 b 值均在 [0,n?1] 的范圍內(nèi)，則對(duì)于任意 0≤i<n，都有 0≤fa[i]<n。

第25題

#include <iostream>
using namespace std;
const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];

int getRoot(int v) {
    if (fa[v] == v) return v;
    return getRoot(fa[v]);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        fa[i] = i;
        cnt[i] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, x, y;
        cin >> a >> b;
        x = getRoot(a);
        y = getRoot(b);
        ans += cnt[x] * cnt[y];
        fa[x] = y;
        cnt[y] += cnt[x];
    }
    cout << ans << endl;
    return 0;
}

4)若輸入的 a 和 b 值均在 [0,n?1] 的范圍內(nèi)，則對(duì)于任意 0≤i<n，都有 1≤cnt[i]≤n。

第26題

#include <iostream>
using namespace std;
const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];

int getRoot(int v) {
    if (fa[v] == v) return v;
    return getRoot(fa[v]);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        fa[i] = i;
        cnt[i] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, x, y;
        cin >> a >> b;
        x = getRoot(a);
        y = getRoot(b);
        ans += cnt[x] * cnt[y];
        fa[x] = y;
        cnt[y] += cnt[x];
    }
    cout << ans << endl;
    return 0;
}

5)當(dāng) n 等于 50 時(shí)，若 a、b 的值都在 [0,49] 的范圍內(nèi)，且在第 25 行時(shí)總是不等于 y，那么輸出為 ( )

第27題

#include <iostream>
using namespace std;
const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];

int getRoot(int v) {
    if (fa[v] == v) return v;
    return getRoot(fa[v]);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        fa[i] = i;
        cnt[i] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, x, y;
        cin >> a >> b;
        x = getRoot(a);
        y = getRoot(b);
        ans += cnt[x] * cnt[y];
        fa[x] = y;
        cnt[y] += cnt[x];
    }
    cout << ans << endl;
    return 0;
}

6）此程序的時(shí)間復(fù)雜度是（ ）

第28題

本題t是s的子序列的意思是：從s中刪去若干個(gè)字符，可以得到t。特別的，如果s == t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“acd”不是“abcde”的子序列。

S[x..y]表示s[x]…s[y]共 y-x+1y?x+1 個(gè)字符構(gòu)成的字符串，若 x>yx>y 則s[x..y]是空串。t[x..y]同理。

#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];

int main() {
    cin >> s >> t;
    int slen = s.length(), tlen= t.length();

    for (int i = 0, j = 0; i < slen; ++i) {
        if (j < tlen && s[i] == t[j]) ++j;
        pre[i] = j;// t[0..j-1]是s[0..i]的子序列
    }

    for (int i = slen - 1, j = tlen - 1; i >= 0; --i) {
        if(j >= 0 && s[i] == t[j]) --j;
        suf[i]= j; //t[j+1..tlen-1]是s[i..slen-1]的子序列
    }

    suf[slen] = tlen -1;
    int ans = 0;
    for (int i = 0, j = 0, tmp= 0; i <= slen; ++i) {
        while (j <= slen && tmp >= suf[j] + 1) ++j;
        ans = max(ans, j - i - 1);
        tmp = pre[i];
    }
    cout << ans << endl;
    return 0;
}

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

1）程序輸出時(shí)，suf數(shù)組滿足：對(duì)任意 0≤i<slen，suf[i]≤suf[i+1]。

第29題

本題t是s的子序列的意思是：從s中刪去若干個(gè)字符，可以得到t。特別的，如果s == t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“acd”不是“abcde”的子序列。

S[x..y]表示s[x]…s[y]共 y-x+1y?x+1 個(gè)字符構(gòu)成的字符串，若 x>yx>y 則s[x..y]是空串。t[x..y]同理。

#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];

int main() {
    cin >> s >> t;
    int slen = s.length(), tlen= t.length();

    for (int i = 0, j = 0; i < slen; ++i) {
        if (j < tlen && s[i] == t[j]) ++j;
        pre[i] = j;// t[0..j-1]是s[0..i]的子序列
    }

    for (int i = slen - 1, j = tlen - 1; i >= 0; --i) {
        if(j >= 0 && s[i] == t[j]) --j;
        suf[i]= j; //t[j+1..tlen-1]是s[i..slen-1]的子序列
    }

    suf[slen] = tlen -1;
    int ans = 0;
    for (int i = 0, j = 0, tmp= 0; i <= slen; ++i) {
        while (j <= slen && tmp >= suf[j] + 1) ++j;
        ans = max(ans, j - i - 1);
        tmp = pre[i];
    }
    cout << ans << endl;
    return 0;
}

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

2）當(dāng) t 是 s 的子序列時(shí)，輸出一定不為 0。

第30題

本題t是s的子序列的意思是：從s中刪去若干個(gè)字符，可以得到t。特別的，如果s == t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“acd”不是“abcde”的子序列。

S[x..y]表示s[x]…s[y]共 y-x+1y?x+1 個(gè)字符構(gòu)成的字符串，若 x>yx>y 則s[x..y]是空串。t[x..y]同理。

#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];

int main() {
    cin >> s >> t;
    int slen = s.length(), tlen= t.length();

    for (int i = 0, j = 0; i < slen; ++i) {
        if (j < tlen && s[i] == t[j]) ++j;
        pre[i] = j;// t[0..j-1]是s[0..i]的子序列
    }

    for (int i = slen - 1, j = tlen - 1; i >= 0; --i) {
        if(j >= 0 && s[i] == t[j]) --j;
        suf[i]= j; //t[j+1..tlen-1]是s[i..slen-1]的子序列
    }

    suf[slen] = tlen -1;
    int ans = 0;
    for (int i = 0, j = 0, tmp= 0; i <= slen; ++i) {
        while (j <= slen && tmp >= suf[j] + 1) ++j;
        ans = max(ans, j - i - 1);
        tmp = pre[i];
    }
    cout << ans << endl;
    return 0;
}

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

3）程序運(yùn)行到第 23行時(shí)，j - i- 1 一定不小于 0

第31題

本題t是s的子序列的意思是：從s中刪去若干個(gè)字符，可以得到t。特別的，如果s == t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“acd”不是“abcde”的子序列。

S[x..y]表示s[x]…s[y]共 y-x+1y?x+1 個(gè)字符構(gòu)成的字符串，若 x>yx>y 則s[x..y]是空串。t[x..y]同理。

#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];

int main() {
    cin >> s >> t;
    int slen = s.length(), tlen= t.length();

    for (int i = 0, j = 0; i < slen; ++i) {
        if (j < tlen && s[i] == t[j]) ++j;
        pre[i] = j;// t[0..j-1]是s[0..i]的子序列
    }

    for (int i = slen - 1, j = tlen - 1; i >= 0; --i) {
        if(j >= 0 && s[i] == t[j]) --j;
        suf[i]= j; //t[j+1..tlen-1]是s[i..slen-1]的子序列
    }

    suf[slen] = tlen -1;
    int ans = 0;
    for (int i = 0, j = 0, tmp= 0; i <= slen; ++i) {
        while (j <= slen && tmp >= suf[j] + 1) ++j;
        ans = max(ans, j - i - 1);
        tmp = pre[i];
    }
    cout << ans << endl;
    return 0;
}

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

4）當(dāng) t 是 s 的子序列時(shí)，pre 數(shù)組和 suf 數(shù)組滿足：對(duì)任意 0≤i<slen，pre[i]>suf[i+1]。

第32題

本題t是s的子序列的意思是：從s中刪去若干個(gè)字符，可以得到t。特別的，如果s == t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“acd”不是“abcde”的子序列。

S[x..y]表示s[x]…s[y]共 y-x+1y?x+1 個(gè)字符構(gòu)成的字符串，若 x>yx>y 則s[x..y]是空串。t[x..y]同理。

#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];

int main() {
    cin >> s >> t;
    int slen = s.length(), tlen= t.length();

    for (int i = 0, j = 0; i < slen; ++i) {
        if (j < tlen && s[i] == t[j]) ++j;
        pre[i] = j;// t[0..j-1]是s[0..i]的子序列
    }

    for (int i = slen - 1, j = tlen - 1; i >= 0; --i) {
        if(j >= 0 && s[i] == t[j]) --j;
        suf[i]= j; //t[j+1..tlen-1]是s[i..slen-1]的子序列
    }

    suf[slen] = tlen -1;
    int ans = 0;
    for (int i = 0, j = 0, tmp= 0; i <= slen; ++i) {
        while (j <= slen && tmp >= suf[j] + 1) ++j;
        ans = max(ans, j - i - 1);
        tmp = pre[i];
    }
    cout << ans << endl;
    return 0;
}

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

5）若 tlen = 10，輸出為 0 ，則 slen 最小為：

第33題

本題t是s的子序列的意思是：從s中刪去若干個(gè)字符，可以得到t。特別的，如果s == t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“acd”不是“abcde”的子序列。

S[x..y]表示s[x]…s[y]共 y-x+1y?x+1 個(gè)字符構(gòu)成的字符串，若 x>yx>y 則s[x..y]是空串。t[x..y]同理。

#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];

int main() {
    cin >> s >> t;
    int slen = s.length(), tlen= t.length();

    for (int i = 0, j = 0; i < slen; ++i) {
        if (j < tlen && s[i] == t[j]) ++j;
        pre[i] = j;// t[0..j-1]是s[0..i]的子序列
    }

    for (int i = slen - 1, j = tlen - 1; i >= 0; --i) {
        if(j >= 0 && s[i] == t[j]) --j;
        suf[i]= j; //t[j+1..tlen-1]是s[i..slen-1]的子序列
    }

    suf[slen] = tlen -1;
    int ans = 0;
    for (int i = 0, j = 0, tmp= 0; i <= slen; ++i) {
        while (j <= slen && tmp >= suf[j] + 1) ++j;
        ans = max(ans, j - i - 1);
        tmp = pre[i];
    }
    cout << ans << endl;
    return 0;
}

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

6）若 tlen = 10， 輸出為 2，則 slen 最小為

第34題

（匠人的自我修養(yǎng)）一個(gè)匠人決定要學(xué)習(xí) n 個(gè)新技術(shù)，要想成功學(xué)習(xí)一個(gè)新技術(shù)，他不僅要擁有一定的經(jīng)驗(yàn)值，而且還必須要先學(xué)會(huì)若干個(gè)相關(guān)的技術(shù)。學(xué)會(huì)一個(gè)新技術(shù)之后，他的經(jīng)驗(yàn)值會(huì)增加一個(gè)對(duì)應(yīng)的值。給定每個(gè)技術(shù)的學(xué)習(xí)條件和習(xí)得后獲得的經(jīng)驗(yàn)值，給定他已有的經(jīng)驗(yàn)值，請(qǐng)問(wèn)他最多能學(xué)會(huì)多少個(gè)新技術(shù)。

輸入第一行有兩個(gè)數(shù)，分別為新技術(shù)個(gè)數(shù) n(1≤n≤10³)，以及已有經(jīng)驗(yàn)值(≤10⁷)。

接下來(lái) n 行。第 i 行的兩個(gè)整數(shù)，分別表示學(xué)習(xí)第 i 個(gè)技術(shù)所需的最低經(jīng)驗(yàn)值 (≤10⁷)，以及學(xué)會(huì)第 i 個(gè)技術(shù)后可獲得的經(jīng)驗(yàn)值 (≤10⁴)。

接下來(lái) n 行。第 i 行的第一個(gè)數(shù) m_i(0≤m_i<n)，表示第 i 個(gè)技術(shù)的相關(guān)技術(shù)數(shù)量。緊跟著 m 個(gè)兩兩不同的數(shù)，表示第 i 個(gè)技術(shù)的相關(guān)技術(shù)編號(hào)，輸出最多能學(xué)會(huì)的新技術(shù)個(gè)數(shù)。

下面的程序已 O(n²)的時(shí)間復(fù)雜完成這個(gè)問(wèn)題，試補(bǔ)全程序。

#include<cstdio>
using namespace std;
const int maxn = 1001;

int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn],bonus[maxn];
int points;
bool find(){
    int target=-1;
    for (int i = 1;i<=n;++i)
        if(① && ②){
            target = i;
            break;
    }
    if(target==-1)
        return false;
    unlock[target]=-1;
    ③
    for (int i=0;i<cnt[target];++i)
        ④
    return true;
}

int main(){
    scanf("%d%d",&n, &points);
    for (int i =1; i<=n;++i){
        cnt [i]=0;
        scanf("%d%d",&threshold[i],&bonus[i]);
    }
    for (int i=1;i<=n;++i){
        int m;
        scanf("%d",&m);
        ⑤
        for (int j=0; j<m ;++j){
            int fa;
            scanf("%d", &fa);
            child [fa][cnt[fa]]=i;
            ++cnt[fa];
        }
    }

    int ans = 0;
    while(find())
        ++ans;

    printf("%d
", ans);
    return 0;
}

① 處應(yīng)填（ ）

第35題

（匠人的自我修養(yǎng)）一個(gè)匠人決定要學(xué)習(xí) n 個(gè)新技術(shù)，要想成功學(xué)習(xí)一個(gè)新技術(shù)，他不僅要擁有一定的經(jīng)驗(yàn)值，而且還必須要先學(xué)會(huì)若干個(gè)相關(guān)的技術(shù)。學(xué)會(huì)一個(gè)新技術(shù)之后，他的經(jīng)驗(yàn)值會(huì)增加一個(gè)對(duì)應(yīng)的值。給定每個(gè)技術(shù)的學(xué)習(xí)條件和習(xí)得后獲得的經(jīng)驗(yàn)值，給定他已有的經(jīng)驗(yàn)值，請(qǐng)問(wèn)他最多能學(xué)會(huì)多少個(gè)新技術(shù)。

輸入第一行有兩個(gè)數(shù)，分別為新技術(shù)個(gè)數(shù) n(1≤n≤103)，以及已有經(jīng)驗(yàn)值(≤107)。

接下來(lái) n 行。第 i 行的兩個(gè)整數(shù)，分別表示學(xué)習(xí)第 i 個(gè)技術(shù)所需的最低經(jīng)驗(yàn)值 (≤107)，以及學(xué)會(huì)第 i 個(gè)技術(shù)后可獲得的經(jīng)驗(yàn)值 (≤104)。

接下來(lái) n 行。第 i 行的第一個(gè)數(shù) mi(0≤mi<n)，表示第 i 個(gè)技術(shù)的相關(guān)技術(shù)數(shù)量。緊跟著 m 個(gè)兩兩不同的數(shù)，表示第 i 個(gè)技術(shù)的相關(guān)技術(shù)編號(hào)，輸出最多能學(xué)會(huì)的新技術(shù)個(gè)數(shù)。

下面的程序已 O(n2)的時(shí)間復(fù)雜完成這個(gè)問(wèn)題，試補(bǔ)全程序。

#include<cstdio>
using namespace std;
const int maxn = 1001;
int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn],bonus[maxn];
int points;
bool find(){
    int target=-1;
    for (int i = 1;i<=n;++i)
        if(① && ②){
            target = i;
            break;
    }
    if(target==-1)
        return false;
    unlock[target]=-1;
    ③
    for (int i=0;i<cnt[target];++i)
        ④
    return true;
}
int main(){
    scanf("%d%d",&n, &points);
    for (int i =1; i<=n;++i){
        cnt [i]=0;
        scanf("%d%d",&threshold[i],&bonus[i]);
    }
    for (int i=1;i<=n;++i){
        int m;
        scanf("%d",&m);
        ⑤
        for (int j=0; j<m ;++j){
            int fa;
            scanf("%d", &fa);
            child [fa][cnt[fa]]=i;
            ++cnt[fa];
        }
    }
    int ans = 0;
    while(find())
        ++ans;
    printf("%d
", ans);
    return 0;
}

② 處應(yīng)填（ ）

第36題

（匠人的自我修養(yǎng)）一個(gè)匠人決定要學(xué)習(xí) n 個(gè)新技術(shù)，要想成功學(xué)習(xí)一個(gè)新技術(shù)，他不僅要擁有一定的經(jīng)驗(yàn)值，而且還必須要先學(xué)會(huì)若干個(gè)相關(guān)的技術(shù)。學(xué)會(huì)一個(gè)新技術(shù)之后，他的經(jīng)驗(yàn)值會(huì)增加一個(gè)對(duì)應(yīng)的值。給定每個(gè)技術(shù)的學(xué)習(xí)條件和習(xí)得后獲得的經(jīng)驗(yàn)值，給定他已有的經(jīng)驗(yàn)值，請(qǐng)問(wèn)他最多能學(xué)會(huì)多少個(gè)新技術(shù)。

輸入第一行有兩個(gè)數(shù)，分別為新技術(shù)個(gè)數(shù) n(1≤n≤103)，以及已有經(jīng)驗(yàn)值(≤107)。

接下來(lái) n 行。第 i 行的兩個(gè)整數(shù)，分別表示學(xué)習(xí)第 i 個(gè)技術(shù)所需的最低經(jīng)驗(yàn)值 (≤107)，以及學(xué)會(huì)第 i 個(gè)技術(shù)后可獲得的經(jīng)驗(yàn)值 (≤104)。

接下來(lái) n 行。第 i 行的第一個(gè)數(shù) mi(0≤mi<n)，表示第 i 個(gè)技術(shù)的相關(guān)技術(shù)數(shù)量。緊跟著 m 個(gè)兩兩不同的數(shù)，表示第 i 個(gè)技術(shù)的相關(guān)技術(shù)編號(hào)，輸出最多能學(xué)會(huì)的新技術(shù)個(gè)數(shù)。

下面的程序已 O(n2)的時(shí)間復(fù)雜完成這個(gè)問(wèn)題，試補(bǔ)全程序。

#include<cstdio>
using namespace std;
const int maxn = 1001;
int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn],bonus[maxn];
int points;
bool find(){
    int target=-1;
    for (int i = 1;i<=n;++i)
        if(① && ②){
            target = i;
            break;
    }
    if(target==-1)
        return false;
    unlock[target]=-1;
    ③
    for (int i=0;i<cnt[target];++i)
        ④
    return true;
}
int main(){
    scanf("%d%d",&n, &points);
    for (int i =1; i<=n;++i){
        cnt [i]=0;
        scanf("%d%d",&threshold[i],&bonus[i]);
    }
    for (int i=1;i<=n;++i){
        int m;
        scanf("%d",&m);
        ⑤
        for (int j=0; j<m ;++j){
            int fa;
            scanf("%d", &fa);
            child [fa][cnt[fa]]=i;
            ++cnt[fa];
        }
    }
    int ans = 0;
    while(find())
        ++ans;
    printf("%d
", ans);
    return 0;
}

③ 處應(yīng)填（ ）

第37題

（匠人的自我修養(yǎng)）一個(gè)匠人決定要學(xué)習(xí) n 個(gè)新技術(shù)，要想成功學(xué)習(xí)一個(gè)新技術(shù)，他不僅要擁有一定的經(jīng)驗(yàn)值，而且還必須要先學(xué)會(huì)若干個(gè)相關(guān)的技術(shù)。學(xué)會(huì)一個(gè)新技術(shù)之后，他的經(jīng)驗(yàn)值會(huì)增加一個(gè)對(duì)應(yīng)的值。給定每個(gè)技術(shù)的學(xué)習(xí)條件和習(xí)得后獲得的經(jīng)驗(yàn)值，給定他已有的經(jīng)驗(yàn)值，請(qǐng)問(wèn)他最多能學(xué)會(huì)多少個(gè)新技術(shù)。

輸入第一行有兩個(gè)數(shù)，分別為新技術(shù)個(gè)數(shù) n(1≤n≤103)，以及已有經(jīng)驗(yàn)值(≤107)。

接下來(lái) n 行。第 i 行的兩個(gè)整數(shù)，分別表示學(xué)習(xí)第 i 個(gè)技術(shù)所需的最低經(jīng)驗(yàn)值 (≤107)，以及學(xué)會(huì)第 i 個(gè)技術(shù)后可獲得的經(jīng)驗(yàn)值 (≤104)。

接下來(lái) n 行。第 i 行的第一個(gè)數(shù) mi(0≤mi<n)，表示第 i 個(gè)技術(shù)的相關(guān)技術(shù)數(shù)量。緊跟著 m 個(gè)兩兩不同的數(shù)，表示第 i 個(gè)技術(shù)的相關(guān)技術(shù)編號(hào)，輸出最多能學(xué)會(huì)的新技術(shù)個(gè)數(shù)。

下面的程序已 O(n2)的時(shí)間復(fù)雜完成這個(gè)問(wèn)題，試補(bǔ)全程序。

#include<cstdio>
using namespace std;
const int maxn = 1001;

int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn],bonus[maxn];
int points;
bool find(){
    int target=-1;
    for (int i = 1;i<=n;++i)
        if(① && ②){
            target = i;
            break;
    }
    if(target==-1)
        return false;
    unlock[target]=-1;
    ③
    for (int i=0;i<cnt[target];++i)
        ④
    return true;
}

int main(){
    scanf("%d%d",&n, &points);
    for (int i =1; i<=n;++i){
        cnt [i]=0;
        scanf("%d%d",&threshold[i],&bonus[i]);
    }
    for (int i=1;i<=n;++i){
        int m;
        scanf("%d",&m);
        ⑤
        for (int j=0; j<m ;++j){
            int fa;
            scanf("%d", &fa);
            child [fa][cnt[fa]]=i;
            ++cnt[fa];
        }
    }

    int ans = 0;
    while(find())
        ++ans;

    printf("%d
", ans);
    return 0;
}

④ 處應(yīng)填（ ）

第38題

（匠人的自我修養(yǎng)）一個(gè)匠人決定要學(xué)習(xí) n 個(gè)新技術(shù)，要想成功學(xué)習(xí)一個(gè)新技術(shù)，他不僅要擁有一定的經(jīng)驗(yàn)值，而且還必須要先學(xué)會(huì)若干個(gè)相關(guān)的技術(shù)。學(xué)會(huì)一個(gè)新技術(shù)之后，他的經(jīng)驗(yàn)值會(huì)增加一個(gè)對(duì)應(yīng)的值。給定每個(gè)技術(shù)的學(xué)習(xí)條件和習(xí)得后獲得的經(jīng)驗(yàn)值，給定他已有的經(jīng)驗(yàn)值，請(qǐng)問(wèn)他最多能學(xué)會(huì)多少個(gè)新技術(shù)。

輸入第一行有兩個(gè)數(shù)，分別為新技術(shù)個(gè)數(shù) n(1≤n≤103)，以及已有經(jīng)驗(yàn)值(≤107)。

接下來(lái) n 行。第 i 行的兩個(gè)整數(shù)，分別表示學(xué)習(xí)第 i 個(gè)技術(shù)所需的最低經(jīng)驗(yàn)值 (≤107)，以及學(xué)會(huì)第 i 個(gè)技術(shù)后可獲得的經(jīng)驗(yàn)值 (≤104)。

接下來(lái) n 行。第 i 行的第一個(gè)數(shù) mi(0≤mi<n)，表示第 i 個(gè)技術(shù)的相關(guān)技術(shù)數(shù)量。緊跟著 m 個(gè)兩兩不同的數(shù)，表示第 i 個(gè)技術(shù)的相關(guān)技術(shù)編號(hào)，輸出最多能學(xué)會(huì)的新技術(shù)個(gè)數(shù)。

下面的程序已 O(n2)的時(shí)間復(fù)雜完成這個(gè)問(wèn)題，試補(bǔ)全程序。

#include<cstdio>
using namespace std;
const int maxn = 1001;

int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn],bonus[maxn];
int points;
bool find(){
    int target=-1;
    for (int i = 1;i<=n;++i)
        if(① && ②){
            target = i;
            break;
    }
    if(target==-1)
        return false;
    unlock[target]=-1;
    ③
    for (int i=0;i<cnt[target];++i)
        ④
    return true;
}

int main(){
    scanf("%d%d",&n, &points);
    for (int i =1; i<=n;++i){
        cnt [i]=0;
        scanf("%d%d",&threshold[i],&bonus[i]);
    }
    for (int i=1;i<=n;++i){
        int m;
        scanf("%d",&m);
        ⑤
        for (int j=0; j<m ;++j){
            int fa;
            scanf("%d", &fa);
            child [fa][cnt[fa]]=i;
            ++cnt[fa];
        }
    }

    int ans = 0;
    while(find())
        ++ans;

    printf("%d
", ans);
    return 0;
}

⑤處應(yīng)填（ ）

第39題

（取石子）Alice 和 Bob 兩個(gè)人在玩取石子游戲，他們制定了 n 條取石子的規(guī)則，第 i 條規(guī)則為：如果剩余的石子個(gè)數(shù)大于等于 a[i] 且大于等于 b[i]，那么她們可以取走 b[i] 個(gè)石子。他們輪流取石子。如果輪到某個(gè)人取石子，而她們無(wú)法按照任何規(guī)則取走石子，那么他就輸了，一開(kāi)始石子有 m 個(gè)。請(qǐng)問(wèn)先取石子的人是否有必勝的方法？

輸入第一行有兩個(gè)正整數(shù)，分別為規(guī)則個(gè)數(shù) n(1≤n≤64),以及石子個(gè)數(shù) m(≤10⁷)。

接下來(lái) n 行。第i行有兩個(gè)正整數(shù) a[i]和 b[i]。1≤a[i]≤10⁷,b[i]≤64

如果先取石子的人必勝，那么輸出“Win”，否則輸出“Loss”

提示：

可以使用動(dòng)態(tài)規(guī)劃解決這個(gè)問(wèn)題。由于b[i] 不超過(guò) 64，所以可以使用位無(wú)符號(hào)整數(shù)去壓縮必要的狀態(tài)。

Status 是勝負(fù)狀態(tài)的二進(jìn)制壓縮，trans 是狀態(tài)轉(zhuǎn)移的二進(jìn)制壓縮。

代碼說(shuō)明：

“~”表示二進(jìn)制補(bǔ)碼運(yùn)算符，它將每個(gè)二進(jìn)制位的 0 變成 1、1 變?yōu)?0；

而“^”表示二進(jìn)制異或運(yùn)算符，它將兩個(gè)參與運(yùn)算的數(shù)重的每個(gè)對(duì)應(yīng)的二進(jìn)制位一一進(jìn)行比較，若兩個(gè)二進(jìn)制位相同，則運(yùn)算結(jié)果的對(duì)應(yīng)二進(jìn)制位為 0，反之為 1。

ull 標(biāo)識(shí)符表示它前面的數(shù)字是 unsigned long long 類型。

試補(bǔ)全程序

#include <cstdio>
#include<algorithm>
using namespace std ;
const int maxn =64;
int n,m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win；
int main() {
    scanf(“%d%d”,＆n, ＆m);
    for (int i = 0; i < n; ++i)
        scanf(“%d%d”, ＆a[i], ＆b[i]);
    for (int  i = 0; i < n; ++i)
         for (int j = i + 1; j < n; ++j)
            if (aa[i] > a[j]) {
                swap(a[i], a[j]);
                swap(b[i], b[j]);
            }
    status = ①;
    trans = 0;
    for (int i = 1, j = 0; i <= m; ++i) {
        while (j < n && ②) {
            ③;
            ++j;
        }
        win = ④;
        ⑤;
    }

    puts(win ? “Win” : “Loss”)；

    return 0;
}

① 處應(yīng)填（ ）

第40題

（取石子）Alice 和 Bob 兩個(gè)人在玩取石子游戲，他們制定了 n 條取石子的規(guī)則，第 i 條規(guī)則為：如果剩余的石子個(gè)數(shù)大于等于 a[i] 且大于等于 b[i]，那么她們可以取走 b[i] 個(gè)石子。他們輪流取石子。如果輪到某個(gè)人取石子，而她們無(wú)法按照任何規(guī)則取走石子，那么他就輸了，一開(kāi)始石子有 m 個(gè)。請(qǐng)問(wèn)先取石子的人是否有必勝的方法？

輸入第一行有兩個(gè)正整數(shù)，分別為規(guī)則個(gè)數(shù) n(1≤n≤64),以及石子個(gè)數(shù) m(≤107)。

接下來(lái) n 行。第i行有兩個(gè)正整數(shù) a[i]和 b[i]。1≤a[i]≤107,b[i]≤64

如果先取石子的人必勝，那么輸出“Win”，否則輸出“Loss”

提示：

可以使用動(dòng)態(tài)規(guī)劃解決這個(gè)問(wèn)題。由于b[i] 不超過(guò) 64，所以可以使用位無(wú)符號(hào)整數(shù)去壓縮必要的狀態(tài)。

Status 是勝負(fù)狀態(tài)的二進(jìn)制壓縮，trans 是狀態(tài)轉(zhuǎn)移的二進(jìn)制壓縮。

代碼說(shuō)明：

“~”表示二進(jìn)制補(bǔ)碼運(yùn)算符，它將每個(gè)二進(jìn)制位的 0 變成 1、1 變?yōu)?0；

而“^”表示二進(jìn)制異或運(yùn)算符，它將兩個(gè)參與運(yùn)算的數(shù)重的每個(gè)對(duì)應(yīng)的二進(jìn)制位一一進(jìn)行比較，若兩個(gè)二進(jìn)制位相同，則運(yùn)算結(jié)果的對(duì)應(yīng)二進(jìn)制位為 0，反之為 1。

ull 標(biāo)識(shí)符表示它前面的數(shù)字是 unsigned long long 類型。

#include <cstdio>
#include<algorithm>
using namespace std ;
const int maxn =64;
int n,m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win；
int main() {
    scanf(“%d%d”,＆n, ＆m);
    for (int i = 0; i < n; ++i)
        scanf(“%d%d”, ＆a[i], ＆b[i]);
    for (int  i = 0; i < n; ++i)
         for (int j = i + 1; j < n; ++j)
            if (aa[i] > a[j]) {
                swap(a[i], a[j]);
                swap(b[i], b[j]);
            }
    status = ①;
    trans = 0;
    for (int i = 1, j = 0; i <= m; ++i) {
        while (j < n && ②) {
            ③;
            ++j;
        }
        win = ④;
        ⑤;
    }

    puts(win ? “Win” : “Loss”)；

    return 0;
}

② 處應(yīng)填（ ）

第41題

（取石子）Alice 和 Bob 兩個(gè)人在玩取石子游戲，他們制定了 n 條取石子的規(guī)則，第 i 條規(guī)則為：如果剩余的石子個(gè)數(shù)大于等于 a[i] 且大于等于 b[i]，那么她們可以取走 b[i] 個(gè)石子。他們輪流取石子。如果輪到某個(gè)人取石子，而她們無(wú)法按照任何規(guī)則取走石子，那么他就輸了，一開(kāi)始石子有 m 個(gè)。請(qǐng)問(wèn)先取石子的人是否有必勝的方法？

輸入第一行有兩個(gè)正整數(shù)，分別為規(guī)則個(gè)數(shù) n(1≤n≤64),以及石子個(gè)數(shù) m(≤107)。

接下來(lái) n 行。第i行有兩個(gè)正整數(shù) a[i]和 b[i]。1≤a[i]≤107,b[i]≤64

如果先取石子的人必勝，那么輸出“Win”，否則輸出“Loss”

提示：

可以使用動(dòng)態(tài)規(guī)劃解決這個(gè)問(wèn)題。由于b[i] 不超過(guò) 64，所以可以使用位無(wú)符號(hào)整數(shù)去壓縮必要的狀態(tài)。

Status 是勝負(fù)狀態(tài)的二進(jìn)制壓縮，trans 是狀態(tài)轉(zhuǎn)移的二進(jìn)制壓縮。

代碼說(shuō)明：

“~”表示二進(jìn)制補(bǔ)碼運(yùn)算符，它將每個(gè)二進(jìn)制位的 0 變成 1、1 變?yōu)?0；

而“^”表示二進(jìn)制異或運(yùn)算符，它將兩個(gè)參與運(yùn)算的數(shù)重的每個(gè)對(duì)應(yīng)的二進(jìn)制位一一進(jìn)行比較，若兩個(gè)二進(jìn)制位相同，則運(yùn)算結(jié)果的對(duì)應(yīng)二進(jìn)制位為 0，反之為 1。

ull 標(biāo)識(shí)符表示它前面的數(shù)字是 unsigned long long 類型。

試補(bǔ)全程序

#include <cstdio>
#include<algorithm>
using namespace std ;
const int maxn =64;
int n,m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win；
int main() {
    scanf(“%d%d”,＆n, ＆m);
    for (int i = 0; i < n; ++i)
        scanf(“%d%d”, ＆a[i], ＆b[i]);
    for (int  i = 0; i < n; ++i)
         for (int j = i + 1; j < n; ++j)
            if (aa[i] > a[j]) {
                swap(a[i], a[j]);
                swap(b[i], b[j]);
            }
    status = ①;
    trans = 0;
    for (int i = 1, j = 0; i <= m; ++i) {
        while (j < n && ②) {
            ③;
            ++j;
        }
        win = ④;
        ⑤;
    }

    puts(win ? “Win” : “Loss”)；

    return 0;
}

③ 處應(yīng)填（ ）

第42題

（取石子）Alice 和 Bob 兩個(gè)人在玩取石子游戲，他們制定了 n 條取石子的規(guī)則，第 i 條規(guī)則為：如果剩余的石子個(gè)數(shù)大于等于 a[i] 且大于等于 b[i]，那么她們可以取走 b[i] 個(gè)石子。他們輪流取石子。如果輪到某個(gè)人取石子，而她們無(wú)法按照任何規(guī)則取走石子，那么他就輸了，一開(kāi)始石子有 m 個(gè)。請(qǐng)問(wèn)先取石子的人是否有必勝的方法？

輸入第一行有兩個(gè)正整數(shù)，分別為規(guī)則個(gè)數(shù) n(1≤n≤64),以及石子個(gè)數(shù) m(≤107)。

接下來(lái) n 行。第i行有兩個(gè)正整數(shù) a[i]和 b[i]。1≤a[i]≤107,b[i]≤64

如果先取石子的人必勝，那么輸出“Win”，否則輸出“Loss”

提示：

可以使用動(dòng)態(tài)規(guī)劃解決這個(gè)問(wèn)題。由于b[i] 不超過(guò) 64，所以可以使用位無(wú)符號(hào)整數(shù)去壓縮必要的狀態(tài)。

Status 是勝負(fù)狀態(tài)的二進(jìn)制壓縮，trans 是狀態(tài)轉(zhuǎn)移的二進(jìn)制壓縮。

代碼說(shuō)明：

“~”表示二進(jìn)制補(bǔ)碼運(yùn)算符，它將每個(gè)二進(jìn)制位的 0 變成 1、1 變?yōu)?0；

而“^”表示二進(jìn)制異或運(yùn)算符，它將兩個(gè)參與運(yùn)算的數(shù)重的每個(gè)對(duì)應(yīng)的二進(jìn)制位一一進(jìn)行比較，若兩個(gè)二進(jìn)制位相同，則運(yùn)算結(jié)果的對(duì)應(yīng)二進(jìn)制位為 0，反之為 1。

ull 標(biāo)識(shí)符表示它前面的數(shù)字是 unsigned long long 類型。

試補(bǔ)全程序

#include <cstdio>
#include<algorithm>
using namespace std ;
const int maxn =64;
int n,m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win；
int main() {
    scanf(“%d%d”,＆n, ＆m);
    for (int i = 0; i < n; ++i)
        scanf(“%d%d”, ＆a[i], ＆b[i]);
    for (int  i = 0; i < n; ++i)
         for (int j = i + 1; j < n; ++j)
            if (aa[i] > a[j]) {
                swap(a[i], a[j]);
                swap(b[i], b[j]);
            }
    status = ①;
    trans = 0;
    for (int i = 1, j = 0; i <= m; ++i) {
        while (j < n && ②) {
            ③;
            ++j;
        }
        win = ④;
        ⑤;
    }
    puts(win ? “Win” : “Loss”)；
    return 0;
}

④ 處應(yīng)填（ ）

第43題

（取石子）Alice 和 Bob 兩個(gè)人在玩取石子游戲，他們制定了 n 條取石子的規(guī)則，第 i 條規(guī)則為：如果剩余的石子個(gè)數(shù)大于等于 a[i] 且大于等于 b[i]，那么她們可以取走 b[i] 個(gè)石子。他們輪流取石子。如果輪到某個(gè)人取石子，而她們無(wú)法按照任何規(guī)則取走石子，那么他就輸了，一開(kāi)始石子有 m 個(gè)。請(qǐng)問(wèn)先取石子的人是否有必勝的方法？

輸入第一行有兩個(gè)正整數(shù)，分別為規(guī)則個(gè)數(shù) n(1≤n≤64),以及石子個(gè)數(shù) m(≤107)。

接下來(lái) n 行。第i行有兩個(gè)正整數(shù) a[i]和 b[i]。1≤a[i]≤107,b[i]≤64

如果先取石子的人必勝，那么輸出“Win”，否則輸出“Loss”

提示：

可以使用動(dòng)態(tài)規(guī)劃解決這個(gè)問(wèn)題。由于b[i] 不超過(guò) 64，所以可以使用位無(wú)符號(hào)整數(shù)去壓縮必要的狀態(tài)。

Status 是勝負(fù)狀態(tài)的二進(jìn)制壓縮，trans 是狀態(tài)轉(zhuǎn)移的二進(jìn)制壓縮。

代碼說(shuō)明：

“~”表示二進(jìn)制補(bǔ)碼運(yùn)算符，它將每個(gè)二進(jìn)制位的 0 變成 1、1 變?yōu)?0；

而“^”表示二進(jìn)制異或運(yùn)算符，它將兩個(gè)參與運(yùn)算的數(shù)重的每個(gè)對(duì)應(yīng)的二進(jìn)制位一一進(jìn)行比較，若兩個(gè)二進(jìn)制位相同，則運(yùn)算結(jié)果的對(duì)應(yīng)二進(jìn)制位為 0，反之為 1。

ull 標(biāo)識(shí)符表示它前面的數(shù)字是 unsigned long long 類型。

試補(bǔ)全程序

#include <cstdio>
#include<algorithm>
using namespace std ;
const int maxn =64;
int n,m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win；
int main() {
    scanf(“%d%d”,＆n, ＆m);
    for (int i = 0; i < n; ++i)
        scanf(“%d%d”, ＆a[i], ＆b[i]);
    for (int  i = 0; i < n; ++i)
         for (int j = i + 1; j < n; ++j)
            if (aa[i] > a[j]) {
                swap(a[i], a[j]);
                swap(b[i], b[j]);
            }
    status = ①;
    trans = 0;
    for (int i = 1, j = 0; i <= m; ++i) {
        while (j < n && ②) {
            ③;
            ++j;
        }
        win = ④;
        ⑤;
    }

    puts(win ? “Win” : “Loss”)；

    return 0;
}

⑤處應(yīng)填（ ）