本文由zhc撰写小测8 - 最短路径 实时评测问题描述：唐僧被妖怪关在迷宫中。孙悟空好不容易找到一张迷宫地图，并通过一个魔法门来到来到迷宫某个位置。假设迷宫是一个n * m的矩阵，它有两种地形，0表示平地，1表示沼泽，孙悟空只能停留在平地上。孙悟空目前的位置在坐标(sx,sy)处，他可以向上下左右四个方向移动。请你帮助孙悟空计算一下，迷宫中是否存在一条路从他所在位置(sx,sy)到达唐僧所在位置(tx,ty)，如果有，请计算出最短的一条路径。输入描述：每个测试样例的第1行是2个正整数n (1≤n≤100)，m (1≤m≤100)，表示迷宫是n * m的矩阵。接下来的n行输入迷宫，每行有m个数字（0或者1），数字之间用一个空格间隔。接下来的1行是4个整数sx,sy,tx,ty，1≤sx,tx≤n，1≤sy,ty≤m，表示孙悟空所在位置为第sx行第sy列，唐僧所在位置为第tx行第tx列。迷宫左上角编号是(1,1)，右下角编号是(n, m)。数据保证(sx,sy)格和(tx,ty)必定为平地，且孙悟空的初始位置(sx, sy)并不在唐僧所在格(tx, ty)。输出描述：输出孙悟空到达唐僧处所需经过的最短路径，如果不能到达，请输出“No”输入样例1：2 20 11 01 1 2 2输出样例1：No输入样例2：4 40 0 0 10 1 0 00 1 0 00 0 0 11 1 3 4输出样例2：5#include <iostream> #include<vector> #include<cstring> using namespace std; int n,m; int near[4][2]={0,1,0,-1,1,0,-1,0}; int d[101][101]; int best[101][101]; int vis[101][101]; void refresh(int x,int y){ for(int i=0;i<4;++i){ int x0=x+near[i][0]; int y0=y+near[i][1]; if(x0<1||x0>n||y0<1||y0>m) continue; if(d[x0][y0]==1&&best[x0][y0]>(best[x][y]+d[x0][y0])){ best[x0][y0]=best[x][y]+d[x0][y0]; } } } int main(){ cin>>n>>m; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ int t; cin>>t; d[i][j]=1-t; best[i][j]=9999; vis[i][j]=0; } } int sx,sy,tx,ty; cin>>sx>>sy>>tx>>ty; if(sx==tx&&sy==ty){ cout<<0; return 0; } best[sx][sy]=0; vis[sx][sy]=1; refresh(sx,sy); while(true){ int min=9999; int x,y; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ if(d[i][j]==1&&vis[i][j]==0&&min>best[i][j]){ min=best[i][j]; x=i; y=j; } } } if(min==9999) break; if(x==tx&&y==ty) break; vis[x][y]=1; refresh(x,y); } if(best[tx][ty]==9999) cout<<"No"; else cout<<best[tx][ty]; return 0; } 小测9 - 简单哈希 实时评测题目描述使用线性探测法(Linear Probing)可以解决哈希中的冲突问题，其基本思想是：设哈希函数为h(key) = d, 并且假定哈希的存储结构是循环数组, 则当冲突发生时, 继续探测d+1, d+2…, 直到冲突得到解决.例如, 现有关键码集为 {47，7，29，11，16，92，22，8，3}，设：哈希表表长为m=11；哈希函数为Hash(key)=key mod 11；采用线性探测法处理冲突。建哈希表如下：现在给定哈希函数为Hash(key)= key mod m，要求按照上述规则, 使用线性探测法处理冲突.要求建立起相应哈希表，并按要求打印。输入描述仅有一个测试用例, 第1行为整数n与m（1 <= n, m <= 10000）， n代表key的总数, m代表哈希表的长度, 并且令哈希函数为: Hash(key) = key mod m.接下来n行，每行一个整数，代表一个key。Key与key两两不相同 ( 0 <= key <= 10, 000)。输出描述输出建立好的hash表，比如下表应输出0#111#222#NULL3#474#925#166#37#78#299#810#NULL#include<iostream> using namespace std; int main(){ int n,m; cin>>n>>m; int data[m]; for(int i=0;i<m;++i) data[i]=-1; for(int i=0;i<n;++i){ int num; cin>>num; int key=num%m; int k=0; while(data[(key+k)%m] !=-1) ++k; data[(key+k)%m]=num; } for(int i=0;i<m;++i){ cout<<i<<"#"; if(data[i]==-1) cout<<"NULL"<<endl; else cout<<data[i]<<endl; } }小测10 - 简单字符串匹配 题目描述给定两个字符串s1和s2，要求判定s2是否能够被s1做循环移位（rotate）得到的字符串包含。说明：字符串s1和s2中不包含空格，每个字符串至少包含一个字符。例如：给定S1= AABCD，S2=CDAA，则返回True；给定s1=ABCD，S2=ACBD，则返回False输入描述第一行为整数n（n<2,000,0），第2到n+1行为n个输入数据，每行包括两个字符串，字符串s1和字符串s2。字符串的长度不超过100。输出描述针对每个例子，如果s2能够被s1做循环移位得到的字符串包含，输出True，否则输出False；每个输出结果为独立的一行。输入样例2AABCD CDAAABCD ACBD输出样例TrueFalse#include<iostream> using namespace std; int main(){ int times; cin>>times; while(times-->0){ string s1,s2; cin>>s1>>s2; bool ok=false; for(int i=0;i<s1.size();++i){ if(s1[i]==s2[0]){ ok=true; int k1=i; int k2=0; while(k2<s2.size()){ if(s1[k1]!=s2[k2]){ ok=false; break; } k1++; k1=k1%(s1.size()); k2++; } if(ok) break; } } if(ok) cout<<"True"<<endl; else cout<<"False"<<endl; } return 0; }小测11 - 畅通工程 实时评测 2022-01-19 18:08 1000 ms 32 MB 李正鸿 (lizhh98@mail2.sysu.edu.cn)题目描述某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。输入描述本题目包含多组数据，请处理到文件结束。每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。接下来是M行道路信息。每一行有三个整数A,B,X(0<A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。输出描述对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.输入样例3 30 1 10 2 31 2 10 23 10 1 11 2输出描述2-1#include<iostream> #include<cstring> using namespace std; #define int_max 2000000//int_max int N; int best[200]; int vist[200]; int d[200][200]; void refresh(int x){ for(int i=0;i<N;++i){ if(d[x][i]!=-1&&best[i]>(best[x]+d[x][i])) best[i]=best[x]+d[x][i]; } } int main(){ while(cin>>N){ int M; cin>>M; //memset(vist,0,sizeof(vist)); //memset(best,int_max,sizeof(best)); memset(d,-1,sizeof(d)); for(int i=0;i<N;++i){ d[i][i]=0; vist[i]=0; best[i]=int_max; } for(int i = 0; i <M ; ++i){ int x,y,t; cin>>x>>y>>t; if(x!=y&&(d[x][y]==-1||t<d[x][y])){ d[x][y]=t; d[y][x]=t; } } int start,end; cin>>start>>end; if(start==end){ cout<<0<<endl; continue; } best[start]=0; vist[start]=1; refresh(start); while(true){ int min=int_max; int closest; for(int i=0;i<N;++i){ if(vist[i]==0&&min>best[i]){ min=best[i]; closest=i; } } if(min==int_max) break; if(closest==end) break; vist[closest]=1; refresh(closest); } if(best[end]==int_max) cout<<-1<<endl; else cout<<best[end]<<endl; } return 0; }小测12 - 飞盘高手 题目描述杰克是美国某小镇有名的飞盘高手。他掷飞盘的时候有一个习惯，在一叠飞盘中，从第一个飞盘（即位于顶端的飞盘）开始，从上往下依次编号为1～N。当至少还有两个飞盘的时候，杰克通常会掷出一个飞盘，然后把新的第一个飞盘放到所有飞盘的最后。输入N，输出每次扔掉的飞盘，以及最后剩下的飞盘。输入描述第一行为一个整数t（0<t<20），表示测试用例个数。以下t行每行包含一个整数n（0<n<40）,为一个测试用例的飞碟数。输出描述为每个测试用例单独输出一行，该行中依次输出每次掷出的飞盘编号以及最后剩下飞盘，每个飞盘后跟着一个空格。输入样例274输出样例1 3 5 7 4 2 61 3 2 4#include<iostream> #include<queue> using namespace std; int main(){ int t; cin>>t; while(t-->0){ int n; cin>>n; queue<int> Q; for(int i = 1; i<=n;++i) Q.push(i); for(int k=0;k<n;++k){ cout<<Q.front()<<" "; Q.pop(); Q.push(Q.front()); Q.pop(); } cout<<endl; } }
本文由zhc撰写小测1 - 字符串的反转 问题描述：给定一个字符串，你需要颠倒一个句子中每个单词中的字符顺序，同时保留空格和初始单词顺序。输入样例：Let's take the contest输出样例：s'teL ekat eht tsetnoc #include<iostream> using namespace std; // #include<string> int main(){ string s=""; while(cin>>s){ for(int j = s.size()-1 ; j >= 0 ; j--) cout<<s.at(j); cout<<" " ; } return 0; }小测2 - 数一数叶数问题：请你实现下列函数，计算给定二叉树的叶数：#include "BinaryNode.h" int leaves(const BinaryNode* root); #include "BinaryNode.h" int leaves(const BinaryNode* root); //BinaryNode.h #include <iostream> using namespace std; typedef int T; struct BinaryNode{ T data; BinaryNode *left, *right; BinaryNode(T d, BinaryNode *l=NULL, BinaryNode* r=NULL):data(d), left(l), right(r) {}; };//num_leaves.cpp #include "BinaryNode.h" int leaves(const BinaryNode* root){ if(root==NULL) return 0; if(root->left==NULL&&root->right==NULL) return 1; return leaves(root->left)+leaves(root->right); }小测3 - 求两个集合的交集假定用下列顺序结构存储一个集合，集合元素按照从小到大顺序存储：typedef int ElemType; typedef struct { ElemType elem[MAXSIZE]; // 线性表占用的数组空间 int last; /*记录线性表中最后一个元素在数组 elem[ ] 中的位置（下标值），空表置为-1*/ } SeqList;请实现下面求集合交集的函数：//LC是LA和LB表示集合的交集void merge(SeqList LA, SeqList LB, SeqList *LC);\\SeqList.h #include "stdio.h" #include "stdlib.h" #define MAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/ typedef int ElemType; typedef struct { ElemType elem[MAXSIZE]; // 线性表占用的数组空间 int last; /*记录线性表中最后一个元素在数组 elem[ ] 中的位置（下标值），空表置为-1*/ } SeqList;#include"SeqList.h" void merge(SeqList *LA, SeqList *LB, SeqList *LC){ int len1 = LA->last; int len2 = LB->last; int i=0; int j=0; int k=-1; while(true){ while(LA->elem[i]<LB->elem[j]&&LA->elem[i]!=-1) ++i; while(LA->elem[i]>LB->elem[j]&&LB->elem[i]!=-1) ++j; if(i>len1||j>len2||LA->elem[i]==-1||LB->elem[j]==-1) break; if(LA->elem[i]==LB->elem[j]){ ++k; LC->elem[k]=LA->elem[i]; ++i; ++j; } } LC->last=k; }小测4 - 检查一个序列是否构成堆 实时评测问题描述：给定一个整数序列，请检查该序列是否构成堆。问题补充：输入: 第一行是一个整数n(0 < n < 10000)，第二行是n个整数。输出: 如果序列是极小堆，即堆顶是最小元，则输出"min heap"；如果是极大堆，即堆顶是最大元，则输出“max heap”； 否则不是堆，则输出“no”。如果既是极大堆，又是极小堆，则输出“both”。输出包括一行，最后有换行。输入输出格式样例：输入53 4 2 1 1输出no#include<iostream> using namespace std; int main(){ int n; cin>>n; int data[n+1];//2*k,2*k+1 for(int i=1;i<=n;++i){ cin>>data[i]; } int key=1; int min_heap=1; while(key<n){ int left=2*key; if(left+1<=n){ if(data[key]<=data[left]&&data[key]<=data[left+1]) key+=1; else{ min_heap=0; break; } }else if(left==n){ if(data[key] <=data[left]) key+=1; else{ min_heap=0; break; } }else if(left>n){ key+=1; } } key=1; int max_heap=1; while(key<n){ int left=2*key; if(left+1<=n){ if(data[key]>=data[left]&&data[key]>=data[left+1]) key+=1; else{ max_heap=0; break; } }else if(left==n){ if(data[key]>=data[left]) key+=1; else{ max_heap=0; break; } }else if(left>n){ key+=1; } } if(min_heap==1&&max_heap==1) cout<<"both"<<endl; else if(min_heap==1) cout<<"min heap"<<endl; else if(max_heap==1) cout<<"max heap"<<endl; else cout<<"no"<<endl; } 小测5 - 验证回文字符串 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。输入：一行字符串输出：是否能成为回文字符串（0：不能；1：能）示例输入abca示例输出1注意:示例当中，你可以删除c字符，使其成为回文字符串。//abctttca //actttcba #include<iostream> #include<string> using namespace std; int main(){ string str; cin>>str; int times=0; int i=0; int j=str.size()-1; while(i<j){ if(str[i]==str[j]){ ++i; --j; } else{ if(str[i+1]==str[j]){ i+=2; --j; ++times; } else if(str[i]==str[j-1]){ i++; j-=2; ++times; } else{ times+=2; break; } } } if(times<=1) cout<<1; else cout<<0; }小测6 - 最长有效括号 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。输入：一个只包含 '(' 和 ')' 的字符串。输出：最长的包含有效括号的子串的长度。示例输入：)()())示例输出:4注：示例中的最长有效括号子串为 "()()"#include<iostream> #include<string> #include<stack> using namespace std; int length(string str,int start,int end){ stack<char> s; int len=0; int i=start; while(i<=end){ char t = str[i]; if(s.empty()&&t==')') return 0; if(t=='(') s.push('('); if(!s.empty()&&t==')'){ s.pop(); len+=2; } ++i; } if(s.empty()) return len; else return 0; } int main(){ string str; cin>>str; int max_len=0; /*for(int i=0;i<str.size()-1;++i){ for(int j=i+1;j<str.size()&&str[i]=='(';j+=2){ if(str[j]!=')') continue; int len=length(str,i,j); if(len>max_len) max_len=len; } } */ for(int i=0;i<str.size()-1;++i){ for(int j=i+1;j<str.size();++j){ int len=length(str,i,j); if(len>max_len) max_len=len; } } cout<<max_len; }小测7 - 坐缆车 问题描述:M山上设置了n个只下山不上山的缆车点1,2…n。游客可以从山上的某一点上缆车，并从其下方任意点下缆车。缆车点i到缆车点j之间的费用为r（i，j），1<=i<=j<=n。试计算从山顶1到山脚n坐缆车所需的最少费用。输入格式：第一行一个正整数n，表示有n个缆车点，接下来n-1行是一个半矩阵,当前行表示当前点按顺序到其下方点的费用r(i，j)，从点1开始。输出格式：一个整数，表示最小费用输入样例35 15（1到2的费用为5,1到3的费用为15）7（2到3的费用为7）输出样例12#include<iostream> using namespace std; int main(){ int n; cin>>n; int d[n+1][n+1]; int best[n+1]; for(int i=1;i<n;++i){ for(int j=i+1;j<=n;++j){ cin>>d[i][j]; } best[i+1]=d[1][i+1]; } best[1]=0; if(n==1){ cout<<0; return 0; } if(n==2){ cout<<d[1][2]; return 0; } for(int k=3;k<=n;++k){ for(int i=1;i<k;++i){ if(best[k]> best[i]+d[i][k]) best[k]=best[i]+d[i][k]; } } cout<<best[n]<<endl; return 0; }
题目描述We have a set of strings (set A) and a set of queries (set B). Each query is to check whether a string exists in set A or not. If yes, output this string.Your task is to implement the following function:void query(string A[], int n, string B[], int m);Here, n is the number of strings in set A, m is the number of strings in set B. 1<=n,m<=500,000.Submit the function only.输入描述No input.输出描述Output the strings in set B which exist in set A. The output should follow the original order of the strings in set B.提示For example,A[0]=“ABC”, A[1]=“CD”, A[2]=“D”B[0] = “A”, B[1] =“CD”, B[2]=“BC”, B[3]=“ABC”,then you should output:CDABCZHC的答案#include"query.h" using namespace std; #include<iostream> int myhash(const string s,int n){ int hash = 13; int i = 0 ; while(s[i]){ hash += (int)(s[i]); hash =(hash*13)%n; ++i; } return hash%n; } void query(string A[], int n, string B[], int m){ int N=2*n; string hash_A[N]; for(int i = 0 ; i < n ; ++i){ int key = myhash(A[i],N); if(hash_A[key] == "") hash_A[key]=A[i] ; else{ int k = 0; while(hash_A[(key+k*k)%N]!=""){//平方探测法 ++k; } hash_A[(key+k*k)%N]=A[i] ; } } for(int i = 0 ; i < m ; ++i){ int key = myhash(B[i],N); int k = 0; while(hash_A[(key+k*k)%N]!= ""){ if(B[i]==hash_A[(key+k*k)%N]){ cout<<B[i]<<endl; break; } ++k; } } }Yizuodi的答案#include <iostream> using namespace std; int get_hash(const string s,int n){ int hash = 0; for(int i=0;i<s.size();++i){ hash += s[i]-'A'+1; hash = (hash*26)%n; } return hash%n; } void query(string A[], int n, string B[], int m){ string hashtable[2*n]; for(int i = 0 ; i < n ; ++i){ int key = get_hash(A[i],2*n)%(2*n); if(hashtable[key].size() == 0){ hashtable[key]=A[i]; } else{ int j = 0; while(hashtable[(key+j*j)%(2*n)].size() != 0){ ++j; } hashtable[(key+j*j)%(2*n)]=A[i]; } } for(int i = 0 ; i < m ; ++i){ int key = get_hash(B[i],2*n)%(2*n); int j = 0; while(hashtable[(key+j*j)%(2*n)].size() != 0){ if(B[i]==hashtable[(key+j*j)%(2*n)]){ cout<<B[i]<<endl; break; } ++j; } } }
[软工初级实训]中山大学_软工初级实训参考资料
CSDN参考中山大学2018年软件工程专业初级实训2017中山大学软件工程初级实训
温馨提示：此内容可能已过期/不符合项目要求/编译无法通过。作者：zhc#ifndef MEETING_H #define MEETING_H #include <vector> #include "Date.cpp" //改了 class Meeting { public: /** * @brief default constructor */ Meeting() = default; /** * @brief constructor with argument */ Meeting(const std::string &t_sponsor, const std::vector<std::string> &t_participator, const Date &t_startTime, const Date &t_endTime, const std::string &t_title) { std::string m_sponsor = t_sponsor; std::vector<std::string> m_participators = t_participator; Date m_startDate = t_startTime; Date m_endDate = t_endTime; std::string m_title = t_title; } /** * @brief copy constructor of left value */ Meeting(const Meeting &t_meeting){ std::string m_sponsor = t_meeting.getSponsor(); std::vector<std::string> m_participators = t_meeting.getParticipator(); Date m_startDate = t_meeting.getStartDate(); Date m_endDate = t_meeting.getEndDate(); std::string m_title = t_meeting.getTitle(); } /** * @brief get the meeting's sponsor * @return a string indicate sponsor */ std::string getSponsor(void) const{ return m_sponsor; } /** * @brief set the sponsor of a meeting * @param the new sponsor string */ void setSponsor(const std::string &t_sponsor){ m_sponsor = t_sponsor; } /** * @brief get the participators of a meeting * @return return a string vector indicate participators */ std::vector<std::string> getParticipator(void) const{ return m_participators ; } /** * @brief set the new participators of a meeting * @param the new participators vector */ void setParticipator(const std::vector<std::string> &t_participators){ m_participators = t_participators ; } /** * @brief add a new participator to the meeting * @param the new participator */ void addParticipator(const std::string &t_participator){ m_participators.push_back(t_participator); } /** * @brief remove a participator of the meeting * @param the participator to be removed */ void removeParticipator(const std::string &t_participator){ std::vector<std::string> ::iterator itor ; for(itor = m_participators.begin(); itor!=m_participators.end() ;itor++){ if(*itor == t_participator) itor = m_participators.erase(itor) ; } } /** * @brief get the startDate of a meeting * @return return a string indicate startDate */ Date getStartDate(void) const{ return m_startDate ; } /** * @brief set the startDate of a meeting * @param the new startdate of a meeting */ void setStartDate(const Date &t_startTime){ m_startDate = t_startTime ; } /** * @brief get the endDate of a meeting * @return a date indicate the endDate */ Date getEndDate(void) const{ return m_endDate ; } /** * @brief set the endDate of a meeting * @param the new enddate of a meeting */ void setEndDate(const Date &t_endTime){ m_endDate = t_endTime ; } /** * @brief get the title of a meeting * @return a date title the endDate */ std::string getTitle(void) const{ return m_title ; } /** * @brief set the title of a meeting * @param the new title of a meeting */ void setTitle(const std::string &t_title){ m_title = t_title ; } /** * @brief check if the user take part in this meeting * @param t_username the source username * @return if the user take part in this meeting */ bool isParticipator(const std::string &t_username) const{ for(const auto& item : m_participators ){ if(item == t_username) return true ; } return false ; } private: std::string m_sponsor; std::vector<std::string> m_participators; Date m_startDate; Date m_endDate; std::string m_title; }; #endif
温馨提示：此内容可能已过期/不符合项目要求/编译无法通过。作者：zhc#ifndef USER_H #define USER_H #include <initializer_list> #include <string> class User { public: /** * @brief the default constructor */ User() = default; /** * constructor with arguments */ User(const std::string &t_userName, const std::string &t_userPassword, const std::string &t_userEmail, const std::string &t_userPhone) { std::string m_name = t_userName; std::string m_password = t_userPassword; std::string m_email = t_userEmail; std::string m_phone = t_userPhone; } /** * @brief copy constructor */ User(const User &t_user) { std::string m_name = t_user.getName(); std::string m_password = t_user.getPassword() ; std::string m_email = t_user.getEmail(); std::string m_phone = t_user.getPhone(); } /** * @brief get the name of the user * @return return a string indicate the name of the user */ std::string getName() const{ return m_name ; } /** * @brief set the name of the user * @param a string indicate the new name of the user */ void setName(const std::string &t_name){ std::string m_name = t_name ; } /** * @brief get the password of the user * @return return a string indicate the password of the user */ std::string getPassword() const{ return m_password; } /** * @brief set the password of the user * @param a string indicate the new password of the user */ void setPassword(const std::string &t_password){ std::string m_password = t_password; } /** * @brief get the email of the user * @return return a string indicate the email of the user */ std::string getEmail() const{ return m_email ; } /** * @brief set the email of the user * @param a string indicate the new email of the user */ void setEmail(const std::string &t_email){ std::string m_email = t_email ; } /** * @brief get the phone of the user * @return return a string indicate the phone of the user */ std::string getPhone() const{ return m_phone ; } /** * @brief set the phone of the user * @param a string indicate the new phone of the user */ void setPhone(const std::string &t_phone){ std::string m_phone = t_phone ; } private: std::string m_name; std::string m_password; std::string m_email; std::string m_phone; }; #endif
温馨提示：此内容可能已过期/不符合项目要求/编译无法通过。作者：zhc#include "Storage.hpp" #include "Path.hpp" #include <fstream> using namespace std; std::shared_ptr<Storage> Storage::m_instance = nullptr; Storage::Storage() { m_dirty = false; readFromFile(); }; bool Storage::readFromFile(void) { ifstream fusers(Path::userPath); ifstream fmeetings(Path::meetingPath); if (!(fusers.is_open() && fmeetings.is_open())){ return false; } string str1; while (getline(fusers, str1)) { string name, password, email, phone; if(str1.size() == 0) { continue; } int len=str1.size(); vector<int>pos; for(int i = 0; i < len ; i++){ if(str1[i] == '"') pos.push_back(i); } for(int i = pos[0]+1 ; i < pos[1] ; i++){ name.push_back(str1[i]); } for(int i = pos[2]+1 ; i < pos[3] ; i++){ password.push_back(str1[i]); } for(int i = pos[4]+1 ; i < pos[5] ; i++){ email.push_back(str1[i]); } for(int i = pos[6]+1 ; i < pos[7] ; i++){ phone.push_back(str1[i]); } User u(name, password, email, phone); m_userList.push_back(u); } fusers.close(); string str2; while (getline(fmeetings, str2)) { string sponsor, participators, startDate, endDate, title; if(str2.size() == 0) { continue; } int len=str2.size(); vector<int> pos; for(int i = 0; i < len ; i++){ if(str2[i] == '"') pos.push_back(i); } for(int i = pos[0]+1 ; i < pos[1] ; i++){ sponsor.push_back(str2[i]); } for(int i = pos[2]+1 ; i < pos[3] ; i++){ participators.push_back(str2[i]); } for(int i = pos[4]+1 ; i < pos[5] ; i++){ startDate.push_back(str2[i]); } for(int i = pos[6]+1 ; i < pos[7] ; i++){ endDate.push_back(str2[i]); } for(int i = pos[8]+1 ; i < pos[9] ; i++){ title.push_back(str2[i]); } vector<string> v_participators; int len2=participators.size(); string parti; for(int i=0;i<len2;i++){ if(participators[i]!='&'){ parti.push_back(participators[i]); } else{ string temp=parti; v_participators.push_back(temp); parti.clear(); } } v_participators.push_back(parti); Date start(startDate); Date end(endDate); Meeting meeting(sponsor, v_participators, start, end, title); m_meetingList.push_back(meeting); } fmeetings.close(); return true; }; bool Storage::writeToFile(void) { ofstream fusers(Path::userPath); ofstream fmeetings(Path::meetingPath); if (!(fusers.is_open() && fmeetings.is_open())){ return false; } for (auto it = m_userList.begin();it != m_userList.end();it++) { fusers<<'"'<<(*it).getName()<<'"'<<','<<'"'<<(*it).getPassword()<<'"'<<','<<'"'<<(*it).getEmail()<<'"'<<','<<'"'<<(*it).getPhone()<<'"'; fusers<<"\n"; } fusers.close(); for(auto it = m_meetingList.begin();it != m_meetingList.end();it++) { fmeetings<<'"'<<(*it).getSponsor()<<'"'<<','<<'"'; vector<string> par = (*it).getParticipator(); int len = par.size(); for(int i = 0 ; i < len-1 ; i++){ fmeetings<<par[i]<<'&'; } fmeetings<<par[len-1]; fmeetings<<'"'<<','<<'"'<<(*it).getStartDate().dateToString((*it).getStartDate())<<'"'<<','<<'"'<<(*it).getEndDate().dateToString((*it).getEndDate())<<'"'<<','<<'"'<<(*it).getTitle()<<'"'; fmeetings<<"\n"; } fmeetings.close(); return true; }; std::shared_ptr<Storage> Storage::getInstance(void) { if (m_instance == nullptr) { m_instance = shared_ptr<Storage>(new Storage()); } return m_instance; }; Storage::~Storage() { sync(); }; void Storage::createUser(const User &t_user) { m_userList.push_back(t_user); m_dirty = true; }; std::list<User> Storage::queryUser(std::function<bool(const User &)> filter) const { std::list<User> result; for (auto it = m_userList.begin();it != m_userList.end();it++) { if (filter(*it)){ result.push_back(*it); } } return result; }; int Storage::updateUser(std::function<bool(const User &)> filter, std::function<void(User &)> switcher) { int num = 0; for (auto it = m_userList.begin();it != m_userList.end();it++) { if (filter(*it)) { switcher(*it); num++; } } if(num > 0){ m_dirty = true; } return num; }; int Storage::deleteUser(std::function<bool(const User &)> filter) { int num = 0; for (auto it = m_userList.begin();it != m_userList.end();) { if (filter(*it)) { it = m_userList.erase(it); num++; } else{ it++; } } if (num > 0){ m_dirty = true; } return num; }; void Storage::createMeeting(const Meeting &t_meeting) { m_meetingList.push_back(t_meeting); m_dirty = true; }; std::list<Meeting> Storage::queryMeeting( std::function<bool(const Meeting &)> filter) const { list<Meeting> meeting; for (auto it = m_meetingList.begin();it != m_meetingList.end();it++) { if (filter(*it)) meeting.push_back(*it); } return meeting; }; int Storage::updateMeeting(std::function<bool(const Meeting &)> filter, std::function<void(Meeting &)> switcher) { int num = 0; for (auto it = m_meetingList.begin();it != m_meetingList.end();it++) { if (filter(*it)) { switcher(*it); num++; } } if (num > 0){ m_dirty = true; } return num; }; int Storage::deleteMeeting(std::function<bool(const Meeting &)> filter) { int num = 0; for (auto it = m_meetingList.begin();it != m_meetingList.end();) { if (filter(*it)) { it = m_meetingList.erase(it); num++; } else it++; } if (num > 0){ m_dirty = true; } return num; }; bool Storage::sync(void) { m_dirty = false; return writeToFile(); };
温馨提示：此内容可能已过期/不符合项目要求/编译无法通过。作者：zhc#ifndef DATE_H #define DATE_H #include <initializer_list> #include <string> class Date { public: /** * @brief default constructor */ Date() = default ; /** * @brief constructor with arguments */ Date(int t_year, int t_month, int t_day, int t_hour, int t_minute){ m_year = t_year; m_month = t_month; m_day = t_day; m_hour = t_hour; m_minute = t_minute; } /** * @brief constructor with a string */ Date(const std::string &dateString){ bool ok= true ; if(dateString.size()!=16) ok = false ; else if(dateString[4]!='-'||dateString[7]!='-'||dateString[10]!='/'||dateString[13]!=':') ok = false ; if(ok){ int t = 0; int num = 0; for(int i = 0; i < dateString.size();++i ){ int tmp = (int)dateString[i]; if(tmp>=48 && tmp<=57){ t = 10*t+(tmp-48) ; ++num; } if(num==4){ m_year = t; t = 0 ; } if(num==6){ m_month = t; t = 0 ; } if(num==8){ m_day = t; t = 0 ; } if(num==10){ m_hour = t; t = 0 ; } if(num==12){ m_minute = t; t = 0 ; } } } else{ m_year = 0; m_month = 0; m_day = 0; m_hour = 0; m_minute = 0; } } /** * @brief return the year of a Date * @return a integer indicate the year of a date */ int getYear(void) const{ return m_year ; } /** * @brief set the year of a date * @param a integer indicate the new year of a date */ void setYear(const int t_year){ m_year = t_year ; } /** * @brief return the month of a Date * @return a integer indicate the month of a date */ int getMonth(void) const{ return m_month ; } /** * @brief set the month of a date * @param a integer indicate the new month of a date */ void setMonth(const int t_month){ m_month = t_month ; } /** * @brief return the day of a Date * @return a integer indicate the day of a date */ int getDay(void) const{ return m_day ; } /** * @brief set the day of a date * @param a integer indicate the new day of a date */ void setDay(const int t_day){ m_day = t_day ; } /** * @brief return the hour of a Date * @return a integer indicate the hour of a date */ int getHour(void) const{ return m_hour ; } /** * @brief set the hour of a date * @param a integer indicate the new hour of a date */ void setHour(const int t_hour){ m_hour = t_hour ; } /** * @brief return the minute of a Date * @return a integer indicate the minute of a date */ int getMinute(void) const{ return m_minute ; } /** * @brief set the minute of a date * @param a integer indicate the new minute of a date */ void setMinute(const int t_minute){ m_minute = t_minute ; } /** * @brief check whether the date is valid or not * @return the bool indicate valid or not */ static bool isValid(const Date &t_date){ bool ok=true; int i= t_date.getYear(); int month = t_date.getMonth(); int day = t_date.getDay(); int days; if(i==1||i==3||i==5||i==7||i==8||i==10||i==12) days=31; else if (i==4||i==6||i==9||i==11) days=30; else if ((i%4==0 && i % 100 != 0)|| i % 400 == 0) days=29; else days=28; if (i<1000|| i>9999&&month<1&&month>12&&day<1&&day>days) ok = false ; if(t_date.getHour()<0|| t_date.getHour()>59||t_date.getMinute()<0||t_date.getMinute()>59) ok = false; return ok; } /** * @brief convert a string to date, if the format is not correct return * 0000-00-00/00:00 * @return a date */ static Date stringToDate(const std::string &t_dateString){ Date newdate(t_dateString) ; return newdate ; } /** * @brief convert a date to string, if the date is invalid return * 0000-00-00/00:00 */ static std::string dateToString(const Date &t_date){ char a[17]; a[4] = '-' ; a[7] = '-' ; a[10] = '/' ; a[13] = ':' ; a[16] = '\0' ; a[0] = t_date.getYear()/1000; a[1] = (t_date.getYear()/100)%10; a[2] = (t_date.getYear()/10)%10; a[3] = t_date.getYear()%10; a[5] = t_date.getMonth()/10; a[6] = t_date.getMonth()%10 ; a[8] = t_date.getDay()/10; a[9] = t_date.getDay()%10 ; a[11] = t_date.getHour()/10; a[12] = t_date.getHour()%10 ; a[14] = t_date.getMinute()/10; a[15] = t_date.getMinute()%10 ; std::string s(a) ; return s ; } /** * @brief overload the assign operator */ Date &operator=(const Date &t_date){ m_year = t_date.getYear() ; m_month = t_date.getMonth() ; m_day = t_date.getDay() ; m_hour = t_date.getHour() ; m_minute = t_date.getMinute() ; return *this ; } /** * @brief check whether the CurrentDate is equal to the t_date */ bool operator==(const Date &t_date) const{ if(t_date.getYear() != m_year ) return false ; if(t_date.getMonth() != m_month) return false ; if(t_date.getDay() != m_year) return false ; if(t_date.getHour() != m_hour) return false ; if(t_date.getMinute() != m_minute) return false ; return true ; } /** * @brief check whether the CurrentDate is greater than the t_date */ bool operator>(const Date &t_date) const{ int t[5]; t[0] = m_year-t_date.getYear(); t[1] = m_month - t_date.getMonth(); t[2] = m_day - t_date.getDay(); t[3] = m_hour-t_date.getHour() ; t[4] = m_minute - t_date.getMinute(); int dt = (((t[0]*12+t[1])*30+t[2])*24+t[3])*60+t[4]; if(dt>0) return true ; else return false ; } /** * @brief check whether the CurrentDate is less than the t_date */ bool operator<(const Date &t_date) const{ int t[5]; t[0] = m_year-t_date.getYear(); t[1] = m_month - t_date.getMonth(); t[2] = m_day - t_date.getDay(); t[3] = m_hour-t_date.getHour() ; t[4] = m_minute - t_date.getMinute(); int dt = (((t[0]*12+t[1])*30+t[2])*24+t[3])*60+t[4]; if(dt<0) return true ; else return false ; } /** * @brief check whether the CurrentDate is greater or equal than the t_date */ bool operator>=(const Date &t_date) const{ int t[5]; t[0] = m_year-t_date.getYear(); t[1] = m_month - t_date.getMonth(); t[2] = m_day - t_date.getDay(); t[3] = m_hour-t_date.getHour() ; t[4] = m_minute - t_date.getMinute(); int dt = (((t[0]*12+t[1])*30+t[2])*24+t[3])*60+t[4]; if(dt>=0) return true ; else return false ; } /** * @brief check whether the CurrentDate is less than or equal to the t_date */ bool operator<=(const Date &t_date) const{ int t[5]; t[0] = m_year-t_date.getYear(); t[1] = m_month - t_date.getMonth(); t[2] = m_day - t_date.getDay(); t[3] = m_hour-t_date.getHour() ; t[4] = m_minute - t_date.getMinute(); int dt = (((t[0]*12+t[1])*30+t[2])*24+t[3])*60+t[4]; if(dt<=0) return true ; else return false ; } private: int m_year; int m_month; int m_day; int m_hour; int m_minute; }; #endif
题目描述把一个包含n个正整数的序列划分成m个连续的子序列（每个正整数恰好属于一个序列）。设第i个序列的各数之和为S(i)，如何让所有S(i)的最大值尽量小？例如序列1 2 3 2 5 4，划分成3个序列的最优方案为1 2 3 | 2 5 | 4，其中S(1)=6, S(2)=7, S(3)=4，最大值为7；如果划分成1 2 | 3 2 | 5 4，则最大值为9，不如刚才的好。n≤10^6，所有数之和不超过10^9。输入描述可能有多个输入样例。每个样例第一行输入两个整数n和m，第二行输入n个整数。输出描述输出所有子序列划分中子序列和的最大值的最小值。输入样例6 31 2 3 2 5 4输出样例7zhc的code：//最大值最小化 #include<iostream> using namespace std; bool ok(int *data,int num,int groups,int mid);//判断mid是否可以做子序列和的最大值 int main(){ int num;//数字个数 while(cin >> num ){ int groups; //划分数 cin >> groups ; int data[num] ; int sum= 0 ; int min = 0 ;//子序列和的最大值的下界 for(int i = 0 ; i < num ; ++i){ cin>>data[i] ; sum+=data[i] ; if(data[i]>min) min = data[i] ;//子序列和的最大值的下界= max_of_data[i] } int max=sum-groups+1 ;//子序列和的最大值的上界,其余n-1组都只有1个1时 int min_of_max ;//最小的子序列和的最大值 while( min<=max){ int mid = (min+max)/2 ; if(ok(data,num,groups,mid)){ //mid可以做子序列和的最大值时 max=mid-1; min_of_max = mid ; } else min = mid+1 ; //mid不能做子序列和的最大值时 } cout << min_of_max <<endl ; } } bool ok(int *data,int num,int groups,int mid){ int sum = 0 ; int groups0 = 1; //记录按子序列和的最大值为mid时的划分数 for(int i = 0 ; i < num ; ++i){ sum+=data[i] ; if(sum > mid){ //如果sum+data[i]>mid时就 sum=data[i] ; ++groups0 ; } } if(groups0 <= groups) return true ;//组数和小于等于groups，说明可以分组 else return false ; }Yizuodi的答案#include <iostream> using namespace std; bool v(int *data, int size, int partnum, int mid_of_max) //判断mid_of_max是否可以做子序列和的最大值 { int sum = 0; int partnum_new = 1; //记录按子序列和的最大值为mid时的划分数 for (int i = 0; i < size; ++i) { sum += data[i]; if (sum > mid_of_max)//如果sum加上data[i]大于mid_of_max，那么就划分新的子序列 { sum = data[i]; ++partnum_new;//子序列数量+1 } } if (partnum_new <= partnum) return true; //组数和小于等于partnum，说明可以划分出指定子序列 else return false; } int main() { int size, partnum; //整数个数,划分个数 while (cin >> size) { cin >> partnum; int data[size]; //用于存储输入的整数 int sum_of_int = 0; int lowerbound_of_max = 0; //子序列和的最大值的下界 for (int i = 0; i < size; ++i) { cin >> data[i]; sum_of_int += data[i]; if (data[i] > lowerbound_of_max) { lowerbound_of_max = data[i]; //data[i]中最大值为子序列和的最大值的下界 } } int upperbound_of_max = sum_of_int - partnum + 1; //子序列和的最大值的上界,这里的情况为其余n-1组仅含一个1 int min_of_max=lowerbound_of_max; //子序列和的最大值的最小值 while (lowerbound_of_max <= upperbound_of_max) { int mid_of_max = (lowerbound_of_max + upperbound_of_max) / 2; if (v(data, size, partnum, mid_of_max))//mid_of_max可以做子序列和的最大值时 { upperbound_of_max = mid_of_max - 1;//看看mid_of_max小一点能否找到更小的最大值 min_of_max = mid_of_max;//把已找到的进行记录 } else//mid_of_max不能做子序列和的最大值时 { lowerbound_of_max = mid_of_max + 1;//看看mid_of_max大一点能否找到最大值 } } cout << min_of_max << endl; } }
题目描述实现二分查找函数，函数接口如下。#include "binSearch.h" int binSearch(const int s[], const int size, const int target) { // 请将实现代码添加在这里 }size为数组s的实际大小。假定s非递减有序，如果s中存在值为target的元素，则返回最后一次出现的位序号，否则返回-1表示不存在。位序号从0开始计。调用样例int s[8] = {0,1,1,3,3,3,6,6};cout << binSearch(s,8,3) << endl; //输出5cout << binSearch(s,8,4) << endl; //输出-1//"binSearch.h" # ifndef BIN_SEARCH_H # define BIN_SEARCH_H int binSearch(const int s[], const int size, const int target); # endif zhc的answer：//binSearch.cpp int binSearch(const int s[], const int size, const int target) { int bottom = 0 ; int top = size-1 ; int index = -1 ; while(bottom <= top ){ int mid = (bottom+top)/2 ; if( s[mid] > target ) top = mid-1 ; else{ bottom = mid+1 ; if(s[mid] == target) index=mid ; } } return index; }Yizuodi的答案#include "binSearch.h" int binSearch(const int s[], const int size, const int target) { int bottom = 0 ; int top = size - 1 ; int index = -1 ;//默认不存在 while( bottom <= top ){ int mid = (bottom+top)/2 ; if( s[mid] > target ) { top = mid - 1 ; } else { bottom = mid + 1 ; if(s[mid] == target) { index = mid ; } } } return index; }