程序设计实习 MOOC Week 9 DEX

接續上一篇

D - 热血格斗场

題目

总时间限制: 1000ms 内存限制: 65536kB

描述

为了迎接08年的奥运会,让大家更加了解各种格斗运动,facer新开了一家热血格斗场。格斗场实行会员制,但是新来的会员不需要交入会费,而只要同一名老会员打一场表演赛,证明自己的实力。

我们假设格斗的实力可以用一个正整数表示,成为实力值。另外,每个人都有一个唯一的id,也是一个正整数。为了使得比赛更好看,每一个新队员都会选择与他实力最为接近的人比赛,即比赛双方的实力值之差的绝对值越小越好,如果有两个人的实力值与他差别相同,则他会选择比他弱的那个(显然,虐人必被虐好)。

不幸的是,Facer一不小心把比赛记录弄丢了,但是他还保留着会员的注册记录。现在请你帮facer恢复比赛纪录,按照时间顺序依次输出每场比赛双方的id。

输入

第一行一个数n(0 < n <=100000),表示格斗场新来的会员数(不包括facer)。以后n行每一行两个数,按照入会的时间给出会员的id和实力值。一开始,facer就算是会员,id为1,实力值1000000000。输入保证两人的实力值不同。

输出

N行,每行两个数,为每场比赛双方的id,新手的id写在前面。

样例输入

3
2 1
3 3
4 2

样例输出

2 1
3 2
4 2

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <stdlib.h>
#include <set>
using namespace std;
int main() {
#define oo 0x3f3f3f3f
for(int n, id, power; scanf("%d", &n) == 1;) {
set< pair<int, int> > S;
S.insert(make_pair(1000000000, 1));
for(int i = 0; i < n; i++) {
scanf("%d %d", &id, &power);
S.insert(make_pair(power, id));
set< pair<int, int> >::iterator it;
it = S.find(make_pair(power, id));
pair<int, int> f1, f2;
f1 = make_pair(-oo, 0);
f2 = make_pair(oo, 0);
if(it != S.begin()) {
it--;
f1 = *it;
it++;
}
if(it != S.end()) {
it++;
f2 = *it;
it--;
}
if(abs(f2.first - power) < abs(f1.first - power))
f1 = f2;
printf("%d %d\n", id, f1.second);
}
}
return 0;
}

E - priority queue练习题

題目

总时间限制: 2500ms 内存限制: 131072kB

描述

我们定义一个正整数a比正整数b优先的含义是:
*a的质因数数目(不包括自身)比b的质因数数目多;
*当两者质因数数目相等时,数值较大者优先级高。

现在给定一个容器,初始元素数目为0,之后每次往里面添加10个元素,每次添加之后,要求输出优先级最高与最低的元素,并把该两元素从容器中删除。

输入

第一行: num (添加元素次数,num <= 30)

下面10*num行,每行一个正整数n(n < 10000000).

输出

每次输入10个整数后,输出容器中优先级最高与最低的元素,两者用空格间隔。

样例输入

1
10 7 66 4 5 30 91 100 8 9

样例输出

66 5

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <set>
using namespace std;
int getPF(int n) {
int ret = 0;
for(int i = 2; i*i <= n; i++) {
if(n%i == 0) {
while(n /= i, n%i == 0);
ret++;
}
}
if(n != 1 && ret > 0) ret++;
return ret;
}
int main() {
for(int n; scanf("%d", &n) == 1;) {
multiset< pair<int, int> > S;
while(n--) {
for(int i = 0, x; i < 10; i++) {
scanf("%d", &x);
S.insert(make_pair(getPF(x), x));
}
multiset< pair<int, int> >::iterator it;
multiset< pair<int, int> >::iterator jt;
it = S.begin();
jt = S.end();
jt--;
printf("%d %d\n", (*jt).second, (*it).second);
S.erase(it);
S.erase(jt);
}
}
return 0;
}

X - 思考题最后一题,不计分,供测试

題目

总时间限制: 1000ms 内存限制: 65536kB

描述

请补齐下面程序,使得补齐后的程序,对于下面指定的输入数据,能产生指定的输出。
1
2
3
4
5
6
#include <iostream>
#include <string>
using namespace std;
template <class T>
class CMyistream_iterator
{

// 在此处补充你的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
};
int main()
{
int t;
cin >> t;
while (t--) {
CMyistream_iterator<int> inputInt(cin);
int n1,n2,n3;
n1 = * inputInt;
int tmp = * inputInt;
cout << tmp << endl;
inputInt ++;
n2 = * inputInt;
inputInt ++;
n3 = * inputInt;
cout << n1 << "," << n2<< "," << n3 << ",";
CMyistream_iterator<string> inputStr(cin);
string s1,s2;
s1 = * inputStr;
inputStr ++;
s2 = * inputStr;
cout << s1 << "," << s2 << endl;
}
return 0;
}

输入

第一行是整数t,表示有t组数据。
每组数据由三个整数和两个字符串组成。整数都是小于220的正整数,字符串中间没有空格

输出

对每组输入数据,输出两行。
第一行是输入的第一个整数。
第二行依次输出输入的各项,用逗号","分隔。

样例输入

2
79 90 20 hello me
21 375 45 Jack good

样例输出

79
79,90,20,hello,me
21
21,375,45,Jack,good

解法

這裡要特別小心串流處理,這裡仍是用指針去維護。

