1001 素数因子 思路：用素数筛选法筛选出范围内的全部素数，然后判断是否能整除就好了。
#include <iostream> #include <cstdio> #include <cmath> using namespace std; const int N = 100000; bool isPrime[N]; void initPrime() { fill(isPrime, isPrime + N, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i<N; i++){ if (isPrime[i]){ for (int j = i * 2; j<N; j += i) isPrime[j] = false; } } } int main(){ int t; cin >> t; initPrime(); while (t--){ int n; cin >> n; int counter = 0; for (int i = 1; i <= sqrt(n); i++){ if (n%i == 0){ if (isPrime[i]) counter++; if (n / i != i) if (isPrime[n / i]) counter++; } } cout << counter << endl; } return 0; }1002 矩阵小游戏 思路：用到的前缀和的思想，我们把全部的矩形的元素和加起来，之后我们算一个x*y的矩阵的元素和就直接在这些矩阵和计算就好了。（这里前缀和的思路和我博客中的一道题的思路很像：传送门）
#include <iostream> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <set> #include <map> #include <algorithm> #define N 1010 #define LL long long using namespace std; LL sum, ans[N][N]; int main() { cin.sync_with_stdio(false); int t, temp; cin >> t; while (t--) { int m, n, x, y; cin >> n >> m >> x >> y; sum = 0; memset(ans, 0, sizeof(ans)); for (int i = 1; i <= n; i++) { sum = 0; for (int j = 1; j <= m; j++) { cin >> temp; sum += temp; ans[i][j] = ans[i - 1][j] + sum; } } LL tans = 0; for (int i = 1; i <= n - x + 1;i++) { for (int j = 1; j <= m - y + 1;j++) { int xx = i + x - 1; int yy = j + y - 1; LL yous = ans[i - 1][yy]; LL zuox = ans[xx][j - 1]; tans = max(tans, ans[xx][yy] + ans[i - 1][j - 1] - zuox - yous); } } cout << tans << endl; } return 0; }1003 凯撒加密 思路：因为给了你密码表，所以我们只需要把密码表对应存进map中就好了，我们要建两个map，一个由明文对应的密文，另一个是密文对应的明文，都把空格加入map，代表空格对应的就是空格。然后直接遍历串就好了。
#include <iostream> #include <string> #include <cstdio> #include <cstdlib> #include <set> #include <map> #define N 1010 #define LL long long using namespace std; map<char, char> a, b; int main() { cin.sync_with_stdio(false); string str1, str2; cin >> str1 >> str2; int T; for (int i = 0; i < str1.length(); i++) { a[str1[i]] = str2[i]; b[str2[i]] = str1[i]; } a[' '] = ' '; b[' '] = ' '; cin >> T; while (T--) { cin >> str1; cin.get(); getline(cin, str2); if (str1 == "Encrypt") { for (int i = 0; i < str2.length(); i++) { cout << a[str2[i]]; } cout << endl; } else { for (int i = 0; i < str2.length(); i++) { cout << b[str2[i]]; } cout << endl; } } return 0; }1004 贪吃蛇 思路：这个很好写，根据题意判断什么时候旋转，然后单纯的模拟就好了（先存在数组中最后输出）。
#include <iostream> using namespace std; int mp[105][105]; int dir[4][2] = { 1,0,0,-1,-1,0,0,1 }; int n; bool ok(int x, int y){ if (x<0 || x >= n || y<0 || y >= n)return false; int cnt = mp[y][x + 1] + mp[y + 1][x]; if (x != 0) cnt += mp[y][x - 1]; if (y != 0) cnt += mp[y - 1][x]; if (cnt >= 2)return false; return true; } int main(){ int t; cin >> t; while (t--){ cin >> n; for (int i = 0; i<105; i++) for (int j = 0; j<105; j++) mp[i][j] = 0; int d = 0; int x = 0, y = n - 1; while (1){ mp[y][x] = 1; if (!ok(x + dir[d][0], y + dir[d][1])){ d++, d %= 4; if (!ok(x + dir[d][0], y + dir[d][1])) break; } x += dir[d][0]; y += dir[d][1]; } for (int i = n - 1; i >= 0; i--){ for (int j = 0; j<n; j++) cout << (mp[i][j] == 1 ? '*' : ' '); cout << endl; } cout << endl; } return 0; }1005 读数字 思路：判断数字的不同情况，我这里用了map去转换数字到中文，但是我们要知道以下几个规则：
末尾的0不用读出来中间连续的0只需要读一次千位没有0然后直接模拟就好了。
#include <iostream> #include <string> #include <set> #include <map> #define N 1010 #define LL long long using namespace std; map<int, string> mapp; int main() { cin.sync_with_stdio(false); int T, n; cin >> T; mapp[1] = "一"; mapp[2] = "二"; mapp[3] = "三"; mapp[4] = "四"; mapp[5] = "五"; mapp[6] = "六"; mapp[7] = "七"; mapp[8] = "八"; mapp[9] = "九"; while (T--) { cin >> n; int num = 0; int flag = 0; string str=""; if (n == 0) { cout << "零" << endl; } else{ while (n) { int m = n % 10; n /= 10; if (num == 0) { if (m != 0) str = mapp[m], flag = 1; } else if (num == 1) { if (m == 0) { if (flag) { flag = 2; str = "零" + str; } } else { str = mapp[m] + "十" + str; } } else if (num == 2) { if (m == 0) { if (flag == 1) { str = "零" + str; } } else { str = mapp[m] + "百" + str; } } else { str = mapp[m] + "千" + str; } num++; } cout << str << endl; } } return 0; }1006 数字黑洞 思路：写两个子函数， 一个将一个四位数变成最大的四位数，另一个变成最小的，然后对输入的数字逐步转换 直到出现6174 并对四位数字全相同的数进行特判。
#include<cstdio> #include<iostream> using namespace std; typedef long long ll; int da[4], xiao[4]; int bianda(int x) { int k = 0; while (x>0) { da[k++] = x % 10; x /= 10; } for (int i = k; i<4; i++) da[i] = 0; for (int i = 0; i<3; i++) for (int j = i + 1; j<4; j++) if (da[i]<da[j]) swap(da[i], da[j]); int sum = 0; for (int i = 0; i<4; i++) { sum *= 10; sum += da[i]; } return sum; } int bianxiao(int x) { int k = 0; while (x>0) { xiao[k++] = x % 10; x /= 10; } for (int i = k; i<4; i++) xiao[i] = 0; for (int i = 0; i<3; i++) for (int j = i + 1; j<4; j++) if (xiao[i]>xiao[j]) swap(xiao[i], xiao[j]); int sum = 0; for (int i = 0; i<4; i++) { sum *= 10; sum += xiao[i]; } return sum; } int main() { int t; cin >> t; while (t--) { int n, cnt = 0; cin >> n; if (n % 1111 == 0) cout << "no" << endl; else { while (n != 6174) { int nd = bianda(n); int nx = bianxiao(n); cnt++; n = nd - nx; } cout << cnt << endl; } } return 0; }1007 抢红包 思路：我们用set进行去重，然后因为set是按序排列的，所以直接判断set中有没有三个元素，如果有就输出第三小的，否则输出-1。 当然我们也可以用数组来写，sort一下，然后手动计数就好了。
#include <iostream> #include <string> #include <set> #include <map> #define N 1010 #define LL long long using namespace std; set<int> s; int main() { cin.sync_with_stdio(false); int n, T, m; cin >> T; while (T--) { cin >> n; s.clear(); for (int i = 0; i < n; i++) { cin >> m; s.insert(m); } if (s.size() < 3) { cout << -1 << endl; } else { int i = 0; for (set<int>::iterator it = s.begin(); i < 3; it++, i++) { if (i == 2) { cout << *it << endl; } } } } return 0; }1008 最大面积 思路：我们知道周长相同的矩形，想让他面积尽可能大的话，就要把长宽接近，但是因为题目是2*n个字符，所以字符数肯定是偶数的，所以什么矩形要不是正方形，要不就是长比宽打一个单位的矩形。我们知道这个结论以后直接判断出他是否能围成一个正方形，然后算出长宽输出。
#include <iostream> using namespace std; int main(){ int T,n; int a,b; char c; cin.sync_with_stdio(false); cin>>T; while(T--){ cin>>n>>c; if(n%2){ a=n/2+2; b=n/2+1; } else{ a=n/2+1; b=n/2+1; } for(int i=0;i<a;i++){ cout<<c; } cout<<endl; for(int i=2;i<b;i++){ cout<<c; for(int j=2;j<a;j++){ cout<<" "; } cout<<c<<endl; } for(int i=0;i<a;i++){ cout<<c; } cout<<endl; if(T!=0){ cout<<endl; } } return 0; }1009 旅游 思路：由于加了过路费这一限制条件，本题不能直接使用类似dijkstra最短路算法，由于数据量不大，可以考虑用深度优先搜索（dfs）求解。本题是基础dfs，理解了dfs算法后就不难看懂本题的代码。其中vis[]数组代表在某条搜索树的路径上访问过哪些节点，在进入k这个搜索节点时，将vis[k]置1，表示在搜索路径中有k这个节点，回溯时将vis[k]置0，表示已经完成了k这个节点的搜索，此时换一个节点开始搜索，这时k已经不再搜索路径上了，所以vis[k]置0。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 105 #define INF 0x3f3f3f3f #define NIL -1 #define min(a, b) ((a) < (b) ? (a) : (b)) int G[MAXN][MAXN]; int cost[MAXN][MAXN]; int vis[MAXN]; int ans, N, V; void dfs(int s, int L, int C){ if (s == N) { ans = min(ans, L); return; } for (int i = 1; i <= N; ++i) { if (G[s][i] == INF || vis[i]) continue; if (C + cost[s][i] > V) continue; vis[i] = 1; dfs(i, L + G[s][i], C + cost[s][i]); vis[i] = 0; } } int main(){ int T, M, a, b, l, c; scanf("%d", &T); while (T--){ memset(G, 0x3f, sizeof(G)); memset(cost, 0x3f, sizeof(cost)); memset(vis, 0, sizeof(vis)); scanf("%d", &V); scanf("%d %d", &N, &M); while (M--){ scanf("%d %d %d %d", &a, &b, &l, &c); G[a][b] = l; cost[a][b] = c; } ans = INF; dfs(1, 0, 0); if (ans == INF) puts("-1"); else printf("%d\n", ans); } return 0; }1010 分配学号 思路：通过结构体存储学院的院系代码，以及当前能分配的最小序号，然后通过map的院系名称映射该结构体，然后我们根据后面的输入按情况输出，每次合法输出以后都把该学院的最小序号加一。 （注意最后那个最小序号当前可能不是6位数，要格式化输出）
#include <iostream> #include <string> #include <map> #include <iomanip> #define N 1010 #define LL long long using namespace std; struct node { int num; string str; }school; map<string, node> yx; int main() { cin.sync_with_stdio(false); int T, n, m; string str; cin >> T; while (T--) { cin >> n >> m; yx.clear(); for (int i = 0; i < n; i++) { cin >> str >> school.str >> school.num; yx[str] = school; } for (int i = 0; i < m; i++) { cin >> str; if (yx.find(str) != yx.end()) { cout << 2018 << yx[str].str; cout<< setfill('0') << setw(6) << yx[str].num << endl; yx[str].num++; } else { cout << "Invalid" << endl; } cin >> str; } } return 0; }