有正实数构成的数字三角形排列形式如图所示。第一行的数为a1,1;第二行的数从左到右依次为a2,1,a2,2，第n行的数为an,1，an,2，…，an,n。从a1,1开始，每一行的数ai,j只有两条边可以分别通向下一行的两个数ai+1,j和ai+1,j+1。用动态规划算法找出一条从a1,1向下通道an,1，an,2，…，an,n中某个数的路径，使得该路径上的数之和最大。

令C[i][j]是从a1,1到ai,j的路径上的数的最大和，并且C[i][0]= C[0][j]=0，则C[i][j]=（ ）

#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/n”, ans);

}

return 0;

}

（1分）第16行输出ans时，ans的值一定大于i。（ ）

#include <cstdio>

using namepace 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值应在[0，n-1]的范围内。（ ）

本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t；特别的，如果s=t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。

S[x…y]表示s[x]…s[y]共y-x+1个字符构成的字符串，若x＞y则s[x…y]是空串。t[x…y]同理。

#include <cstdio>

#include <algorithm>

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=o; i＜=slen; ++i）{

while（j＜=slen && tmp ＞=suf[j] + 1） ++j；

ans =max(ans, j – I – 1);

tmp = pre[i];

}

cout ＜＜ans ＜＜ end1;

return 0;

}

提示：

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

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

（1分）程序输出时，suf数组满足：对任意0≤i＜slen，suf[i] ≤suf[i+1]。( )

（匠人的自我修养）一个匠人决定要学习n个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。

输入第一行有两个数，分别为新技术个数n（1≤n≤10³），以及已有经验值（≤10⁷）。

接下来n行。第i行的两个正整数，分别表示学习第i个技术所需的最低经验值（≤10⁷），以及学会第i个技术后可获得的经验值（≤10⁴）。

接下来n行。第i行的第一个数m_i（0≤m_i＜n），表示第i个技术的相关技术数量。紧跟着m个两两不同的数，表示第i个技术的相关技术编号，输出最多能学会的新技术个数。

下面的程序已O（n²）的时间复杂完成这个问题，试补全程序。

#include<iostream>

using namesoace std；

const int maxn = 1001；

int n；

int cnt [maxn]

int child [maxn] [maxn]；

int unlock[maxn];

int unlock[maxn];

int threshold [maxn],bonus[maxn];

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＜cut[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\n”, ans);

return 0;

}

①处应填（ ）

(取石子)Alice和Bob两个人在玩取石子游戏。他们制定了n条取石子的规则，第i条规则为：如果剩余石子的个数大于等于a[i]且大于等于b[il， 那么他们可以取走b[i]个石子。他们轮流取石子。如果轮到某个人取石子， 而他无法按照任何规则取走石子，那么他就输了。一开始石子有m个。请问先取石子的人是否有必胜的方法？

输入第一行有两个正整数，分别为规则个数n（1≤n≤64），以及石子个数m（≤10^7）。

接下来n行。第i行有两个正整数a[i]和b[i]（1≤a[i]≤10^7，1≤b[i]≤64）

如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”

提示：

 可以使用动态规划解决这个问题。由于b[i]不超过64，所以可以使用64位无符号整数去压缩必要的状态。

 status是胜负状态的二进制压缩，trans是状态转移的二进制压缩。

试补全程序。

代码说明:

 “~”表示二进制补码运算符，它将每个二进制位的0变成1、1变为0； 

 而“^”表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为0，反之为1。

ull标识符表示它前面的数字是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 (a[i] > a[j]) {

swap(a[i],a[j]);

swap(b[i],b[j]);

}

status = ___(1)___;

trans = 0;

for(int i = 1, j = 0; i <= m; ++i) {

while (j < n && ___(2)___) {

___(3)___

++j;

}

win = ___(4)___;

___(5)___;

}

puts(win ? "Win" : "Loss");

return 0;

}

①处应填（）