Pointer Type(*) 和 Reference Type(&) 使用上也要明白差別。

  • 假使宣告 istream &mcin;
    一定要用 CMyistream_iterator(istream& m): mcin(m) 搭配 mcin >> front

    • 為什麼 mcin = m 不能取代 mcin(m) ?
      雖然我不太明白,但是 Reference Type 一定要在宣告的時候就決定取的位址,也就是說 mcin 再也不能跟動對應的位址,與指標不同的地方就在這裡。

      通常會這個寫來降低複雜度 int& ret = MAP[index]; 其中 ret 再也不能更動位址,當然也許再 C++11 之後的版本會有所不同。

  • 假使宣告 istream *mcin;
    彈性就很大,但使用時都要用 *mcin >> front

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <string>
using namespace std;
template <class T>
class CMyistream_iterator
{
public:
CMyistream_iterator(istream& m): mcin(&m) {
*mcin >> front;
}
void operator ++(int) {
*mcin >> front;
}
T operator * () {
return front;
}
private:
istream *mcin;
T front;
};
int main()
{
int t;
cin >> t;
while (t--) {
CMyistream_iterator<int> inputInt(cin);
int n1,n2,n3;
n1 = * inputInt;
int tmp = * inputInt;
cout << tmp << endl;
inputInt ++;
n2 = * inputInt;
inputInt ++;
n3 = * inputInt;
cout << n1 << "," << n2<< "," << n3 << ",";
CMyistream_iterator<string> inputStr(cin);
string s1,s2;
s1 = * inputStr;
inputStr ++;
s2 = * inputStr;
cout << s1 << "," << s2 << endl;
}
return 0;
}
Read More +

程序设计实习 MOOC Week 9 ABC

關於這一周

練習 STL 的語法。 題目來源

好久沒有練 C++ 程序,這是一個訓練 STL 的題單。

練習項目

std::list

  • list.merge(other_list)
    將 other_list 內容搬運到 list 後,other_list 清空。
  • list.sort()
    不依賴 std::sort, 自己內部有一個 sort()。
  • list.unique()
    跟另外一套的有點相似,一樣是要在排序後才能運行當作去重複。

std::set & std::multiset

  • insert()
  • find()
    查找,後回傳 set<>::iterator 的型態。
  • set<>::iterator
    begin()end() 的型態。
  • set<>::reverse_iterator
    rbegin()rend() 的型態。
  • erase()
    特別小心這個,傳入如果是 iterator 的話,就只會刪除單一元素,如果對於 multiset 來說,傳入一般的值(不是迭代器指針) 則會將所有相同的都刪除。

std::string

  • find(str [, start_pos])
    正向搜索 str 這個字串從 start_pos 開始算起。
  • rfind()
    逆向搜索 str 這個字串。
  • substr(start_post, sub_length)
    從某個位置開始,截出一段長度。

A - List

題目

总时间限制: 4000ms 内存限制: 65536kB

描述

写一个程序完成以下命令:
new id ——新建一个指定编号为id的序列(id<10000)
add id num——向编号为id的序列加入整数num
merge id1 id2——合并序列id1和id2中的数,并将id2清空
unique id——去掉序列id中重复的元素
out id ——从小到大输出编号为id的序列中的元素,以空格隔开

输入

第一行一个数n,表示有多少个命令( n <= 200000)。以后 n 行每行一个命令。

输出

按题目要求输出。

样例输入

16
new 1
new 2
add 1 1
add 1 2
add 1 3
add 2 1
add 2 2
add 2 3
add 2 4
out 1
out 2
merge 1 2
out 1
out 2
unique 1
out 1

样例输出

1 2 3 
1 2 3 4
1 1 2 2 3 3 4

1 2 3 4

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <algorithm>
#include <map>
#include <list>
using namespace std;
int main() {
for(int n; scanf("%d", &n) == 1; ) {
char cmd[10];
int id, num, aid;
map< int, list<int> > S;
while(n--) {
scanf("%s", cmd);
if(cmd[0] == 'n') { // new
scanf("%d", &id);
S[id] = list<int>();
} else if(cmd[0] == 'a') { // add
scanf("%d %d", &id, &num);
S[id].push_back(num);
} else if(cmd[0] == 'm') { // merge
scanf("%d %d", &id, &aid);
S[id].merge(S[aid]);
} else if(cmd[0] == 'u') { // unique
scanf("%d", &id);
S[id].sort();
S[id].unique();
} else { // out
scanf("%d", &id);
S[id].sort();
list<int>::iterator it, jt;
it = S[id].begin(), jt = S[id].end();
int f = 0;
for(; it != jt; it++) {
if(f) putchar(' ');
f = 1;
printf("%d", *it);
}
puts("");
}
}
}
return 0;
}

B - Set

題目

总时间限制: 5000ms 内存限制: 100000kB

描述

现有一整数集(允许有重复元素),初始为空。我们定义如下操作:
add x 把x加入集合
del x 把集合中所有与x相等的元素删除
ask x 对集合中元素x的情况询问
对每种操作,我们要求进行如下输出。
add 输出操作后集合中x的个数
del 输出操作前集合中x的个数
ask 先输出0或1表示x是否曾被加入集合(0表示不曾加入),再输出当前集合中x的个数,中间用空格格开。

输入

第一行是一个整数n,表示命令数。0<=n<=100000。
后面n行命令,如Description中所述。

输出

共n行,每行按要求输出。

样例输入

7
add 1
add 1
ask 1
ask 2
del 2
del 1
ask 1

样例输出

1
2
1 2
0 0
0
2
1 0

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
int main() {
for(int n, x; scanf("%d", &n) == 1;) {
char cmd[10];
multiset<int> S;
set<int> I;
while(n--) {
scanf("%s", cmd);
if(cmd[0] == 'a' && cmd[1] == 'd') { // add
scanf("%d", &x);
I.insert(x);
S.insert(x);
printf("%d\n", S.count(x));
} else if(cmd[0] == 'a' && cmd[1] == 's') { // ask
scanf("%d", &x);
printf("%d %d\n", I.find(x) != I.end(), S.count(x));
} else { // del
scanf("%d", &x);
printf("%d\n", S.count(x));
S.erase(x);
}
}
}
return 0;
}

C - 字符串操作

題目

总时间限制: 1000ms 内存限制: 65536kB

描述

给定n个字符串(从1开始编号),每个字符串中的字符位置从0开始编号,长度为1-500,现有如下若干操作:

    copy N X L:取出第N个字符串第X个字符开始的长度为L的字符串。
    add S1 S2:判断S1,S2是否为0-99999之间的整数,若是则将其转化为整数做加法,若不是,则作字符串加法,返回的值为一字符串。
    find S N:在第N个字符串中从左开始找寻S字符串,返回其第一次出现的位置,若没有找到,返回字符串的长度。
    rfind S N:在第N个字符串中从右开始找寻S字符串,返回其第一次出现的位置,若没有找到,返回字符串的长度。
    insert S N X:在第N个字符串的第X个字符位置中插入S字符串。
    reset S N:将第N个字符串变为S。
    print N:打印输出第N个字符串。
    printall:打印输出所有字符串。
    over:结束操作。

