作为一个编程菜鸡，先刷刷前几题，八道题目争取6题有思路，5题能写出来，3题能AC（大佬勿嘲笑）。由于部分题目已经关闭，无法看到是否AC（以下代码可能无法通过全部测试用例），如有错误，请指出，O(∩_∩)O谢谢。
地址：
http://bailian.openjudge.cn/ssxly2018lx/
A:判决素数个数
全局题号2178 提交次数95 尝试人数32 通过人数28
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 输入两个整数X和Y，输出两者之间的素数个数（包括X和Y）。
- 输入
- 两个整数X和Y（1 <= X,Y <= 105）。
- 输出
- 输出一个整数，表示X，Y之间的素数个数（包括X和Y）。
- 样例输入
-
11 100
- 样例输出
-
125
C++代码
|
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 |
/* Bailian3177 判决素数个数 */ #include <stdio.h> void swap(int *a, int *b) { int t; t = *a; *a = *b; *b = t; } int isprime(int n){ int i; for(i=3; i*i<=n; i+=2) if(n % i == 0) return 0; return 1; } int main(void) { int x, y, sum=0, i; scanf("%d%d", &x, &y); if(x > y) swap(&x, &y); if(x <= 2) { x = 3; sum = 1; } else { if(x % 2 == 0) x++; sum = 0; } for(i=x; i<=y; i+=2) if(isprime(i)) sum++; printf("%d\n", sum); return 0; } |
B:编码字符串
全局题号12556 提交次数56 尝试人数32 通过人数32
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 在数据压缩中，一个常用的方法是行程长度编码压缩。对于一个待压缩的字符串，我们可以依次记录每个字符及重复的次数。例如，待压缩的字符串为”aaabbbbcbb”，压缩结果为(a,3)(b,4)(c,1)(b,2)。这种压缩对于相邻数据重复较多的情况有效，如果重复状况较少，则压缩的效率较低。
现要求根据输入的字符串，首先将字符串中所有大写字母转化为小写字母，然后将字符串进行压缩。
- 输入
- 一个字符串，长度大于0，且不超过1000，全部由大写或小写字母组成。
- 输出
- 输出为编码之后的字符串，形式为：(a,3)(b,4)(c,1)(d,2)，即每对括号内分别为小写字符及重复的次数，不含任何空格。
- 样例输入
-
1aAABBbBCCCaaaaa
- 样例输出
-
1(a,3)(b,4)(c,3)(a,5)
C++实现
|
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 |
#include<iostream> #include<vector> #include<string> using namespace std; int main(){ string str; cin>>str; string ans = ""; int cnt = 1; for(int i = 0; i < str.length(); i++){ if(tolower(str[i]) == tolower(str[i + 1]) && i + 1 < str.length()){ cnt++; }else{ cout<<'('; cout<<char(tolower(str[i])); cout<<","; cout<<to_string(cnt); cout<<")"; cnt = 1; } } cout<<endl; return 0; } |
C:岛屿周长
全局题号12558 提交次数38 尝试人数28 通过人数28
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 用一个n*m的二维数组表示地图，1表示陆地，0代表海水，每一格都表示一个1*1的区域。地图中的格子只能横向或者纵向连接（不能对角连接），连接在一起的陆地称作岛屿，同时整个地图都被海水围绕。假设给出的地图中只会有一个岛屿，并且岛屿中不会有湖（即不会有水被陆地包围的情况出现）。请判断所给定的二维地图中岛屿的周长。
- 输入
- 第一行为n和m，表示地图的大小(1<=n<=100, 1<=m<=100)。接下来n行，每行有m个数，分别描述每一格的数值。数值之间均用空格隔开。
- 输出
- 只有一行，即岛屿的周长（正整数）。
- 样例输入
-
12343 41 1 1 00 1 0 01 1 0 0
- 样例输出
-
114
C++实现
|
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 |
#include<iostream> #include<vector> #include<cstdio> using namespace std; int e[101][101]; bool visit[101][101]; int go[][2] = {0, 1, 0, -1, 1, 0, -1, 0}; int n, m; int perimeter = 0; void DFS(int x, int y){ for(int i = 0; i < 4; i++){ int nx = x + go[i][0]; int ny = y + go[i][1]; if(nx < 0 || nx > n - 1 || ny < 0 || ny > m - 1){ perimeter++; continue; } if(e[nx][ny] == 0){ perimeter++; continue; } if(visit[nx][ny])continue; visit[nx][ny] = true; DFS(nx, ny); visit[nx][ny] = false; } } int main(){ cin>>n>>m; int srcx, srcy; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ scanf("%d", &e[i][j]); if(e[i][j] == 1){ srcx = i; srcy = j; } } } visit[srcx][srcy] = true; DFS(srcx, srcy); cout<<perimeter<<endl; return 0; } |
D:Safecracker
全局题号250 提交次数35 尝试人数17 通过人数13
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- “The item is locked in a Klein safe behind a painting in the second-floor library. Klein safes are extremely rare; most of them, along with Klein and his factory, were destroyed in World War II. Fortunately old Brumbaugh from research knew Klein’s secrets and wrote them down before he died. A Klein safe has two distinguishing features: a combination lock that uses letters instead of numbers, and an engraved quotation on the door. A Klein quotation always contains between five and twelve distinct uppercase letters, usually at the beginning of sentences, and mentions one or more numbers. Five of the uppercase letters form the combination that opens the safe. By combining the digits from all the numbers in the appropriate way you get a numeric target. (The details of constructing the target number are classified.) To find the combination you must select five letters v, w, x, y, and z that satisfy the following equation, where each letter is replaced by its ordinal position in the alphabet (A=1, B=2, …, Z=26). The combination is then vwxyz. If there is more than one solution then the combination is the one that is lexicographically greatest, i.e., the one that would appear last in a dictionary.”
v – w2+ x3– y4+ z5= target
“For example, given target 1 and letter set ABCDEFGHIJKL, one possible solution is FIECB, since 6 – 92+ 53– 34+ 25= 1. There are actually several solutions in this case, and the combination turns out to be LKEBA. Klein thought it was safe to encode the combination within the engraving, because it could take months of effort to try all the possibilities even if you knew the secret. But of course computers didn’t exist then.”
“Develop a program to find Klein combinations in preparation for field deployment. Use standard test methodology as per departmental regulations.
- 输入
- Input consists of one or more lines containing a positive integer target less than twelve million, a space, then at least five and at most twelve distinct uppercase letters. The last line will contain a target of zero and the letters END; this signals the end of the input.
- 输出
- For each line output the unique Klein combination, or ‘no solution’ if there is no correct combination. Use the exact format shown below.”
- 样例输入
-
123451 ABCDEFGHIJKL11700519 ZAYEXIWOVU3072997 SOUGHT1234567 THEQUICKFROG0 END
- 样例输出
-
1234LKEBAYOXUZGHOSTno solution
C++实现
|
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> #include<string> #include<cmath> using namespace std; string ans, s; int target; bool visit[20]; //v - w2+ x3- y4+ z5= target void DFS(int cnt, char *tempchar){ if(cnt == 5){ int num = 0; //记录计算的值 string t = ""; for(int i = 0; i < cnt; i++){ t += tempchar[i]; if(i % 2 == 1)num -= powl(tempchar[i] - 'A' + 1, i + 1); //计算式子 if(i % 2 == 0)num += powl(tempchar[i] - 'A' + 1, i + 1); } if(num == target && t > ans) ans = t; //判断是否满足等式且字母序较大 return; } for(int i = 0; i < s.length(); i++){ //对于每个字母 if(visit[i])continue; visit[i] = true; tempchar[cnt] = s[i]; DFS(cnt + 1, tempchar); visit[i] = false; //回溯 } } int main(){ while(cin>>target>>s){ if(target == 0 && s == "END")break; ans = ""; char tempchar[5]; //存储待判断的值 fill(visit, visit + 20, 0); DFS(0, tempchar); if(ans == "")cout<<"no solution"<<endl; else cout<<ans<<endl; } return 0; } |
E:怪盗基德的滑翔翼
全局题号4977 提交次数51 尝试人数20 通过人数18
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。
有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已，怪盗基德只能操作受损的滑翔翼逃脱。
假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。初始时，怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。请问，他最多可以经过多少幢不同建筑的顶部（包含初始时的建筑）？
- 输入
- 输入数据第一行是一个整数K（K < 100），代表有K组测试数据。
每组测试数据包含两行：第一行是一个整数N(N < 100)，代表有N幢建筑。第二行包含N个不同的整数，每一个对应一幢建筑的高度h（0 < h < 10000），按照建筑的排列顺序给出。 - 输出
- 对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量。
- 样例输入
-
123456738300 207 155 299 298 170 158 65865 158 170 298 299 155 207 300102 1 3 4 5 6 7 8 9 10
- 样例输出
-
123669
C++实现
|
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 |
#include<iostream> #include<vector> using namespace std; int main(){ int T, n; cin>>T; while(T--){ cin>>n; vector<int> building(n); for(int i = 0; i < n; i++){ scanf("%d", &building[i]);{ } } int dpi[101]; int dpd[101]; int maxi = 0, maxd = 0; for(int i = 0; i < n; i++){ dpi[i] = 1; for(int j = 0; j < i; j++){ if(building[j] < building[i]){ dpi[i] = dpi[i] > dpi[j] + 1 ? dpi[i] : dpi[j] + 1; } } if(dpi[i] > maxi)maxi = dpi[i]; } for(int i = n - 1; i >= 0; i--){ dpd[i] = 1; for(int j = n - 1; j > i; j--){ if(building[j] < building[i]){ dpd[i] = dpd[i] > dpd[j] + 1 ? dpd[i] : dpd[j] + 1; } } if(dpd[i] > maxd)maxd = dpd[i]; } printf("%d\n", maxi > maxd ? maxi : maxd); } return 0; } |
