作为一个编程菜鸡，先刷刷前几题，八道题目争取6题有思路，5题能写出来，3题能AC（大佬勿嘲笑）。由于部分题目已经关闭，无法看到是否AC（以下代码可能无法通过全部测试用例），如有错误，请指出，O(∩_∩)O谢谢。
A:最简真分数
全局题号3526 提交次数67 尝试人数39 通过人数38
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。
- 输入
- 第一行是一个正整数n（n<=600）。
第二行是n个不同的整数，相邻两个整数之间用单个空格隔开。整数大于1且小于等于1000。 - 输出
- 一个整数，即最简真分数组合的个数。
- 样例输入
-
1273 5 7 9 11 13 15
- 样例输出
-
117
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 |
#include<iostream> #include<vector> using namespace std; int gcd(int x, int y){ if(y == 0)return x; else return gcd(y, x % y); } int main(){ int n; cin>>n; vector<int> all(n); for(int i = 0; i < n; i++){ cin>>all[i]; } int ans = 0; for(int i = 0; i < n - 1; i++){ for(int j = i + 1; j < n; j++){ if(gcd(all[i], all[j]) == 1)ans++; } } cout<<ans<<endl; return 0; } /* 7 3 5 7 9 11 13 15 */ |
B:n-gram串频统计
全局题号7604 提交次数128 尝试人数34 通过人数31
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 在文本分析中常用到n-gram串频统计方法，即，统计相邻的n个单元（如单词、汉字、或者字符）在整个文本中出现的频率。假设有一个字符串，请以字符为单位，按n-gram方法统计每个长度为 n 的子串出现的频度，并输出最高频度以及频度最高的子串。所给的字符串只包含大小写字母，长度不多于500个字符，且 1 < n < 5。
如果有多个子串频度最高，则根据其在序列中第一次出现的次序依次输出，每行输出一个，如果最高频度不大于1，则输出NO。
- 输入
- 第一行为n；
第二行为字符串。 - 输出
- 输出最高频度以及频度最高的所有子串。若最高频度不大于1，只输出一行NO。
- 样例输入
-
123abcdefabcd
- 样例输出
-
1232abcbcd
- 提示
- 样例中，所有的3-gram是：abc,bcd,cde,def,efa,fab,abc,bcd。最后面的cd不足以形成3-gram，则不考虑。这样，abc 和 bcd 都出现了2次，其余的只出现了1次。
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> #include<unordered_map> #include<algorithm> using namespace std; struct node{ string s; int pos; }; bool cmp(node a, node b){return a.pos < b.pos;} int main(){ int n, max = 0; string str; cin>>n>>str; unordered_map<string, int> cnt; for(int i = 0; i <= str.length() - n; i++){ cnt[str.substr(i, n)]++; } for(auto it = cnt.begin(); it != cnt.end(); it++){ if(max < it->second)max = it->second; } cout<<max<<endl; vector<node> ans; for(auto it = cnt.begin(); it != cnt.end(); it++){ if(max == it->second){ node temp; temp.s = it->first; temp.pos = str.find(it->first); ans.push_back(temp); } } sort(ans.begin(), ans.end(), cmp); for(int i = 0; i < ans.size(); i++){ cout<<ans[i].s<<endl; } return 0; } |
C:垂直直方图
全局题号1802 提交次数74 尝试人数37 通过人数37
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 输入4行全部由大写字母组成的文本，输出一个垂直直方图，给出每个字符出现的次数。注意：只用输出字符的出现次数，不用输出空白字符，数字或者标点符号的输出次数。
- 输入
- 输入包括4行由大写字母组成的文本，每行上字符的数目不超过80个。
- 输出
- 输出包括若干行。其中最后一行给出26个大写英文字母，这些字母之间用一个空格隔开。前面的几行包括空格和星号，每个字母出现几次，就在这个字母的上方输出一个星号。注意：输出的第一行不能是空行。
- 样例输入
-
1234THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG.THIS IS AN EXAMPLE TO TEST FOR YOURHISTOGRAM PROGRAM.HELLO!
- 样例输出
-
1234567891011*** ** * * ** * * ** * * * * ** * * * * * * * * ** * * * * * * * * * * * ** * * * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * * * * * * * * * * * *A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
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 |
#include<iostream> #include<vector> #include<map> using namespace std; int main(){ string one, two, three, four, all = ""; getline(cin, one); getline(cin, two); getline(cin, three); getline(cin, four); all += one; all += two; all += three; all += four; map<char, int> cnt; for(int i = 0; i < all.length(); i++){ if(all[i] >= 'A' && all[i] <= 'Z'){ cnt[all[i]]++; } } int maxc = 0; for(char c = 'A'; c <= 'Z'; c++){ if(maxc < cnt[c])maxc = cnt[c]; } int temp = maxc; for(int i = 1; i <= temp; i++){ for(char j = 'A'; j <= 'Z'; j++){ if(cnt[j] == maxc){ printf("%c%s", '*', j == 'Z' ? "\n" : " "); cnt[j]--; } else printf("%c%s", ' ', j == 'Z' ? "\n" : " "); } maxc--; } for(char c = 'A'; c <= 'Z'; c++){ printf("%c%s", c, c == 'Z' ? "\n" : " "); } return 0; } |
F:Game Prediction
全局题号325 提交次数27 尝试人数11 通过人数8
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- Suppose there are M people, including you, playing a special card game. At the beginning, each player receives N cards. The pip of a card is a positive integer which is at most N*M. And there are no two cards with the same pip. During a round, each player chooses one card to compare with others. The player whose card with the biggest pip wins the round, and then the next round begins. After N rounds, when all the cards of each player have been chosen, the player who has won the most rounds is the winner of the game.
Given your cards received at the beginning, write a program to tell the maximal number of rounds that you may at least win during the whole game.
- 输入
- The input consists of several test cases. The first line of each case contains two integers m (2 <= m <= 20) and n (1<= n <= 50), representing the number of players and the number of cards each player receives at the beginning of the game, respectively. This followed by a line with n positive integers, representing the pips of cards you received at the beginning. Then a blank line follows to separate the cases.
The input is terminated by a line with two zeros.
- 输出
- For each test case, output a line consisting of the test case number followed by the number of rounds you will at least win during the game.
- 样例输入
-
12345672 51 7 2 10 96 1162 63 54 66 65 61 57 56 50 53 480 0
- 样例输出
-
12Case 1: 2Case 2: 4
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 |
#include<iostream> #include<vector> using namespace std; bool cards[1001]; //贪心策略 int main(){ int m, n, t = 0; while(cin>>m>>n){ t++; if(m == 0 && n == 0)break; int ans = 0, others_large = 0; fill(cards, cards + 1000, false); for(int i = 1; i <= n; i++){ int temp; cin>>temp; cards[temp] = true; } for(int i = n * m; i >= 1; i--){ if(cards[i]){ if(others_large == 0)ans++; else others_large--; }else{ others_large++; } } cout<<"Case "<<t<<": "<<ans<<endl; } return 0; } |
G:Networking
全局题号289 提交次数83 尝试人数28 通过人数17
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- You are assigned to design network connections between certain points in a wide area. You are given a set of points in the area, and a set of possible routes for the cables that may connect pairs of points. For each possible route between two points, you are given the length of the cable that is needed to connect the points over that route. Note that there may exist many possible routes between two given points. It is assumed that the given possible routes connect (directly or indirectly) each two points in the area.
Your task is to design the network for the area, so that there is a connection (direct or indirect) between every two points (i.e., all the points are interconnected, but not necessarily by a direct cable), and that the total length of the used cable is minimal. - 输入
- The input file consists of a number of data sets. Each data set defines one required network. The first line of the set contains two integers: the first defines the number P of the given points, and the second the number R of given routes between the points. The following R lines define the given routes between the points, each giving three integer numbers: the first two numbers identify the points, and the third gives the length of the route. The numbers are separated with white spaces. A data set giving only one number P=0 denotes the end of the input. The data sets are separated with an empty line.
The maximal number of points is 50. The maximal length of a given route is 100. The number of possible routes is unlimited. The nodes are identified with integers between 1 and P (inclusive). The routes between two points i and j may be given as i j or as j i. - 输出
- For each data set, print one number on a separate line that gives the total length of the cable used for the entire designed network.
- 样例输入
-
12345678910111213141516171819202122232425261 02 31 2 372 1 171 2 683 71 2 192 3 113 1 71 3 52 3 893 1 911 2 325 71 2 52 3 72 4 84 5 113 5 101 5 64 2 120
- 样例输出
-
12340171626
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 49 50 51 52 53 54 55 56 57 58 59 |
#include<iostream> #include<algorithm> #include<vector> using namespace std; //Kruskal最小生成树模板题 int n, m, father[100000]; struct node{ int src, dst; int val; }; bool cmp(node a, node b){return a.val < b.val;} int findFather(int a){ int t = a; while(a != father[a])a = father[a]; //找到根节点 return a; } void init(){ for(int i = 1; i <= n; i++)father[i] = i; } int unionSet(int x, int y){ //和并查集一样，如果将根合并 int fx = findFather(x); int fy = findFather(y); if(fx != fy){ father[fx] = fy; return 1; }return 0; } int main(){ while(cin>>n){ if(n == 0)break; init(); //初始化不能丢 cin>>m; int ans = 0; vector<node> pool(m); for(int i = 0; i < m; i++){ cin>>pool[i].src>>pool[i].dst>>pool[i].val; } sort(pool.begin(), pool.end(), cmp); int k = 0, i = 0; while(k < n - 1){ if(unionSet(pool[i].src, pool[i].dst)){ //如果两个节点的根不一样则合并，本质上将两个预给定的边选择出来 //也不会成环 k++; ans += pool[i].val; } i++; } cout<<ans<<endl; } return 0; } |