其中N,X,L可由find与rfind操作表达式构成,S,S1,S2可由copy与add操作表达式构成。

输入

第一行为一个整数n(n在1-20之间)

接下来n行为n个字符串,字符串不包含空格及操作命令等。

接下来若干行为一系列操作,直到over结束。

输出

根据操作提示输出对应字符串。

样例输入

3
329strjvc
Opadfk48
Ifjoqwoqejr
insert copy 1 find 2 1 2 2 2
print 2
reset add copy 1 find 3 1 3 copy 2 find 2 2 2 3
print 3
insert a 3 2
printall
over

样例输出

Op29adfk48
358
329strjvc
Op29adfk48
35a8

解法

這一題算是裡面最繁瑣的一題,一部分是因為其輸入的規則需要遞歸分析。
而為了實現遞歸分析,需要可以偷看輸入的下一個 token,因此先把每一個 token 切出來放在 queue 裏頭。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <queue>
#include <ctype.h>
using namespace std;
char s[32][512], lineStr[1024];
string str[32];
int strSize;
queue<string> tokenQ;
int str2num(string s) {
return atoi(s.c_str());
}
string num2str(int n) {
string s;
stringstream ss(s);
ss << n;
return ss.str();
}
int isValidNum(string s) {
int ret = 0;
for(int i = 0; i < s.length(); i++) {
if(!isdigit(s[i]))
return -1;
ret = ret * 10 + s[i] - '0';
if(ret > 99999)
return -1;
}
return ret;
}
string parsing() {
string p = tokenQ.front();
tokenQ.pop();
if(p == "copy") {
string N, X, L;
int n, x, l;
if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
N = parsing();
} else {
N = tokenQ.front(), tokenQ.pop();
}
if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
X = parsing();
} else {
X = tokenQ.front(), tokenQ.pop();
}
if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
L = parsing();
} else {
L = tokenQ.front(), tokenQ.pop();
}
n = str2num(N), x = str2num(X), l = str2num(L);
return str[n].substr(x, l);
} else if(p == "add") {
string S1, S2;
int s1, s2;
if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
S1 = parsing();
} else {
S1 = tokenQ.front(), tokenQ.pop();
}
if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
S2 = parsing();
} else {
S2 = tokenQ.front(), tokenQ.pop();
}
s1 = isValidNum(S1), s2 = isValidNum(S2);
if(s1 < 0 || s2 < 0)
return S1 + S2;
else
return num2str(s1 + s2);
} else if(p == "find") {
string S, N;
int s, n;
if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
S = parsing();
} else {
S = tokenQ.front(), tokenQ.pop();
}
if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
N = parsing();
} else {
N = tokenQ.front(), tokenQ.pop();
}
n = str2num(N);
int pos = str[n].find(S);
if(pos != string::npos) {
return num2str(pos);
} else {
return num2str(str[n].length());
}
} else if(p == "rfind") {
string S, N;
int s, n;
if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
S = parsing();
} else {
S = tokenQ.front(), tokenQ.pop();
}
if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
N = parsing();
} else {
N = tokenQ.front(), tokenQ.pop();
}
n = str2num(N);
int pos = str[n].rfind(S);
if(pos != string::npos) {
return num2str(pos);
} else {
return num2str(str[n].length());
}
} else if(p == "insert") {
string S, N, X;
int s, n, x;
if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
S = parsing();
} else {
S = tokenQ.front(), tokenQ.pop();
}
if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
N = parsing();
} else {
N = tokenQ.front(), tokenQ.pop();
}
if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
X = parsing();
} else {
X = tokenQ.front(), tokenQ.pop();
}
n = str2num(N), x = str2num(X);
str[n].insert(x, S);
} else if(p == "reset") {
string S, N, X;
int s, n, x;
if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
S = parsing();
} else {
S = tokenQ.front(), tokenQ.pop();
}
if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
N = parsing();
} else {
N = tokenQ.front(), tokenQ.pop();
}
n = str2num(N);
str[n] = S;
} else if(p == "print") {
string S, N, X;
int s, n, x;
if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
N = parsing();
} else {
N = tokenQ.front(), tokenQ.pop();
}
n = str2num(N);
printf("%s\n", str[n].c_str());
} else if(p == "printall") {
for(int i = 1; i <= strSize; i++)
printf("%s\n", str[i].c_str());
} else if(p == "over") {
}
return "";
}
int main() {
for(int n; scanf("%d", &n) == 1;) {
int N, X, L, S1, S2, S;
for(int i = 1; i <= n; i++) {
scanf("%s", s[i]);
str[i] = s[i];
}
strSize = n;
while(getchar() != '\n');
while(gets(lineStr)) {
stringstream sin(lineStr);
string token;
while(sin >> token)
tokenQ.push(token);
parsing();
}
}
return 0;
}
Read More +

JQuery 魔法陣製作 Magic Circle

製作起源

魔法陣字型出處

也是因為在 2014-04-17 出了一款魔法陣字型,在藉由惡友們的催促下,不,是誘導下嘗試做了 jquery 的插件來完成魔法陣的製作。當然沒有網址中做得那麼好看。

不過具體下也努力去完成了。附圖如下:

製作

前置作業

  • JQuery
  • CSS 旋轉和陰影配置

開始

  • 配置多層圓,可以參考 這裡,先將內容拆成 <span>A</span> 的形式。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    h1 span {
    font: 24px myFirstFont, Monaco, MonoSpace;
    height: 300px;
    position: absolute;
    width: 20px;
    left: 50%;
    top: 0;
    -webkit-transform-origin: 50% 50%;
    -moz-transform-origin: 50% 50%;
    -ms-transform-origin: 50% 50%;
    -o-transform-origin: 50% 50%;
    transform-origin: 50% 50%;
    }
  • 將每個 <span> 設置成絕對座標配置,乍看下是一個長條形,並且使用 transform-origin 50% 50% 設置旋轉中心,也就是長條形的正中間。rgba(177, 17, 22, 1) 為血紅色

