夜间模式暗黑模式
字体
阴影
滤镜
圆角

Category: Algorithm

4 篇文章

thumbnail
C++迭代器
[toc] 迭代器类型 输入迭代器输出迭代器正向迭代器双向迭代器随机访问迭代器 将指针用作迭代器 迭代器是广义指针,而指针满足所有迭代器的要求 输出迭代器示例 引入头文件#include<iterator>out_iter 迭代器现在是一个接口,可以使用cout来显示信息 ostream_iterator 第一个模板参数(此处为int)指出了发送给输出流的数据类型,第二个模板参数(此处为char)指出了输出流使用的字符类型(另一个可能的值是wchar_t)。构造函数的第一个参数(此处为cout)指出了要使用的输出流,它也可以是用于文件输出的流;最后一个字符串参数是发送给输出流的每个数据项后面的分隔符。stl的copy()函数可以将一个容器复制到另一个容器,前两个参数是输入迭代器,最后一个参数是输出迭代器。copy()函数将覆盖目标容器的数据。也可以构建一个匿名迭代器copy(dice, dice + 6, ostream_iterator<int, char>(cout, "")); #include <iostream> #include<iterator> using namespace std; int main() { ostream_iterator<int, char> out_iter(cout, " "); int dice[] = { 1,2,3,4,5,6 }; copy(dice, dice + 6, out_iter); //output:1 2 3 4 5 6 copy(dice, dice + 6, ostream_iterator<int, char>(cout, " ")); //same output } 输入迭代器 copy(istream_iterator(cin), istream_iterator(), v.begin());istream_iterator第一个模板参数指出要读取的数据类型,第二个参数指出输入流使用的字符类型。使用构造函数参数cin意味着使用由cin管理的输入流,省略构造函数表示输入失败,因此上述代码从输入流读取,直到文件结尾、类型不匹配或出现其他输入故障为止。 reverse_iterator 对reverse_iterator的递增操作将导致它被递减vector的rbegin和rend成员提供了反向迭代的功能。前者返回一个指向超尾的反向迭代器,后者指向第一个元素的反向迭代器。 copy(v.begin(), v.end(), out_iter); //display forward copy(v.rbegin(), v.rend(), out_iter); //display in reverse order rbegin()和end()返回相同的值(超尾),但是它们的类型不同(reverse_iterator和iterator),对rend和begin()同理。对反向指针需要做一种特殊补偿,反向指针通过先递减,再解引用解决位置问题。 其他预定义迭代器 insert_iterator 没有限制front_insert_iterator 只能用于允许在起始位置做时间固定插入的容器类型。vector不能满足这种要求,但queue满足。back_insert_iterator 只能用于允许在尾部快速插入(O(1))的容器,vector符合这种要求。 可以使用insert_iterator<vector<int> >insert_iter(v, v.begin());来实现vector的首元素插入
thumbnail
UVa 1588 – Kickdown
[begin]给[/begin]定两串由数字1和2构成的序列,表示目标钢条厚度分布情况。求能切割出目标两串钢条的厚度为3的钢条的最小长度。有什么好说的?暴力模拟就行了。 //cpp #include<iostream> #include<cstring> using namespace std; int main(){ char s[105], t[105]; int len1, len2, len; while(cin>>s>>t){ int i, j, x, y; int len1 = strlen(s), len2 = strlen(t); for( i=0; i<len1; i++ ){ bool flag = true; for( j=0; j<len2 && j+i<len1 ; j++) if(s[i+j]=='2'&&t[j]=='2'){ flag = false; break; } if (flag) break; } x = max(len1, len2+i); i = j = 0; for( i=0; i<len2; i++){ bool flag = true; for( j=0; j<len1 && j+i<len2; j++ ) if(t[i+j]=='2'&&s[j]=='2'){ flag = false; break ; } if(flag) break; } y = max(len2, len1+i); cout<<min(x,y)<<endl; } return 0; }
thumbnail
UVa 1587 – Box
给定六个长方形的宽高,试问能否将其组成一个长方体。对于一个长方体来说有长宽高这三种属性,并且正对面全等。不妨设长宽高为abc(其中a>b>c),则六个面宽高情况一定为ab、ab、ac、ac、bc、bc。长宽格式固定,思路就立马出现了。 //cpp #include <bits/stdc++.h> using namespace std; struct face{ int x, y; }a[6]; bool check() { if(memcmp(a, a+1, sizeof(face)) || memcmp(a+2, a+3, sizeof(face)) || memcmp(a+4, a+5, sizeof(face))) return false; if(a[0].x!=a[2].x || a[0].y!= a[4].x || a[2].y!=a[4].y) return false; return true; } int main() { while(cin >> a[0].x >> a[0].y >> a[1].x >> a[1].y >> a[2].x >> a[2].y >> a[3].x >> a[3].y >> a[4].x >> a[4].y >> a[5].x >> a[5].y){ for(int i = 0; i < 6; ++i) if(a[i].x < a[i].y) swap(a[i].x, a[i].y); sort(a, a+6, [](const face a, const face b) {return a.x==b.x ? (a.y > b.y) : (a.x > b.x);}); printf("%s\n", check() ? "POSSIBLE" : "IMPOSSIBLE"); } return 0; }
thumbnail
UVa 202 – Repeating Decimals
如何判定两个自然数除得有理小数的循环节及其长度?我们可以通过模拟人工笔算除法的过程发现其内在的规律。对于一般的除数m,除法运算后所得余数情况至多有m-1种。根据抽屉原理,必然会有循环节的出现。我们要做的就是记录每一步的运算情况,就像自己手算除法一样,并从中判断余数重复,进而问题得解。 //cpp #include "pch.h" #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #define MAXLEN 3003 using namespace std; int ans[MAXLEN], sign[MAXLEN], remain[MAXLEN]; int main() { int n, m, temp; while (cin >> n >> m) // n为被除数,m为除数 { // 初始化 temp = n; memset(ans, 0, sizeof(ans)); memset(sign, 0, sizeof(sign)); int count = 0; // 整数部分除法运算 ans[count++] = n / m; n %= m; // 小数部分除法运算 // ans数组用来存储每一位商 // sign数组用来标记m-1种余数的出现情况 // s数组用来记录每一步的余数 // 若余数没有重复(!sign[n])并且没有将n除尽,则继续除法运算 while (!sign[n] && n) { sign[n] = count; remain[count] = n; ans[count++] = 10 * n / m; n = 10 * n % m; } // 输出整数部分 printf("%d/%d = %d", temp, m, ans[0]); printf("."); for (int i = 1; i < count && i <= 50; ++i) { // 判断何时开始循环 输出括号 if (n && remain[i] == n) printf("("); printf("%d", ans[i]); } // 除尽特判 if (!n) printf("(0"); if (count > 50) printf("..."); printf(")\n"); printf(" %d = number of digits in repeating cycle\n\n", !n ? 1 : count - sign[n]); } return 0; }