这里主要是Windows开发编程题 – 小部分选择题。
距离的总和
时间限制：C/C++语言 2000MS；其他语言 4000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
定义两个大于2的偶数之间的距离，为这两个数之间质数的个数。
从小到大输入n个大于2的偶数，输出所有数两两之间距离的总和（应该有n*(n-1)/2个距离，输出总和就好)。
输入
第一行是输入偶数的个数，最小为2，最大可能到几万。
之后每行为一个偶数，最小是4，最大可能是几百万，不重复的升序排列。
输出
输入数据两两间距离的总和，这应该是一个不小于0的整数。
样例输入
3
4
6
12
样例输出
6
题意解析：
以样例为例，数据是 4 6 12 ，对应素数是 5 7 11
4-6距离是 一个素数 5
6-12距离是 两个素数 7 和 11
所以总距离应该是 1(4-5) + 2(6-12) + 3(4-12) = 6
思路：筛法打表 – 前缀和
代码如下：
|
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 |
#include <iostream> #include <iomanip> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <cassert> #include <climits> #include <ctime> #include <vector> #include <queue> #include <list> #include <stack> #include <map> #include <numeric> #include <sstream> #include <set> #include <utility> #include <deque> #include <functional> #include <iterator> using namespace std; typedef long long LL; typedef unsigned int UInt; typedef unsigned long long ULL; typedef long double LD; int HashSu[10000010]; //1000W vector <int> su; vector <int> V; vector <int> Num; //打表 int CalSu(int n) { for(int i=0;i<=n;i++) { HashSu[i] = -1; } HashSu[0] = 0; HashSu[1] = 0; HashSu[2] = 1; //2是第一个素数 for(int i = 2; i <= n; i++) { if(HashSu[i] != 0) { HashSu[i] = 1; su.push_back(i); for(int j = 2; i * j<= n; j++) { HashSu[i*j] = 0; } } } } int main() { int num; scanf("%d",&num); int a; int Max = 0; for(int i=0;i<num;i++) { cin >> a; if(a > Max) Max = a; V.push_back(a); Num.push_back(0); } //打表 - 计算素数 CalSu(Max + 1); //判断从 V[i-1] 到 V[i] 内有多少素数 - 记录在 Num[i] 内 int key = 1; for(int i = 1; i < su.size() && su[i] <= Max; i++) { //如果值比较小 if(su[i] < V[key] && su[i] > V[key-1]) { Num[key] += 1; } else if(su[i] > V[key]) { key++; i--; } } //计算前缀和 for(int i=1;i<Num.size();i++) { Num[i] += Num[i-1]; } //计算结果 - 不会超时哦 LL ans = 0; for(int i=0; i < num; i++) { for(int j = i + 1; j < num; j++) { ans += (Num[j] - Num[i]); } } cout << ans << endl; } |
这里有同学想问一下 筛法打表 和 前缀和 是怎么回事？
先说筛法打表吧 – 这是一个快速判断从 [0,n]之间的所有素数的方法。
原理是基于一个素数的约数除了它本身和1外没有其他数。
所以先进行基本处理 0不是素数 1不是素数 2是素数
接下来从2开始对所有数据进行处理，如果是素数的，就放入到vector里面(这是我们筛出来的素数)，然后将后面的从[0,n]之间的所有2的倍数都设置为非素数。
然后处理下一个数，再下一个，再下一个。
然后我们现在考虑数x，我们遍历到x的时候，发现它没有被设置为非素数，意思是前面[2,x-1]的所有数据都不是x的倍数，是不是就说明了x是一个素数呢…然后我们再把 x的倍数 设置为非素数...
这就是筛法打表的原理。计算量理论讲是 O(n^1.5)，比一个个判断要快。
接下来我们对输入的数据进行处理…这里以我们的数据V[ 4 6 12]为例。
要处理的数据是素数数据 su[2 3 5 7 11] – 这里我们设置一个Num数组，Num[i]记录V[i-1]到V[i]之间的素数个数
要注意的是 Num[0] (V[0] = 4)，它的值必须是0.
然后我们就能得到Num[0,1,2] ->（4,5,6,7,11,12） 这里我加粗的是数据 – 红色的是素数
然后我们将Num数组的数据从 V[i-1]到V[i]之间的素数个数 改为 从V[0]到V[i]之间的素数
这样数组就变成了Num[0,1,3] …
这样:
4(V[0])-6(V[1])之间的素数个数就是 Num[1] – Num[0] = 1
6(V[1])-12(V[2])之间的素数个数就是 Num[2] – Num[1] = 2
4(V[0])-12(V[2])之间的素数个数就是 Num[2] – Num[0] = 3
然后加起来就是 – 我们的结果6…
一个字符串的最大回文前缀长度
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
求一个字符串的最大回文前缀长度。回文是指正反方向读起来都一样的字符串，比如“abcdcba”就是一个回文。
输入
一个文本文件，至少包含一个字节。每个字节是一个字符。最大长度可能有几十万字节。
输出
最大回文前缀的长度。
样例输入
sogou
样例输出
1
题意解析：
题目要问的是 最大 回文 前缀 长度
翻译过来就是 字符串的所有前缀里面最长的回文
那么，哪些是前缀呢，以样例为例，它有5个前缀
- sogou
- sogo
- sog
- so
- s
然后我们在这五个前缀里面找到最长的回文。发现只有s，s的长度是1，于是结果就是1.
思路：…好像没什么思路哦…尴尬 – 就那么一判断。
代码如下：
|
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 |
#include <iostream> #include <iomanip> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <cassert> #include <climits> #include <ctime> #include <vector> #include <queue> #include <list> #include <stack> #include <map> #include <numeric> #include <sstream> #include <set> #include <utility> #include <deque> #include <functional> #include <iterator> using namespace std; typedef long long LL; typedef unsigned int UInt; typedef unsigned long long ULL; typedef long double LD; char Str[1000010]; //100W bool IsHui(int end) { for(int i = 0; i < (end+1)/2; i++) { if(Str[i] != Str[end-i]) { return false; } } return true; } int main() { gets(Str); int len = strlen(Str); for(int i = len; i > 0; i--) { if( IsHui(i - 1) ) { cout << i << endl; break; } } } |
选择题刻意记了一道题，主要是想验证下static有什么不同：
问下面的代码，在哪一个输出的位置报错。
|
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 |
#include <iostream> using namespace std; class A { public: void FunctionA() { cout << "FunctionA" << endl; } virtual void FunctionB() { cout << "FunctionB" << endl; } static void FunctionC() { cout << "FunctionC" << endl; } }; class B : public A { public: virtual void FunctionB() { cout << "FunctionB" << endl; } int FunctionD() { cout << "FunctionD" << endl; } }; int main() { B *b = NULL; b->FunctionA(); b->FunctionB(); b->FunctionC(); b->FunctionD(); return 0; } |
要注意这里b是NULL，所以应该是在B这里，找虚函数表的时候报错了。
有疑问的是C，它有static有没有影响。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
typedef void (*Func)(void); void (*pFun)(void) = NULL; pFun = (Func)(&A::FunctionA); cout << "A::FunctionA : " << (void*)(&A::FunctionA) << " - "; pFun(); pFun = (Func)(&A::FunctionB); cout << "A::FunctionB : " << (void*)(&A::FunctionB) << " - "; pFun(); pFun = (Func)(&A::FunctionC); cout << "A::FunctionC : " << (void*)(&A::FunctionC) << " - "; pFun(); |
拿上面的代码测试了一下，函数地址还是在类里面。…
static修饰 表示该函数仅在这个文件内可见，也就是你不能在另外的文件内调用这个函数。
有考到一个PE文件段的内容的：
下面链接里的17.1.2里面有讲到常用段的意义
链接：http://blog.tk-xiong.com/archives/921
其他题目没怎么注意了…
你投的移动安卓么?
Windows啊…标题说了…
回文这题我真的是服, 还有第一题到底所有的数是指的偶数还是质数, 没看懂
这里的所有数指的是输入的数据。输入的所有数据的两两之间距离
居然是原题，我怎么之前没有看到呢。
这是刚发的
不是原题。是我刚写的…尴尬