更新

  • 接著要計算字距,來方便每一個字符偏轉角度。而且每一層圓的偏轉角度還有所不同,這裡我並沒有詳細去計算。

  • transform rotate(50 deg) 用來旋轉

  • 光暈效果呈現 box-shadow 0px 0px 10px rgba(177, 17, 22, 1) 於外部產生陰影。

    • 至於內部效果沒有做得很好看。

山田かみら 的建議下,進行的大幅度地修改,同時也發現之前的版本有過度延遲的問題,原因都發生於過多的 for each 計算。

  • 先修正過於愚蠢的 CSS,加入比較好的 class 處理,來達到可以物件化。
  • 原本文字的處理仍需要使用旋轉的方式運作,而考慮將每一個圈放到同一個正方形內,直接對正方形作旋轉即可,剩下的操作交給瀏覽器去進行計算。因此,做了架構上的分層。

關於代碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<script>
$(function() {
$("#test1").magicsquare('fire', {radius: 500, radius_padding: 150,
radius_center: 200, duration: 10});
$("#test2").magicsquare('fire', {radius: 300, radius_padding: 50,
radius_center: 50, duration: 30});
$("#test1").draggable();
$("#test2").draggable();
$(".center-content").click(function() {
$("#test1").magicsquare('boom');
$("#test2").magicsquare('boom');
});
});
</script>

不知道 CSS3 穩定了沒有,在動畫處理引用 animate.css。

但是如果要完成連續型的動畫播放,單純 CSS 目前不想去研究能不能寫腳本。所以在定秒處理之後呼叫 callback() 去進行下一個動畫放置 (仍以 jquery 為主)。

剩下的交給 山田君 了。

Demo & 下載

very old version demo gif
demo link

repo jquery-magic-circle on Github

Reference

Read More +

軟體開發方法論(翻譯部分內容)

長篇大論

只求軟體開發的工程方法,最近上敏捷方法,教授開始講到了始祖 …

於是上演了輪番翻譯的戲碼,讓各種同學參與這份大型工程,關於翻譯的同時,深刻地理解到這也是為什麼無法接觸國外的最新資訊啊,曲解、誤解、亂解 …

我的語言記憶體如此小,卻搭載世界最複雜的語言。

In the past few years there’s been a blossoming of a new style of software methodology - referred to as agile methods. Alternatively characterized as an antidote to bureaucracy or a license to hack they’ve stirred up interest all over the software landscape. In this essay I explore the reasons for agile methods, focusing not so much on their weight but on their adaptive nature and their people-first orientation.

Probably the most noticeable change to software process thinking in the last few years has been the appearance of the word ‘agile’. We talk of agile software methods, of how to introduce agility into a development team, or of how to resist the impending storm of agilists determined to change well-established practices.

也許在這過去幾年最引人注目對軟件過程的思考的改變 - “敏捷 agile” 一詞的出現。我們將談論如何將敏捷軟體方法(agile software method)引入到開發團隊,或者如何抗拒即將到來的敏捷提倡者所帶來的風暴,這風暴將改變原先建立的好的業界實踐方法。

This new movement grew out of the efforts of various people who dealt with software process in the 1990s, found them wanting, and looked for a new approach to software process. Most of the ideas were not new, indeed many people believed that much successful software had been built that way for a long time. There was, however, a view that these ideas had been stifled and not been treated seriously enough, particularly by people interested in software process.

這新運動來自于 1990 年起不同人對於軟體程序的努力,他們發現和找到一個新的軟體程序。大多數敏捷方法的想法並不新,大多數人認為很多成功的軟件本來就有內置這種方式很久了,的確是有的,然而有一觀點指出,這些想法對於對軟體過程感興趣的人眼中並沒有受到重視,甚至被受到抑制。

This essay was originally part of this movement. I originally published it in July 2000. I wrote it, like most of my essays, as part of trying to understand the topic. At that time I’d used Extreme Programming for several years after I was lucky enough to work with Kent Beck, Ron Jeffries, Don Wells, and above all the rest of the Chrysler C3 team in 1996. I had since had conversations and read books from other people who had similar ideas about software process, but had not necessarily wanted to take the same path as Extreme Programming. So in the essay I wanted to explore what were the similarities and differences between these methodologies.

這篇文章也是新運動的起源一部份,最初發表于 2000 年 7 月。作為嘗試了解這文章一部份,您必須知曉這篇文章的風格如同其他大多數我寫的文章。在很幸運地與 Kent Beck, Ron Jeffries, Don Wells 共事後,我已經使用極限編程 (Extreme Programming) 好幾年。從 1996 年的 Chrysler C3 team 那時。我有機會與別人互相交流資訊和書籍來得到他們對於軟體過程中的類似想法,但即使是極限編程 (Extreme Programming) 也沒有一定要採用一樣的走法,所以在這篇文章中,我想要探索這些方法間的異同。

My conclusion then, which I still believe now, is that there were some fundamental principles that united these methodologies, and these principles were a notable contrast from the assumptions of the established methodologies.

以我的話來說,我至今仍相信那些方法一定有一些共同的基本原則,這些原則可能會從原本既有的(主流)方法假設中有明顯地對比。

This essay has continued to be one of the most popular essays on my website, which means I feel somewhat bidden to keep it up to date. In its original form the essay both explored these differences in principles and provided a survey of agile methods as I then understood them. Too much has happened with agile methods since for me to keep up with the survey part, although I do provide some links to continue your explorations. The differences in principles still remain, and this discussion I’ve kept.

這篇文章將會一直是一篇這個網站最熱門的文章,也意味者我會感到使命去保持這篇文章的更新。在文章原始架構中,會探討我所了解的這些原則的差異和提供敏捷方法的調查。當我在調查的同時,敏捷方法已經發生了變動,但仍我也提供一些鏈結供您探索,這些原則的差異和討論內容仍會保留在這篇文章中。

