A. Playing with Paper
如果a是b的整数倍，那么将得到a/b个正方形，否则的话还会另外得到一个(b, a%b)的长方形。
时间复杂度和欧几里得算法一样。
#include <iostream>
#include <cstdio>
using namespace std; //const int maxn = ; int main()
{
//freopen("in.txt", "r", stdin); long long a, b, ans = ;
scanf("%I64d%I64d", &a, &b);
while(a % b != )
{
ans += a / b;
long long ta = b;
long long tb = a % b;
a = ta; b = tb;
}
ans += a / b;
printf("%I64d\n", ans); return ;
}
代码君
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
#include <iostream>
#include <cstdio>
using namespace std; const int maxn = + ; int n;
char s1[maxn], s2[maxn]; int G[][]; int main()
{
//freopen("in.txt", "r", stdin); scanf("%d", &n); getchar();
gets(s1+); gets(s2+); int ans = , p1 = -, p2 = -;
for(int i = ; i <= n; i++) if(s1[i] != s2[i]) ans++; for(int i = ; i <= n; i++) if(s1[i] != s2[i])
{
int x = s1[i]-'a', y = s2[i]-'a';
G[x][y] = i;
if(G[y][x]) { p1 = i; p2 = G[y][x]; ans -= ; break; }
} bool flag = false;
if(p1 + p2 == -)
{
for(int i = ; i < ; i++)
{
for(int j = ; j < ; j++) if(G[i][j])
{
for(int k = ; k < ; k++) if(G[j][k])
{
flag = true;
ans--;
p1 = G[i][j]; p2 = G[j][k];
break;
}
if(flag) break;
}
if(flag) break;
}
} printf("%d\n%d %d\n", ans, p1, p2); return ;
}
代码君
C. Glass Carving
果然，熟练使用STL是很有必要的，减小编码复杂度，速度上也不会太慢。
话说有一个人对着一块玻璃横着或者竖着切来切去。
每次切完都要询问一下最大的一块玻璃的面积是多少。
将所有切割的位置放在一个集合中，还有所有相邻位置之间的距离放在一个多重集合里面。
每一次切割位置x，都将a<x<b这个区间分成了两个，同时将x加入到对应的切割位置集合；然后更新一下距离集合，具体就是删除b-a这段距离(如果有多个，只要删除一个就好了)，然后分别插入(x-a) 和 (b-x)这两段被分隔开的距离。
#include <bits/stdc++.h>
using namespace std; int main()
{
//freopen("in.txt", "r", stdin); set<int> sh, sv;
multiset<int> mh, mv;
set<int>::iterator l, r; int w, h, n;
scanf("%d%d%d", &w, &h, &n); getchar();
sh.insert(); sh.insert(h);
sv.insert(); sv.insert(w);
mh.insert(h); mv.insert(w); while(n--)
{
char op; int cut;
scanf("%c %d", &op, &cut); getchar();
if(op == 'H')
{
l = sh.lower_bound(cut);
r = l; l--;
sh.insert(cut);
mh.insert(cut-(*l));
mh.insert((*r)-cut);
mh.erase(mh.find((*r) - (*l)));
}
else
{
l = sv.lower_bound(cut);
r = l; l--;
sv.insert(cut);
mv.insert(cut - (*l));
mv.insert((*r) - cut);
mv.erase(mv.find((*r) - (*l)));
} printf("%I64d\n", (long long)(*mh.rbegin()) * (*mv.rbegin()));
} return ;
}
代码君
最后再说一点题外话：这次是只要删除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/ 中的实例：
// multiset::equal_elements
#include <iostream>
#include <set> typedef std::multiset<int>::iterator It; // aliasing the iterator type used int main ()
{
int myints[]= {,,,,,};
std::multiset<int> mymultiset (myints, myints+); // 2 16 30 30 30 77 std::pair<It,It> ret = mymultiset.equal_range(); // ^ ^ mymultiset.erase(ret.first,ret.second); std::cout << "mymultiset contains:";
for (It it=mymultiset.begin(); it!=mymultiset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n'; return ;
}
代码君