A. Playing with Paper
如果a是b的整数倍，那么将得到a/b个正方形，否则的话还会另外得到一个(b, a%b)的长方形。
时间复杂度和欧几里得算法一样。
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 5 //const int maxn = ; 6 7 int main() 8 { 9 //freopen("in.txt", "r", stdin); 10 11 long long a, b, ans = 0; 12 scanf("%I64d%I64d", &a, &b); 13 while(a % b != 0) 14 { 15 ans += a / b; 16 long long ta = b; 17 long long tb = a % b; 18 a = ta; b = tb; 19 } 20 ans += a / b; 21 printf("%I64d ", ans); 22 23 return 0; 24 }
B. Error Correct System
代码略矬。。
贪心，建一个有向图G[a][b] = i，代表第i个字符“想”从字母a变成字母b，也就是说s1[i] == a, s2[i] == b，如果s1中第i个字母从a变成b后，题中定义的那个Hamming distance就会减小1.如果有G[a][b] 和 G[b][a]的话，直接将这两个字符交换就好了，Hamming distance一共减少2。
否则，退而求其次，交换一下只满足G[a][b] G[b][c]的两个位置的字符，这样Hamming distance减小1.
再否则，，，直接输出-1 -1
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 5 const int maxn = 200000 + 10; 6 7 int n; 8 char s1[maxn], s2[maxn]; 9 10 int G[30][30]; 11 12 int main() 13 { 14 //freopen("in.txt", "r", stdin); 15 16 scanf("%d", &n); getchar(); 17 gets(s1+1); gets(s2+1); 18 19 int ans = 0, p1 = -1, p2 = -1; 20 for(int i = 1; i <= n; i++) if(s1[i] != s2[i]) ans++; 21 22 for(int i = 1; i <= n; i++) if(s1[i] != s2[i]) 23 { 24 int x = s1[i]-'a', y = s2[i]-'a'; 25 G[x][y] = i; 26 if(G[y][x]) { p1 = i; p2 = G[y][x]; ans -= 2; break; } 27 } 28 29 bool flag = false; 30 if(p1 + p2 == -2) 31 { 32 for(int i = 0; i < 26; i++) 33 { 34 for(int j = 0; j < 26; j++) if(G[i][j]) 35 { 36 for(int k = 0; k < 26; k++) if(G[j][k]) 37 { 38 flag = true; 39 ans--; 40 p1 = G[i][j]; p2 = G[j][k]; 41 break; 42 } 43 if(flag) break; 44 } 45 if(flag) break; 46 } 47 } 48 49 printf("%d %d %d ", ans, p1, p2); 50 51 return 0; 52 }
C. Glass Carving
果然，熟练使用STL是很有必要的，减小编码复杂度，速度上也不会太慢。
话说有一个人对着一块玻璃横着或者竖着切来切去。
每次切完都要询问一下最大的一块玻璃的面积是多少。
将所有切割的位置放在一个集合中，还有所有相邻位置之间的距离放在一个多重集合里面。
每一次切割位置x，都将a<x<b这个区间分成了两个，同时将x加入到对应的切割位置集合；然后更新一下距离集合，具体就是删除b-a这段距离(如果有多个，只要删除一个就好了)，然后分别插入(x-a) 和 (b-x)这两段被分隔开的距离。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int main() 5 { 6 //freopen("in.txt", "r", stdin); 7 8 set<int> sh, sv; 9 multiset<int> mh, mv; 10 set<int>::iterator l, r; 11 12 int w, h, n; 13 scanf("%d%d%d", &w, &h, &n); getchar(); 14 sh.insert(0); sh.insert(h); 15 sv.insert(0); sv.insert(w); 16 mh.insert(h); mv.insert(w); 17 18 while(n--) 19 { 20 char op; int cut; 21 scanf("%c %d", &op, &cut); getchar(); 22 if(op == 'H') 23 { 24 l = sh.lower_bound(cut); 25 r = l; l--; 26 sh.insert(cut); 27 mh.insert(cut-(*l)); 28 mh.insert((*r)-cut); 29 mh.erase(mh.find((*r) - (*l))); 30 } 31 else 32 { 33 l = sv.lower_bound(cut); 34 r = l; l--; 35 sv.insert(cut); 36 mv.insert(cut - (*l)); 37 mv.insert((*r) - cut); 38 mv.erase(mv.find((*r) - (*l))); 39 } 40 41 printf("%I64d ", (long long)(*mh.rbegin()) * (*mv.rbegin())); 42 } 43 44 return 0; 45 }
最后再说一点题外话：这次是只要删除multiset中一个元素，只要S.erase(S.find(val))就行了。
如果我们想要删除所有multiset中值为val的元素该怎么办？
有一个equal_range的成员函数，调用S.equal_range(val)就会返回一个pair<multiset::iterator, multiset::iterator>类型的值ret，它代表了一个区间，这个区间中就包含了multiset中所有值为val的元素。最后删除的时候，直接S.erase(ret.first, ret.second)
下面是http://www.cplusplus.com/reference/set/multiset/equal_range/ 中的实例：
1 // multiset::equal_elements 2 #include <iostream> 3 #include <set> 4 5 typedef std::multiset<int>::iterator It; // aliasing the iterator type used 6 7 int main () 8 { 9 int myints[]= {77,30,16,2,30,30}; 10 std::multiset<int> mymultiset (myints, myints+6); // 2 16 30 30 30 77 11 12 std::pair<It,It> ret = mymultiset.equal_range(30); // ^ ^ 13 14 mymultiset.erase(ret.first,ret.second); 15 16 std::cout << "mymultiset contains:"; 17 for (It it=mymultiset.begin(); it!=mymultiset.end(); ++it) 18 std::cout << ' ' << *it; 19 std::cout << ' '; 20 21 return 0; 22 }