Most software development is a chaotic activity, often characterized by the phrase “code and fix”. The software is written without much of an underlying plan, and the design of the system is cobbled together from many short term decisions. This actually works pretty well as the system is small, but as the system grows it becomes increasingly difficult to add new features to the system. Furthermore bugs become increasingly prevalent and increasingly difficult to fix. A typical sign of such a system is a long test phase after the system is “feature complete”. Such a long test phase plays havoc with schedules as testing and debugging is impossible to schedule.

大多數軟體開發是一個混亂的開始,常常以一句話代以概括 ”撰寫!修復!“,這些軟體在撰寫時不用事先有基礎的計劃,也不用系統架構,將由短期項目討論就可以拼湊起來。這確切在系統很小時可以運作,但當系統越大時將會變得相當困難去增加新的功能。此外,BUG 也會越來越普遍見到,且越來越難除錯。這典型系統是在功能齊備後,才經由長時間的測試階段。這麼長時間的測試階段將嚴重破壞測試和除錯的行程,使得行程根本無法安排。試階段起著嚴重破壞的時間表為測試和調試是不可能的安排。

The original movement to try to change this introduced the notion of methodology. These methodologies impose a disciplined process upon software development with the aim of making software development more predictable and more efficient. They do this by developing a detailed process with a strong emphasis on planning inspired by other engineering disciplines - which is why I like to refer to them as engineering methodologies (another widely used term for them is plan-driven methodologies).

起源運動將要改變這種方法的概念,這些方法論所施加的紀律,將協助軟體開發變得更可預測和更有效率。他們將透過製定詳細的過程,這些過程特別強調設計,靈感來自于其他工程學門- 這就是為什麼我喜歡稱呼它們為 ”工程方法 enginerring methodologies“ (對於他們來說,另一個廣泛使用的術語為 “計劃驅動方法 plan-driven methodologies”)

Engineering methodologies have been around for a long time. They’ve not been noticeable for being terribly successful. They are even less noted for being popular. The most frequent criticism of these methodologies is that they are bureaucratic. There’s so much stuff to do to follow the methodology that the whole pace of development slows down.

工程方法已經存有一段歷史,它們都沒有被注目那背後可怕的成功,它們相當少被認為是受流行的,常見的批評為 ”它們是官僚政治的“ // 相當死板的 ? 。有相當多的項目都遵循這套方法論使用緩慢的發展步伐。

Agile methodologies developed as a reaction to these methodologies. For many people the appeal of these agile methodologies is their reaction to the bureaucracy of the engineering methodologies. These new methods attempt a useful compromise between no process and too much process, providing just enough process to gain a reasonable payoff.

敏捷方法的發展就是反映這些工程方法論,對于大多數的人而言,敏捷方法的吸引力是反映出工程方法的官僚主義,這些新方法是在沒有進展和太多進展中的折衷妥協方案,提供一種恰當的過程來獲得合理回饋。

The result of all of this is that agile methods have some significant changes in emphasis from engineering methods. The most immediate difference is that they are less document-oriented, usually emphasizing a smaller amount of documentation for a given task. In many ways they are rather code-oriented: following a route that says that the key part of documentation is source code.

這一切的結過是,敏捷方法從工程方法中有顯的改變。最明顯的差異是少寫文件(文件導向),通常強調少量文件的工作,在許多說法上,它們更偏向代碼導向(code-oriented: 文件的關鍵部分是源代碼 source code)

糟透的軟體開發

在土木工程中,建造一個橋來說,通常在設計草圖完成後,即使換了別的公司繼續接按下去做,一樣能按照這個設計草圖完成。如果在施工過程中遇到問題,通常問題也不會太難,而且非常容易被解決。

在了解這些設計草圖後,可以發現勞心者和勞力者的工作是分開的,設計由專家耗費心力完成,而實作能由工人來按照草圖,因此這些設計草圖是確保工人們能看得懂,但是在軟體工程中,大部分都是勞心者和勞力者集一人之中。

施工是一個相當耗費成本的工作,在早期的軟體工程開發專家,希望能將土木工程的方法轉移到軟體工程上。讓專家進行設計,再讓低成本的工作人員來完成實作,設計費用通常比實作費用來的低,工程師仍有高低薪之分,新一代的低薪工程師呢!

專家寫出來的設計草圖,要讓 programmer 看得懂,通常是非常困難的。即使是 UML 圖,雖然在紙(草圖)上看起來相當不錯,但是實作上的問題卻相當多,土木工程的設計圖可以經過數學模型去測試,但是軟體工程的設計圖只能由人腦去找到邏輯BUG,即使是設計熟練的專家,要設計出不會有實作問題的草圖也是常發生的。

接續著剛剛討論的造橋問題,設計費用只占了全部花費的十分之一,按照草圖寫 code 是相當簡單的,根據 McConnell 調查大型專案,只有 15% 的成本進行程式撰寫和測試(這裡我們需要勞力成本比例越高越好)。即使把其他成本混在一起,設計仍占了 50% 的成本比例。軟體工程只是工程分枝中之一,這其中一定有蹊蹺。

結論

  • 軟體的建造相當便宜,甚至於免費(只淤需要電腦和編譯器,沒有實體。)
  • 軟體受設計影響,因此需要有創造力和有天賦的人。
  • 俱有創新的程序不容易去規劃,可預測的性質甚至變成不可能。
  • 我們需要不同於傳統工程的方法,來解決這詭異的軟體工程的開發程序。

常常有開發者收到客戶不斷地改變需求,但是改變需求是常態,但是對於開發者而言卻是想不透的謎。這表示當初需求並沒有弄完整,但是也不能說像客戶簽訂契約——表示在軟體完成前,需求都不會改變。需求改變是很正常的,這客戶來說這個契約反而不合理。

按需求收費,加什麼功能要多少錢?估算收費也是不好量化,也會根據產品使用的方式和使用者有關,因此品質的水準與費用是不好預估。客戶以為“軟”體容易修改,但並不是每個需求都容易修改,通常會耗費大量的時間去滿足客戶的需求。

