include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;
int main()
{
int t[256];
char s[10];
int i;
scanf(“%s”, s);
for(i = 0; i < 256; i) t[i] = 0;
for(i = 0; i < strlen(s); i) t[s[i]];
for(i = 0; i < strlen(s); i)
if(t[s[i]] == 1) {
cout << s[i] << endl;
return 0;
}
cout << “no” << endl;
return 0;
}
输入：

1
xyzxyw
题目答案

z

题目解析

采用分析程序功能的方法来分析此题可得，此程序先统计输入字符串中每个字母出现的次数，然后求这个字符串中第一个仅出现一次的字母。因此对于读入的字符串“xyzxyw”，答案应该为 z。
（切割绳子）有 nn 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段，求绳段的最大长度是多少。

输入：第一行是一个不超过 100100 的正整数 nn，第二行是 nn 个不超过 10^610
6
的正整数，表示每条绳子的长度，第三行是一个不超过 10^810
8
的正整数 mm。

输出 ：绳段的最大长度，若无法切割，输出 Failed。

1

include [HTML_REMOVED]

2
using namespace std;
3
int n, m, i, lbound, ubound, mid, count;
4
int len[100]; //绳子长度
5
int main()
6
{
7
cin >> n;
8
count = 0;
9
for (i = 0; i < n; i) {
10
cin >> len[i];
11
①;
12
}
13
cin >> m;
14
if (②) {
15
cout << “Failed” << endl;
16
return 0;
17
}
18
lbound = 1 ;
19
ubound = 1000000 ;
20
while (③) {
21
mid = ④;
22
count =0 ;
23
for (i = 0; i < n; i )
24
⑤;
25
if (count < m)
26
ubound = mid - 1 ;
27
else
28
lbound = mid ;
29
}
30
cout << lbound << endl;
31
return 0;
32
}
题目答案

填空位置 ①：

count = count + len[i]

填空位置 ②：

count < m

填空位置 ③：

lbound < ubound

填空位置 ④：

(lbound + ubound + 1) / 2

填空位置 ⑤：

count = count +len[i] / mid

题目解析

本题主要考查二分算法和贪心算法。二分算法中间的for循环使用贪心算法计算能够切割出的绳段个数。

结合第 ①② 空可知，当绳段长度为 11 时可以切出的绳段个数最多，即所有绳子的长度相加，所以输出Failed的条件应该是所有绳子的总长度小于 mm。故用count计算总长度，第 ① 空填count=count+len[i]或count+=len[i]，第二空填count[HTML_REMOVED]count。

第 ③④⑤ 空均在二分里，第 ③ 空是二分的结束条件，故应该填lbound[HTML_REMOVED]lbound，即当前二分的区间长度还大于 11 的时候，说明没有确定最终值是多少。第 ④ 空需要特别注意，由于底下ubound是通过mid-1，lbound是通过mid来更新的，所以这空需要填(lbound+ubound+1)/2或(lbound+ubound+1)>>1或(lbound+ubound)/2+1，三者意思相同。

第 ⑤ 空是用来求当确定绳子的切割长度为mid后，最多能切多少段绳段，故应该填count=count+len[i]/mid或者count+=len[i]/mid。