如果需求不穩定,就得不到可預測的計劃去完成軟體。

真的不可預測?

在 NASA 太空軟體開發中,他們的計劃是可以預測的,但這也只是一個特別的例子,主要原因是長期時間,龐大的團隊,穩定的需求。

更可怕的是,如果客戶需求不穩定,卻告知有可預測的計劃,這樣自欺欺人的行為相當令人詬病。

”可預測“是令人相當渴望的,這導致一開始擬定的計劃越飄越遠,最後計劃將會分崩離析。

按照方法論運行總是美好的,但是在軟體開發上必須要捨棄掉,但這樣的舉動相當困難,要捨棄一直以來處理事情的方式,但也並不是讓事情處理變得無法控制的混沌,捨棄“預測”吧!

控制 “不可預測”程序

使用迭代方式,並且將計劃越短越好,看起來就是多方面失敗的開始,但卻有機會看來進步的地方,當計劃越短,就能越早知道反饋(feedback)。

文件可以隱藏缺失,沒有經過測試將會有更多的缺失。

XP 一周或兩周,SCRUM 一個月之類的,越熟練則會越短時間。

=====

並不是每個工程師都像零件,換個人就可以繼續運行。

不可更換的人零件都跑了,也就是最有創意的人力都走了,可更換的人卻留下了。

Programmer 是有責任的專業人員?

早期是工廠的運行模式,希望能讓工人多做一點事情,來讓成本降低。

每個 programmer 是獨特的,產出的代碼也都不同,每一個人的創意不同,把人當資源就錯了。

施工和設計能不能分開?施工只是由編譯器來,因此軟體全是文創業,算是設計類型的職業。

Read More +

《刺激消費,我是主角》心得

當代消費文化與社會 期中報告

閱讀書名:《刺激消費,我是主角》
書目作者:日野佳惠子

對於當今社會物質富裕已經為大多數人的基礎,因此消費行為也越來越特異化,從注重環保以及各種責任意義,消費的著重點也有所不同。

如何聰明消費?或者說消費出聰明的價值?的確有一股取向,有錢人的消費模式在於大批購買,而我們這種一般人對於聰明的消費是相當自豪的,聰明消費能夠展現自己能在低價購入高品質的產品,這裡的低價就不單單只是低消費額,是一個相對於產品應有的價值之下。在這股潮流之下,依賴情報消費真的很重要,因此也易受於口碑品牌的影響。就如比特幣剛出時,大批人覺得是一個未來重要的貨幣商品而大量購買 … 等。

如果徵才也是互動型的消費,文中說明消費者若有貢獻出一己之力的機會,將會更容易讓其主動消費,例如廣告為『我們想像身為家庭主婦的您,購買做家事的能力與烹飪能力』比起『時薪 OO 徵才』好太多了,文中所提的例子相當有感,能對別人有所助益,即使中間的過程是消費的一環,也是相當具有自願性的行為。不單單只是為了個人去購買商品,同時也是為了其他外界因素而進行消費。如同當初 Firefox 打擊微軟的 IE 手法,提供開源代碼的方式,希望其他人參與這場攻防戰,願意幫助這個軟體更完善,在不花一毛錢的情況下,這個組織靠著消費者活到了至今。

模仿身邊的人進行消費,如果這個商品是對於土豪們為取向,那麼消費族群也總是那一群,需要靠身邊親朋好友的消費習慣來渲染自己,如果身邊沒有人這麼消費,那要成為第一個購買者的機會是相當低的,因此企業常會用親民的代表人物來推銷自己的商品。我相信在相同處境下,需求是彼此靠攏的。這有點粒子群聚算法的感覺。

『對於不懂得使用方法的人,不了解真正含義的人,無法因商品獲得快樂的人而言,即使技術再進步,一切都是毫無意義。』看到這一句話,越來越明白消費的同時也是在教導,如果單純只是想要擴張客源,沒有好好教導消費者如何使用也是不行的。

『消費者也是加工者,開創低價商品交給消費者加工,並且銷售宣傳』由於消費者不喜歡與別人相同,又想要做出自己的風格,低價商品的拓展性就變得相當高了,低價商品通常有著量多便宜的特性,譬喻成大自然的元素也不為過。想到這一點,有人開發出有前景的軟硬體,通常會湧出一批人去購買,並且修正或運用然後進行傳播,這影響力堪稱指數擴張。這也應對消費者也是企業的助手,一群消費者就是一大群的應援團,將與企業或產品一同發展。

『不消費的智慧』雖然使得商品沒有利益,但是這也表示新的消費可能再也不是利益,而是商品後頭的智慧,看著越來越多的消費手法,沒有智慧學習的商品,除了一般生活所需外,在未來可能很難遍及市場,娛樂市場又是另外一回事。

『把整個環境一同賣給你』即使商品單獨具有高性能,沒有環境展現其性能事件很糟糕的事情,就如蘋果電腦和軟體總是整包出售,兩項缺一不可。而最近微軟最近正有著附上環境出售的趨勢,不過搭配性不強,跟裸機差不多。

Read More +

a007. 判斷質數

題目

內容:

請判斷某數是否為質數

輸入說明:

輸入有多組測試資料(以EOF結尾),每組測試資料占一行,只包含一個整數x, 2 ≦ x ≦ 2147483647。

輸出說明:

對於每組測試資料,如果輸入的x為質數,則輸出一行「質數」(不含引號);否則輸出一行「非質數」(不含引號)。詳見範例測試資料。

範例輸入:

13
14

範例輸出:

質數
非質數

解法

  • 作法:
    Miller-Rabin Algorithm
a007.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**********************************************************************************/
/* Problem: a007 "判斷質數" */
/* Language: CPP (715 Bytes) */
/* Result: AC(0.2s, 224KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2014-04-18 20:25:42 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int Pow(long long x, int n, long long mod) {
long long Ans = 1, t = x;
while(n) {
if(n&1)
Ans *= t, Ans %= mod;
t *= t, t %= mod, n >>= 1;
}
return (int)Ans;
}
int JudgePrime(int n) {
if(n == 2 || n == 3) return 1;
if(n == 1) return 0;
if(!(n&1)) return 0;
int a, x, flag = 1, t;
for(a = 0; a < 2; a++) {
x = rand()%(n-4)+2;
t = Pow(x, n-1, n);
if(t != 1) return 0;
}
return 1;
}
int main() {
int n;
while(scanf("%d", &n) == 1) {
if(JudgePrime(n)) puts("質數");
else puts("非質數");
}
return 0;
}
Read More +

a576. No Cheating

題目

內容:

有個學校想辦一場考試,提供了 T 間教室。每間教室的座位都是 M×N 的矩陣(不同教室的 M, N 可以不一樣),而有的座位壞掉了不能坐。此外,為了避免學生作弊,如下圖,對任何一個學生而言,他的左方、左前方、右方、右前方都不可以有人坐。請問每間教室所能容納的學生數最多為何?

輸入說明:

第一行有一個數字 T,代表學校有 T 間教室。接下來會有每個教室的資料,每筆資料會有在同一行兩個正整數 M, N,代表座位的配置是 M×N。接下來的 M 行,每行有 N 個字元,’.’代表那個座位是好的,而’x’則代表那個座位壞了。

輸出說明:

對於每間教室,輸出”Case #X: Y”, 其中 X 代表這是第幾間教室,而 Y 則代表這間教室能容納的學生數最大值。

範例輸入:

4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....

範例輸出:

Case #1: 4
Case #2: 1
Case #3: 2
Case #4: 46

解法

  • 作法:
    按列黑白染色,會發現不能連的位置恰好可以化成二分圖,求最大獨立集即可。
    最大獨立集 = 點個數 - 最大匹配數
a576.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/**********************************************************************************/
/* Problem: a576 "No Cheating" from GCJ 2008 Round 3 C */
/* Language: CPP (3826 Bytes) */
/* Result: AC(0.1s, 1.2MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2014-04-18 18:09:46 */
/**********************************************************************************/
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
using namespace std;
struct Node {
int x, y, v;// x->y, v
int next;
} edge[65536];
int e, head[6500], prev[6500], record[6500];
int level[6500], visited[6500];
void addEdge(int x, int y, int v) {
edge[e].x = x, edge[e].y = y, edge[e].v = v;
edge[e].next = head[x], head[x] = e++;
edge[e].x = y, edge[e].y = x, edge[e].v = 0;
edge[e].next = head[y], head[y] = e++;
}
bool buildLevelGraph(int s, int t) {
memset(level, 0, sizeof(level));
queue<int> Q;
Q.push(s), level[s] = 1;
while(!Q.empty()) {
int tn = Q.front();
Q.pop();
for(int i = head[tn]; i != -1; i = edge[i].next) {
int y = edge[i].y;
if(edge[i].v > 0 && level[y] == 0) {
level[y] = level[tn] + 1;
Q.push(y);
}
}
}
return level[t] > 0;
}
int constructBlockingFlow(int s, int t) {
int ret = 0;
stack<int> stk;
memset(visited, 0, sizeof(visited));
stk.push(s);
while(!stk.empty()) {
int now = stk.top();
if(now != t) {
for(int i = head[now]; i != -1; i = edge[i].next) {
int y = edge[i].y;
if(visited[y] || level[y] != level[now] + 1)
continue;
if(edge[i].v > 0) {
stk.push(y), prev[y] = now, record[y] = i;
break;
}
}
if(stk.top() == now)
stk.pop(), visited[now] = 1;
} else {
int flow = 1e+9, bottleneck;
for(int i = t; i != s; i = prev[i]) {
int ri = record[i];
flow = min(flow, edge[ri].v);
}
for(int i = t; i != s; i = prev[i]) {
int ri = record[i];
edge[ri].v -= flow;
edge[ri^1].v += flow;
if(edge[ri].v == 0)
bottleneck = prev[i];
}
while(!stk.empty() && stk.top() != bottleneck)
stk.pop();
ret += flow;
}
}
return ret;
}
int maxflowDinic(int s, int t) {
int flow = 0;
while(buildLevelGraph(s, t))
flow += constructBlockingFlow(s, t);
return flow;
}
int main() {
int n, m;
int testcase, cases = 0;
int i, j, k, x, y;
char g[128][128];
int id[128][128];
scanf("%d", &testcase);
while(testcase--) {
e = 0;
memset(head, -1, sizeof(head));
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
scanf("%s", g[i]);
int ST[2] = {0, 0};
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(g[i][j] == '.') {
id[i][j] = ST[j&1]++;
} else {
id[i][j] = -1;
}
}
}
int source = ST[0] + ST[1];
int sink = source + 1;
for(int i = 0; i < ST[0]; i++)
addEdge(source, i, 1);
for(int i = 0; i < ST[1]; i++)
addEdge(i + ST[0], sink, 1);
int dx[] = {-1, -1, 0, 0, 1, 1};
int dy[] = {-1, 1, -1, 1, 1, -1};
int tx, ty, u, v;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j += 2) {
if(id[i][j] == -1)
continue;
v = id[i][j];
for(int k = 0; k < 6; k++) {
tx = i + dx[k];
ty = j + dy[k];
if(tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
u = id[tx][ty];
if(u == -1)
continue;
addEdge(v, u + ST[0], 1);
}
}
}
int ret = maxflowDinic(source, sink);
printf("Case #%d: %d\n", ++cases, ST[0] + ST[1] - ret);
}
return 0;
}
Read More +

a858. 數三角形

題目

內容:

你有一個大小為N的完全圖,這N(N-1)/2條邊可能是紅色或黑色。任三個不同的點都形成一個三角形,請問三邊同色的三角形有幾個?

輸入說明:

第一行輸入一個正整數N,其中N<=1,000。接下來的N行,每行有N個數字,其中第i行的第j個數字代表邊(i,j)的顏色,紅色用1表示,黑色用2表示,i=j時則用0表示。

輸出說明:

請輸出同色三角形的數目。

範例輸入:

4
0 1 2 1
1 0 1 1
2 1 0 2
1 1 2 0

範例輸出:

1

解法

  • 作法:
    分治,將輸入 n 個劃分成兩堆,分別窮舉所有可能,採用合併的方式去運算。
a858.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**********************************************************************************/
/* Problem: a858 "數三角形" from */
/* Language: CPP (462 Bytes) */
/* Result: AC(0.1s, 264KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2014-04-17 11:06:20 */
/**********************************************************************************/
#include <stdio.h>
int main() {
int n, x;
while (scanf("%d", &n) == 1) {
int p = (n) * (n-1) * (n-2) / 6;
int s = 0;
for (int i = 0; i < n; i++) {
int b = 0, r = 0;
for(int j = 0; j < n; j++) {
scanf("%d", &x);
r += x == 1;
b += x == 2;
}
s += r * b;
}
printf("%d\n", p - s/2);
}
return 0;
}
Read More +

a962. 新專輯

題目

內容:

給定正整數N,請求出(N除以1的餘數)+(N除以2的餘數)+(N除以3的餘數)+…+(N除以N的餘數)。

輸入說明:

輸入只有一個正整數N,其中1<=N<=1014。

輸出說明:

為了避免要寫大數,你只要輸出這個奇怪的和除以1000000009的餘數就好了。

範例輸入:

10

範例輸出:

13

解法

  • 作法:
    各種方式要避免 mod 運算。
a962.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**********************************************************************************/
/* Problem: a962 "新專輯" from TIOJ 1674 */
/* Language: CPP (1612 Bytes) */
/* Result: AC(0.8s, 272KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2014-04-18 20:11:19 */
/**********************************************************************************/
#include <stdio.h>
#include <math.h>
#define MOD 1000000009LL
long long inv(long long n, long long m) { // get n*? = 1 (mod m)
long long la = 1, lb = 0, ra = 0, rb = 1;
long long i = 0, t, mod = m;
while(n%m) {
if(!i) {
la -= n/m*ra;
lb -= n/m*rb;
} else {
ra -= n/m*la;
rb -= n/m*lb;
}
i = !i;
t = n, n = m, m = t%m;
}
if(i)
return (la%mod+mod)%mod;
return (ra%mod+mod)%mod;
}
int main() {
long long inv2 = inv(2, MOD);
long long n;
while(scanf("%lld", &n) == 1) {
long long ret = 0, hret = 0;
long long half = (long long)sqrt(n)/5;
long long u = -1, v = 0;
for(half = 1; u != v; half++, u = v, v = n/half) {
hret += n%half;
}
hret -= n%(half - 1);
hret %= MOD;
long long l = half - 1, r, div;
long long a0, d, tn, buff;
while(l <= n) {
div = n / l;
r = n / div;
a0 = n % l, d = -div, tn = r - l + 1;
if(tn >= MOD) tn %= MOD;
if(d >= MOD) d %= MOD;
if(a0 >= MOD) a0 %= MOD;
buff = (a0 * 2 + (tn - 1)*d);
if(buff < 0 || buff >= MOD) buff %= MOD;
buff *= tn;
if(buff < 0 || buff >= MOD) buff %= MOD;
ret += buff;
l = r + 1;
}
ret %= MOD;
ret = (ret * inv2)%MOD;
ret = (ret + hret + MOD)%MOD;
printf("%lld\n", ret);
}
return 0;
}
/*
100000000000000
*/
Read More +

a981. 求和問題

題目

內容:

給你N個正整數, 試求哪幾個之和剛好為M, 印出所有合條件的解, 如有多組解, 請按由小到大的順序印出(格式可參考樣例輸出)

輸入說明:

n m (1<=n<=30, 1<=m<=100000000) n個正整數, 全部以空格分開

輸出說明:

  • 其和剛好等於m的數, 如果有多組解則按由小到大全部印出, 如果無解則印出 -1

範例輸入:

10 100
10 20 40 30 50 80 60 70 5 15

範例輸出:

5 10 15 20 50
5 10 15 30 40
5 10 15 70
5 15 20 60
5 15 30 50
5 15 80
10 20 30 40
10 20 70
10 30 60
10 40 50
20 30 50
20 80
30 70
40 60

解法

  • 作法:
    分治,將輸入 n 個劃分成兩堆,分別窮舉所有可能,採用合併的方式去運算。
a981.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
int main() {
int n, m;
int A[35];
while(scanf("%d %d", &n, &m) == 2) {
for(int i = 0; i < n; i++)
scanf("%d", &A[i]);
sort(A, A + n, greater<int>());
int h1Cnt = n / 2, h2Cnt = n - h1Cnt;
map<long long, vector<int> > h1, h2;
for(int i = (1<<h1Cnt)-1; i >= 0; i--) {
long long sum = 0;
for(int j = 0; j < h1Cnt; j++) {
if((i>>j)&1) sum += A[j];
}
h1[sum].push_back(i);
}
for(int i = (1<<h2Cnt)-1; i >= 0; i--) {
long long sum = 0;
for(int j = 0; j < h2Cnt; j++) {
if((i>>j)&1) sum += A[j + h1Cnt];
}
h2[sum].push_back(i<<h1Cnt);
}
set<int> ret;
for(map<long long, vector<int> >::iterator it = h1.begin();
it != h1.end(); it++) {
long long f = (long long)m - it->first;
map<long long, vector<int> >::iterator jt = h2.find(f);
if(jt != h2.end()) {
for(vector<int>::iterator iv = it->second.begin();
iv != it->second.end(); iv++) {
for(vector<int>::iterator jv = jt->second.begin();
jv != jt->second.end(); jv++) {
ret.insert(*iv| *jv);
}
}
}
}
if(ret.size() == 0)
puts("-1");
for(set<int>::reverse_iterator it = ret.rbegin();
it != ret.rend(); it++) {
for(int i = n-1; i >= 0; i--) {
if(((*it)>>i)&1) {
printf("%d ", A[i]);
}
}
puts("");
}
}
return 0;
}
Read More +